Minimax (czasami MinMax) jest to metoda minimalizacji maksymalnych możliwych strat. Ewentualnie można je uznać jako maksymalizujące minimalny zysk (maximin). Opiera się to na teorii gry o sumie zerowej, obejmującej oba przypadki, ten, w którym gracze wykonują ruchy naprzemiennie i ten, w którym wykonują ruchy jednocześnie. Zostało to również rozszerzone na bardziej złożone gry i ogólne podejmowanie decyzji gdy istnieje warunek obecności niepewności.
Teoria Minimax
Twierdzenie to zostało ustanowione 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”.
Dla każdej dwuosobowej gry o sumie zerowej istnieje wartość V oraz strategia mieszana dla każdego gracza tak, że (a) – biorąc pod uwagę strategię drugiego gracza, najlepszy możliwy zwrot dla pierwszego gracza wynosi V, oraz (b) – biorąc pod uwagę strategię pierwszego gracza, najlepszy możliwy zwrot dla drugiego gracza wynosi -V.
Odpowiednia strategia dla gracza 1. gwarantuje, że otrzyma zwrot V niezależnie od gracza 2. i podobnie gracz 2. może zagwarantować, że otrzyma zwrot -V. Nazwa Minimax pojawiła się, ponieważ każdy z graczy minimalizuje maksymalną możliwą spłatę dla drugiego gracza – ponieważ gra jest grą o sumie zerowej, maksymalizuje również jej minimalną spłatę.
Stwierdzenie to założył John von Neumann, którego powiedzenie jest cytowane jako „O ile mi wiadomo, nie byłoby teorii gier…. bez tej teorii… Myślałem, że nic nie jest warte opublikowania, dopóki teoria minimax nie zostanie udowodniona”.
Opis algorytmu Minimax
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).
Posiadając funkcję S, która ocenia wartość stanu gry w dowolnym momencie (gracz min chce zminimalizować ten stan, a gracz max chce go zmaksymalizować), obliczamy drzewo wszystkich możliwych stanów gry do pewnej głębokości (zazwyczaj ograniczonej przez naszą moc obliczeniową). Zakładając, że rozgałęzienie drzewa stanów jest stałe i wynosi b (tzn. na każdy ruch można odpowiedzieć b) oraz głębokość d (tak wiele ruchów do przodu jest symulowanych algorytmem minmax), mamy stany końcowe, dla których obliczamy wartość gry z funkcją S. Tak więc gracz-min zawsze wybiera ruch, który prowadzi do niższej wartości końcowej, podczas gdy gracz max wybiera przeciwny. Po tej symulacji gracz znajdujący się w korzeniu drzewa (obecnie wykonujący ruch) jest pewien, że jego ruch jest optymalny w kontekście stanu gry informacji z symulacji wykonanej algorytmem minimaksu do głębokości d (tj. maksymalizuje minimalny zysk).
Algorytm służy do wyboru optymalnego ruchu w danym momencie, więc po ruchu przeciwnika musimy przeprowadzić symulację ponownie. Większa głębokość d symulacji prowadzi do lepszych ruchów. Optymalizacja algorytmu z cięciami alfa-beta pozwala, w optymalnym przypadku, zredukować liczbę stanów branych pod uwagę do ~, co w efekcie pozwala nam symulować ruchy prawie dwukrotnie głębsze.
W celu osiągnięcia optymalnych, minimalnych wyników ważne jest posiadanie dobrej funkcji oceny statusu S. Zazwyczaj nie znamy optymalnej funkcji S, ponieważ w takim przypadku gra byłaby rozwiązana (znalibyśmy optymalną strategię, taką jak koło i krzyż), dlatego stosuje się różne heurystyki, zwykle wyrażone jako wielomian liniowy w stosunku do parametrów stanu gry.
