минимакс для tic-tac-toe

Question

Я пытаюсь решить tic-tac-toe с помощью простого минимаксного алгоритма. Простой, но должен охватывать много языка. Что я до сих пор:

Плата представлена ​​в виде массива из 9 (несвязанных) переменных, которые либо установлены на x, либо o.

Условие выигрыша тогда в основном: win(Player, [X1,X2,X3|_]) :- X1==Player,X2==Player,X3==Player. и т. Д. Для всех восьми вариантов. draw просто проверяет, связаны ли все переменные.

Переводы также просты: move(Player, [X|_], 0, 0) :- var(X), X=Player., снова для всех возможных позиций (я оставлю код повторно открытым для более поздней программы :)).

Теперь я могу сгенерировать все возможные ходы простым обратным следом: move(Player, Board, X, Y)., который должен в основном быть всем, что мне нужно для минимакса (очевидно, простая функция утилиты, которая возвращает 1, если компьютер выигрывает, 0 в случае ничьей и -1 if человек побеждает, это легко). Я просто не знаю, как его реализовать, и все примеры, которые я нахожу в сети, довольно сложны и не совсем понятны.

Примечание. Я в порядке с n^2 или худшим поведением во время исполнения - это действительно не эффективность. И да, я знаю, как писать минимакс в lisp, python, java - просто не знаю, как «переносить» этот код в пролог.

Answer 1

Ну, как у вас уже есть свой ход/4 предикат, я хотел бы начать с собирать все шаги, которые можно:

findall(X-Y, move(Player, Board, X, Y), Moves)

А потом это просто вопрос оценки каждого хода, не Это? Для этого я бы написал предикат, как board_player_move_value/4, который, учитывая плату и ход данного игрока, определяет, насколько хорошо движение для этого игрока. Именно этот предикат, вероятно, зависит от дальнейших ходов, которые возможны (для другого игрока) на этом этапе, и именно здесь происходит минимакс. Например, если этот ход побеждает в игре, это хороший ход. Если другой игрок может выиграть в следующем ходу, это плохой ход и т. Д. Я бы использовал этот предикат для создания набора терминов формы Value-Move, используя для этого сортировку ключей keysort/2, а затем выберите один из шагов с лучшим значением, где «лучше» зависит от того, пытаюсь ли я найти ход для минимизирующего или максимизирующего игрока.