Этим утром я понял, что написал сообщение в блоге после того, как заставил непревзойденный компьютерный проигрыватель работать на всех языках, на которых я играл в крестики-нолики (доказательство: Первое использование минимакса, Минимакс в Java, «Негамакс в Рубин"). Теперь, когда у меня есть рабочее решение на Clojure, пришло время опубликовать его в блоге.
Я немного беспокоился о реализации минимакса в Clojure, так как в некоторых из моих предыдущих реализаций я полагался на состояние — роскошь, которой у нас нет в Clojure. В функциональном программировании вы передаете данные в функцию, а она возвращает другие данные. Это все, что у вас есть. Если вы не используете свои данные, которые вы получите обратно немедленно, они исчезнут. Я думал, что моя реализация будет совсем другой, но в итоге получилось очень похоже на то, что я делал раньше.
Эта функция вызывается с помощью функции choose-space (строка 42) с переданным состоянием доски. Состояние доски представляет собой хэш-карту с размером доски (т. е. количеством строк/столбцов) и списком ходов в последовательном порядке. доска с нулевым индексом (поэтому позиция 0 — это верхний левый угол, позиция 4 — середина, позиция 8 — нижний правый угол), например. { :size 3 :board [4] } (подробнее).
choose-space вызывает negamax и передает board-state, начальное depth из 0, начальное colour из 1 и marker компьютера (X или O). Этот маркер определяется состоянием доски при начальном вызове функции — при четном количестве ходов (0 считается четным) это X, при нечетном количестве ходов — O. В данной реализации X всегда идет первым.
negamax сначала проверяет, закончилась ли игра, и если да, то присваивает счет этому результату на основе выигранной игры и глубины рекурсивного алгоритма. Чем меньше эмулируемых ходов, пока игрок не сможет помешать противнику выиграть, тем лучше. Этот счет умножается на colour, который всегда равен 1 или -1, в зависимости от того, какой игрок сделал последний ход в эмулируемом сценарии.
Если игра не окончена, вызывается функция score-spaces. Это занимает каждое доступное место на доске и эмулирует ход туда. Затем он снова рекурсивно вызывает функцию negamax.
После завершения рекурсивного вызова, предполагая, что глубина не равна нулю, negamax возвращает наивысший из возможных результатов (при условии, что игрок, против которого он играет, также непобедим. Это negamax-score. В Clojure есть встроенная функция под названием zipma, которая принимает два списка и сшивает их вместе в карту, где первый список является ключом, а второй — значением. В этом случае первый список — это список доступных пространств, а второй — соответствующий негамакс баллы.
Единственный раз, когда глубина равна нулю, а игра не закончилась negamax, выбирается место с наибольшим шансом минимизировать проигрыш. Это то, что возвращает метод choose-space и, в конечном счете, выбор, который делает компьютер.
На самом деле я начал с алгоритма Minimax, но потом подумал об Alpha Beta Pruning и решил переписать его. На самом деле это было безболезненно, и мои тесты на удивление остались зелеными. Между ними не слишком большая разница.
По моему опыту в ruby, сокращение альфа-бета значительно проще в Negamax, но не в Clojure. В Clojure нет очевидного способа вернуться из вызова функции досрочно, как в некоторых других языках, просто вставив оператор return.
Мои наставники дали мне понять, что если я использую reduce и reduced, я могу делать именно то, что хочу, так что теперь мне просто нужно найти время, чтобы сделать это. Я очень рад, что у меня это получилось, и не могу дождаться, когда это заработает с Alpha Beta Pruning!
