Minimax je v teorii her metoda, jejímž cílem je minimalizovat očekávanou ztrátu. Za tímto účelem hráč předpokládá, že rozhodnutí jeho soupeře bude nepříznivé. To znamená, že nejhorší scénář se očekává před pohybem soupeře.
Jinými slovy, metoda minimax spočívá v tom, jak se co nejlépe rozhodnout za předpokladu, že druhý hráč pro vás zvolí nejhorší scénář.
Musíme vzít v úvahu, že tato metoda je použitelná ve hře pro dvě osoby (dva hráči) a že nejde o kooperativní, ale o hru s nulovým součtem. To znamená, že to, co jeden hráč vyhraje, ztratí druhý a naopak. V důsledku toho bude mít každý agent zájem na maximalizaci své vlastní užitečnosti, i když to druhého bolí.
V tomto bodě si musíme také pamatovat, že teorie her je odvětví matematiky a ekonomiky, které studuje volbu, která optimalizuje situaci jednotlivce, když náklady a přínosy nejsou stanoveny předem, ale závisí na rozhodnutí ostatních.
Algoritmus Minimax v rozhodovacím stromu
Vidíme, jak se metoda minimax používá v rozhodovacím stromu s několika uzly. Hra začíná dole a končí výsledkem na nejvyšší úrovni.
U základny stromu provede soupeř první tah, takže se očekává nejhorší výsledek. Poté je na druhé úrovni hráč x, který se bude snažit maximalizovat svůj zisk, s přihlédnutím k rozhodnutí, které dříve učinil soupeř.
Na třetí úrovni je opět soupeřův tah a tak dále. Níže ukážeme příklad.
Příklad algoritmu Minimax
V následujícím rozhodovacím stromě ukážeme výsledky získané hráčem x v každém okamžiku hry. Na základně, na první úrovni, rozhoduje soupeř. Z tohoto důvodu jsou uvedeny scénáře, ve kterých může hráč prohrát -10 nebo vyhrát 5.
Na druhé úrovni je to na hráči x, takže maximalizuje svůj zisk. Mezi prohrou 10 nebo vítězstvím 1 vyhrajete 1. Podobně mezi výhrou 5 nebo 7 vyhrajete 7.
Pak je opět řada na protivníkovi, takže budou uvedeny scénáře, ve kterých má hráč x nejhorší výsledek, -3 a 4, podle případu. A konečně, mezi prohrou 3 nebo vítězstvím 4, hráč x udělá rozhodnutí, které mu umožní druhé.
Musíme vzít v úvahu, že hodnoty každého uzlu budou záviset na funkci nástroje.
Pro lepší pochopení stromu předpokládejme, že na základně je rozhodnutí o distribuci produktu. Konkurent (protivník) může distribuci zadat externě (viz levá strana stromu). V takovém případě si musí vybrat například mezi dealerem A a B. Zvolí si tedy první možnost, což způsobí, že hráč x prohraje 10 (Pokud by zvolil B, hráč x vyhraje 12).
Pravděpodobně však protivník upřednostňuje distribuci svého zboží sám, protože si může pronajmout motorová vozidla nebo si koupit nákladní automobil. Z obou scénářů vyberte ten první, který je pro hráče x méně lichotivý, protože vyhrává 5 a ne 10.