Понимание минимакса с альфа-бета-обрезкой
Извините за изображение, это прямо из моих заметок.
За последний день я перечитывал минимаксные деревья и обрезку альфа-данных и немного готовился к своему проекту. Который является реализацией для Отелло в с.
Я прочитал об этом кучу ресурсов, и я знаю, что об этом часто спрашивают. Прежде чем я начну свои функции оценки, я хотел бы понять это полностью.
На прикрепленном изображении не могу понять, что за функция Min_Node(pos) а также Max_Node(pos) будет делать точно, любой вклад будет принята с благодарностью.
Если у кого-то есть какие-либо советы или вещи, на которые я должен обратить внимание при реализации этой и моей функции оценки для Othello, я готов воспользоваться любой помощью, которую смогу найти.
2 ответа
Мне удалось выяснить, что такое узел max и min, в данном случае, Max_Node(pos) проверяет, является ли это игрок, и возвращает true, потому что это должно быть максимизировано и Min_Node(pos) проверяет, является ли его противник, если истина, то это должно быть минимизировано.
Минимаксный алгоритм, который также описан здесь, должен находить ходы оптимального значения, учитывая текущую позицию в дереве игры. Позиция состоит из конфигурации доски и текущего игрока (что для некоторых игр может быть решено только на конфигурации доски). Обычно значение ходов определяется рекурсивно; для доски в конечной позиции (которая является листом дерева игры), значение 1 если игрок один выиграл, -1 если второй игрок выиграл и 0 для ничейной игры. Значение перемещения определяется путем выполнения этого перемещения и рекурсивной оценки значения. Затем выбирается ход с максимумом (для первого игрока) или минимальным (для второго игрока); в рекурсивной оценке значение является максимальным (или минимальным) значением всех листьев корневого поддерева в текущей позиции. Это, очевидно, то, что функции, упомянутые в первоначальном вопросе, должны.
Альфа-бета-обрезка, как описано здесь, является усовершенствованием этого подхода. Как известны оптимальные значения (они 1 или же -1), оценка может быть остановлена, как только будет найдено движение с желаемым значением.
Этот подход не зависит от реальной игры. Тем не менее, я предлагаю первый шаг, где более простая игра (например, Tic-Tac-Toe) используется в качестве игрушечного примера, который может быть легче отладить.