Minimax (algoritmus)
Minimax je algoritmus, používaný pro hraní strategických her mezi dvěma a více hráči. Principem algoritmu je procházení stromu hry a minimalizace maximálních možných ztrát. Algoritmus bývá základem většiny počítačových programů pro hraní her, jako jsou piškvorky, dáma nebo šachy.
Popis
[editovat | editovat zdroj]
Typickým úkolem je nalézt nejlepší tah v dané pozici. Předpokladem je existence nějaké funkce, která je schopna obodovat libovolnou pozici.
Algoritmus projde všechny možné tahy, provede obodování vzniklých pozic a vybere ten tah, který přinese nejvýhodnější pozici. Obodování se provede buď přímo pomocí statické ohodnocovací funkce, nebo rekurzivním voláním téhož algoritmu za soupeře. Rekurze má omezenou hloubku, aby algoritmus skončil v rozumném čase. Statická ohodnocovací funkce musí být velmi rychlá, proto například v šachách je jejím těžištěm obvykle prostý součet materiálu a jasně definovatelných pozičních výhod, jako je například věž na volném sloupci, nevýhoda dvojpěšce a podobně.
Složitost
[editovat | editovat zdroj]Algoritmus má jen malou paměťovou složitost, neboť si nemusí pamatovat celou během výpočtu propočítanou část stromu hry. V paměti je vždy jen aktuální varianta (cesta od kořene k listu propočtu) a bezprostředně navazující tahy. Problémem však je exponenciální časová složitost. V případě stromu s konstantním větvícím faktorem v a hloubkou h je časová složitost vh.
Z propočtu časové složitosti vyplývá slabina algoritmu: pro hry, které mají velký větvící faktor, jej nelze efektivně nasadit do větší hloubky. Proto je jeho nasazení úspěšné například v šachu, ale samostatně prakticky nepoužitelné v go.
V praxi se proto raději používají algoritmy odvozené od alfa-beta ořezávání, které dosahuje oproti minimaxu ve stejném čase téměř dvojnásobné hloubky propočtu.
Pevná hloubka propočtu
[editovat | editovat zdroj]Dalším problémem základní verze algoritmu je pevná hloubka propočtu a z ní vyplývající komplikace. Listy propočtu odhaduje statická ohodnocovací funkce a ne každá pozice lze lehce bez propočtu odhadnout. Například v šachách se špatně odhaduje pozice uprostřed výměny materiálu. Pokud bílý sebere dámou krytého pěšce, statická ohodnocovací funkce preferuje bílého, který má dočasně o pěšce víc a ztrátu dámy již nedopočítá. V praxi se to řeší dopočtem do tiché pozice bez elementárních taktických obratů. Kromě toho se obvykle prohlubuje propočet variant, která se zdají být významné (například vynucená varianta) a zkracuje nebo zcela ruší propočet variant, které se programu z nějakého důvodu nelíbí (například výrazně horší pozice než v jiné variantě).
Optimalizace
[editovat | editovat zdroj]Strom vytvořený na principu minimaxu jde určitými způsoby optimalizovat. Jedním z takových způsobů je odstranění větví, které nemusíme procházet, protože nemohou jakkoli ovlivnit výsledek. Tomuto algoritmu se říká alfa-beta ořezávání.
