- Mini-max algoritmus je rekurzívny alebo backtracking algoritmus, ktorý sa používa v rozhodovaní a teórii hier. Poskytuje optimálny pohyb pre hráča za predpokladu, že aj súper hrá optimálne.
- Algoritmus Mini-Max využíva rekurziu na vyhľadávanie v hernom strome.
- Algoritmus Min-Max sa väčšinou používa na hranie hier v AI. Ako napríklad šach, dáma, piškvorky, choď a rôzne hry pre hráčov ťahania. Tento algoritmus vypočíta minimaxové rozhodnutie pre aktuálny stav.
- V tomto algoritme hrajú hru dvaja hráči, jeden sa nazýva MAX a druhý sa nazýva MIN.
- Obaja hráči s tým bojujú, pretože súper dostáva minimálny úžitok, zatiaľ čo oni majú maximálny úžitok.
- Obaja hráči v hre sú proti sebe, kde MAX vyberie maximálnu hodnotu a MIN vyberie minimalizovanú hodnotu.
- Algoritmus minimax vykonáva hĺbkový vyhľadávací algoritmus na preskúmanie celého stromu hry.
- Algoritmus minimax pokračuje až do koncového uzla stromu a potom sa strom vráti späť ako rekurzia.
Pseudokód pre 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čiatočný hovor:
Minimax(uzol, 3, pravda)
Fungovanie algoritmu Min-Max:
- Fungovanie algoritmu minimax možno jednoducho opísať na príklade. Nižšie uvádzame príklad herného stromu, ktorý predstavuje hru dvoch hráčov.
- V tomto príklade sú dvaja hráči, jeden sa nazýva Maximizer a druhý sa nazýva Minimizer.
- Maximizer sa pokúsi získať maximálne možné skóre a Minimizer sa pokúsi získať minimálne možné skóre.
- Tento algoritmus používa DFS, takže v tomto hernom strome musíme prejsť celú cestu cez listy, aby sme dosiahli koncové uzly.
- V koncovom uzle sú uvedené koncové hodnoty, takže tieto hodnoty porovnáme a vrátime sa k stromu, kým nenastane počiatočný stav. Nižšie sú uvedené hlavné kroky pri riešení stromu hry pre dvoch hráčov:
Krok 1: V prvom kroku algoritmus vygeneruje celý herný strom a použije funkciu utility na získanie úžitkových hodnôt pre stavy terminálu. V nižšie uvedenom stromovom diagrame si vezmime, že A je počiatočný stav stromu. Predpokladajme, že maximalizér vykoná prvý ťah, ktorý má počiatočnú hodnotu najhoršieho prípadu =- nekonečno, a minimalizátor vykoná ďalší ťah, ktorý má počiatočnú hodnotu najhoršieho prípadu = +nekonečno.
Krok 2: Teraz najskôr nájdeme hodnotu utility pre Maximizer, jeho počiatočná hodnota je -∞, takže každú hodnotu v terminálnom stave porovnáme s počiatočnou hodnotou Maximizera a určíme vyššie hodnoty uzlov. Medzi všetkými nájde maximum.
- Pre uzol D max(-1,- -∞) => max(-1,4)= 4
- Pre uzol E max(2, -∞) => max(2, 6)= 6
- Pre uzol F max(-3, -∞) => max(-3,-5) = -3
- Pre uzol G max(0, -∞) = max(0, 7) = 7
Krok 3: V ďalšom kroku je na rade minimalizátor, takže porovná hodnotu všetkých uzlov s +∞ a nájde 3rdhodnoty uzlov vrstvy.
- Pre uzol B = min(4,6) = 4
- Pre uzol C= min (-3, 7) = -3
Krok 4: Teraz je na rade Maximizer, ktorý opäť vyberie maximálnu hodnotu zo všetkých uzlov a nájde maximálnu hodnotu pre koreňový uzol. V tomto hernom strome sú iba 4 vrstvy, takže sa okamžite dostaneme ku koreňovému uzlu, ale v skutočných hrách bude viac ako 4 vrstvy.
- Pre uzol A max(4, -3)= 4
To bol úplný pracovný postup minimax hry pre dvoch hráčov.
Vlastnosti algoritmu Mini-Max:
Obmedzenie algoritmu minimax:
Hlavnou nevýhodou algoritmu minimax je, že je veľmi pomalý pri zložitých hrách, ako sú šach, choď, atď. Tento typ hier má obrovský faktor rozvetvenia a hráč má veľa možností, ako sa rozhodnúť. Toto obmedzenie algoritmu minimax sa dá vylepšiť alfa-beta prerezávanie o ktorých sme hovorili v ďalšej téme.