Algorytm min-max

Minimax

Minimax (czasami określany jako minmax) to technika mająca na celu minimalizowanie maksymalnych potencjalnych strat. Można ją również interpretować jako maksymalizację minimalnego zysku (maximin). Metoda ta wywodzi się z teorii gier o sumie zerowej, obejmujących sytuacje, w których gracze wykonują ruchy na przemian, jak i te, gdzie ruchy są wykonywane równocześnie. Zastosowanie minimaxu rozszerza się również na bardziej złożone gry oraz ogólne podejmowanie decyzji w warunkach niepewności.

Teoria Minimax

W teorii minimax:

W przypadku każdej dwuosobowej gry o sumie zerowej istnieje wartość V oraz mieszana strategia dla każdego z graczy, która spełnia następujące warunki: (a) przy strategii przeciwnika, najlepsza możliwa spłata dla gracza pierwszego wynosi V, oraz (b) przy strategii gracza pierwszego, najlepsza możliwa spłata dla gracza drugiego wynosi -V.

Strategia gracza pierwszego zapewnia mu spłatę V niezależnie od strategii gracza drugiego, a gracz drugi może z kolei zagwarantować sobie spłatę -V. Nazwa Minimax pochodzi od faktu, że każdy z graczy stara się minimalizować maksymalną możliwą spłatę dla przeciwnika, a tym samym maksymalizuje swoją minimalną spłatę, ponieważ gra jest o sumie zerowej.

Teoria ta została sformułowana w XX wieku przez Johna von Neumanna, który stwierdził: „Jak do tej pory widzę, nie mogłoby być żadnej teorii gier… bez tej teorii… Byłem zdania, że nic nie jest warte publikowania, aż Teoria Minimax została udowodniona”.

Opis algorytmu

Wykorzystując funkcję S, która ocenia wartość stanu gry w danym momencie (gracz min dąży do minimalizacji tego stanu, a gracz max do maksymalizacji), tworzymy drzewo wszystkich możliwych stanów gry do pewnej głębokości (zazwyczaj ograniczonej naszą mocą obliczeniową). Zakładając, że rozgałęzienie drzewa stanów jest stałe i wynosi b (to znaczy, na każdy ruch można odpowiedzieć b innymi), a głębokość to d (liczba ruchów symulowanych przez algorytm minimax), otrzymujemy:

\(b^{d}\) stanów końcowych, dla których obliczamy wartość stanu gry za pomocą funkcji S. Zaczynamy przeszukiwanie od stanów końcowych, symulując optymalne wybory dla obu graczy, tak aby na głębokości d (w liściach drzewa) uzyskali oni optymalną wartość S (stan gry po wykonaniu d ruchów). Gracz min zawsze wybiera ruch prowadzący do mniejszej wartości końcowej, podczas gdy gracz max działa odwrotnie. Po przeprowadzeniu symulacji gracz znajdujący się w korzeniu drzewa (aktualnie wykonujący ruch) ma pewność, że jego ruch jest optymalny w kontekście informacji o stanie gry uzyskanej z symulacji algorytmem minimax na głębokość d (tj. maksymalizuje minimalny zysk).

Algorytm ten służy do wyboru 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 poprzez zastosowanie odcięć alfa-beta pozwala w najlepszym przypadku zmniejszyć liczbę rozpatrywanych stanów do około:

\(2b^{d/2}\), co w efekcie umożliwia symulację ruchów prawie dwa razy głębiej.

Aby uzyskać optymalne wyniki przy użyciu minimaxu, kluczowe jest posiadanie dobrej funkcji oceny stanu gry S. Zazwyczaj nie znamy idealnej funkcji S, ponieważ w takim przypadku gra byłaby już rozwiązana (znalibyśmy optymalną strategię, jak na przykład w grze w kółko-krzyżyk). Dlatego wykorzystuje 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

\(\delta\) służy do oszacowania parametru \(\theta \in \Theta\). Zakłada się także istnienie funkcji ryzyka

R(\theta, \delta), zwykle definiowanej jako całka z funkcji straty. W tym kontekście \(\tilde{\delta}\) nazywana jest minimax, jeśli spełnia:

\(\sup_{\theta} R(\theta, \tilde{\delta}) = \inf_{\delta} \sup_{\theta} R(\theta, \delta).\)

Alternatywnym kryterium w ramach teorii decyzji jest estymator Bayesa przy założeniu wcześniejszej rozkładu \(\Pi\). Estymator jest Bayesowski, jeżeli minimalizuje średnie ryzyko:

\(\int_{\Theta} R(\theta, \delta) \, d\Pi(\theta).\)