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

Ce programme est une ébauche de Puissance 4 puisque l’algorithme d’élagage et les méthodes heuristiques n’ont pas été implementé. De plus, l’environnement graphique est inexistant puisque c’est une application de type console. Ceci permet de nous concentrer sur la méthode.

Notes:

Le code a été testé sous Windows 98 avec Visual C++ 6.
Les relations et la structure des classes sont représentées par la notation UML. Ceci étant à titre d’essai, il peut avoir des inexactitudes.
Dans les explications, les noms possédant une majuscule designent des objets. L’Unité Logique est un objet de type CLogicUnit.

Une structure générale naturelle

Il semble au premier abord que le Puissance 4 soit assimilable en réalité à une console de jeu, style Game Boy. Il s’ensuit que le Puissance 4 a :

un clavier (keyboard) qui gère les entrées. Il capture le numéro de colonne où le joueur veut jouer, les demandes d’informations, de remise à zéro du plateau, de la mise en route de l’IA,…
une unité d’affichage (display). L’unité affiche le plateau, des informations, avertit quand un des joueurs a gagné ;
une unité logique (logic unit). Le “ cœur du Puissance 4 “ qui gère les entrées et les sorties et calcule les meilleurs coup.

Le tout est inclus dans une “ boite “ que l’on modélisera par CJeu. Bref, ceci reste classique. On obtient ainsi :

Structure Generale

Par l’intermédiaire de CKeyboard::GetKey(), l’objet Keyboard redirige les entrées claviers vers l’Unité Logique qui va traiter ces messages par des fonctions différentes :CLogicUnit:: GiveUp()si un des joueurs veut abandonner, CLogicUnit::SetIA() si un joueur veut jouer contre l’ordinateur… Les fonctions Keyboard devront être réécrites en cas de portage sous Windows, mais l’interface restera la même.

A propos de portage futur, la classe CDisplay a été dérivée pour donner des classes CDisplayTest et CDisplayWindow. CDisplay est une classe d’interface (toutes ses fonctions membres sont virtuelles). Seul dans cette version les fonctions membres de CDisplayTest ont été implantées, puisque le programme tourne uniquement en mode console.

On utilise CDisplayTest par : m_pDisplay=new CDisplayTest(this); dans le constructeur de CJeu.

On allume le jeu Puissance en appelant dans main(), CJeu::Run().

Détection des alignements

Avant de poursuivre plus en amont, il faut s’intéresser à la détection des alignements. Cette détection est essentielle puisque :

elle indique quel joueur va gagner ;
elle va conditionner la méthode d’évaluation.

Qu’est ce que l’évaluation ? C’est l’évaluation d’un plateau donné. Le plateau est constitué d’une grille qui contient des pions de couleur BLEU, ROUGE ou ne contient rien (RIEN). C’est pourquoi il faut définir une classe CPlateau. L’objet LogicUnit instancie une classe CPlateau lors de sa construction. Ce Plateau contient une Grille m_Grille[LARGEUR][HAUTEUR]. Au départ, m_Grille est initialisé à RIEN. Donc pour évaluer un Plateau possédant une grille donnée du point de vu de joueur, on déclare une fonction Evaluation : CPlateau : : Evaluation(color_joueur joueur).

Le principe de l ‘évaluation est assez simple en théorie : il faut évaluer séparément chaque alignement qu’ils soient de longueur 2, 3 ou 4 et sommer leurs scores pour obtenir le score du plateau. D’où l’idée de définir une classe alignement que l’on nommera CVecteur. Pourquoi CVecteur ? Et bien , en analogie à un … vecteur puisque un alignement peut être représenté par les données suivantes :

m_X, l’abscisse du point base
m_Y, l’ordonnée du point base
m_Longueur, la longueur du vecteur (=2,3 ou 4)
m_Dir, la direction du vecteur
couleur, la couleur du vecteur (BLEU ou ROUGE)

Chaque vecteur pointe par rapport à une direction cardinale. En prenant pour origine le point base de coordonnée (m_X, m_Y), le vecteur peut pointer dans 8 directions possibles. Mais par un mécanisme de détection des vecteurs particulière, le vecteur ne peut pointer que vers le Nord-Est (m_Dir=1), l’Est (m_Dir=2), le Sud-Est (m_Dir=3) et le Sud (m_Dir=4).

Voici un plateau représentant une sitaution donnée.

On a :

`m_X`	`m_Y`	`m_Longueur`	`m_Dir`	`Couleur`
1	1	2	4	BLEU
1	0	3	1	BLEU
2	0	2	1	ROUGE
2	0	2	2	ROUGE
3	1	2	4	ROUGE
2	2	2	3	ROUGE
7	2	2	4	ROUGE
6	0	2	2	BLEU

Ainsi, Plateau gère une liste de Vecteur par l’intermédiaire d’un conteneur séquentiel de la STL : vector. Ainsi on a :

typedef vector<CVecteur> ListVecteur;
ListVecteur* m_pListVecteur;

Ce n’est pur coïncidence que le conteneur et la classe representant un alignement portent (presque) le même nom.

valeur du Plateau=somme des valeurs des Vecteurs contenus dans le Plateau

Un objet ListVecteur est construit dans le constructeur de LogicUnit. Grâce à la fonction CPlayeau::Redetection(), on remplit la ListVecteur. Ainsi on peut détecter si un des joueurs a gagné : on cherche dans ListVecteur un vecteur dont la donnée membre m_Longueur est égale à 4. On dipose aussi de la pierre angulaire pour l’évaluation d’une situation.

Evaluation des Vecteurs

La première idée est d’attribuer un score dépendant uniquement de la longueur du vecteur. Un vecteur 3 a un meilleur score qu’un vecteur 2. Mais c’est un peu plus complexe que cela. Que penser de ces divers cas ?

Le vecteur de longueur 3 vaut 0, il n’a aucun intéret puisque le joueur ROUGE ne pourra pas gagner avec ce vecteur.

Ce vecteur de longueur 2 vaut à priori autant qu’un vecteur de longueur 3.

Et celui-çi?

Environement des Vecteurs

On s’aperçoit que la valeur d’un vecteur dépend de sa longueur et de son environnement. L’environnement d’un vecteur est variable suivant la longueur du vecteur. Pour un vecteur 2, on a :

On considère qu’il ya deux environnements (droit et gauche) chacun constitués de 4 cases. Dans le schéma précédant, on oriente le schéma suivant la direction du vecteur (voir l’utilité de m_UX et m_UY données membres de CVecteur) Cet environnement influe sur le score du vecteur.

L’environement d’un vecteur 3 est ainsi le suivant :

Chaque environement d’un Vecteur 3 est constitué de deux cases.

Pourquoi ne pas choisir des environenements plus grand ? En fait les deux environements des vecteurs définissent une zone d’extension maximum dans le cas où le vecteur se transformerait en coup gagnant (Vecteur de longueur 4). Le choix de définir une extension d’environement se situant sous les vecteurs (cases 3 et 4 pour un Vecteur 2 et case 2 pour un Vecteur 3) est motivé par le fait qu’il faut que ces cases soient remplies en partie pour que le Vecteur se transforme en coup gagnant. Je rappelle qu’un pion ne peut léviter…

Face à ces observations, on va définir une classe CEnvironementVecteur que l’on dérivera en CEnvironementVecteur2 et CEnvironementVecteur3. Un Vecteur a deux Environement, celui de droite et celui de gauche. Les données membres des Environements sont des tableaux d’entiers prenant comme valeur :

0 pour dire que la case X est vide
1 pour dire que la case X est de la même couleur que le vecteur associé
2 pour dire que la case X est de la couleur opposée au vecteur associé

Evaluation des Environenements

Chaque Environement est lié à un autre objet, il s’agit de CParametre. Un objet Parametre est une partie intégrante de l’Unité Logique. Il stocke les paramètres associés aux cases Environement.

Combien faut-il de paramètres pour carractériser un environement d’un vecteur 2 ? Il en faut 12 théoriquement. En effet, 3 paramètres (pour RIEN, COULEUR_VECTEUR, COULEUR_INVERSE_VECTEUR) pour chaque case d’environement(case 1, 2 ,3 et 4). 4*3=12! Il est clair que certaines paramètres sont inutiles, puisque attribuer un paramètre à la case 1 lorsqu’il y a COULEUR_VECTEUR ne sert à rien puisqu’on suppose que la méthode de détection marche.

Le but de la définition des classes CParametre et CEnvironement est de parvenir à évaluer les Environements des Vecteurs. Rappelez-vous que chaque vecteur a un Environement droit et un Environement gauche. Ainsi,

valeur du vecteur=valeur de son environement droit + valeur de son environement gauche

Cette dernière équation n’est pas valide dans le cas d’un Vecteur de direction 4 (il pointe alors vers le Sud). Dans ce cas, on évalura seulement un environnement constitué d’une seule case : la case qui est au dessus de l’extrémité haute du vecteur.

Je vais expliquer comment on évalue un CEnvironement2, la méthode sera la même pour un CEnvironement3 (voir le code source). Un Environement ne vaut rien si un pion adverse est dans la Case 1, donc m_Parametre[0][2]=0. Dans m_Parametre[x][y], x represente la case x+1, y=0 quand la case=RIEN, y=1 (COULEUR_VECTEUR), y=2 (COULEUR_INVERSE_VECTEUR). L’Environement 2 vaut autant qu’un Environement 3 si il y a un pion de COULEUR_VECTEUR dans la case 2 et RIEN dans la case 1. Sa valeur augmente si l’on sait que un pion pourra être mis dans une case 1 et 2, c’est à dire si il y a un pion dans les cases 3 et 4. Ainsi m_Parametre[2][1] = m_Parametre[2][2]. De même, m_Parametre[3][1] = m_Parametre[3][2]. On peut affirmer que m_Parametre[2][1] > m_Parametre[3][1].

Schéma de CEnvironement et CParametre

Ainsi par construction et en séparant des cas divers, on arrive à obtenir le score d’un Environement. Ce score pourra être modulé par l’objet Parametre, en faisant varier des coefficients. C’est dans la pratique que ces coefficients seront modifiés, mais le bon sens reste le principal facteur de choix des ces paramètres.

Synthèse

Après l’implémentation de CVecteur::GetScore(), on a :

/*====================GetScore============================================================
*BUT: donne le score d'un vecteur
*-> calcul le score de l'environement gauche (==0) puis de l'environeemnt droit (==1)
*RMQ:Pour un vecteur de direction 4, il ne faut que caluler l'environement droit
et la case 1 seulement quelque soit sa longueur
*RENVOI: le score du vecteur
==========================================================================================*/
int CVecteur::GetScore() const
{

	int score=0;
	CEnvironementVecteur* pEnvironement;
	
	
	if(m_Dir==4)
	{
		if(m_Longueur==2)	//on ne traite que des longueurs==2 ou ==3
		{
			if(Around(1,0)==RIEN)	//attention, en haut c'est le coté 0
				return m_pPlateau->GetLogicUnit()->m_Parametre[0]->GetParametre(1,0);
			else
				return 0;
		}
		if(m_Longueur==3)
		{
			if(Around(1,0)==RIEN)
				return m_pPlateau->GetLogicUnit()->m_Parametre[1]->GetParametre(1,0);
			else return 0;
		}
		return ERREUR;
	}
	else
	{	
		if(m_Longueur==2)
		{
			//on s'occupe de la partie gauche
			int prov[4];
			prov[0]=Around(1,0);
			prov[1]=Around(2,0);
			prov[2]=Around(3,0);
			prov[3]=Around(4,0);

			pEnvironement=new CEnvironementVecteur2(prov,m_pPlateau->GetLogicUnit()->m_Parametre[0]);
			score+=pEnvironement->Evaluation();

			//on s'occupe de la partie droite
			prov[0]=Around(1,1);
			prov[1]=Around(2,1);
			prov[2]=Around(3,1);
			prov[3]=Around(4,1);
		
			pEnvironement->SetEnvironement(prov);
			score+=pEnvironement->Evaluation();

		}
		else
		{
			if(m_Longueur==3)
			{
				//on s'occupe de la partie gauche
				int prov[2];
				prov[0]=Around(1,0);
				prov[1]=Around(2,0);
				
			
				
				pEnvironement=new CEnvironementVecteur3(prov,m_pPlateau->GetLogicUnit()->m_Parametre[1]);
				score+=pEnvironement->Evaluation();

				//on s'occupe de la partie droite
				prov[0]=Around(1,1);
				prov[1]=Around(2,1);
			
				pEnvironement->SetEnvironement(prov);
				score+=pEnvironement->Evaluation();

		
			}

		else
			return ERREUR;	//on ne traite pas les longueurs!=2 et !=3
		}
	}

	delete pEnvironement;	//on libere la memoire

	return score;	//on retourne le score definitif
}

Il ne reste plus qu’à sommer les vecteurs pour trouver le score d’un Plateau. Ceci donne :

/*=========================EvaluationPlateau========================================
*BUT:calcul la valeur du plateau pour le Joueur
*PARAMETRE:Joueur/indique que c'set par rapport à ce joueur qu'on calcule le score
*RETOUR: la somme des vecteurs de Joueur-la somme des vecteurs de l'adversaire
		si il y a un coup gagnat, renvoi de COUP_GAGNANT_JOUEUR ou COUP_GAGNANT_ADVERSAIRE
*======================================================================================*/
int CPlateau::EvaluationPlateau(color_joueur Joueur) const
{
	int score=0;

	//Redetection();

	for(ListVecteur::const_iterator itor=m_pListVecteur->begin();itor!=m_pListVecteur->end();itor++)
	{
		if(itor->GetLongueur()==4)
		{
			if(itor->GetColor()!=Joueur)
				return COUP_GAGNANT_ADVERSAIRE;
			else
				return COUP_GAGNANT_JOUEUR;
		}
		else
		{
			if(itor->GetColor()!=Joueur)
				score-=itor->GetScore();
			else
				score+=itor->GetScore();
		}
	}
	return score;	
}

Qu’est-ce qu’il reste à faire ? On sait évaluer un Plateau, il reste à implémenter l’algorithme du Mini-Max.

La méthode de détection dans le code source n’a été implementé que partiellement. Seul la fonction CPlateau::Redetection() est fiable, mais lente. Ceci nous donne l’organisation générale suivante :

Implémentation de l’algorithme Mini-Max

Le reste est classique et ne devrait pas poser de problème. On définit une classe CArbre à laquelle on associe un membre Plataeu qui est l’exacte réplique du Plateau qui sera la situation “racine” (voir l’algorithme du Puissance 4).

On calcule le meilleur coup par une fonction récurrente.

/*================================Branche===========================================
*BUT:calcul par une méthode de récurrence le score des niveaux de l'arbre
*PARAMETRE:color/le joueur qui va jouer le coup

		color
	/  /  |  \  \
	      
          niveau/le niveau de la branche par rapport à l'arbre. La racine de l'arbre est 0
		  m_Buffer/un tableau stockant les scores des branches.
->Pour notre branche,m_Buffer[niveau][X], X position de la branche par rapport à la branche parent.
->Notre branche est le resultat de l'ajout du pion dans la colonne X
		  compteur/les compteurs pour évoluer dans l'arbre X=compteur[niveau]

*RMQ:Pas d'implementation alpha-béta
==========================================================================================*/
void CArbre::Branche(color_joueur color, int niveau,int (*m_Buffer)[LARGEUR],int* compteur)
{
	if(niveau==m_Niveau-1)
	{
		for(compteur[niveau+1]=0;compteur[niveau+1]<LARGEUR;compteur[niveau+1]++)
		{
			if(m_pPlateauProv->AjoutPion(compteur[niveau+1],color)!=ERREUR)
			{
				m_Buffer[niveau+1][compteur[niveau+1]]=m_pPlateauProv->EvaluationPlateau(m_EvaluationForPlayer);
				m_pPlateauProv->EnlevePion(compteur[niveau+1]);
			}
			else 
				m_Buffer[niveau][compteur[niveau]]=REMPLI;

		}
		
		if(color==m_EvaluationForPlayer)	//##
		{
			m_Buffer[niveau][compteur[niveau]]=Max(m_Buffer[niveau+1]);
		}
		else
		{
			m_Buffer[niveau][compteur[niveau]]=Min(m_Buffer[niveau+1]);
		}
	}
	else
	{
		for(compteur[niveau+1]=0;compteur[niveau+1]<LARGEUR;compteur[niveau+1]++)
		{
			if(m_pPlateauProv->AjoutPion(compteur[niveau+1],color)!=ERREUR)
			{
				if(m_pPlateauProv->Puissance4())
				{
					m_Buffer[niveau+1][compteur[niveau+1]]=CoupGagnant(color);
					break;
				}
				else
				{
					Branche(GetInversePion(color),niveau+1,m_Buffer,compteur);
				}
			}
			else
			{
				m_Buffer[niveau+1][compteur[niveau+1]]=REMPLI;
				break;
			}


			m_pPlateauProv->EnlevePion(compteur[niveau+1]);

			if(color!=m_EvaluationForPlayer)	//##
			{
				m_Buffer[niveau][compteur[niveau]]=Max(m_Buffer[niveau+1]);
			}
			else
			{
				m_Buffer[niveau][compteur[niveau]]=Min(m_Buffer[niveau+1]);
			}
		}
	}
}