1. Introduction▲
Bienvenue à cette nouvelle partie sur la programmation d'un morpion. Nous allons introduire une intelligence artificielle (dans le reste de l'article, j'utiliserais aussi IA) pour pouvoir jouer contre un ordinateur. Bien sûr, pour aller encore plus loin, on va définir trois niveaux de difficulté pour l'IA et on va permettre à l'utilisateur de choisir s'il y a un ou deux ordinateurs.
L'algorithme le plus connu pour implémenter une intelligence artificielle pour ce type de jeu est appelé Min-Max. Nous allons présenter cet algorithme.
2. Généralités▲
2-1. L'algorithme Min-Max▲
Lorsque nous regardons le déroulement d'une partie, cela peut être vu comme l'élaboration d'un arbre de possibilités.
Lorsque l'ordinateur doit choisir son prochain coup, il parcourt toutes les différentes possibilités et choisira la meilleure possibilité. Bien sûr, comment fait-il pour décider? Si l'ordinateur a une technique pour évaluer une configuration, il peut parcourir toutes les possibilités et choisir la meilleure solution.
2-1-1. Décision avec une profondeur 1▲
Lorsque l'IA doit décider son prochain coup, il parcourt les différentes possibilités. Si nous limitions la recherche à une profondeur de 1, cela veut dire que l'ordinateur va donc se restreindre à regarder le prochain coup.
L'image suivante montre comment l'ordinateur va choisir le prochain coup. En haut se trouve l'état courant du jeu et je l'appelle aussi la configuration courante.
L'IA va regarder tous les coups possibles et va choisir le meilleur (nous supposons donc que l'ordinateur joue les ronds). Regardons maintenant comment on peut évaluer les configurations du jeu.
2-1-2. Fonction d'évaluation▲
Nous avons, jusqu'ici, passé sous silence comment évaluer une partie et nous verrons que c'est un des plus grands soucis de cet algorithme. Une mauvaise évaluation et l'ordinateur fera des mauvais choix. Une évaluation trop compliquée rendra l'algorithme trop complexe et trop lent.
Nous avons vu comment fonctionne une IA qui regarde seulement le prochain coup. Mais, vous vous doutez que dans le cas général, il sera plus intéressant de pouvoir regarder plusieurs coups à l'avance. Mais comment parcourir correctement l'arbre et comment choisir entre les différents coups possibles ?
Nous avons déjà parlé de fonction d'évaluation. Supposons que nous avons une fonction evalue qui regarde un plateau de morpion et en donne un score. Par convention, on suppose qu'un entier peut parfaitement représenter une évaluation d'un jeu.
Dans le cas général, la fonction peut retourner n'importe quelle valeur entière. On suppose que 0 représente une impression d'égalité par la fonction, une valeur négative signifie que la fonction a une impression que l'ordinateur est en train de perdre et une valeur positive signifie que la fonction a une impression que l'ordinateur est en train de gagner.
Nous verrons dans la suite de ce tutoriel comment programmer correctement cette fonction. À présent, regardons comment l'IA va parcourir les configurations possibles avec une profondeur 2.
2-1-3. Décision avec une profondeur 2▲
L'image suivante montre les possibilités avec une profondeur 2. À présent, l'ordinateur aura la connaissance des deux prochains coups pour faire son choix. Déjà, nous remarquons que si l'IA choisit le coup de droite, nous pourrons gagner la partie en jouant ensuite le coup de gauche (on aura donc trois X au milieu du morpion).
C'est donc nécessaire que l'IA puisse voir qu'il ne faut pas aller vers la droite. D'ailleurs, vous remarquerez que si l'IA joue n'importe quel autre coup que celui de gauche, nous pourrons gagner la partie.
Pour résoudre ce problème, nous savons que nous devons utiliser la fonction d'évaluation. Comme évaluation basique nous allons définir :
- évaluation(jeu) = 1000 si l'IA a gagné ;
- évaluation(jeu) = -1000 si l'IA a perdu ;
- évaluation(jeu) = 0 sinon.
Donc si nous utilisons l'évaluation, la dernière image deviendra :
La fonction d'évaluation nous donne une valeur pour chaque configuration du jeu. Mais quelle valeur faut-il donner des nœuds de profondeur 1 ?
La solution est extrêmement logique. Les nœuds de profondeur 1 représentent les choix que ferait l'adversaire de l'ordinateur (généralement un humain, mais cela pourrait être un autre ordinateur, c'est pour cela que je ferai référence d'adversaire). Bien sûr, l'IA va supposer que l'adversaire va choisir le meilleur coup possible. Donc pour chaque nœud qui représente le choix de l'adversaire, le coup qu'il choisirait devrait mettre l'IA dans la plus grande difficulté (donc devrait avoir le score le plus petit).
Donc en supposant cela, il est logique que la valeur des nœuds de profondeur 1 soit égale au minimum des valeurs de ses fils. On obtient donc :
Donc pour terminer, l'IA aura comme choix le coup de gauche qui mènera vers une évaluation de 0 ou le coup de droite qui mène vers une évaluation de -1000. Si vous avez bien suivi, l'IA va bien sûr devoir choisir le coup de gauche. La valeur de ce nœud est donc le maximum de ses fils. Voici ce que cela donne :
2-1-4. Généralisation▲
Je pense que la section précédente a été bénéfique pour bien illustrer le fonctionnement de l'algorithme du Min-Max. Finalement, l'idée est de parcourir un arbre de configurations. Lorsqu'on arrive à une feuille de l'arbre, on utilise la fonction d'évaluation pour donner une valeur à la configuration.
Ensuite, pour les nœuds qui ne sont pas des feuilles. On utilise soit le minimum des valeurs des fils si le nœud représente le choix de l'adversaire (c'est donc un nœud Min), soit le maximum des valeurs des fils si le nœud représente le choix de l'IA (c'est donc un nœud Max).
2-2. L'algorithme▲
2-2-1. Présentation▲
Une première version de l'algorithme de l'évaluation de la valeur d'un nœud de l'arbre peut donc être donnée par :
- Si c'est une feuille, utiliser la fonction eval;
- Si c'est un noeud Max, la valeur sera le maximum des fils;
- Sinon, c'est un noeud Min, la valeur sera le minimum des fils.On peut rendre cet algorithme plus proche d'un langage de programmation en écrivant ceci :
Fonction calculValeurNoeud(Noeud n)
{
Si n est une feuille alors
retourner eval(n);
Sinon
Si c'est un noeud max alors
retourner le maximum des évaluations des fils du noeud
sinon
retourner le minimum des évaluations des fils du noeud
Fin Si
}On remarque tout de suite l'aspect récursif de cet algorithme. Ceci est encore une version simplifiée puisque nous devons gérer les cas d'une partie terminée. À présent, nous allons présenter la nouvelle version de l'algorithme. Cet algorithme va se diviser en trois fonctions : calcIA, calcMin et calcMax.
Voici la fonction calcIA :
Fonction calculIA(Jeu *j, int prof)
{
Soit maxcourant = MINIMUM;
Pour chaque coup possible
Faire
Jouer le coup
max = calcMax(j, prof-1);
Si max > maxcourant alors
maxcourant = max;
FinSi
Annuler le coup
FinPour
Jouer le coup qui a eu le score maximum
}Vous remarquerez que cette dernière version de l'algorithme commence à ressembler de plus en plus à un code C++. En effet, dans l'algorithme, nous avons réintroduit la classe Jeu et nous avons mis en place l'utilisation d'une profondeur. Et nous avons introduit la valeur MINIMUM qui sera définie comme la minoration stricte de la fonction d'évaluation.
La fonction d'entrée calcIA est assez simple : on regarde tous les coups possibles et on appelle la fonction calcMax. Cette fonction calcule l'évaluation d'un nœud de type Max. Voici son algorithme :
Fonction calcMax(Jeu *j, int prof)
{
Soit max = MINIMUM;
Si la partie est terminée ou si la profondeur == 0 alors
retourner eval(n);
Sinon
Pour chaque coup possible
Faire
Jouer le coup
tmp = calcMin(j, prof-1);
Si tmp > max alors
max = tmp;
FinSi
Annuler le coup
FinPour
Retourner max;
}Cette fonction ressemble beaucoup à la précédente. La seule différence est ce qu'on fait du maximum après le parcours. Dans la fonction calcIA, on joue le coup, mais, dans la fonction calcMax, on retourne le maximum. La fonction calcMin est exactement la même sauf qu'on définit une valeur MAXIMUM et qu'on cherche un minimum à la place.
2-2-2. Discussion du choix de la profondeur▲
Le deuxième paramètre de l'algorithme Min-Max est la profondeur du parcours. En effet, nous avons parlé de profondeur 1 et 2, mais nous pouvons généraliser à une profondeur n.
Mais il y a un aspect de l'algorithme qu'il ne faut pas oublier: la complexité. En effet, la fonction d'évaluation peut être suffisamment compliquée que le simple nombre d'appels suffirait à rendre l'algorithme inutilisable. Prenons le simple jeu du morpion, si on calcule la taille de l'arbre, on obtient 9! nœuds (ce qui est égal à 362 880).
Il n'y a pas de bonne réponse à la profondeur du parcours qu'il faudrait utiliser. Généralement, il faut utiliser la plus grande profondeur possible sans pour autant faire attendre le joueur 1h pour un coup de morpion.
Dans cette version du morpion, nous allons définir trois niveaux de difficulté de l'IA. En fait, ce sera la profondeur qui va être la définition de l'intelligence. Une profondeur 3 sera la difficulté Facile, 5 sera Moyen et 9 sera Difficile.
2-2-3. La fonction évaluation▲
Nous avons montré l'importance de la fonction d'évaluation. Si cette fonction est mal établie, alors l'IA ne va pas jouer correctement. Pour beaucoup de jeux, cette fonction sera très difficile à mettre en place. Heureusement, pour le morpion, c'est assez simple.
Une possibilité (et celle que j'utilise ici) pour le morpion est cette évaluation :
Si la partie est terminée alors
Si c'est une égalité, alors on retourne 0
Sinon
Si l'ordinateur a gagné, alors retourne 1000 (le maximum possible);
Sinon l'ordinateur a perdu, alors retourne -1000 (le minimum possible);
Fin Si
Fin Si
Sinon
Soit la somme = 0
Pour chaque ligne, chaque colonne, chaque diagonale,
S'il y a au moins un pion de chaque joueur, on ne fait rien
Sinon
S'il y a 2 pions de l'adversaire, on enlève 30 à somme
sinon s'il y a 2 pions du joueur de l'IA, on ajoute 30 à somme
sinon s'il y a 1 pion de l'adversaire, on enlève 10 à somme
sinon s'il y a 1 pion de l'IA, on ajoute 10 à somme
Fin Si
Fin Si
Fin Pour
Fin SiOn voit que si la partie est terminée, on retourne -1000, 0 et 1000 si la partie est respectivement perdue pour l'IA, une égalité ou gagnée pour l'IA. Ceux-ci sont les valeurs de références pour cette évaluation, ensuite on introduira des nuances.
Donc si la partie est bien partie, l'évaluation sera positive. Si l'IA est en train de perdre, l'évaluation sera donc négative. L'IA va donc tenter d'aller vers les configurations qui ont une évaluation positive et l'algorithme va supposer que son adversaire va vouloir aller vers les évaluations négatives.
3. La classe IA▲
Nous allons voir à présent comment nous allons implémenter la classe IA.
3-1. IA.h▲
La classe IA possède seulement un membre : joueurCourant. Cet élément représente le type de l'IA pour pouvoir calibrer correctement la fonction d'évaluation. En effet, si l'IA joue rond et que les ronds gagnent, alors la fonction devrait rendre 1000. Par contre, si le type de l'IA est croix, mais c'est toujours les ronds qui gagnent alors on devrait obtenir -1000. C'est à cela que servira ce membre de la classe.
De plus, nous verrons que nous pouvons avoir deux IA qui jouent l'un contre l'autre. L'utilisation de ce membre permet de savoir pendant le parcours quel est le type de l'IA qui doit jouer (rond ou croix).
const int MINEVAL=-100000;
const int MAXEVAL=100000;
//Classe qui gère l'intelligence artificielle
class IA
{
private:
Case joueurCourant;
public:
IA();
~IA();
//Fonction qui calcule le prochain coup
void calcIA(Jeu *j, int prof);
//Fonctions pour le calcul
int calcMin(Jeu *j, int prof);
int calcMax(Jeu *j, int prof);
//Fonction qui évalue le jeu
int calcScore(int, int);
int evalue(Jeu *j);
int comptePions(Jeu *j);
};Les fonctions membres se divisent en deux groupes :
- L'évaluation à travers la fonction evalue qui retournera un entier et les fonctions comptePions, calcScore serviront pour ce calcul ;
- Le parcours de l'arbre de configurations qui se fait avec les fonctions calcIA, calcMin et calcMax.
Nous allons maintenant pouvoir voir l'implémentation de cette classe.
3-2. IA.cpp▲
3-2-1. La fonction calcScore▲
Commençons cette sous-section par la présentation du calcul d'évaluation. Pour évaluer une configuration, le programme va regarder le nombre de pions et le nombre de pions de l'IA moins le nombre de pions de l'adversaire pour chaque horizontale, verticale et diagonale. Grâce à ces deux compteurs, nous pourrons définir ce qu'il faut pour calculer la participation à la somme de l'évaluation. Voici le code qui retourne cette participation :
int IA::calcScore(int cntpion, int cntjoueur)
{
//On regarde le nombre de pions
switch(cntpion)
{
case 1:
return 10*cntjoueur;
case 2:
return 30*cntjoueur;
default:
return 0;
}
}3-2-2. La fonction evalue▲
Mais il faut maintenant calculer ces deux compteurs pour chaque horizontal, chaque vertical et chaque diagonale. Le code de la fonction evalue est divisé en deux parties. Tout d'abord on regarde si le jeu est fini. Si c'est le cas, on retourne 1000 si l'IA a gagné, -1000 s'il a perdu et 0 sinon.
//Si le jeu est fini
if(jeu->getFini())
{
//Si l'IA a gagné, on retourne 1000 - le nombre de pions
if(jeu->getTypeGagne() == joueurCourant)
{
return 1000-comptePions(jeu);
}
else if(jeu->getTypeGagne() == Vide)
{
//Egalite -> on retourne 0
return 0;
}
else
{
//Si l'IA a perdu, on retourne -1000 + le nombre de pions
return -1000+comptePions(jeu);
}
}
//On ajoute au score cette nouvelle participation
score += calcScore(cntpion,cntjoueur);Dans l'implémentation finale, j'ai rajouté quelque chose lorsqu'il a une défaite ou une victoire. En effet, il y a cette histoire de nombre de pions que j'ajoute (ou retire) à -1000 (ou 1000).
La raison de cet ajout est très simple à comprendre. S'il l'IA regarde avec une profondeur de 5 et qu'il y a deux victoires : une à la profondeur 1 et l'autre à la profondeur 5. Je préfère que l'IA aille pour la victoire directe au lieu de faire durer le plaisir. Rendre 1000 - nombre de pions permet de dire que dans le premier cas on aurait le score 999 et dans l'autre case 995. Donc l'IA favorisera bien la victoire directe.
Pour la défaite, on fait l'inverse. Si c'est sûr qu'on va perdre, on va aller vers la défaite la plus lointaine puisqu'il est tout de même possible que l'adversaire fasse une erreur.
La suite de la fonction evalue est le parcours des diagonales, des verticales et des horizontales. Nous allons montrer le code pour une diagonale, mais sachez que c'est la même chose pour les autres alignements potentiels.
//On regarde chaque case
for(i=0;i<3; i++)
{
//Si la case n'est pas vide
if(!jeu->estVide(i,i))
{
//On incrémente d'un pion
cntpion++;
//Si c'est le même type du joueur courant
if(jeu->getCase(i,i)==joueurCourant)
//On incrémente le compteur
cntjoueur++;
else
//On décrémente le compteur
cntjoueur--;
}
}Donc ce code regarde si la case est vide. Si ce n'est pas le cas, on incrémente le nombre de pions de cet alignement. Ensuite, on regarde si la case est occupée par un pion de l'IA ou de l'adversaire. Si c'est de l'IA, on incrémente cntjoueur, sinon on le décrémente. Finalement, cela revient à avoir comme possibilités pour les couples (nombre de pions, compteur du nombre des pions IA moins le nombre de pions de l'adversaire) :
- (0,0) -> aucun pion ;
- (1,1) -> un seul pion, et c'est le pion de l'IA (c'est une bonne chose, il y a une possibilité lointaine de gagner) ;
- (1,-1) -> un seul pion, mais c'est le pion de l'adversaire ;
- (2,-2) -> deux pions et c'est deux pions de l'adversaire (vraiment pas bon, il pourrait gagner) ;
- (2,0) -> deux pions, mais un de chaque type, ceci ne mènera qu'à une égalité pour cet alignement ;
- (2,2) -> deux pions et deux de l'IA (bonne chose, l'IA peut bientôt gagner).
Je pense que si vous regardez de nouveau la définition de la fonction calcScore, vous allez arriver à comprendre mieux son fonctionnement.
3-3. L'algorithme du Min-Max▲
Il faut, encore une fois de plus, compléter l'algorithme du Min-Max pour ce programme. Je vais maintenant passer directement à l'explication du code. L'implémentation du Min-Max est divisée en trois parties : la fonction qui permet de choisir entre les différents coups possibles, la fonction qui gère le choix des nœuds Max et celle qui gère le choix des nœuds Min.
3-3-1. La fonction calcIA▲
La fonction calcIA est le point d'entrée du programme qui choisira le prochain coup pour l'ordinateur. L'algorithme de la fonction peut se résumer en quelques phrases. On va parcourir toutes les possibilités de la configuration courante et calculer l'évaluation de l'IA pour chaque case. En prenant le maximum, on va donc avoir le meilleur choix que nous donne l'évaluation.
La seule chose dont on a n'a pas encore discuté est la technique utilisée pour parcourir les possibilités et surtout pour effectuer le parcours de l'arbre de configurations. La solution la plus simple est de simuler qu'on joue la partie et annuler les coups lorsqu'on veut tenter autre chose.
Le problème c'est qu'annuler un coup n'est pas toujours évident. Si ce n'est pas possible, une alternative est de copier la configuration, jouer le coup et ensuite on libère la mémoire.
Puisqu'on est en train de programmer un morpion, annuler un coup est facile. Mais pour un reversi, il serait probablement préférable de passer par des copies.
void IA::calcIA(Jeu *jeu, int prof)
{
int i,j,tmp;
int max = MINEVAL;
int maxi=-1,maxj=-1;
//On met en place le joueur courant
joueurCourant = jeu->getTour();
//Si la profondeur est nulle ou la partie est finie,
//on ne fait pas le calcul
if((prof!=0)||(!jeu->getFini()))
{
//On parcourt les cases du morpion
for(i=0;i<3; i++)
for(j=0;j<3;j++)
{
//Si la case est vide
if(jeu->estVide(i,j))
{
//On simule qu'on joue cette case
jeu->joue(i,j);
//On appelle la fonction calcMin pour lancer l'IA
tmp = calcMin(jeu, prof-1);
//Si ce score est plus grand
if((tmp>max)||((tmp==max)&&(Rand::randi(2))))
{
//On le choisit
max = tmp;
maxi = i;
maxj = j;
}
//On annule le coup
jeu->annuleCoup(i,j);
}
}
}
//On jouera le coup maximal
jeu->joue(maxi,maxj);
}Lorsqu'on regarde le fonctionnement de cette fonction, on remarque qu'on parcourt les cases du morpion. Si une case est vide, on joue la case. Ensuite, on regarde quel serait le score de cette configuration. Puisque c'est un nœud Min (en effet, vu que, maintenant, c'est le tour de l'adversaire, celui-ci va essayer de minimiser l'évaluation).
Ensuite, lorsqu'on a la valeur du nœud, on le compare avec le maximum courant. Ce maximum est initialisé à une valeur qui minore strictement la fonction d'évaluation.
Remarquez que le choix d'un coup se fait donc grâce à ce test :
//Si ce score est plus grand
if((tmp>max)||((tmp==max)&&(Rand::randi(2))))À quoi sert le ou logique? Si jamais l'évaluation obtenue est égale au maximum courant, on utilise un générateur aléatoire pour aider à choisir entre les deux possibilités. Nous ne cherchons pas à faire un générateur parfait, encore moins un équiprobable. Pour ce jeu, nous souhaitons simplement que l'IA ne semble pas jouer tout le temps les mêmes coups.
Une fois que l'algorithme a choisi le meilleur coup possible, il le joue avant de rendre la main.
3-3-2. La fonction calcMin▲
Pour qu'il n'y ait pas de jaloux, et parce que le code est assez simple, nous allons présenter la fonction calcMin puisque nous avons présenté l'algorithme pour la fonction calcMax.
Cette fonction gère le calcul de la valeur d'un nœud de type Min. Ce code ressemble énormément à la fonction calcMax. Voici son code :
int IA::calcMin(Jeu *jeu, int prof)
{
int i,j,tmp;
int min = MAXEVAL;
//Si on est à la profondeur voulue, on retourne l'évaluation
if(prof==0)
return evalue(jeu);
//Si la partie est finie, on retourne l'évaluation de jeu
if(jeu->getFini())
return evalue(jeu);
//On parcourt le plateau de jeu et on le joue si la case est vide
for(i=0;i<3; i++)
for(j=0;j<3;j++)
{
if(jeu->estVide(i,j))
{
//On joue le coup
jeu->joue(i,j);
tmp = calcMax(jeu, prof-1);
if(tmp<min)
{
min = tmp;
}
//On annule le coup
jeu->annuleCoup(i,j);
}
}
return min;
}Comme vous le voyez, le code de la fonction calcMin ressemble étrangement à celui de calcIA.
4. La classe Jeu▲
Le reste de cette partie sera très rapide vu qu'il n'y a presque pas de changements. En effet, il y a simplement quelques ajouts du côté de la classe Jeu pour permettre à l'algorithme d'IA de faire son travail. Voici une présentation des modifications.
4-1. Le fichier Jeu.h▲
Afin d'avoir la possibilité de modifier le type de joueur des ronds et des croix, il nous faut définir une énumération prenant tous les types possibles.
enum TypeJoueur {Humain, Facile, Moyen, Difficile};Remarquez qu'on ne définit pas directement ici ce que veut dire Facile, Moyen ou Difficile. Ce sera le moteur du jeu qui s'en chargera directement (vu que c'est lui qui aura le contrôle de l'IA).
Ensuite, nous allons avoir deux nouveaux membres de la classe Jeu : le type de chaque joueur.
//Type des joueurs (humain/ordi)
TypeJoueur j1, j2;Pour que l'IA puisse bien fonctionner, l'IA doit avoir une certaine maîtrise du jeu sous-jacent. Effectivement, on a surtout besoin de fonctions qui sondent le jeu et récupère l'état du jeu (qui a gagné ? est-ce que la case (i,j) est vide ?).
//Fonction qui retourne le joueur courant
Case getTour();
//Fonction qui retourne qui a gagné
Case getTypeGagne();
//Fonction qui retourne le type de la case
Case getCase(int i, int j);
//Fonction qui retourne si le joueur courant est un humain
bool estHumain();
//Fonction qui retourne le type du joueur courant
TypeJoueur getTypeJoueur();
//Fonction qui retourne l'état de la case
bool estVide(int i, int j);
//Fonction qui joue la case (i,j)
void joue(int i,int j);
//Fonction qui annule le dernier coup
void annuleCoup(int a, int b);
//Fonction qui met en place le type des joueurs
void setTypeJoueur(int i, int type);Je pense que les noms sont assez évocateurs pour ne pas devoir expliquer plus.
4-2. Le fichier Jeu.cpp▲
Bien qu'il y ait 9 nouvelles fonctions à cette classe, elles sont toutes extrêmement simples donc je ne vais pas allonger inutilement cet article (qui est déjà suffisamment long !). En effet, pour bien faire, je dois encore présenter la classe Menu et la classe Rand.
5. La classe Menu▲
Dans la classe Menu, nous allons ajouter une possibilité de choisir le type des joueurs. Une image sera sûrement bénéfique.
Nous allons donc ajouter deux zones textes comme le titre (donc des zones où l'on ne peut pas cliquer) et deux boutons comme le bouton nouveau (pour gérer le type de chaque joueur).
Cette partie va donc présenter l'ajout de ces éléments et comment on les intègre au jeu.
5-1. L'ajout des membres▲
Pour gérer correctement ces nouveaux éléments du menu, nous avons simplement à ajouter les variables SLD_Rect pour les positions et les SDL_Surface pour les nouvelles images.
//Informations pour le type de joueur
//Positions et surfaces du texte des joueurs
SDL_Rect postxtj1, postxtj2;
SDL_Surface* txtj[2];
//Positions et surfaces des types des joueurs
SDL_Rect postypej1, postypej2;
SDL_Surface* typejoueur[4];
//Type des joueurs
int typej1, typej2;Nous avons donc les positions et les surfaces des textes Joueur 1 et Joueur 2. Ensuite, nous définissons les positions et surfaces pour le type des joueurs (il y aura Humain, Facile, Moyen et Difficile).
Enfin, nous définissons le type des joueurs 1 et 2. Ces deux variables typej1 et typej2 vont servir pour savoir quelle surface dessiner du tableau typejoueur.
5-2. Les implications▲
Puisque déjà beaucoup de choses ont déjà été mises en place pour afficher le menu. Ajouter ces éléments ne demande pas beaucoup de changements.
5-2-1. Les changements des fonctions existantes▲
Si on regarde toutes les fonctions existantes de cette classe, il y a seulement quelques ajouts pour initialiser, détruire, gérer les clics et afficher ces nouveaux éléments. Nous n'allons pas montrer tout le nouveau code pour deux grandes raisons : cette partie est déjà assez longue et les ajouts ne présentent pas d'intérêt. En effet, si vous avez compris le code de la partie précédente, il n'y aura pas de surprises ici.
5-2-2. L'affichage et la gestion du clic▲
Regardons d'abord comment nous affichons ces nouveaux éléments. Il suffit d'ajouter ceci :
SDL_BlitSurface(txtj[0],NULL,screen,&postxtj1);
SDL_BlitSurface(txtj[1],NULL,screen,&postxtj2);
SDL_BlitSurface(typejoueur[typej1],NULL,screen,&postypej1);
SDL_BlitSurface(typejoueur[typej2],NULL,screen,&postypej2);La seule chose à noter est l'utilisation des valeurs typej1 et typej2 pour afficher la bonne surface pour le type de chaque joueur. Donc en changeant cette valeur, l'affichage est directement mis à jour.
Pour modifier le type des joueurs, l'utilisateur doit cliquer sur la surface en question. Voici comment on gère le clic :
//Est-ce qu'on est dans le bouton type joueur1?
else if((postypej1.x<x)&&(postypej1.x+typejoueur[typej1]->w>x)&&(postypej1.y<y)&&(postypej1.y+typejoueur[typej1]->h>y))
{
typej1= (typej1+1)%4;
}
//Est-ce qu'on est dans le bouton type joueur2?
else if((postypej2.x<x)&&(postypej2.x+typejoueur[typej2]->w>x)&&(postypej2.y<y)&&(postypej2.y+typejoueur[typej2]->h>y))
{
typej2= (typej2+1)%4;
}Puisque le tableau typejoueur possède quatre éléments, les indices vont de 0 à 3. Pour cycler à travers les types, on incrémente la valeur courante. Bien sûr, lorsque la valeur vaut 4, il faut revenir à 0 donc on utilise un modulo.
5-2-3. L'ajout de getType▲
Nous allons tout de même ajouter une fonction à cette classe. En effet, lorsqu'on modifie le type d'un joueur, on peut passer par le moteur pour mettre à jour le type du joueur dans la classe Jeu. Rappelons que nous avons à présent une redondance dans les données.
//Fonction retourne le type des joueurs
int Menu::getType(int i)
{
if(i==1)
return typej1;
else
return typej2;
}Effectivement, le type des joueurs se trouve dans la classe Menu et dans la class Jeu. Ceci est dû au fait que ces classes doivent passer par le moteur pour se parler. Il est donc plus facile à faire une petite redondance. Par contre, si nous avions plus de valeurs, il serait préférable de mettre en place un autre système.
Pourquoi éviter les redondances ? Il faut éviter les redondances dans un code à cause des risques d'incohérences. Gardez comme règle générale qu'il faut mieux les éviter.
Ici, nous allons laisser le moteur décider le moment de mettre à jour le type des joueurs. Je présente cette solution, plutôt que de laisser le menu mettre directement l'instance du jeu à jour, parce que je trouve que celle-ci a plusieurs avantages :
- la simple modification d'un paramètre du jeu peut engendrer beaucoup de calculs ou de modifications de l'état du jeu, il est donc préférable d'attendre le dernier moment avant de mettre à jour la valeur ;
- si c'est le moteur qui gère les mises à jour, le menu n'a pas besoin de savoir qui a besoin de savoir qu'il y a eu un changement dans les paramètres ;
- enfin, si on modifie plusieurs fois le type sans retourner dans le jeu, il n'est sûrement pas nécessaire de mettre à jour tout de suite les valeurs qui ont changé.
6. La classe Rand et son intérêt▲
J'ai parlé de l'utilisation d'un générateur de nombres aléatoires dans ce tutoriel. Logiquement, il nous faut une classe qui l'implémentera.
6-1. L'intérêt▲
Pourquoi centraliser le générateur de nombres aléatoires ?
La difficulté d'un tel générateur est de le rendre le plus aléatoire possible. Centraliser ce code permet de commencer avec un générateur naïf et, comme d'habitude, si nous voulons avoir un meilleur générateur, il suffira de le changer.
Le reste du code n'a pas besoin de savoir comment le générateur de nombres aléatoires est implémenté.
6-2. L'implémentation▲
L'implémentation de ce générateur de nombres aléatoires est assez simple. Nous commencerons par définir la variable statique cnt. Cette variable va servir pour compter le nombre de fois qu'on appelle le générateur.
Lorsque ce générateur sera appelé un certain nombre de fois, on remet le générateur à zéro. Ceci se fait à travers la fonction newSeed.
//Mis en place du compteur
int Rand::cnt=0;
//Vérification du compteur
void Rand::checkSeed()
{
//Si on a trop appelé le générateur de nombres, on remet le tout à zéro
if((!cnt)||(cnt>10000))
{
srand(time(NULL));
cnt=0;
}
}
//Générer une nouvelle séquence...
void Rand::newSeed(int s)
{
srand(s);
}
//Générer un nombre aléatoire
int Rand::randi()
{
checkSeed();
return rand();
}
//Générer un nombre aléatoire entre [0,max-1]
int Rand::randi(int max)
{
checkSeed();
if(max)
return rand()%max;
return 0;
}Finalement, ce code n'a rien de particulier. On utilise la fonction rand, ce qui nous permet d'avoir un générateur correct. Remarquez qu'au début de chaque fonction on appelle checkSeed. Ceci permet de refaire automatiquement une sélection du nombre de générations.
7. Conclusion▲
Encore une partie bien longue parce qu'avant de parler d'implémentation, il a fallu présenter la théorie et les idées de base. Une fois cette théorie en place, les spécificités du morpion ont ajouté quelques détails lors de l'implémentation.
De plus, pour faire une bonne implémentation d'une intelligence artificielle, il a fallu implémenter un générateur de nombres aléatoires.
Enfin, pour des jeux de plateau où il y a des tours et des coups à jouer, l'algorithme du Min-Max s'implémente facilement. En effet, il faut parcourir toutes les configurations possibles et après, ce n'est qu'un parcours d'un arbre de configurations.
Dans la prochaine partie, nous verrons comment améliorer cet algorithme en limitant le nombre de configurations qui sont nécessaires pour calculer le prochain coup.
Jc
Liens
- Sommaire du tutoriel
- Ouvrir une fenêtre SDL
- Lier la souris à la fenêtre et afficher des ronds à l'endroit cliqué
- Ajouter les règles du jeu et le finaliser
- Ajouter les classes Objet et Moteur pour rendre le jeu plus souple
- Ajouter un menu dans un jeu
- Ajouter une Intelligence Artificielle (Min-Max)
- Ajouter une Intelligence Artificielle (Alpha-Beta)
8. Téléchargements▲
Voici le code source de ce tutoriel : zip (1.2 Mo)