- Mini-max algoritmus je rekurzivní nebo backtracking algoritmus, který se používá v rozhodování a teorii her. Poskytuje optimální pohyb pro hráče za předpokladu, že soupeř také hraje optimálně.
- Algoritmus Mini-Max využívá rekurzi k prohledávání herního stromu.
- Algoritmus Min-Max se většinou používá pro hraní her v AI. Jako jsou šachy, dáma, tic-tac-toe, go a různé tahací hry. Tento algoritmus vypočítá rozhodnutí minimax pro aktuální stav.
- V tomto algoritmu hrají hru dva hráči, jeden se nazývá MAX a druhý se nazývá MIN.
- Oba hráči s tím bojují, protože soupeř získá minimální výhodu, zatímco oni získají maximální výhodu.
- Oba hráči hry jsou proti sobě navzájem, kde MAX vybere maximalizovanou hodnotu a MIN vybere minimalizovanou hodnotu.
- Algoritmus minimax provádí hloubkový vyhledávací algoritmus pro prozkoumání celého stromu hry.
- Algoritmus minimax pokračuje celou cestu dolů k terminálovému uzlu stromu a poté se strom vrátí zpět jako rekurze.
Pseudokód pro algoritmus MinMax:
function minimax(node, depth, maximizingPlayer) is if depth ==0 or node is a terminal node then return static evaluation of node if MaximizingPlayer then // for Maximizer Player maxEva= -infinity for each child of node do eva= minimax(child, depth-1, false) maxEva= max(maxEva,eva) //gives Maximum of the values return maxEva else // for Minimizer player minEva= +infinity for each child of node do eva= minimax(child, depth-1, true) minEva= min(minEva, eva) //gives minimum of the values return minEva
Počáteční hovor:
Minimax(uzel, 3, pravda)
Fungování algoritmu Min-Max:
- Fungování algoritmu minimax lze snadno popsat na příkladu. Níže uvádíme příklad herního stromu, který představuje hru dvou hráčů.
- V tomto příkladu jsou dva hráči, jeden se nazývá Maximizer a druhý se nazývá Minimizer.
- Maximizer se pokusí získat maximální možné skóre a Minimizer se pokusí získat minimální možné skóre.
- Tento algoritmus používá DFS, takže v tomto herním stromu musíme projít celou cestu skrz listy, abychom dosáhli koncových uzlů.
- V koncovém uzlu jsou uvedeny koncové hodnoty, takže tyto hodnoty porovnáme a budeme strom zpětně sledovat, dokud nenastane počáteční stav. Níže jsou uvedeny hlavní kroky při řešení stromu hry pro dva hráče:
Krok 1: V prvním kroku algoritmus vygeneruje celý herní strom a použije funkci utility pro získání hodnot užitečnosti pro stavy terminálu. V níže uvedeném stromovém diagramu vezměme, že A je počáteční stav stromu. Předpokládejme, že maximalizér vezme první tah, který má počáteční hodnotu v nejhorším případě =- nekonečno, a minimalizátor provede další tah, který má počáteční hodnotu v nejhorším případě = +nekonečno.
Krok 2: Nyní nejprve najdeme hodnotu utilit pro Maximizer, jeho počáteční hodnota je -∞, takže každou hodnotu v terminálovém stavu porovnáme s počáteční hodnotou Maximizeru a určíme vyšší hodnoty uzlů. Mezi všemi najde maximum.
- Pro uzel D max(-1,- -∞) => max(-1,4)= 4
- Pro uzel E max(2, -∞) => max(2, 6)= 6
- Pro uzel F max(-3, -∞) => max(-3,-5) = -3
- Pro uzel G max(0, -∞) = max(0, 7) = 7
Krok 3: V dalším kroku je na řadě minimalizátor, takže porovná hodnotu všech uzlů s +∞ a najde 3rdhodnoty uzlů vrstvy.
- Pro uzel B= min(4,6) = 4
- Pro uzel C= min (-3, 7) = -3
Krok 4: Nyní je na řadě Maximizer, který opět vybere maximum ze všech uzlů a najde maximální hodnotu pro kořenový uzel. V tomto herním stromu jsou pouze 4 vrstvy, takže se okamžitě dostaneme ke kořenovému uzlu, ale ve skutečných hrách bude více než 4 vrstev.
- Pro uzel A max(4, -3)= 4
To byl kompletní pracovní postup minimax hry pro dva hráče.
Vlastnosti algoritmu Mini-Max:
Omezení algoritmu minimax:
Hlavní nevýhodou algoritmu minimax je, že je opravdu pomalý u komplexních her, jako jsou šachy, go atd. Tento typ her má obrovský faktor rozvětvení a hráč má spoustu možností, jak se rozhodnout. Toto omezení algoritmu minimax lze zlepšit alfa-beta prořezávání které jsme probrali v dalším tématu.