Algorithme Minimax avec élagage Alpha-bêta

Depuis l’avènement de l’Intelligence Artificielle (IA), le jeu est l’une des applications les plus intéressantes de l’IA.

Les premiers programmes d’échecs ont été écrits par Claude Shannon et Alan Turing en 1950, presque dès que les ordinateurs sont devenus programmables.

Les jeux d’échecs, de tic-tac-toe et de Go sont intéressants car ils offrent une pure abstraction de la compétition entre les deux armées.

C’est cette abstraction qui fait du jeu un domaine attrayant pour la recherche en IA.

Dans cet article, nous allons passer en revue les bases de l’algorithme Minimax ainsi que le fonctionnement de l’algorithme.

Nous examinerons également l’optimisation de l’algorithme minimax, l’élagage alpha-bêta.

Qu’est-ce que l’algorithme Minimax ?

Minimax est un algorithme récursif qui est utilisé pour choisir un coup optimal pour un joueur en supposant que l’autre joueur joue également de manière optimale.

Il est utilisé dans des jeux tels que tic-tac-toe, go, échecs, Isola, dames et de nombreux autres jeux à deux joueurs.

De tels jeux sont appelés jeux d’information parfaite car il est possible de voir tous les mouvements possibles d’un jeu particulier.

Il peut y avoir des jeux à deux joueurs qui ne sont pas d’informations parfaites comme le Scrabble car le coup de l’adversaire ne peut pas être prédit.

C’est similaire à ce que nous pensons lorsque nous jouons à un jeu: « si je fais ce mouvement, mon adversaire ne peut faire que ces mouvements », etc.

Minimax est appelé ainsi car il aide à minimiser la perte lorsque l’autre joueur choisit la stratégie ayant la perte maximale.

Terminologie

• Arbre de jeu : C’est une structure en forme d’arbre constituée de tous les mouvements possibles qui vous permettent de passer d’un état du jeu à l’état suivant.

Un jeu peut être défini comme un problème de recherche avec les composants suivants:

• État initial : Il comprend la position de la planche et indique de qui il s’agit.
• Fonction successeur: Il définit les mouvements légaux qu’un joueur peut effectuer.
• État du terminal: C’est la position du plateau lorsque le jeu se termine.
• Fonction utilitaire : C’est une fonction qui attribue une valeur numérique au résultat d’une partie. Par exemple, aux échecs ou au tic-tac-toe, le résultat est une victoire, une défaite ou un match nul, et ceux-ci peuvent être représentés par les valeurs +1, -1 ou 0, respectivement. Il y a des jeux qui ont une gamme beaucoup plus large de résultats possibles; par exemple, les utilitaires dans le backgammon varient de +192 à -192. Une fonction utilitaire peut également être appelée fonction de gain.

Comment fonctionne l’algorithme ?

Il y a deux joueurs impliqués dans une partie, appelés MIN et MAX. Le joueur MAX essaie d’obtenir le score le plus élevé possible et MIN essaie d’obtenir le score le plus bas possible, c’est-à-dire que MIN et MAX essaient d’agir l’un en face de l’autre.

Le processus général de l’algorithme Minimax est le suivant:

Étape 1: Tout d’abord, générez l’arborescence complète du jeu en commençant par la position actuelle du jeu jusqu’aux états terminaux. Voici à quoi ressemble l’arbre du jeu pour le jeu tic-tac-toe.

Comprenons la terminologie définie en termes du diagramme ci-dessus.

1. L’état initial est le premier calque qui définit que la carte est vide c’est au tour de MAX de jouer.
2. Fonction successeur répertorie tous les mouvements successeurs possibles. Il est défini pour toutes les couches de l’arborescence.
3. L’état terminal est la dernière couche de l’arborescence qui affiche l’état final, c’est-à-dire si le joueur MAX gagne, perd ou est lié à l’adversaire.
4. Les utilitaires dans ce cas pour les états de terminal sont 1, 0 et -1 comme discuté précédemment, et ils peuvent également être utilisés pour déterminer les utilitaires des autres nœuds.

Étape 2: Appliquez la fonction utilitaire pour obtenir les valeurs d’utilité pour tous les états de terminal.
Étape 3: Déterminez les utilitaires des nœuds supérieurs à l’aide des utilitaires des nœuds terminaux. Par exemple, dans le diagramme ci-dessous, nous avons les utilitaires pour les états du terminal écrits dans les carrés.

Calculons l’utilitaire pour le nœud gauche (rouge) de la couche au-dessus du terminal. Comme il s’agit du déplacement du joueur MIN, nous choisirons le minimum de tous les utilitaires. Pour ce cas, nous devons évaluer MIN {3, 5, 10}, ce que nous savons être certainement 3. L’utilitaire pour le nœud rouge est donc 3.

De même, pour le nœud vert dans la même couche, il faudra évaluer MIN{2,2} qui vaut 2.

Étape 4: Calculez les valeurs d’utilité à l’aide de feuilles en considérant une couche à la fois jusqu’à la racine de l’arbre.
Étape 5: Finalement, toutes les valeurs sauvegardées atteignent la racine de l’arbre, c’est-à-dire le point le plus haut. À ce stade, MAX doit choisir la valeur la plus élevée.

Dans notre exemple, nous n’avons que 3 couches, donc nous sommes immédiatement arrivés à la racine, mais dans les jeux réels, il y aura beaucoup plus de couches et de nœuds. Nous devons donc évaluer MAX {3,2} qui est 3.

Par conséquent, le meilleur mouvement d’ouverture pour MAX est le nœud gauche (ou le nœud rouge). Ce mouvement est appelé la décision minimax car il maximise l’utilité en supposant que l’adversaire joue également de manière optimale pour le minimiser.

Pour résumer,

Décision Minimax = MAX {MIN{3,5,10}, MIN{2,2}}
= MAX{3,2}
= 3

Code d’alimentation:

function minimax(node, depth, maximizingPlayer) if depth = 0 or node is a terminal node return the utility of the node if maximizingPlayer bestValue := ?? for each child of node v := minimax(child, depth ? 1, FALSE) bestValue := max(bestValue, v) return bestValue else (* minimizing player *) bestValue := +? for each child of node v := minimax(child, depth ? 1, TRUE) bestValue := min(bestValue, v) return bestValue

Optimisation

Les arbres de jeu sont, en général, très longs à construire, et ce n’est que pour les jeux simples qu’ils peuvent être générés en peu de temps.

S’il y a \(b\) mouvements légaux, c’est-à-dire, \(b\) nœuds en chaque point et la profondeur maximale de l’arbre est \(m\), la complexité temporelle de l’algorithme minimax est de l’ordre \(b^m(O(b^m))\).

Pour limiter cette situation, quelques optimisations peuvent être ajoutées à l’algorithme.

Heureusement, il est viable de trouver la décision minimax réelle sans même regarder chaque nœud de l’arborescence du jeu. Par conséquent, nous éliminons les nœuds de l’arbre sans analyser, et ce processus est appelé élagage.

Taille alpha-bêta

La méthode que nous allons examiner dans cet article s’appelle la taille alpha-bêta.

Si nous appliquons l’élagage alpha-bêta à un algorithme minimax standard, il renvoie le même mouvement que celui standard, mais il supprime (pruneau) tous les nœuds qui n’affectent peut-être pas la décision finale.

Comprenons d’abord l’intuition derrière cela et ensuite nous formaliserons l’algorithme. Supposons que nous ayons l’arbre de jeu suivant:

Dans ce cas,
Décision Minimax = MAX{MIN{3,5,10}, MIN{2,a,b}, MIN{2,7,3}}
= MAX{3, c,2}
= 3

Vous seriez surpris!

Comment pourrions-nous calculer le maximum avec une valeur manquante? Voici l’astuce. MIN {2, a, b} serait certainement inférieur ou égal à 2, c’est-à-dire que c < = 2 et donc MAX{3, c, 2} doit être 3.

La question est maintenant de savoir si nous devons vraiment calculer c? Bien sûr que non.

Nous aurions pu arriver à une conclusion sans regarder ces nœuds. Et c’est là que la taille alpha-bêta entre en jeu.

Quelques définitions:

Alpha: C’est le meilleur choix jusqu’à présent pour le joueur MAX. Nous voulons obtenir la valeur la plus élevée possible ici.
Bêta: C’est le meilleur choix jusqu’à présent pour MIN, et il doit s’agir de la valeur la plus basse possible.

Remarque : Chaque nœud doit garder une trace de ses valeurs alpha et bêta. Alpha ne peut être mis à jour que lorsque c’est le tour de MAX et, de même, la bêta ne peut être mise à jour que lorsque c’est la chance de MIN.

Comment fonctionne la taille alpha-bêta?

1. Initialisez alpha=-infinity et beta=infinity dans les pires cas possibles. La condition pour élaguer un nœud est lorsque alpha devient supérieur ou égal à bêta.
2. Commencez par attribuer les valeurs initiales d’alpha et de bêta à la racine et comme alpha est inférieur à bêta, nous ne le taillons pas.
3. Transmettez ces valeurs alpha et bêta au nœud enfant situé à gauche. Et maintenant, à partir de la valeur d’utilité de l’état du terminal, nous mettrons à jour les valeurs de alpha et be, nous n’avons donc pas à mettre à jour la valeur de beta. Encore une fois, nous ne taillons pas car la condition reste la même. De même, le troisième nœud enfant également. Et puis en revenant à la racine, nous définissons alpha = 3 car c’est la valeur minimale que alpha peut avoir.
   
4. Maintenant, alpha = 3 et bêta = infini à la racine. Donc, nous ne taillons pas. En portant cela au nœud central et en calculant MIN {2, infinity}, nous obtenons alpha = 3 et bêta = 2.
5. Taillez les deuxième et troisième nœuds enfants car alpha est maintenant supérieur à bêta.
6. Alpha à la racine reste 3 car il est supérieur à 2. En portant cela au nœud enfant le plus à droite, évaluez MIN {infinity,2} = 2. Mettez à jour la version bêta en 2 et l’alpha reste 3.
7. Taillez les deuxième et troisième nœuds enfants car alpha est maintenant supérieur à bêta.
8. Par conséquent, nous obtenons 3, 2, 2 aux nœuds MIN gauche, centre et droit, respectivement. Et en calculant MAX {3,2,2}, on obtient 3. Par conséquent, sans même regarder quatre feuilles, nous avons pu trouver correctement la décision minimax.

Pseudocode (Source : Cours NPTEL):

evaluate (node, alpha, beta) if node is a leaf return the utility value of node if node is a minimizing node for each child of node beta = min (beta, evaluate (child, alpha, beta)) if beta <= alpha return beta return beta if node is a maximizing node for each child of node alpha = max (alpha, evaluate (child, alpha, beta)) if beta <= alpha return alpha return alpha

Conclusion

Les jeux sont très attrayants et l’écriture de programmes de jeu est peut-être encore plus excitante. Ce que la course de Grand Prix est pour l’industrie automobile, le jeu est pour l’IA.

Tout comme nous ne nous attendions pas à ce qu’une voiture de course fonctionne parfaitement sur une route cahoteuse, nous ne devrions pas nous attendre à ce que les algorithmes de jeu soient parfaits pour toutes les situations.

L’algorithme minimax aussi. Ce n’est peut-être pas la meilleure solution à toutes sortes de jeux informatiques qui ont besoin d’IA.

Mais avec une bonne implémentation, cela peut créer un concurrent difficile.