Минимакс и крестики-нолики - правильный ли мой алгоритм?

Я реализовал минимаксный алгоритм для ТТТ. Когда я заставляю ИИ-игрока сделать первый ход, он оценивает все минимаксные значения возможных ходов как 0. Это означает, что он может выбрать любую клетку на сетке в качестве первого хода. Тем не менее, любой путеводитель по Крестикам-ноликам скажет вам, что выбор угла или центрального квадрата при совершении первого хода — лучший выбор, поскольку в нем больше шансов на победу.

Почему мой алгоритм не отражает этого?

РЕДАКТИРОВАТЬ: Чтобы уточнить, я пытаюсь спросить: это ограничение алгоритма минимакса или моя реализация неверна?


artificial-intelligence tic-tac-toe algorithm minimax
person Lanaru    schedule 20.04.2013    source источник
comment
Трудно сказать, не видя вашей реализации, но, похоже, она работает не очень хорошо.   -  person DPM    schedule 20.04.2013
comment
Я уточнил свой вопрос в редактировании.   -  person Lanaru    schedule 20.04.2013
comment
Весь смысл минимакса в том, что вы можете обрезать дерево решений, чтобы удалить те решения, которые маловероятны на основе краткосрочной оценки. Нет нулевой потребности в сокращении, когда есть только 20 000 с лишним возможностей (3^9) и только 9 000 с лишним допустимых игровых состояний. Если вы просто используете TTT для изучения минимакса, это нормально, просто имейте в виду, что это не идеальный вариант использования.   -  person paxdiablo    schedule 25.02.2015

Ответы (1)


arrow_upward
1
arrow_downward

Ваш алгоритм не должен отражать это: если вы попробуете все начальные позиции, вы обнаружите, что углы и центр дают вам больше путей к победе, чем другие клетки.

Из-за отсутствия сложности в крестиках-ноликах минимакс может смотреть вперед до конца игры, начиная с самого первого хода. Количество доступных ходов быстро уменьшается по мере прохождения игры, поэтому полный поиск заканчивается довольно быстро.

В более сложных играх (отелло, шашки, шахматы) большее значение приобретают так называемые «дебютные книги». Количество доступных ходов в начале игры огромно, поэтому традиционный подход состоит в том, чтобы выбрать ход из «книги» дебютов и придерживаться предварительно рассчитанных «книг ходов» в течение первых трех-шести розыгрышей. Ходы за пределами книги не учитываются, что экономит много ресурсов ЦП на ходах, которые остаются практически неизменными.

person Sergey Kalinichenko    schedule 20.04.2013
comment
If you try out all starting positions, you would find that the corners and the center give you more path to win than other cells. Я это понимаю. Должен ли минимакс разбираться в этом, или он не должен заботиться о количестве выигрышных путей? - person Lanaru; 20.04.2013
comment
Минимаксный алгоритм предназначен для поиска наилучшего хода против совершенного игрока (то есть того, кто всегда выбирает наилучший возможный ход). Против такого игрока ни одна стартовая позиция не будет лучше или хуже любой другой, поскольку игра заканчивается ничьей, независимо от выбранной стартовой позиции. - person Peter Webb; 21.04.2013
comment
@Lanaru Когда минимакс может играть в игру от начала до конца и нет выигрышной стратегии, все ходы выглядят одинаково: нет ни выигрышных, ни проигрышных позиций. Однако если бы минимакс мог играть в игру только до некоторой средней позиции, а затем был бы вынужден оценивать с помощью эвристики, тогда некоторые начальные позиции оценивались бы лучше, чем другие позиции. - person Sergey Kalinichenko; 21.04.2013