This post was published in french and cover the algorithm related to Connect 4 (Puissance 4).

Avertissement: Les mots en lettre capitale indiquent que ce sont des constantes utilisées dans le programme. BLEU indique le joueur bleu ou un pion bleu.

La programmation d’un Puissance 4 est un bon exercice et permet de voir un des algorithmes fondamentaux de la programmation à base d’IA. Je présente toutefois une solution possible non optimisé. De plus, cette solution est une adaptation orientée objet d’une ancienne application écrite en C. Il pourra s’avérer que je sois tomber à certains endroits dans les travers d’une approche fonctionnelle.

Mais bon, comme qui dirait, “ l’important, c’est que ça marche “.

But du jeu

Soit un plateau comportant LARGEUR colonne et HAUTEUR ligne. Ce plateau est à la verticale, de sorte que les pions qui sont ajoutés par tour de rôle par les joueurs (le joueur ROUGE et le joueur BLEU) descendent par effet de “gravité”. Le joueur gagnant est celui qui aligne 4 pions de sa couleur (que ce soit verticalement, horizontalement ou diagonalement)

Algorithme Mini-Max

Au Puissance 4, les joueurs ont LARGEUR possibilités, correspondant au nombre de colonnes du plateau. Il est évident que ce choix diminue quand une colonne est pleine. Ce choix peut être représenté par des branches, où la position donnée s’appelle la racine. On numérote les branches de 1 à LARGEUR, correspondant au coup qui pourra être joué.

Or l’extrémité de la branche 1 peut-être la position donnée du joueur adverse après que le joueur ais mis un pion dans la colonne 1. Ainsi, on constitue un arbre, l’arbre des possibilités, qui possède un nombre finis de niveau. Les positions extrêmes de l’arbre sont appelées de manière toujours imagée les feuilles.

Or dans un jeu comportant deux participants, et c’est le cas pour le Puissance 4, la prise en compte de l’évaluation du meilleur coup peut se faire par la méthode du Mini-Max. Supposons que l’arbre des possibilités soit examiné à une profondeur de quatre coups, cad deux coups pour chaque joueur. Dans la position donnée, c’est au tour des BLEU de jouer.

Dans cette figure, les P(1,I) sont les positions qui résultent des différents premiers coups possibles des BLEU, les P(2,I) celles des ROUGE, et ainsi de suite. Chaque branche est ainsi caractérisée par deux nombres, le niveau, et le coup parent. On évalue les positions résultantes des différents deuxièmes coups pour le camp des ROUGE (c’est à dire les feuilles de l’arbre). On suppose que l’on sait évaluer une branche correspondant à une situation donnée. Les notes sont données du point de vue des BLEU, ce qui veut dire qu’une note élevée est une position intéressante pour les BLEU. Les notes attribuées au niveau trois, cad au niveau précédant, sont dans chaque cas la valeur minimale trouvée dans l’ensemble de leurs descendants directs, car on suppose que l’adversaire joue au mieux dans ses intérêts. Par exemple, considérons un sous-arbre P(3,I) avec les valeurs des P(4,I) en dessous :

Pour arriver aux positions P(4,I), le dernier joueur était du coté des ROUGE. Comme nous supposons qu’il joue pour le mieux, il choisit le coup qui mène à la position ayant la valeur 17 (minimum pour les BLEU). La valeur de la position P(3,I) en haut de l’arbre est donc 17. Pour déduire la note de niveau deux, on remonte du niveau trois de la même manière, mais cette fois en prenant la valeur maximum des descendants directs. En effet, cette fois le coup est au BLEU, qui maximisent leurs intérêts, comme les ROUGE s’efforcent de les minimiser. Les notes se propagent de bas en haut de l’arbre, en prenant alternativement des valeurs maximum et minimum des descendants. Le meilleur coup se voit à travers ce calcul.

Limitation de la méthode

Le nombre de cas a considéré est souvent très important. Il faut mieux avoir les moyens d’éviter l’évaluation de toutes les branches : c’est l’élagage de l’arbre de décision. Voici quelques moyens :

Algorithme alpha-béta

Considérons l’arbre précédant, et en particulier le sous arbre P(2,1)

Nous avons déjà vu que le sous arbre de gauche transmet à P(3,1) la valeur 17. Mais plus à droite, l’occurrence de la valeur 16 fait que P(2,2) recevra toujours une valeur inférieure au 17 de P(2,1). On peut d’ores et déjà éliminer P(2,2) et son sous-arbre, de la suite des calculs.

L’amélioration est assez importante puisqu’elle élimine les coups de faibles intérêts. En effet, pour un niveau 6, le nombre de coups possibles est de LARGEUR^6. Si LARGEUR=8, cela fait 262 144 coups. L’effet de l’algorithme est renforcé par son application récursive aux niveaux successifs.

Méthodes heuristiques

Jusqu’ici, l’exploration de l’arbre s’est fait d’une manière systématique, ce qui n’est pas nécessairement la meilleure méthode. En particulier, le programme opère une évaluation chiffrée de la valeur des seules positions finales(les feuilles de l’arbre) Mais les programmes performants évaluent souvent les positions à chaque niveau de l’arbre, et non seulement en arrivant à la profondeur maximum. Ils ne considèrent les niveaux n+1,n+2, …sous un nœud de niveau n que si ce dernier a lui- même une bonne valeur à priori. Cette technique peut faire rater le meilleur coup, en particulier dans une situation de sacrifice tactique, mais elle permet d’explorer plus en profondeur les sous arbres intéressants.

Il est aussi intéressant, avec une évaluation à chaque niveau, de considérer les meilleures positions en premier, cad d’ordonner les recherches sur l’arbre de décision. Ceci permettant d’éliminer un maximum de branche par l’application de l’algorithme alpha-bata.

Dans le programme exemple, je n’utilise pas les optimisations détaillées plus-haut.