Alors pour commencer cet algorithme ne fonctionne que dans certains cas : à chaque coup il existe un nombre fini de coup à jouer (un nombre pas trop gros de préférence, c’est le problème du Go), le jeu contient également un nombre limité de coup. L’algorithme va établir tous les états (coups) possibles en jouant un coup (niveau 1 de profondeur, premier demi-coup), puis à partir de son coup, il va établir toutes les positions possibles que l’adversaire puisse faire (niveau 2 de profondeur, deuxième demi-coup), et ainsi de suite jusqu’au niveau n. Ce qui nous donne un arbre de toutes les positions possibles. Et l’algorithme choisira le coup optimum pour chaque joueurs, en imaginant que chaque joueurs jouent à chaque fois le meilleur coup possible, même pour l’humain.
Donc partant de cette base nous allons voir comme appliquer cet algorithme sur un jeu relativement simple : le morpion. Alors un jeu de morpion est constitué d’une grille de 3 sur 3. Chaque joueur pose un rond ou une croix puis laisse l’autre joueur poser un rond ou une croix. Le premier joueur qui arrive à alligner 3 ronds ou 3 croix gagne la partie.
/*La grille 3x3 du morpion*/ int grille[3][3] = { { 0,0,0 }, { 0,0,0 }, { 0,0,0 } }; #define ROND 1 #define CROIX 4
Ainsi pour mettre une croix ou un rond on pourra faire grille[x][y] = ROND; Ensuite il va falloir faire une fonction qui détermine si le joueur gagne, perd ou encore si il y a égalité.
#define EGALI 123 /*Vérifie si un des deux a gagné*/ int morpion_Check() { int i,j; int n = 0; /*Nombre de cases avec des ronds ou croix*/ for(i=0;i<3;i++) { n = grille[0][i] + grille[1][i] + grille[2][i]; if(n == 3) return ROND; if(n == 12) return CROIX; } for(i=0;i<3;i++) { n = grille[i][0] + grille[i][1] + grille[i][2]; if(n == 3) return ROND; if(n == 12) return CROIX; } n = grille[0][0] + grille[1][1] + grille[2][2]; if(n == 3) return ROND; if(n == 12) return CROIX; n = grille[0][2] + grille[1][1] + grille[2][0]; if(n == 3) return ROND; if(n == 12) return CROIX; /*Personne n'a gagné pour le moment, peut être une égalité?*/ n = 0; for(i=0;i<3;i++) { for(j=0;j<3;j++) { if(grille[i][j]) n++; } } if(n == 3*3) return EGALI; /*Le jeu n'est pas fini!*/ return 0; }
Cette fonction sera très utile pour le minmax. Donc voici la partie interessante, celle qui gère l’algorithme minmax. Cette fonction comme vous pouvez le voir est une fonction récursive.
/*Fonction qui permet de déterminer l'autre joueur*/ int morpion_Adversaire(joueur) { if(joueur == ROND) return CROIX; else return ROND; } int minimax(int joueur, int profondeur) { int check = morpion_Check(); int adversaire = morpion_Adversaire(joueur); if(check == joueur) { /*Si le joueur gagne, c'est la fête*/ return 100; } else if(check == adversaire) { /*Si le joueur perd, c'est triste :(*/ return -100; } else if(check == EGALI || profondeur == 0) { /*Si il y a égalité ou que l'on est assez profond, alors ça ne fait rien*/ return 0; } int i,j; int max = 0; int truc = 0; /*variable temporaire qui permet de voir les résultats*/ for(i=0;i<3;i++) { for(j=0;j<3;j++) { if(!grille[i][j]) { if(joueur == CROIX) { /*Max*/ truc = minimax(ROND,profondeur-1); if(truc > max) max = truc; } else if(joueur == ROND) { /*Min*/ truc = minimax(CROIX,profondeur-1); if(truc < max) max = truc; } } } } return max; }
Ensuite nous allons voir comment implémenter cette fonction dans le jeu à proprement parlé.
void morpion_IA(int joueur) { int i,j; int truc = 0; int max = 0; /*Les coordonnées du bon endroit :)*/ int x = -1; int y = -1; int adversaire = morpion_Adversaire(joueur); for(i=0;i<3;i++) { for(j=0;j<3;j++) { if(!grille[i][j]) { grille[i][j] = adversaire; truc = minimax(adversaire,1); /*On fixe la profondeur à 1, libre à vous de la changer pour augementer la difficulté.*/ if(truc >= max) { /*On regarde si le coup est au moins aussi bon que le meilleur*/ x = i; y = j; max = truc; } grille[i][j] = 0; } } } grille[x][y] = joueur; }
Donc voilà le plus gros est fait. Maintenant, pour mieu illustrer la chôse on va voir comment faire un morpion programme vs. programme. On prend PAlib parceque ça permet d’afficher directement du texte où on veut, et puis c’est moins prise de tête.
/*Fonction d'affichage*/ void morpion_Affichage() { int i,j; for(i=0;i<3;i++) { for(j=0;j<3;j++) { PA_OutputText(0,i,j,"%d",grille[i][j]); } } } int main(int argc, char ** argv) { PA_Init(); /*Initializes PA_Lib*/ PA_InitVBL(); /*Initializes a standard VBL*/ PA_InitText(1,0); PA_InitText(0,0); u8 joueur = ROND; grille[1][1] = CROIX; while (1) { joueur = morpion_Adversaire(joueur); PA_OutputText(1,1,3,"%d",joueur); morpion_IA(joueur); morpion_Affichage(); PA_WaitForVBL(); } return 0; } /* End of main()*/
Voilà, c’est un super morpion entre le programme et lui même. Ensuite vous êtes libre d’adapter ça à un véritable morpion. De plus cet algorithme est applicable dans de nombreux autres jeux, le Puissance 4 par exemple, l’Othello ou encore mais de manière plus complexe les échecs.