TechCodeview

• L'algorithme mini-max est un algorithme récursif ou de retour en arrière utilisé dans la prise de décision et la théorie des jeux. Il fournit un mouvement optimal au joueur en supposant que son adversaire joue également de manière optimale.
• L'algorithme Mini-Max utilise la récursion pour effectuer une recherche dans l'arbre du jeu.
• L’algorithme Min-Max est principalement utilisé pour les jeux en IA. Tels que les échecs, les dames, le tic-tac-toe, le go et divers jeux de remorquage. Cet algorithme calcule la décision minimax pour l'état actuel.
• Dans cet algorithme, deux joueurs jouent au jeu, l’un s’appelle MAX et l’autre MIN.
• Les deux joueurs se battent car le joueur adverse obtient le bénéfice minimum tandis qu'il obtient le bénéfice maximum.
• Les deux joueurs du jeu sont adversaires l'un de l'autre, MAX sélectionnant la valeur maximisée et MIN sélectionnant la valeur minimisée.
• L'algorithme minimax exécute un algorithme de recherche en profondeur pour l'exploration de l'arbre de jeu complet.
• L'algorithme minimax descend jusqu'au nœud terminal de l'arbre, puis revient en arrière dans l'arbre en tant que récursion.

Pseudo-code pour l'algorithme 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 

Appel initial :

Minimax(nœud, 3, vrai)

Fonctionnement de l'algorithme Min-Max :

• Le fonctionnement de l’algorithme minimax peut être facilement décrit à l’aide d’un exemple. Ci-dessous, nous avons pris un exemple d'arbre de jeu qui représente le jeu à deux joueurs.
• Dans cet exemple, il y a deux joueurs, l'un s'appelle Maximizer et l'autre s'appelle Minimizer.
• Maximizer essaiera d'obtenir le score maximum possible et Minimizer essaiera d'obtenir le score minimum possible.
• Cet algorithme applique DFS, donc dans cet arbre de jeu, nous devons parcourir toutes les feuilles pour atteindre les nœuds terminaux.
• Au nœud terminal, les valeurs terminales sont données, nous allons donc comparer ces valeurs et revenir en arrière dans l'arborescence jusqu'à ce que l'état initial se produise. Voici les principales étapes impliquées dans la résolution de l’arbre de jeu à deux joueurs :

Étape 1: Dans la première étape, l'algorithme génère l'intégralité de l'arbre de jeu et applique la fonction utilitaire pour obtenir les valeurs d'utilité pour les états terminaux. Dans l’arborescence ci-dessous, prenons A comme état initial de l’arbre. Supposons que le maximiseur prenne le premier tour qui a la valeur initiale dans le pire des cas = - l'infini, et que le minimiseur prenne le tour suivant qui a la valeur initiale dans le pire des cas = + l'infini.

Étape 2: Maintenant, nous trouvons d'abord la valeur des utilitaires du Maximizer, sa valeur initiale est -∞, nous comparerons donc chaque valeur dans l'état terminal avec la valeur initiale du Maximizer et déterminerons les valeurs des nœuds les plus élevées. Il trouvera le maximum parmi tous.

• Pour le nœud D max(-1,- -∞) => max(-1,4)= 4
• Pour le nœud E max(2, -∞) => max(2, 6)= 6
• Pour le nœud F max(-3, -∞) => max(-3,-5) = -3
• Pour le nœud G max(0, -∞) = max(0, 7) = 7

Étape 3: Dans l'étape suivante, c'est au tour du minimiseur, il comparera donc la valeur de tous les nœuds avec +∞, et trouvera les 3^rdvaleurs des nœuds de couche.

• Pour le nœud B= min(4,6) = 4
• Pour le nœud C= min (-3, 7) = -3

Étape 4: C'est maintenant au tour de Maximizer, et il choisira à nouveau la valeur maximale de tous les nœuds et trouvera la valeur maximale pour le nœud racine. Dans cet arbre de jeu, il n'y a que 4 couches, on atteint donc immédiatement le nœud racine, mais dans les jeux réels, il y aura plus de 4 couches.

• Pour le nœud A max(4, -3)= 4

C’était le flux de travail complet du jeu minimax à deux joueurs.

Propriétés de l'algorithme Mini-Max :

Complet-L'algorithme Min-Max est terminé. Il trouvera certainement une solution (si elle existe) dans l'arbre de recherche fini.Optimal-L'algorithme Min-Max est optimal si les deux adversaires jouent de manière optimale.Complexité temporelle-Comme il exécute DFS pour l'arbre de jeu, la complexité temporelle de l'algorithme Min-Max est donc O(b^m) , où b est le facteur de ramification de l'arbre à gibier, et m est la profondeur maximale de l'arbre.Complexité spatiale-La complexité spatiale de l'algorithme Mini-max est également similaire à celle du DFS qui est À propos .

Limitation de l'algorithme minimax :

Le principal inconvénient de l'algorithme minimax est qu'il devient très lent pour les jeux complexes tels que les échecs, le go, etc. Ce type de jeux a un énorme facteur de branchement et le joueur a beaucoup de choix à choisir. Cette limitation de l'algorithme minimax peut être améliorée à partir de taille alpha-bêta dont nous avons discuté dans le sujet suivant.