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
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
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
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
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í.
Související články
Externí odkazy
Média použitá na této stránce
Autor: Nuno Nogueira (Nmnogueira), Licence: CC BY-SA 2.5
Minimax algorithm. Circles represent the moves of the player running the algorithm (maximizing player), and squares represent the moves of the opponent (minimizing player). The values inside the circles and squares represent the value α of the minimax algorithm. The red arrows represent the chosen move, the numbers on the left represent the tree depth and the blue arrow the chosen move.