Minimax je v teórii hier metóda, ktorej cieľom je minimalizovať očakávanú stratu. Za týmto účelom hráč predpokladá, že rozhodnutie jeho súpera bude nepriaznivé. To znamená, že najhorší scenár sa očakáva pred pohybom súpera.
Inými slovami, metóda minimax spočíva v tom, ako urobiť najlepšie rozhodnutie za predpokladu, že si druhý hráč vyberie pre vás najhorší scenár.
Musíme vziať do úvahy, že táto metóda je použiteľná v hre pre dve osoby (dvaja hráči) a že nejde o kooperatívnu hru, ale o hru s nulovým súčtom. To znamená, že to, čo jeden hráč vyhrá, druhý stratí a naopak. V dôsledku toho bude mať každý agent záujem na maximalizácii svojej vlastnej užitočnosti, aj keď to druhého bolí.
Na tomto mieste si musíme tiež uvedomiť, že teória hier je odvetvie matematiky a ekonómie, ktoré študuje výber, ktorý optimalizuje situáciu jednotlivca, keď náklady a prínosy nie sú stanovené vopred, ale závisia od rozhodnutí ostatných.
Algoritmus Minimax v rozhodovacom strome
Vidíme, ako sa metóda minimax uplatňuje v rozhodovacom strome s niekoľkými uzlami. Hra sa začína v dolnej časti a končí sa výsledkom na najvyššej úrovni.
O základňu stromu urobí súper prvý ťah, očakáva sa teda najhorší výsledok. Potom v druhej úrovni záleží na hráčovi x, ktorý sa bude snažiť maximalizovať svoj zisk, berúc do úvahy rozhodnutie, ktoré predtým urobil súper.
Na tretej úrovni je opäť na rade súper a podobne. Ukážeme si príklad nižšie.
Príklad algoritmu Minimax
V nasledujúcom rozhodovacom strome uvádzame výsledky dosiahnuté hráčom x v každom okamihu hry. Na základni, na prvej úrovni, rozhoduje súper. Z tohto dôvodu sú uvedené scenáre, v ktorých môže hráč prehrať -10 alebo vyhrať 5.
Na druhej úrovni je to na hráčovi x, takže maximalizuje svoj zisk. Medzi prehrou 10 alebo výhrou 1 vyhráte 1. Rovnako tak medzi výhrou 5 alebo 7 vyhráte 7.
Potom je na rade opäť protivník, takže budú uvedené scenáre, v ktorých má hráč x najhorší výsledok, -3 a 4, podľa prípadu. Nakoniec medzi prehrou 3 alebo výhrou 4 urobí hráč x rozhodnutie, ktoré mu umožní druhé.
Musíme vziať do úvahy, že hodnoty každého uzla budú závisieť od užitočnej funkcie.
Pre lepšie pochopenie stromu predpokladajme, že v základe sa rozhoduje o distribúcii produktu. Konkurent (protivník) môže outsourcovať distribúciu (pozri ľavú stranu stromu). V takom prípade si musí zvoliť napríklad medzi dílerom A a B. Vyberie si teda prvého, ktorý spôsobí, že hráč x prehrá 10 (Ak si zvolí B, hráč x vyhrá 12).
Možno však protivník uprednostňuje distribúciu svojho tovaru sám, keď si môže prenajať motorové vozidlá alebo kúpiť nákladné auto. Z oboch scenárov vyberte prvý, ktorý je pre hráča x menej lichotivý, pretože vyhráva 5 a nie 10.