Алгоритм игры в Чомп

Question

Я пишу программу для игры в Чомп. Вы можете прочитать описание игры на Википедия, Однако я все равно опишу это в любом случае.

Мы играем на шоколадной прутике измерения NXM, то есть бар делится на квадратах NXM. На каждом шагу нынешний игрок выбирает квадрат и ест все внизу и справа от выбранного квадрата. Так, например, следующее приведено первым первым ходом:

Цель состоит в том, чтобы заставить вашего противника съесть последний кусок шоколада (он отравлен).

Что касается детали ИИ, я использовал алгоритм минимаксного устранения с уточнением глубины. Однако я не могу придумать подходящую функцию оценки позиции. Результатом является то, что с моей функцией оценки человеческому игроку довольно легко победить мою программу.

Может кто -нибудь:

• предложить хорошую функцию оценки позиции или
• предоставить некоторую полезную ссылку или
• Предложить альтернативный алгоритм?

Answer 1

Насколько велики ваши доски?

Если ваши доски довольно малы, вы можете решить игру точно с помощью динамического программирования. В Python:

n,m = 6,6
init = frozenset((x,y) for x in range(n) for y in range(m))

def moves(board):
    return [frozenset([(x,y) for (x,y) in board if x < px or y < py]) for (px,py) in board]

@memoize
def wins(board):
    if not board: return True
    return any(not wins(move) for move in moves(board))

Функция выигрывает (Правление) вычисляет, является ли доска победной позиции. Представление платы представляет собой набор кортежей (x, y), указывающий, есть ли часть (x, y) все еще на плате. Функция перемещается в расчетах списка досок, достижимые за один ход.

Логика функции Wins работает так. Если доска пуста на нашем движении, другой игрок должен был съесть последнюю часть, поэтому мы выиграли. Если доска не пуста, мы можем выиграть, если есть any Движение, мы можем сделать так, чтобы результирующая позиция является проигрышной позицией (т.е. не выигрывает IE not wins(move)), потому что тогда мы получили другого игрока в проигрышную позицию.

Вам также понадобится вспомогательная функция, которая кэширует результаты:

def memoize(f):
    cache = dict()
    def memof(x):
        try: return cache[x]
        except:
            cache[x] = f(x)
            return cache[x]
    return memof

Кэшируя, мы только вычислим, кто является победителем для данной позиции один раз, даже если эта позиция доступна несколькими способами. Например, положение одного ряда шоколада можно получить, если первый игрок ест все оставшиеся ряды в своем первом ходе, но его также можно получить во многих других сериях ходов. Было бы расточительно вычислять, кто снова и снова выигрывает на доске одной строки, поэтому мы кэшируем результат. Это улучшает асимптотические показатели из чего -то вроде O((n*m)^(n+m)) к O((n+m)!/(n!m!)), огромное улучшение, хотя все еще медленно для больших досок.

А вот функция печати отладки для удобства:

def show(board):
    for x in range(n):
        print '|' + ''.join('x ' if (x,y) in board else '  ' for y in range(m))

Этот код все еще довольно медленный, потому что код никоим образом не оптимизирован (и это Python ...). Если вы пишете его в C или Java эффективно, вы, вероятно, можете повысить производительность в 100 раз. Вы должны легко иметь возможность обрабатывать доски 10x10, и вы, вероятно, можете обрабатывать до 15x15 досок. Вы также должны использовать другое представление платы, например, немного доски. Возможно, вы даже сможете ускорить его на 1000x, если вы используете несколько процессоров.

Вот вывод из Minimax

Мы начнем с Minimax:

def minimax(board, depth):
  if depth > maxdepth: return heuristic(board)
  else:
    alpha = -1
    for move in moves(board):
      alpha = max(alpha, -minimax(move, depth-1))
    return alpha

Мы можем удалить проверку глубины, чтобы сделать полный поиск:

def minimax(board):
  if game_ended(board): return heuristic(board)
  else:
    alpha = -1
    for move in moves(board):
      alpha = max(alpha, -minimax(move))
    return alpha

Поскольку игра закончилась, эвристика вернет -1 или 1, в зависимости от того, какой игрок победил. Если мы представляем -1 как false и 1 как истинное, то тогда max(a,b) становится a or b, а также -a становится not a:

def minimax(board):
  if game_ended(board): return heuristic(board)
  else:
    alpha = False
    for move in moves(board):
      alpha = alpha or not minimax(move)
    return alpha

Вы можете видеть, что это эквивалентно:

def minimax(board):
  if not board: return True
  return any([not minimax(move) for move in moves(board)])

Если бы мы вместо этого начали с Minimax с обрезкой альфа-бета:

def alphabeta(board, alpha, beta):
  if game_ended(board): return heuristic(board)
  else:
    for move in moves(board):
      alpha = max(alpha, -alphabeta(move, -beta, -alpha))
      if alpha >= beta: break
    return alpha

// start the search:
alphabeta(initial_board, -1, 1)

Поиск начинается с альфа = -1 и бета = 1. Как только альфа становится 1, петля разрывается. Таким образом, мы можем предположить, что Альфа остается -1, а бета остается 1 в рекурсивных вызовах. Таким образом, код эквивалентен этому:

def alphabeta(board, alpha, beta):
  if game_ended(board): return heuristic(board)
  else:
    for move in moves(board):
      alpha = max(alpha, -alphabeta(move, -1, 1))
      if alpha == 1: break
    return alpha

// start the search:
alphabeta(initial_board, -1, 1)

Таким образом, мы можем просто удалить параметры, так как они всегда передаются как одинаковые значения:

def alphabeta(board):
  if game_ended(board): return heuristic(board)
  else:
    alpha = -1
    for move in moves(board):
      alpha = max(alpha, -alphabeta(move))
      if alpha == 1: break
    return alpha

// start the search:
alphabeta(initial_board)

Мы снова можем сделать переход с -1 и 1 на логические:

def alphabeta(board):
  if game_ended(board): return heuristic(board)
  else:
    alpha = False
    for move in moves(board):
      alpha = alpha or not alphabeta(move))
      if alpha: break
    return alpha

Таким образом, вы можете видеть, что это эквивалентно использованию любого с генератором, который останавливает итерацию, как только нашел истинное значение вместо того, чтобы всегда вычислять весь список детей:

def alphabeta(board):
  if not board: return True
  return any(not alphabeta(move) for move in moves(board))

Обратите внимание, что здесь у нас есть any(not alphabeta(move) for move in moves(board)) вместо any([not minimax(move) for move in moves(board)]). Анкет Это ускоряет поиск примерно на 10 в 10 для досок разумного размера. Не потому, что первая форма быстрее, а потому, что она позволяет нам пропустить всю оставшуюся петлю, включая рекурсивные вызовы, как только мы нашли значение, которое верно.

Итак, у вас есть, функция Wins была просто замаскированным Alphabeta. Следующий трюк, который мы использовали для побед, - это запомнить его. В игровом программировании это будет названо «таблицами транспозиции». Таким образом, функция побед выполняет поиск в алфавите с таблицами транспозиции. Конечно, проще записать этот алгоритм напрямую, а не проходить через этот вывод;)

Answer 2

Я не думаю, что здесь возможна хорошая функция оценки позиции, потому что в отличие от таких игр, как шахматы, нет «прогресса», не хватает победы или проигрыша. В статье в Википедии предполагается, что исчерпывающее решение является практичным для современных компьютеров, и я думаю, что вы обнаружите, что это так, учитывая подходящую память и оптимизация.

Связанная игра, которую вы можете найти в интересах Ним.