Алгоритм игры в Chomp

Я пишу программу для игры Chomp. Вы можете прочитать описание игры на Wikipedia, однако я опишу его вкратце.

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

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

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

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

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

Ответ 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))

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

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

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

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 плат. Вы также должны использовать другое представление платы, например бит-доску. Возможно, вы даже сможете ускорить его до 1000 раз, если вы используете несколько процессоров.

Вот вывод из минимакса

Начнем с минимакса:

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 - true, то 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)])

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

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 на booleans:

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

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

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 раз для плат с разумным размером. Не потому, что первая форма выполняется быстрее, а потому, что она позволяет пропустить весь остаток цикла, включая рекурсивные вызовы, как только мы найдем значение True.

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

Ответ 2

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

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