ResponseEve, a responsive template by SiGa

Minimax (czasami minmax) – metoda minimalizowania maksymalnych możliwych strat. Alternatywnie można je traktować jako maksymalizację minimalnego zysku (maximin). Wywodzi się to z teorii gry o sumie zerowej, obejmujących oba przypadki, zarówno ten, gdzie gracze wykonują ruchy naprzemiennie, jak i ten, gdzie wykonują ruchy jednocześnie. Zostało to również rozszerzone na bardziej skomplikowane gry i ogólne podejmowanie decyzji w obecności niepewności.

Teoria Minimax

Teoria minimax:

Dla każdej dwuosobowej gry o sumie zerowej istnieje wartość V i mieszana strategia dla każdego gracza, takie, że (a) – biorąc pod uwagę strategię gracza drugiego, najlepszą możliwą spłatą dla gracza pierwszego jest V, i (b) – biorąc pod uwagę strategię gracza pierwszego, najlepszą możliwą spłatą dla gracza drugiego jest -V.

Odpowiednia strategia gracza 1. gwarantuje mu spłatę V niezależnie od strategii gracza 2. i podobnie gracz 2. może zagwarantować sobie spłatę -V. Nazwa Minimax pojawiła się, ponieważ każdy gracz minimalizuje maksymalną możliwą spłatę dla drugiego – ponieważ gra jest grą o sumie zerowej, także maksymalizuje swoją minimalną spłatę.

Twierdzenie to zostało ustanowione w XX wieku przez Johna von Neumanna^[1], którego powiedzenie jest cytowane „Jak do tej pory widzę, nie mogłoby być żadnej teorii gier… bez tej teorii… Myślałem, że nic nie było warte publikowania, aż Teoria Minimax została udowodniona”^[2].

Opis algorytmu

Posiadając funkcję S oceniającą wartość stanu gry w dowolnym momencie (gracz min chce ten stan zminimalizować, a gracz max zmaksymalizować), obliczamy drzewo wszystkich możliwych stanów w grze do pewnej głębokości(ograniczonej zazwyczaj przez naszą moc obliczeniową). Zakładając, że rozgałęzienie drzewa stanów jest stałe i wynosi b(czyli na każdy ruch można odpowiedzieć b innymi), a głębokość d (tyle ruchów do przodu symulujemy algorytmem minmax), to mamy ${\displaystyle b^{d}}$ stanów końcowych, dla których obliczamy wartość stanu gry funkcją S. Zaczynamy przeglądanie od stanów końcowych, symulując optymalne wybory dla obu graczy, tak aby na głębokości d(w liściach drzewa) była dla nich optymalna liczba S (stan gry po wykonaniu d ruchów). Tak więc gracz min zawsze wybiera ruch, który prowadzi do mniejszej wartości końcowej, a gracz max – przeciwnie. Po przeprowadzeniu tej symulacji gracz, który znajduje się w korzeniu drzewa (aktualnie wykonujący ruch), ma pewność, że jego ruch jest optymalny w kontekście informacji o stanie gry z przeprowadzonej symulacji algorytmem minimax na głębokość d (tzn. maksymalizuje minimalny zysk).

Algorytm służy do wybrania optymalnego ruchu w danym momencie, dlatego po ruchu przeciwnika musimy przeprowadzić symulację ponownie. Większa głębokość d symulacji prowadzi do lepszych ruchów. Optymalizacja algorytmu z odcięciami alfa-beta pozwala, w optymalnym przypadku, zmniejszyć ilość rozpatrywanych stanów do ~${\displaystyle 2b^{d/2},}$ co w efekcie pozwala nam symulować ruchy prawie dwa razy głębiej.

Aby osiągnąć optymalne wyniki minimaxem, ważne jest posiadanie dobrej funkcji oceny stanu gry S. Optymalnej funkcji S zazwyczaj nie znamy, bo w takim wypadku gra byłaby już rozwiązana (znalibyśmy optymalną strategię jak np. w kółko i krzyżyk), dlatego stosuje się różne heurystyki, zazwyczaj wyrażone jako liniowy wielomian od parametrów stanu gry.

Minimax w kryterium statystycznej teorii decyzji

W klasycznej statystycznej teorii decyzji estymator ${\displaystyle \delta }$ używany jest do oszacowania parameteru ${\displaystyle \theta \in \Theta .}$ Zakłada się również funkcję ryzyka ${\displaystyle R(\theta ,\delta ),}$ zwykle określoną jako integralną z utratą funkcji. W tym kontekście ${\displaystyle {\tilde {\delta }}}$ jest nazwana minimax, jeśli spełnia ona

${\displaystyle \sup _{\theta }R(\theta ,{\tilde {\delta }})=\inf _{\delta }\sup _{\theta }R(\theta ,\delta ).}$

Alternatywnym kryterium w decyzji ramowej jest estymator Bayesa w obecności wcześniejszej dystrybucji ${\displaystyle \Pi .}$ Estymator jest Bayesowski, jeśli minimalizuje średnie ryzyko

${\displaystyle \int _{\Theta }R(\theta ,\delta )\,d\Pi (\theta ).}$

Przypisy

Linki zewnętrzne

• Minimax Analysis for Zero Sum Games. geocities.com. [zarchiwizowane z tego adresu (2009-10-27)].
• A visualization applet
• Play a betting-and-bluffing game against a mixed minimax strategy
• The Dictionary of Algorithms and Data Structures entry for minimax
• CLISP minimax – game.