Minimax est une sorte d'algorithme de retour en arrière utilisé dans la prise de décision et la théorie des jeux pour trouver le coup optimal pour un joueur, en supposant que votre adversaire joue également de manière optimale. Il est largement utilisé dans les jeux au tour par tour à deux joueurs tels que Tic-Tac-Toe, Backgammon, Mancala, Chess, etc.
Dans Minimax, les deux joueurs sont appelés maximiseur et minimiseur. Le maximiseur essaie d'obtenir le score le plus élevé possible pendant que le minimiseur essaie de faire le contraire et d’obtenir le score le plus bas possible.
Chaque état du tableau est associé à une valeur. Dans un état donné, si le maximiseur a le dessus, le score du tableau aura tendance à être une valeur positive. Si le minimiseur a le dessus dans cet état de la carte, il aura tendance à avoir une valeur négative. Les valeurs du plateau sont calculées par des heuristiques uniques pour chaque type de jeu.
Exemple:
Considérons un jeu qui a 4 états finaux et les chemins pour atteindre l'état final vont de la racine aux 4 feuilles d'un arbre binaire parfait, comme indiqué ci-dessous. Supposons que vous êtes le joueur qui maximise et que vous avez la première chance de bouger, c'est-à-dire que vous êtes à la racine et votre adversaire au niveau suivant. Quel mouvement feriez-vous en tant que joueur maximisant étant donné que votre adversaire joue également de manière optimale ?
Puisqu’il s’agit d’un algorithme basé sur le retour en arrière, il essaie tous les mouvements possibles, puis revient en arrière et prend une décision.
- Le maximiseur va à GAUCHE : c'est maintenant au tour des minimisateurs. Le minimiseur a désormais le choix entre 3 et 5. Étant le minimiseur, il choisira certainement le moins parmi les deux, soit 3.
- Le maximiseur va à DROITE : c'est maintenant au tour des minimiseur. Le minimiseur a désormais le choix entre 2 et 9. Il choisira 2 car c'est la plus petite des deux valeurs.
Étant le maximiseur, vous choisirez la valeur la plus grande, soit 3. Par conséquent, le mouvement optimal pour le maximiseur est d'aller à GAUCHE et la valeur optimale est 3.
L'arbre du jeu ressemble maintenant à ci-dessous :
L'arbre ci-dessus montre deux scores possibles lorsque le maximiseur effectue des mouvements à gauche et à droite.
Remarque : Même s'il y a une valeur de 9 sur le sous-arbre de droite, le minimiseur ne la sélectionnera jamais. Nous devons toujours partir du principe que notre adversaire joue de manière optimale.
Vous trouverez ci-dessous la mise en œuvre de la même chose.
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
cassidy hutchinson éducation
// 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
qu'est-ce qu'Oracle
# 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);> > > > |
>
>
Sortir:
The optimal value is: 12>
Complexité temporelle : O(b^d) b est le facteur de branchement et d est le nombre de profondeurs ou de plis d'un graphique ou d'un arbre.
Complexité spatiale : O (bd) où b est le facteur de branchement en d est la profondeur maximale de l'arbre similaire à DFS.
L'idée de cet article est de présenter Minimax avec un exemple simple.
- Dans l’exemple ci-dessus, il n’y a que deux choix pour un joueur. En général, il peut y avoir plus de choix. Dans ce cas, nous devons répéter tous les mouvements possibles et trouver le maximum/minimum. Par exemple, au Tic-Tac-Toe, le premier joueur peut effectuer 9 mouvements possibles.
- Dans l'exemple ci-dessus, les scores (feuilles du Game Tree) nous sont donnés. Pour un jeu typique, nous devons dériver ces valeurs
Nous aborderons bientôt Tic Tac Toe avec l'algorithme Minimax.
Cet article est rédigé par Akshay L. Aradhya.