Puissance 4

Règles

Le but du jeu est d'aligner 4 pions sur une grille comptant 6 rangées et 7 colonnes. Chaque joueur dispose de 21 pions d'une couleur (par convention, en général jaune ou rouge). Tour à tour les deux joueurs placent un pion dans la colonne de leur choix, le pion coulisse alors jusqu'à la position la plus basse possible dans ladite colonne à la suite de quoi c'est à l'adversaire de jouer. Le vainqueur est le joueur qui réalise le premier un alignement (horizontal, vertical ou diagonal) d'au moins quatre pions de sa couleur. Si, alors que toutes les cases de la grille de jeu sont remplies, aucun des deux joueurs n'a réalisé un tel alignement, la partie est déclarée nulle.

Source

Stratégies de victoire

Il existe 3 manières de gagner au puissance 4 :

Faute d'inattention

La première correspond à une faute d'inattention de l'homme. On peut ne pas remarquer que l'adversaire a déjà 3 pions d'alignés et donc oublier de le bloquer. Cette erreur ne peut pas être reproduite par un adversaire virtuel avec intelligence artificielle, puisque les algorithmes analysent la grille à la recherche de victoire au coup suivant.

Stratégie pure

Cette victoire est provoquée par un alignement judicieux du joueur permettant d'avoir 2 cases libres avant et après un alignement de 3 pions, ou 2 alignements de 3 pions. L'adversaire ne peut alors bloquer les 2 cases gagnantes et perd la partie.

Au "finish"

Cette victoire intervient lorsque le plateau de jeu est quasiment rempli. Une ou deux colonnes sont alors bloquées par un joueur pour ne pas provoquer la victoire de son adversaire. Lorsque les autres colonnes sont remplies, les joueurs doivent remplir ces colonnes, engendrant la victoire d'un des joueurs ou un match nul.

Algorithme du jeu

Dans mon implémentation du jeu, l'intelligence artificielle cherchera toujours à placer son premier pion dans la colonne du milieu, puisque c'est la case qui permet de faire le plus d'alignements. Si cette case n'est pas libre, alors il choisit sa colonne en fonction de l'algorithme Min-Max :

Min-Max

On considère Max l'agent que l'on cherche à faire gagner et Min son adversaire. L'algorithme Min-Max à comme but l'élaboration d'une stratégie optimale pour le joueur Max. À chaque tour, le joueur Max va choisir le coup qui va maximiser son score, tout en minimisant les bénéfices de l'adversaire. Ces bénéfices sont calculés par une méthode d'évaluation qui, en fonction de l'heuristique choisie, permet de calculer le poids d'une feuille de l'arbre.
Pour des raisons de temps de calcul et de mémoire, nous limitons le nombre de coups en avant par une profondeur de l'arbre.

Alpha-Beta

L'algorithme Min-Max peut être coûteux en terme de complexité et donc en terme de temps d'exécution. La solution proposée par l'algorithme Alpha-Beta consiste donc à ne parcourir que les noeuds pertinents, et à réduire la profondeur de jeu. On parle d'élagage de l'arbre de jeu. Plus la profondeur de l'arbre est importante, plus l'intelligence artificielle sera difficile à battre.

Heuristique

L'heuristique implémenté consiste à créer un tableau de mêmes dimensions que la grille du jeu, où chaque case contient le nombre d'alignements gagnants possibles si l'on place un pion à cet endroit.
La figure suivante montre les premières étapes de la construction de ce tableau :

On obtient alors le tableau suivant :

Ainsi, pour obtenir une évaluation, nous parcourons la grille du jeu. Si le pion appartient au joueur Max, on ajoute le contenu de la case équivalente du tableau à l'évaluation. Si le pion appartient au joueur Min (le joueur adverse), on soustrait ce nombre à l'évaluation.