Intelligence Artificielle et Puissance 4

J'ai dessiné en gras les cases qui peuvent contenir des pions, soit 7 colonnes pour 6 lignes comme tout Puissance 4 qui se respecte. L'intérêt d'utiliser un tableau par rapport à une matrice est qu'un seul indice permet de s'y déplacer dans toutes les directions : pour aller une case vers le haut à droite, ajouter (NB_COLONNES+1+1) ; pour aller vers la gauche, ajouter -1 ; etc. D'où le tableau Directions, qui recense les 4 directions possibles (il ne faudra pas oublier de regarder aussi les symétriques pour avoir toutes les 8 directions). Enfin, j'ai rajouté des lignes et colonnes inutilisées de chaque côté, comme ça en regardant à côté d'une case valide on ne risquera pas de faire des débordements de tableau (ces cases seront marquées comme DEHORS).

On suppose ensuite que l'adversaire va aussi essayer d'atteindre la position la plus avantageuse pour lui. La question est donc : que jouer pour s'assurer le gain maximal ?

On va partir du bas de l'arbre, et affecter une valeur aux différents noeuds successivement. Au dernier niveau de l'arbre, c'est X qui joue. Il va donc choisir le coup qui lui amènera le meilleur score. Par exemple, il choisira la deuxième feuille parmi les trois premières, le noeud du dessus vaut donc 5, on remplit de même tous les noeuds situés juste avant des feuilles (cf dessin ci-dessous).
Au niveau précédent, c'est O qui joue, il va lui essayer d'atteindre le score le plus faible, car on a supposé que le score pour un joueur était l'inverse de celui pour l'autre joueur. Parmi les trois premiers noeuds auxquels on a affecté un score, il va donc retenir la valeur 4, qu'il va affecter à son noeud. Ici, on affiche tous les scores du point de vue de X, mais on verra que dans le programme il n'y a pas différenciation des deux joueurs : c'est symétrique, les scores sont juste inversés un niveau de profondeur sur deux. Bref, on comprend maintenant le nom de minimax : un niveau sur deux on choisit le minimum, et un niveau sur deux le maximum...
Une fois l'arbre complètement rempli en continuant sur le même principe, on peut repartir de son sommet et suivre le chemin 'optimal' en suivant toujours le même score (ici en rouge).

Je préfère tout de suite répondre à l'habituelle question du newbie : et si l'adversaire ne joue pas de manière optimale, tous nos calculs sont faux ! Bien sûr que non, on ne suivra pas le chemin 'optimal' calculé, mais on arrivera à une position plus avantageuse encore... S'il y a toujours des choses non comprises, un examen approfondi de cet exemple devrait être largement suffisant :-p

Pour terminer, voici les deux fonctions de ma macro qui servent à la réflexion : la première renvoie le numéro de colonne à jouer et est appelée directement par la procédure principale ; la seconde renvoie le score d'une position pour une profondeur et un joueur donnés, elle est appelée par la première et s'appellera elle-même récursivement. Vous pourrez avoir le détail des fonctions annexes dans le code-source de la macro, mais je crois que c'est assez explicite...

Function Reflexion() As Integer

Estimation = -INFINI

For col = 1 To NB_COLONNES

If Hauteur(col) <= NB_LIGNES Then

pion = MetPion(col, JoueurEnCours)

If FaitQuatrePionsAlignes(pion, JoueurEnCours) = True Then

Reflexion = col
Exit Function

End If

valeur = -ReflexionRecursive(-JoueurEnCours, ProfondeurMax - 1)
If valeur > Estimation Then Estimation = valeur: Reflexion = col

RetirePion col

End If

Next col

End Function



Function ReflexionRecursive(joueur, profondeur) As Integer

ReflexionRecursive = -INFINI

For col = 1 To NB_COLONNES

If Hauteur(col) <= NB_LIGNES Then

pion = MetPion(col, joueur)

If FaitQuatrePionsAlignes(pion, joueur) = True Then

ReflexionRecursive = GAGNE
RetirePion col
Exit Function

End If

If profondeur <= 0 Then

valeur = ValeurPosition(joueur)

Else

valeur = -ReflexionRecursive(-joueur, profondeur - 1)

End If

RetirePion col

If valeur > ReflexionRecursive Then ReflexionRecursive = valeur

End If

Next col

End Function

L'explication se trouve dans le code-source : à chaque appel de ReflexionRecursive(), le programme commence par jouer le coup (ex : de 2 à 3), lance la réflexion au niveau de profondeur suivant (4, 5 et 6), puis annule le coup (3 à 2) et continue avec le coup suivant (2 à 7). Chaque appel de cette fonction ne 'voit' qu'un niveau de profondeur et appelle le niveau suivant, et retourne sa valeur quand tous les niveaux inférieurs sont traités.

Reprenons maintenant notre arbre avec les valeurs des positions, sans oublier que chaque noeud est initialisé avec la valeur -INFINI.

La réflexion en est au moment où elle vient de remplacer le coefficient du noeud rouge (-INFINI) par 6. Or, on sait que X essaie de maximiser le score, donc que ce noeud aura au moins 6 comme valeur finale. De plus, comme O essaie de minimiser le score et qu'il a déjà la possibilité de jouer un coup valant 5, il ne va pas de toute évidence choisir un coup valant au minimum 6. Bref, il ne sert à rien de calculer les deux feuilles restantes à côté du 6, elles ne seront de toute manière pas retenues !

Ici, on élague deux feuilles, mais l'élagage peut concerner des pans entiers de l'arbre. Plus l'arbre est déséquilibré (certaines branches ne menant que vers de scores très hauts ou très faibles), plus l'élagage va être important, ce qui est habituel dans un jeu de réflexion (sacrifier sa dame en début de partie aux échecs risque d'entraîner une majorité de scores négatifs par exemple ; un champion d'échec se contentera lui de suivre seulement quelques lignes qui lui semblent intéressantes, un élagage énorme). Malheureusement, ce n'est pas vraiment le cas ici, donc voici au final tout ce qui aura été calculé, soit 16 feuilles et 10 noeuds au lieu de 27 feuilles et 13 noeuds :

Bref, voici les lignes à modifier réécrites :

valeur = -ReflexionRecursive(-JoueurEnCours, ProfondeurMax - 1, -Estimation)



Function ReflexionRecursive(joueur, profondeur, alpha) As Integer

valeur = -ReflexionRecursive(-joueur, profondeur - 1, -ReflexionRecursive)

If valeur > ReflexionRecursive Then

ReflexionRecursive = valeur
If ReflexionRecursive >= alpha Then Exit Function ' seule ligne ajoutée

End If


J'ajouterai trois commentaires :

• Avec une programmation un peu intelligente, il est possible d'optimiser l'élagage, par exemple en commençant par examiner les coups qui donnent statistiquement les meilleurs résultats ou qui avaient les meilleurs scores au tour précédent (peut-être pas terrible pour le Puissance 4).
  
  
• Il est aussi possible d'augmenter drastiquement le taux d'élagage en limitant les scores à {-1,0,1} : par exemple, le programme aurait rencontré en temps normal les scores de -9 et -8, il n'aurait pas élagué, là il aurait rencontré -1 et -1 et il aurait élagué (on a bien écrit If ReflexionRecursive >= alpha). On perd bien sûr toute la finesse de notre fonction d'évaluation, mais c'est intéressant en fin de partie quand on cherche juste à trouver une position gagnante, pas une position avantageuse pour gagner... Pour donner des ordres de grandeur, je redonne le nombre de 188 millions d'un début de partie pour une profondeur de 10, on descend à 89 millions avec l'élagage alpha et des scores tirés au hasard entre -1000 et 1000, et à à peine plus de 2 millions pour tous les scores entre -1 et 1. Vous avez dit drastique ?...
  
  
• Il existe bien sûr d'autres moyens de parcourir l'arbre et de l'élaguer. Par exemple, au lieu de parcourir l'arbre avec cette méthode appelée je-sais-plus-quoi, toutes les profondeurs à la fois, on peut le faire profondeur par profondeur en stockant tous les coups qui nous paraissent intéressants dans un niveau avant de passer au suivant. C'est nettement plus compliqué à programmer et on ne peut plus calculer autant de coups dans le même temps, mais ça présente plusieurs avantages : on peut élaguer beaucoup plus et assez facilement, et on peut s'arrêter au bout d'un nombre de coups ou d'un temps donné (cf défi) sans risquer de laisser une partie de l'arbre inexplorée.
  
  

• Bien sûr, augmenter l'intelligence la fonction ValeurPosition. Par exemple, deux cases vides l'une au-dessus de l'autre qui permettent toutes deux à un joueur d'aligner 4 pions forment un piège imparable si l'adversaire ne détient aucune de ces deux cases. Bref, repérer ces positions et leur donner de très forts scores.
  
  
• Accélérer le moteur pour augmenter la profondeur : par exemple, faire une première passe qui déterminera quelles sont les colonnes piégées dans lesquelles ça ne sert à rien de vouloir jouer, ce sera toujours ça de moins à calculer ("éviter les calculs inutiles"). Autre exemple, l'évaluation de deux positions proches a une majorité de calculs en commun, par exemple mettre un pion dans la première ou la deuxième colonne ne peut pas modifier les scores des cases vides à droite. S'arranger pour ne faire ces calculs qu'une seule fois ("éviter de calculer deux fois la même chose") ; à mon avis, c'est le point le plus délicat si on veut supprimer le maximum de calculs...
  
  
• Faire une fonction différente pour la fin de jeu. Ramener la fenêtre de recherche à +/-1 en examinant seulement si une position est perdante ou non comme je l'ai expliqué dans le paragraphe sur l'élagage, pour pouvoir augmenter la profondeur de recherche (en gros, remplacer le corps de ValeurPosition par ValeurPosition = 0, on se contente de dire qu'on ne sait pas ce que ça vaut). Pour les colonnes non piégées, se contenter de regarder la parité des cases vides pour savoir qui sera forcé de prendre l'initiative ensuite.