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