Мини-пояснение «для манекенов»

Question

Я довольно новичок в алгоритмах, и я пытался понять минимакс, я читал много статей, но я все еще не могу понять, как его реализовать в tic-tac-toe игра в питоне. Можете ли вы попытаться объяснить это мне как можно проще, возможно, с помощью некоторого псевдокода или какого-нибудь кода на питоне ?.

Мне просто нужно понять, как это работает. Я прочитал много вещей об этом, и я понял базовый, но я все еще не могу понять, как он может вернуть ход.

Если вы не можете связать мои учебники и образцы, например (http://en.literateprograms.org/Tic_Tac_Toe_(Python)), я знаю, что они хороши, но мне просто нужно идиотское объяснение.

спасибо за ваше время :)

Answer 1

Идея «минимакс» заключается в том, что в игре с двумя игроками один игрок пытается максимизировать какую-то форму счета, а другой игрок пытается свести к минимуму ее. Например, в Tic-Tac-Toe победа X может быть оценена как +1, а выигрыш O - -1. X будет максимальным игроком, пытаясь максимизировать окончательный результат, а O будет минимальным игроком, пытаясь свести к минимуму окончательный результат.

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

Другими словами, игра теоретико-минимаксное значение V для положения платы B определяется как

V(B) = 1 if X has won in this position 
V(B) = -1 if O has won in this position 
V(B) = 0 if neither player has won and no more moves are possible (draw) 

иначе

V(B) = max(V(B1), ..., V(Bn)) where board positions B1..Bn are 
     the positions available for X, and it is X's move 
V(B) = min(V(B1), ..., V(Bn)) where board positions B1..Bn are 
     the positions available for O, and it is O's move 

Оптимальная стратегия X всегда двигаться от В к Bi такой, что V (Bi) максимален, т. Е. Соответствует гаметеоретическому значению V (B), а для O аналогичным образом выбирается минимальное положение преемника.

Однако, как правило, это невозможно рассчитать в играх, таких как шахматы, потому что для вычисления гаметеоретического значения нужно перечислить все дерево игры до окончательных позиций, и это дерево обычно чрезвычайно велико. Поэтому стандартным подходом является монетизация «оценочной функции», которая отображает позиции до баллов, которые, как мы надеемся, коррелируют с гаметеоретическими значениями. Например. в шахматных программах функция оценки, как правило, дают положительные оценки для материальной выгоды, открытые столбцы и т.д. Минимаксному алгоритм их minimaximizes функции оценки балла вместо фактического (невычислимого) gametheoretic значения позиции платы.

Значительная стандартная оптимизация для минимакса - это «обрезка альфа-бета». Он дает те же результаты, что и минимаксный поиск, но быстрее. Minimax также можно отличить в терминах «negamax», где знак оценки отменяется на каждом уровне поиска. Это просто альтернативный способ реализовать минимакс, но он одинаково обрабатывает игроков. Другие методы поиска дерева игр включают в себя итеративное углубление, поиск номера доказательств и многое другое.

Answer 2

Минимаксом является способом изучения пространства потенциальных ходов в двух игроках с чередованием поворотов. Вы пытаетесь выиграть, и ваш оппонент пытается помешать вам выиграть.

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

По этой причине не очень полезно исследовать ветви от ходов, которые вы делаете, что плохо для вас, или перемещает противника, что хорошо для вас.