Minimax este un fel de algoritm de backtracking care este folosit în luarea deciziilor și în teoria jocului pentru a găsi mișcarea optimă pentru un jucător, presupunând că și adversarul tău joacă optim. Este utilizat pe scară largă în jocurile pe rând pentru doi jucători, cum ar fi Tic-Tac-Toe, Table, Mancala, șah etc.
În Minimax cei doi jucători sunt numiți maximizator și minimizer. The maximizator încearcă să obțină cel mai mare scor posibil în timp ce minimizator încearcă să facă opusul și să obțină cel mai mic scor posibil.
Fiecare stat consiliu are o valoare asociată. Într-o anumită stare, dacă maximizatorul are avantajul atunci, scorul tablei va tinde să fie o valoare pozitivă. Dacă minimizatorul are avantajul în acea stare de bord, atunci va tinde să fie o valoare negativă. Valorile tablei sunt calculate prin unele euristice care sunt unice pentru fiecare tip de joc.
Exemplu:
Luați în considerare un joc care are 4 stări finale și căile pentru a ajunge la starea finală sunt de la rădăcină la 4 frunze ale unui arbore binar perfect, așa cum se arată mai jos. Să presupunem că ești jucătorul care maximizează și că ai prima șansă de a te mișca, adică ești la rădăcină și adversarul tău la nivelul următor. Ce mutare ai face ca jucător care maximizează, având în vedere că și adversarul tău joacă optim?
string.compareto c#
Deoarece acesta este un algoritm bazat pe backtracking, încearcă toate mișcările posibile, apoi face înapoi și ia o decizie.
- Maximizatorul merge la STÂNGA: acum este rândul minimizatorilor. Minimizatorul are acum de ales între 3 și 5. Fiind minimizatorul, va alege cu siguranță cel mai puțin dintre ambele, adică 3
- Maximizatorul merge DREAPTA: Acum este rândul minimizatorilor. Minimizatorul are acum de ales între 2 și 9. El va alege 2 deoarece este cea mai mică dintre cele două valori.
Fiind maximizator, ați alege valoarea mai mare care este 3. Prin urmare, mișcarea optimă pentru maximizator este să meargă la STÂNGA, iar valoarea optimă este 3.
Acum arborele jocului arată ca mai jos:
Arborele de mai sus arată două scoruri posibile atunci când maximizatorul face mișcări la stânga și la dreapta.
Notă: Chiar dacă există o valoare de 9 în subarborele din dreapta, minimizatorul nu va alege niciodată asta. Trebuie să presupunem întotdeauna că adversarul nostru joacă optim.
Mai jos este implementarea pentru același lucru.
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;> }> |
>
>
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);> > > > |
>
>
Ieșire:
aleator fără generator în java
The optimal value is: 12>
Complexitatea timpului: O(b^d) b este factorul de ramificare și d este numărul de adâncime sau stratul graficului sau arborelui.
Complexitatea spațiului: O(bd) unde b este factorul de ramificare în d este adâncimea maximă a arborelui similar cu DFS.
Ideea acestui articol este de a introduce Minimax cu un exemplu simplu.
- În exemplul de mai sus, există doar două opțiuni pentru un jucător. În general, pot exista mai multe opțiuni. În acest caz, trebuie să revenim pentru toate mișcările posibile și să găsim maximul/minimul. De exemplu, în Tic-Tac-Toe, primul jucător poate face 9 mișcări posibile.
- În exemplul de mai sus, scorurile (frunzele din Arborele jocului) ne sunt date. Pentru un joc tipic, trebuie să derivăm aceste valori
În curând vom acoperi Tic Tac Toe cu algoritmul Minimax.
Acest articol este contribuit de Akshay L. Aradhya.