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

300px 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. +more 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. +more 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. +more 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. +more Tomuto algoritmu se říká alfa-beta ořezávání.

Související články

Alfa-beta ořezávání * Teorie her

Externí odkazy

[url=https://web.archive.org/web/20111025144500/http://www.linuxsoft.cz/article.php?id_article=1141]Popis algoritmu na Linuxsoft.cz[/url]

Kategorie:Vyhledávací algoritmy Kategorie:Grafové algoritmy Kategorie:Počítače a šachy Kategorie:Teorie her Kategorie:Teorie rozhodování