Minimax (někdy minmax) je metoda v teorii rozhodování pro minimalizaci maximální možné ztráty. Alternativně si ji lze představit jako maximalizaci minimálního zisku (maximin). Vychází z teorie her s nulovým součtem pro dva hráče a zahrnuje jak případy, kdy hráči provádějí střídavé tahy, tak případy, kdy provádějí tahy současně. Byla také rozšířena na složitější hry a na obecné rozhodování za přítomnosti nejistoty.
Jednoduchá verze algoritmu se zabývá hrami, jako je piškvorky, kde každý hráč může vyhrát, prohrát nebo remizovat.
Pokud hráč A může vyhrát v jednom tahu, je jeho nejlepším tahem tento vítězný tah.
Pokud hráč B ví, že jeden tah povede k situaci, kdy hráč A může vyhrát jedním tahem, zatímco jiný tah povede k situaci, kdy hráč A může v nejlepším případě remizovat, pak je nejlepším tahem hráče B ten, který vede k remíze.
V pozdní fázi hry je snadné zjistit, jaký tah je „nejlepší“.
Algoritmus Minimax pomáhá najít nejlepší tah tím, že pracuje zpětně od konce hry. V každém kroku předpokládá, že hráč A se při svém tahu snaží maximalizovat šance na výhru A, zatímco hráč B se v následujícím tahu snaží minimalizovat šance na výhru A (tj. maximalizovat vlastní šance na výhru B).
Kritérium minimaxu v teorii statistického rozhodování
V klasické teorii statistického rozhodování máme k dispozici odhad, který slouží k odhadu parametru . Předpokládáme také funkci rizika , obvykle zadanou jako integrál ztrátové funkce. V tomto rámci se nazývá minimax, pokud splňuje.
Alternativním kritériem v rámci teorie rozhodování je Bayesův odhad za přítomnosti apriorního rozdělení . Odhad je Bayesův, pokud minimalizuje průměrné riziko.
Algoritmus minimaxu s alternativními tahy
Algoritmus minimax je rekurzivní algoritmus pro výběr dalšího tahu ve hře dvou hráčů. Každé pozici nebo stavu hry je přiřazena určitá hodnota. Tato hodnota se vypočítá pomocí funkce vyhodnocení pozice a udává, jak dobré by pro hráče bylo dosáhnout dané pozice. Hráč pak provede tah, který maximalizuje minimální hodnotu pozice vyplývající z možných následujících tahů soupeře. Pokud je na tahu hráč A, přidělí hodnotu každému svému legálnímu tahu.
Jednou z metod přidělování je přiřadit určitou výhru pro A jako +1 a pro B jako -1. To vede ke kombinatorické teorii her, kterou rozvinul John Horton Conway.
Alternativou je použití pravidla, že pokud je výsledkem tahu okamžitá výhra pro A, je mu přiřazeno kladné nekonečno, a pokud je okamžitou výhrou pro B, je mu přiřazeno záporné nekonečno. Hodnota jakéhokoli jiného tahu pro A je minimem hodnot vyplývajících z každé z možných odpovědí B. (A se nazývá maximalizující hráč a B minimalizující hráč), proto se nazývá algoritmus minimax. Výše uvedený algoritmus přiřadí libovolné pozici hodnotu kladného nebo záporného nekonečna, protože hodnota každé pozice bude hodnotou nějaké konečné vyhrávající nebo prohrávající pozice. Často je to obecně možné pouze na samém konci složitých her, jako jsou šachy nebo go, protože není výpočetně možné podívat se dopředu až k dokončení hry, leda ke konci, a místo toho se pozicím přiřazují konečné hodnoty jako odhady míry přesvědčení, že povedou k výhře jednoho nebo druhého hráče.
To lze rozšířit, pokud můžeme dodat heuristickou vyhodnocovací funkci, která dává hodnoty nefinálním stavům hry, aniž by se uvažovaly všechny možné následující úplné posloupnosti. Pak můžeme omezit minimaxový algoritmus tak, aby se díval pouze na určitý počet tahů dopředu. Tento počet se nazývá „look-ahead“ a měří se v „tazích“. Například „Deep Blue“ se dívá dopředu na 12 tahů.
Algoritmus si lze představit jako prozkoumávání uzlů herního stromu. Efektivní faktor větvení stromu je průměrný počet dětí každého uzlu (tj. průměrný počet legálních tahů v pozici). Počet uzlů, které je třeba prozkoumat, obvykle roste exponenciálně s počtem tahů (v případě vyhodnocování vynucených tahů nebo opakovaných pozic je menší než exponenciální). Počet uzlů, které je třeba prozkoumat při analýze hry, je tedy přibližně roven faktoru větvení zvýšenému na mocninu počtu polí. Není proto možné kompletně analyzovat hry, jako jsou šachy, pomocí algoritmu minimax.
Výkonnost naivního minimaxového algoritmu lze výrazně zlepšit, aniž by to ovlivnilo výsledek, použitím alfa-beta ořezávání.
Lze použít i jiné heuristické metody prořezávání, ale ne u všech je zaručeno, že poskytnou stejný výsledek jako prohledávání bez prořezávání.
Věta o minimu se simultánními tahy
Následující příklad hry s nulovým součtem, kde A a B provádějí tahy současně, ilustruje algoritmus minimax. Pokud má každý hráč tři možnosti a matice výplat pro A je:
a B má stejnou matici výplat s obrácenými znaménky (tj. pokud jsou volby A1 a B1, pak B zaplatí A 3), pak jednoduchá minimaxová volba pro A je A2, protože nejhorším možným výsledkem je pak nutnost zaplatit 1, zatímco jednoduchá minimaxová volba pro B je B2, protože nejhorším možným výsledkem je pak žádná platba. Toto řešení však není stabilní, protože pokud B věří, že A zvolí A2, pak B zvolí B1, aby získal 1; pak pokud A věří, že B zvolí B1, pak A zvolí A1, aby získal 3; a pak B zvolí B2; a nakonec si oba hráči uvědomí obtížnost volby. Je tedy zapotřebí stabilnější strategie.
Některé možnosti jsou dominantní a lze je vyloučit: B si nevybere B3, protože B2 bude mít lepší výsledek bez ohledu na to, co si vybere A. A si nevybere A3, protože A1 nebo A2 bude mít lepší výsledek bez ohledu na to, co si vybere A.
A se může vyhnout očekávané platbě vyšší než 1/3 tím, že zvolí A1 s pravděpodobností 1/6 a A2 s pravděpodobností 5/6 bez ohledu na to, co zvolí B. B si může zajistit očekávaný zisk alespoň 1/3 použitím náhodné strategie volby B1 s pravděpodobností 1/3 a B2 s pravděpodobností 2/3 bez ohledu na to, co zvolí A. Tyto smíšené minimaxové strategie jsou nyní stabilní a nelze je vylepšit.
John von Neumann v roce 1928 dokázal větu o minimálním součtu, podle níž takové strategie vždy existují ve hrách s nulovým součtem pro dvě osoby a lze je nalézt řešením soustavy simultánních rovnic.
Minimax tváří v tvář nejistotě
Teorie minimaxu byla rozšířena na rozhodování, kde neexistuje žádný jiný hráč, ale kde důsledky rozhodnutí závisí na neznámých skutečnostech. Například rozhodnutí o vyhledávání nerostů s sebou nese náklady, které budou zbytečné, pokud se nerosty nevyskytují, ale přinesou velké odměny, pokud se vyskytují. Jedním z přístupů je považovat to za hru proti přírodě a s využitím podobného myšlení jako u Murphyho zákonů zvolit přístup, který minimalizuje maximální očekávanou ztrátu, a to za použití stejných technik jako u her s nulovým součtem pro dvě osoby.
Kromě toho byly vyvinuty stromy expectiminimaxů pro hry pro dva hráče, ve kterých hraje roli náhoda (například kostky).
Minimax ve hrách s nenulovým součtem
Pokud mají hry nenulový součet z hlediska výplat mezi hráči, mohou se vyvinout zdánlivě neoptimální strategie. Například ve vězňově dilematu je strategií minimaxu pro každého z vězňů zradit toho druhého, přestože by každý z nich udělal lépe, kdyby se ani jeden nepřiznal ke své vině. U her s nenulovým součtem tedy nemusí být nejlepší strategie nutně minimaxová.