Minimax w teorii gier to metoda mająca na celu zminimalizowanie oczekiwanej straty. W tym celu gracz zakłada, że decyzja podjęta przez przeciwnika będzie niekorzystna. Oznacza to, że najgorszy scenariusz jest oczekiwany przed ruchem przeciwnika.
Innymi słowy, metoda minimax polega na tym, jak podjąć najlepszą decyzję, zakładając, że drugi gracz wybierze dla ciebie najgorszy scenariusz.
Musimy wziąć pod uwagę, że ta metoda ma zastosowanie w grze dwuosobowej (dwóch graczy) i że nie jest to gra kooperacyjna, ale gra o sumie zerowej. Oznacza to, że to, co jeden gracz wygrywa, jest tracone przez drugiego i odwrotnie. W konsekwencji, każdy agent będzie zainteresowany maksymalizacją własnej użyteczności, nawet jeśli szkodzi to drugiemu.
W tym miejscu musimy również pamiętać, że teoria gier to dział matematyki i ekonomii, który bada wybór, który optymalizuje sytuację jednostki, gdy koszty i korzyści nie są z góry ustalone, ale zależą od decyzji innych.
Algorytm Minimax w drzewie decyzyjnym
Możemy zobaczyć, jak metoda minimax jest stosowana w drzewie decyzyjnym z kilkoma węzłami. Gra zaczyna się na dole, a kończy wynikiem na najwyższym poziomie.
U podstawy drzewka przeciwnik wykonuje pierwszy ruch, więc spodziewany jest najgorszy wynik. Następnie, na drugim poziomie, to gracz x będzie dążył do maksymalizacji swojego zysku, biorąc pod uwagę decyzję podjętą wcześniej przez przeciwnika.
Na trzecim poziomie znowu kolej na przeciwnika i tak dalej. Poniżej pokażemy przykład.
Przykład algorytmu Minimax
W poniższym drzewie decyzyjnym pokazujemy wyniki uzyskane przez gracza x w każdym momencie gry. W bazie, na pierwszym poziomie, decyzję podejmuje przeciwnik. Z tego powodu podane są scenariusze, w których gracz może stracić -10 lub wygrać 5.
Na drugim poziomie zależy to od gracza x, więc zmaksymalizuje on swój zysk. Pomiędzy stratą 10 a wygraną 1 wygrasz 1. Podobnie, jeśli wygrasz 5 lub 7, wygrasz 7.
Potem znowu kolej na przeciwnika, więc zostaną podane scenariusze, w których gracz x ma najgorszy wynik, -3 i 4, w zależności od przypadku. Wreszcie, pomiędzy przegraną 3 a wygraną 4, gracz x podejmie decyzję, która pozwoli temu drugiemu.
Musimy wziąć pod uwagę, że wartości każdego węzła będą zależeć od funkcji użyteczności.
Aby lepiej zrozumieć drzewo, załóżmy, że podstawą decyzji jest dystrybucja produktu. Zawodnik (przeciwnik) może zlecić dystrybucję (patrz lewa strona drzewa). W takim przypadku musi wybrać, na przykład, między krupierem A i B. W ten sposób wybiera tego pierwszego, co powoduje, że gracz x traci 10 (jeśli wybrał B, gracz x wygrałby 12).
Być może jednak przeciwnik woli sam dystrybuować swoje towary, mając możliwość wypożyczenia pojazdów silnikowych lub zakupu ciężarówki. Z obu scenariuszy wybierz pierwszy, który jest mniej pochlebny dla gracza x, ponieważ wygrywa 5, a nie 10.