Мин / Макс Tic Tac Toe

Question

Я создаю крестики-нолики с мин / макс, чтобы я мог расширить их до обрезки альфа-бета. Поэтому во время моих мин / макс я нахожу, что путь с опережением к +1 (победа Х) -1 (победа О) или 0 (ничья), однако для конфигурации доски, такой как это:

В течение 0 ходов он выбирает нижний левый, так как этот ход приводит к его победе. Если бы я проверил каждую таблицу на предмет наличия блока, он не будет работать так быстро, и я не думаю, что именно так должно быть реализовано min / max.

0|x|0
-|x|-
-|-|- 

Может кто-нибудь объяснить, почему мин / макс недостаточно умны, чтобы это обнаружить. Я думал, что он посмотрел на левые узлы и вернул + 1 / -1 / 0.

Answer 1

Редактировать: Я смешивал "чистый" минимакс с минимаксом + эвристика. Я отредактировал свой ответ, чтобы решить эту проблему.

Может быть, это поможет определить minmax. От Статья студента Калифорнийского университета в Беркли :

minimax(player,board)
    if(game over in current board position)
        return winner
    children = all legal moves for player from this board
    if(max's turn)
        return maximal score of calling minimax on all the children
    else (min's turn)
        return minimal score of calling minimax on all the children

С минимаксом вы пытаетесь минимизировать свои потери, а не максимизировать свою прибыль. Итак, «твой» ход - ход min's. С этим определением, если вы можете когда-либо проиграть, выбрав квадрат, то он будет помечен -1. Если вы можете когда-либо связать, но никогда не проиграете, это будет помечено 0. Только если это гарантированный выигрыш, он будет помечен 1.

Должен ли я проверять каждую таблицу на наличие блока

Если вы правильно определяете свой счет и алгоритм (подбирая правильных игроков к правильной логике), вам не нужно «проверять блок». Любое поддерево игры, в котором игрок не блокировал, должно неявно оцениваться -1, потому что в какой-то момент (вероятно, очень быстро) оно приведет к потере, и эта потеря будет пузыриться.

Реальная проблема с этим алгоритмом (и где вы можете получать результаты, которые вы не ожидаете), это когда все поддеревья приводят к возможным потерям. На этом этапе вам нужно будет использовать эвристику, чтобы получить более точную информацию о том, какой шаг вы должны предпринять. Вам нужно что-то лучше, чем просто {-1, 0, 1}, потому что некоторые ходы могут позволить вам выиграть, но вы заблокируете их, потому что вы также можете проиграть.

Answer 2

Я не совсем уверен в вашей проблеме. Как указывалось ранее, мин / макс имеет проблемы, когда более одного пути приводит к победе или все пути приводят к проигрышу. В таком случае математически правильно выбрать любой или выигрышный путь или любой путь вообще для проигрыша. Однако, если вы играете с неидеальным противником, зачастую более разумно выбрать самый короткий выигрышный путь и самый длинный проигрышный (чтобы надеяться, что противник не будет играть идеально и выберет неправильный выбор).

Это поведение довольно легко реализовать в мин / макс, используя затухание для каждой рекурсии. То есть всякий раз, когда вы возвращаете что-то из рекурсивного вызова, умножьте результат на 0,9 или что-то вроде этого. Это приведет к более высоким оценкам для более длинных отрицательных путей и меньшим оценкам для более длинных положительных путей.

Это, однако, приводит к проблемам, как только вы начинаете использовать эвристику для прорыва.