Minimax (algoritmus)

Minimax je algoritmus, ktorý má určiť najlepšiu stratégiu hry tým, že prezerá dopredu rôzne postupnosti ťahov a snaží sa nájsť takú postupnosť, ktorá vedie k výhre hráča. Minimax algoritmus je považovaný za jeden zo základných algoritmov umelej inteligencie v problematike riešenia problémov opísaných ako hra.

Hra ako problém hľadania a algoritmus minimax

Nech máme hru pre dvoch hráčov, ktorých pomenujeme Max a Min, pričom Max začína hru a následne sa postupne v ťahoch hráči striedajú, kým nie je hra ukončená a následne výsledok hry bodovo ohodnotený. V tomto prípade je hra problémom hľadania:

• začiatočný stav reprezentuje začiatok hry pred prvým ťahom hráča Max
• množina operátorov definuje povolené ťahy hráčov
• množina stavov reprezentuje všetky možné stavy hry
• cieľový test definuje koniec hry
• bodovacia funkcia definuje číselné ohodnotenie výsledkov hry

Algoritmus minimax určuje najlepšiu stratégiu pre hráča Max za predpokladu, že protihráč Min vždy zahrá ťah, ktorý je pre Maxa najhorším možným ťahom, a teda Max sa snaží maximalizovať svoje skóre a Min sa snaží minimalizovať Maxovo skóre. Minimax zaručuje hráčovi optimálnu hru za predpokladu, že výsledok nezávisí od náhodného deja.

Postup algoritmu minimax

Zo začiatku je potrebné vygenerovanie stromu hľadania, ktorý predstavuje preskúmanie všetkých možných stavov hry až po koncové stavy, a teda predstavuje množinu stavov. Jednotlivé stavy je potrebné bodovo ohodnotiť tak, že zo začiatku je na koncové stavy aplikovaná bodovacia funkcia a postupne sa ohodnocujú jednotlivé uzly stromu hľadania až po samotný koreň stromu, pričom platí, že ak je na ťahu Max, na uzol sa prenáša maximum z hodnôt nasledovníkov a ak je na ťahu Min, prenáša sa minimum z hodnôt nasledovníkov. V prípade vygenerovania a ohodnotenia stromu hľadania je možné vykonať ťah, vedúci do najlepšieho postavenia.