Как уменьшить обрезку Minimax/Alpha-Beta на более короткие пути?

Question

Я работаю над простой проблемой tic-tac-toe, я и пытаюсь понять, как работает алгоритм Minimax.

Если я использую функцию утилиты 1 для X win, -1 для вывода O и 0 для игры, то я не понимаю, как алгоритм определяет приоритеты более коротких решений. Как я понимаю, он идет к самому глубокому узлу, и событие, если оно не кратчайший путь, но это приводит к возможной победе, тогда он его выберет.

Позвольте мне объяснить в этом примере. Вот состояние платы и X очереди (обозначения из https://www.hackerrank.com/challenges/tic-tac-toe):

OX_ 
_X_ 
__O 

Если мы ищем из верхнего левого положения вправо вниз, то алгоритм найдет, что если положить X в положении (0, 2) потому что это ведет к неминуемой победе следующий ход:

OXX 
_X_ 
__O 

Однако умнее выбор будет (2, 1) и непосредственное положение выигрышная:

OX_ 
_X_ 
_XO 

Я не вижу как Minimax o r Обрезка альфа-беты будет определять приоритетность такого поведения.

Так что мой вопрос в том, правильно ли я это понимаю и как я мог его улучшить.

Answer 1

Минимум для Tic Tac Toe имеет несколько возможных количественных оценок: выигрыш, проигрыш, ничья. Алгоритм Minimax задает максимум всех способов, с помощью которых позиция игрока могла быть минимизирована последующими ходами другого игрока. Победе в следующем ходу будет назначена Бесконечность, четкий выбор. В противном случае, в Tic Tac Toe, он будет уделять приоритетное внимание ничьей, за исключением нескольких особых случаев, таких как выигрыш в следующем ходу или возможность создания вилки (что приведет к определенной победе в переходе после следующей).

Альфа-бета-обрезка - это метод оптимизации, который позволяет избегать изучения разделов дерева поиска, когда можно показать, что любая часть раздела даст худший результат, чем тот, который уже был найден; например, говорят, что одна полномасштабная разведка дает потенциальную ничью, а лист другого узла показывает потерю; не было бы смысла изучать других детей последнего узла (если вы не предполагали, что другой игрок не всегда будет играть лучший ход). Вы можете найти эту ссылку полезной: https://www.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html