Ответ 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", где знак оценки отменяется на каждом уровне поиска. Это просто альтернативный способ реализовать минимакс, но он одинаково обрабатывает игроков. Другие методы поиска дерева игр включают в себя итеративное углубление, поиск числа доказательств и т.д.