Minimax je akýsi backtrackingový algoritmus, ktorý sa používa pri rozhodovaní a teórii hier na nájdenie optimálneho ťahu pre hráča za predpokladu, že aj váš súper hrá optimálne. Je široko používaný v ťahových hrách pre dvoch hráčov, ako sú Tic-Tac-Toe, Backgammon, Mancala, Chess atď.
V Minimax sa títo dvaja hráči nazývajú maximalizátor a minimalizátor. The maximalizátor sa snaží získať čo najvyššie skóre minimalizátor sa snaží urobiť opak a získať čo najnižšie skóre.
Každý stav dosky má s ním spojenú hodnotu. V danom stave, ak má maximalizér navrch, bude mať skóre rady kladnú hodnotu. Ak má minimalizátor navrchu v tomto stave dosky, bude mať tendenciu mať nejakú zápornú hodnotu. Hodnoty hracej plochy sa vypočítavajú pomocou niektorých heuristiek, ktoré sú jedinečné pre každý typ hry.
Príklad:
Predstavte si hru, ktorá má 4 konečné stavy a cesty k dosiahnutiu konečného stavu sú od koreňa po 4 listy dokonalého binárneho stromu, ako je znázornené nižšie. Predpokladajme, že ste maximalizujúci hráč a máte prvú šancu pohnúť sa, t. j. vy ste pri koreni a váš súper na ďalšej úrovni. Aký ťah by ste urobili ako maximalizujúci hráč vzhľadom na to, že aj váš súper hrá optimálne?
Keďže ide o algoritmus založený na backtrackingu, skúša všetky možné pohyby, potom sa vráti späť a urobí rozhodnutie.
- Maximalizátor ide DOĽAVA: Teraz sú na rade minimalizátory. Minimalizátor má teraz na výber medzi 3 a 5. Keďže je minimalizátorom, rozhodne si vyberie najmenej spomedzi oboch, teda 3
- Maximalizátor ide DOPRAVA: Teraz sú na rade minimalizátory. Minimalizátor má teraz na výber medzi 2 a 9. Vyberie si 2, pretože je to najmenej spomedzi dvoch hodnôt.
Ako maximalizátor by ste zvolili väčšiu hodnotu, ktorá je 3. Optimálnym krokom pre maximalizér je teda ísť DOĽAVA a optimálna hodnota je 3.
Teraz strom hry vyzerá takto:
Vyššie uvedený strom zobrazuje dve možné skóre, keď maximalizér robí pohyby doľava a doprava.
Poznámka: Aj keď je v pravom podstrome hodnota 9, minimalizátor ju nikdy nevyberie. Vždy musíme vychádzať z toho, že súper hrá optimálne.
Nižšie je uvedená implementácia toho istého.
C++
// A simple C++ program to find> // maximum score that> // maximizing player can get.> #include> using> namespace> std;> // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is> // of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> int> minimax(>int> depth,>int> nodeIndex,>bool> isMax,> >int> scores[],>int> h)> {> >// Terminating condition. i.e> >// leaf node is reached> >if> (depth == h)> >return> scores[nodeIndex];> >// If current move is maximizer,> >// find the maximum attainable> >// value> >if> (isMax)> >return> max(minimax(depth+1, nodeIndex*2,>false>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>false>, scores, h));> >// Else (If current move is Minimizer), find the minimum> >// attainable value> >else> >return> min(minimax(depth+1, nodeIndex*2,>true>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>true>, scores, h));> }> // A utility function to find Log n in base 2> int> log2(>int> n)> {> >return> (n==1)? 0 : 1 + log2(n/2);> }> // Driver code> int> main()> {> >// The number of elements in scores must be> >// a power of 2.> >int> scores[] = {3, 5, 2, 9, 12, 5, 23, 23};> >int> n =>sizeof>(scores)/>sizeof>(scores[0]);> >int> h = log2(n);> >int> res = minimax(0, 0,>true>, scores, h);> >cout <<>'The optimal value is : '> << res << endl;> >return> 0;> }> |
c# tutoriál
>
>
Java
// A simple java program to find maximum score that> // maximizing player can get.> import> java.io.*;> class> GFG {> > // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> >static> int> minimax(>int> depth,>int> nodeIndex,>boolean> isMax,> >int> scores[],>int> h)> {> >// Terminating condition. i.e leaf node is reached> >if> (depth == h)> >return> scores[nodeIndex];> >// If current move is maximizer, find the maximum attainable> >// value> >if> (isMax)> >return> Math.max(minimax(depth+>1>, nodeIndex*>2>,>false>, scores, h),> >minimax(depth+>1>, nodeIndex*>2> +>1>,>false>, scores, h));> >// Else (If current move is Minimizer), find the minimum> >// attainable value> >else> >return> Math.min(minimax(depth+>1>, nodeIndex*>2>,>true>, scores, h),> >minimax(depth+>1>, nodeIndex*>2> +>1>,>true>, scores, h));> }> // A utility function to find Log n in base 2> >static> int> log2(>int> n)> {> return> (n==>1>)?>0> :>1> + log2(n/>2>);> }> // Driver code> >public> static> void> main (String[] args) {> >// The number of elements in scores must be> >// a power of 2.> >int> scores[] = {>3>,>5>,>2>,>9>,>12>,>5>,>23>,>23>};> >int> n = scores.length;> >int> h = log2(n);> >int> res = minimax(>0>,>0>,>true>, scores, h);> >System.out.println(>'The optimal value is : '> +res);> > >}> }> // This code is contributed by vt_m> |
>
>
C#
// A simple C# program to find maximum score that> // maximizing player can get.> using> System;> public> class> GFG> {> > // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> static> int> minimax(>int> depth,>int> nodeIndex,>bool> isMax,> >int> []scores,>int> h)> {> >// Terminating condition. i.e leaf node is reached> >if> (depth == h)> >return> scores[nodeIndex];> >// If current move is maximizer, find the maximum attainable> >// value> >if> (isMax)> >return> Math.Max(minimax(depth+1, nodeIndex*2,>false>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>false>, scores, h));> >// Else (If current move is Minimizer), find the minimum> >// attainable value> >else> >return> Math.Min(minimax(depth+1, nodeIndex*2,>true>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>true>, scores, h));> }> // A utility function to find Log n in base 2> static> int> log2(>int> n)> {> >return> (n==1)? 0 : 1 + log2(n/2);> }> // Driver code> static> public> void> Main ()> {> >// The number of elements in scores must be> >// a power of 2.> >int> []scores = {3, 5, 2, 9, 12, 5, 23, 23};> >int> n = scores.Length;> >int> h = log2(n);> >int> res = minimax(0, 0,>true>, scores, h);> >Console.WriteLine(>'The optimal value is : '> +res);> > }> }> // This code is contributed by ajit.> |
>
>
Python3
# A simple Python3 program to find> # maximum score that> # maximizing player can get> import> math> def> minimax (curDepth, nodeIndex,> >maxTurn, scores,> >targetDepth):> ># base case : targetDepth reached> >if> (curDepth>=>=> targetDepth):> >return> scores[nodeIndex]> > >if> (maxTurn):> >return> max>(minimax(curDepth>+> 1>, nodeIndex>*> 2>,> >False>, scores, targetDepth),> >minimax(curDepth>+> 1>, nodeIndex>*> 2> +> 1>,> >False>, scores, targetDepth))> > >else>:> >return> min>(minimax(curDepth>+> 1>, nodeIndex>*> 2>,> >True>, scores, targetDepth),> >minimax(curDepth>+> 1>, nodeIndex>*> 2> +> 1>,> >True>, scores, targetDepth))> > # Driver code> scores>=> [>3>,>5>,>2>,>9>,>12>,>5>,>23>,>23>]> treeDepth>=> math.log(>len>(scores),>2>)> print>(>'The optimal value is : '>, end>=> '')> print>(minimax(>0>,>0>,>True>, scores, treeDepth))> # This code is contributed> # by rootshadow> |
>
>
Javascript
> // Javascript program to find maximum score that> // maximizing player can get.> // Returns the optimal value a maximizer can obtain.> // depth is current depth in game tree.> // nodeIndex is index of current node in scores[].> // isMax is true if current move is of maximizer, else false> // scores[] stores leaves of Game tree.> // h is maximum height of Game tree> >function> minimax(depth, nodeIndex, isMax,> >scores, h)> {> >// Terminating condition. i.e leaf node is reached> >if> (depth == h)> >return> scores[nodeIndex];> > >// If current move is maximizer, find the maximum attainable> >// value> >if> (isMax)> >return> Math.max(minimax(depth+1, nodeIndex*2,>false>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>false>, scores, h));> > >// Else (If current move is Minimizer), find the minimum> >// attainable value> >else> >return> Math.min(minimax(depth+1, nodeIndex*2,>true>, scores, h),> >minimax(depth+1, nodeIndex*2 + 1,>true>, scores, h));> }> > // A utility function to find Log n in base 2> >function> log2(n)> {> return> (n==1)? 0 : 1 + log2(n/2);> }> > // Driver Code> >// The number of elements in scores must be> >// a power of 2.> >let scores = [3, 5, 2, 9, 12, 5, 23, 23];> >let n = scores.length;> >let h = log2(n);> >let res = minimax(0, 0,>true>, scores, h);> >document.write(>'The optimal value is : '> +res);> > > > |
>
Vymazať vyrovnávaciu pamäť npm
>
Výkon:
The optimal value is: 12>
Časová zložitosť: O(b^d) b je faktor vetvenia a d je počet hĺbky alebo vrstvy grafu alebo stromu.
Priestorová zložitosť: O(bd) kde b je faktor vetvenia na d je maximálna hĺbka stromu podobná DFS.
Myšlienkou tohto článku je predstaviť Minimax na jednoduchom príklade.
- Vo vyššie uvedenom príklade má hráč iba dve možnosti. Vo všeobecnosti môže byť viac možností. V takom prípade musíme opakovať všetky možné ťahy a nájsť maximum/minimum. Napríklad v hre Tic-Tac-Toe môže prvý hráč urobiť 9 možných ťahov.
- Vo vyššie uvedenom príklade sú nám dané skóre (listy stromu hry). Pre typickú hru musíme tieto hodnoty odvodiť
Čoskoro pokryjeme Tic Tac Toe algoritmom Minimax.
Do tohto článku prispeli Akshay L. Aradhya.