Минимаксное объяснение "для чайников"

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

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

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

Благодарю вас за ваше время:)

Ответ 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 move
 V(B) = min(V(B1), ..., V(Bn)) where board positions B1..Bn are
        the positions available for O, and it is O move

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

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

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

Ответ 2

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

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

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