Algorytm min-max

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, 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”.

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  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 ~ 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  używany jest do oszacowania parameteru  Zakłada się również funkcję ryzyka  zwykle określoną jako integralną z utratą funkcji. W tym kontekście  jest nazwana minimax, jeśli spełnia ona
 

Alternatywnym kryterium w decyzji ramowej jest estymator Bayesa w obecności wcześniejszej dystrybucji  Estymator jest Bayesowski, jeśli minimalizuje średnie ryzyko

Przypisy

Linki zewnętrzne 
 
 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.

Teoria decyzji
Algorytmy