Насколько велики ваши доски?
Если ваши доски довольно маленькие, то вы можете решить игру именно с помощью динамического программирования.В 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 (доска) вычисляет, является ли доска выигрышной позицией.Представление на доске представляет собой набор кортежей (x, y), указывающих, находится ли фигура (x, y) на доске.Функция перемещений вычисляет список досок, доступных за один ход.
Логика функции выигрышей работает следующим образом.Если на нашем ходу доска пуста, другой игрок, должно быть, съел последний кусок, поэтому мы выиграли.Если доска не пуста, то мы можем выиграть, если есть ход any, который мы можем сделать так, чтобы полученная позиция была проигрышной (т.е. не выигрышной, т.е. not wins(move)), потому что тогда мы поставили другого игрока в проигрышную позицию.
Вам также понадобится вспомогательная функция memoize, которая кэширует результаты:
def memoize(f):
cache = dict()
def memof(x):
try: return cache[x]
except:
cache[x] = f(x)
return cache[x]
return memof
Кэшируя, мы только вычисляем, кто является победителем для данной позиции один раз, даже если эта позициядостижимы несколькими способами.Например, позиция одного ряда шоколада может быть получена, если первый игрок съел все оставшиеся ряды за свой первый ход, но это также может быть получено с помощью многих других серий ходов.Было бы расточительно вычислять, кто победит на однорядной доске снова и снова, поэтому мы кешируем результат.Это улучшает асимптотику с примерно 101 * * до 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 раз.Вы легко сможете справиться с досками 10х10, и, вероятно, сможете справиться с досками 15х15.Вам также следует использовать другое представление доски, например битовую доску.Возможно, вы даже сможете ускорить его в 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 на логическое значение:
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.
Итак, у вас есть функция winsбыл просто замаскированный поиск по алфавиту.Следующий трюк, который мы использовали для побед, - это запомнить его.В программировании игры это можно назвать с помощью «таблиц транспонирования».Таким образом, функция wins выполняет алфавитный поиск по таблицам транспонирования.Конечно, проще записать этот алгоритм напрямую, а не проходить этот вывод;)