MrCool
01/08/2005, 19h56
Alors même que je n'ai pas fini l'article sur la création d'un morpion en SDL, je viens vous soumettre la future deuxième partie de cet article avec conception d'une IA à l'aide de MinMax.
Actuellement ce code fonctionne mais mon IA est très très bête. Je trouve cela bizarre de la part d'un algo qui explore (et pour le coûp c'est bien le cas!) *toutes* les coûps possibles.
Est-ce un comportement normal? J'aurais pensé qu'un tel algo serait "invincible".
NB: toute aide sera précieuse, mais ne cherchez pas à optimiser pour l'instant, je veux un algo qui reste très simple pour l'article. Il sera certainement refait plus tard avec AlphaBeta :)
#include <SDL/sdl.h>
#include <stdlib.h>
#define Maximum(a,b) ((a)>(b))?(a):(b)
#define Minimum(a,b) ((a)<(b))?(a):(b)
#define JOUEUR_IA CARRE
#define JOUEUR_HUMAIN ROND
enum e_case
{
VIDE=0,
CARRE=1,
ROND=-1
};
enum e_case TestGagnant(const enum e_case *plateau);
enum e_case MinMax(enum e_case *plateau, enum e_case joueur);
void IAJoue(enum e_case *plateau);
void DEBUT_PrintPlateau(enum e_case *plateau)
{
int i,j;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
switch(plateau[i*3+j])
{
case VIDE:
printf("-");
break;
case ROND:
printf("O");
break;
case CARRE:
printf("X");
break;
}
printf("\n");
}
}
enum e_case TestGagnant(const enum e_case *plateau)
{
int i;
/* Teste les lignes */
for(i=0;i<3;i++)
if( (plateau[(i*3)+0]==plateau[(i*3)+1]) && (plateau[(i*3)+0]==plateau[(i*3)+2]) )
if(plateau[(i*3)+0]!=VIDE)
return plateau[(i*3)+0];
/* Teste les colonnes */
for(i=0;i<3;i++)
if( (plateau[i]==plateau[3+i]) && (plateau[i]==plateau[6+i]) )
if(plateau[i]!=VIDE)
return plateau[i];
/* Teste les diagonales */
if( (plateau[0]==plateau[4]) && (plateau[0]==plateau[8]) )
if(plateau[0]!=VIDE)
return plateau[0];
if( (plateau[2]==plateau[4]) && (plateau[2]==plateau[6]) )
if(plateau[2]!=VIDE)
return plateau[2];
return VIDE;
}
enum e_case MinMax(enum e_case *plateau, enum e_case joueur)
{
unsigned char i, j, estNul;
enum e_case copie[9];
enum e_case res, tmp;
DEBUT_PrintPlateau(plateau);
/* teste s'il y a un gagnant */
tmp=TestGagnant(plateau);
if(tmp!=VIDE)
return tmp;
/* la partie est soit nulle, soit non-finie */
/* initialisation des variables */
estNul=1;
res=VIDE;
if(joueur==JOUEUR_IA)
tmp=-2;
else
tmp=2;
/* Copie du tableau */
for(i=0;i<9;i++)
copie[i]=plateau[i];
for(i=0;i<9;i++)
if(copie[i]==VIDE)
{ /* il s'agit d'un coûp possible, évaluons-le */
copie[i]=joueur;
tmp=MinMax(copie, (joueur==CARRE)?ROND:CARRE);
if(joueur==JOUEUR_IA) /* l'ia joue */
res=Maximum(tmp,res); /* on maximise le score quand nous jouons; */
else
res=Minimum(tmp,res); /* on le minimise quand l'adverssaire joue. */
/* Un coûp est possible, cette situation n'est donc pas finale */
estNul=0;
/* Réinitialisation du tableau */
for(j=0;j<9;j++)
copie[j]=plateau[j];
}
if(estNul) /* la partie est nulle! */
res=0;
return res;
}
void IAJoue(enum e_case *plateau)
{
unsigned char i,j;
enum e_case copie[9];
enum e_case score[9];
int score_max, coup_max;
/* Initialisation */
for(i=0;i<9;i++)
{
score[i]=-2;
copie[i]=plateau[i];
}
for(i=0;i<9;i++)
{
if(plateau[i]==VIDE)
{
/* On tente un coûp. */
copie[i]=JOUEUR_IA;
/* Si le coûp est gagnant, inutile d'aller chercher plus loin! */
if(TestGagnant(copie)==JOUEUR_IA)
{
plateau[i]=JOUEUR_IA;
return;
}
/* Evaluation du score avec cette action. */
score[i]=MinMax(copie, JOUEUR_HUMAIN);
/* Réinitialisation du tableau */
for(j=0;j<9;j++)
copie[j]=plateau[j];
}
}
/* Détermination du meilleur coûp */
coup_max=0;
score_max=-2;
for(i=0;i<9;i++)
if(score[i]>score_max)
score_max=score[i], coup_max=i;
/* On joue! */
plateau[coup_max]=JOUEUR_IA;
}
int main(int argc, char **argv)
{
SDL_Surface *screen, *fond, *carre, *rond;
SDL_Event event;
SDL_Rect dest;
int isdone;
int cx, cy, i;
enum e_case joueur, gagnant;
enum e_case plateau[9]=
{VIDE,VIDE,VIDE,
VIDE,VIDE,VIDE,
VIDE,VIDE,VIDE};
SDL_Init(SDL_INIT_VIDEO);
screen = SDL_SetVideoMode(640,480,32,SDL_HWSURFACE|SDL_DOUBLEBUF);
SDL_WM_SetCaption("Morpion - Games Creators Network (http://www.games-creators.org)",NULL);
/* chargement des médias */
fond=SDL_LoadBMP("fond.bmp");
carre=SDL_LoadBMP("carre.bmp");
rond=SDL_LoadBMP("rond.bmp");
isdone=0;
joueur=JOUEUR_HUMAIN;
gagnant=VIDE;
while((!isdone)&&(gagnant==VIDE))
{
/* Si c'est à l'ia de joueur... elle joue! */
if(joueur==JOUEUR_IA)
{
IAJoue(plateau);
joueur=JOUEUR_HUMAIN;
gagnant=TestGagnant(plateau);
continue;
}
while(SDL_PollEvent(&event))
{
switch(event.type)
{
case SDL_MOUSEBUTTONUP:
if(joueur==JOUEUR_IA) break;
if(event.button.x<100) break;
if(event.button.x>295) break;
if(event.button.y<100) break;
if(event.button.y>295) break;
/* Détermination de la case */
cx = (event.button.x-100)/65;
cy = (event.button.y-100)/65;
if(plateau[cx+3*cy]!=VIDE) break;
plateau[cx+3*cy]=joueur;
if(joueur==CARRE)
joueur=ROND;
else
joueur=CARRE;
break;
case SDL_QUIT:
isdone=1;
break;
}
}
/* Test du gagnant */
gagnant=TestGagnant(plateau);
/* affichage fond */
SDL_BlitSurface(fond, NULL, screen, NULL);
/* affichage de la carte */
dest.w=dest.h=64;
for(i=0;i<9;i++)
switch(plateau[i])
{
case VIDE:
break;
case CARRE:
dest.x=100+(i%3)*65, dest.y=100+(i/3)*65;
SDL_BlitSurface(carre, NULL, screen, &dest);
break;
case ROND:
dest.x=100+(i%3)*65, dest.y=100+(i/3)*65;
SDL_BlitSurface(rond, NULL, screen, &dest);
break;
}
/* inversion des tampons */
SDL_Flip(screen);
}
if(gagnant!=VIDE)
{
dest.w=dest.h=64;
while(!isdone)
{
while(SDL_PollEvent(&event))
if(event.type==SDL_QUIT) isdone=1;
dest.x=300+rand()%(640-64-300);
dest.y=rand()%(480-64);
if(gagnant==ROND)
SDL_BlitSurface(rond, NULL, screen, &dest);
else
SDL_BlitSurface(carre, NULL, screen, &dest);
SDL_Flip(screen);
}
}
/* Libération des médias */
SDL_FreeSurface(fond);
SDL_FreeSurface(carre);
SDL_FreeSurface(rond);
SDL_Quit();
return 0;
}
Actuellement ce code fonctionne mais mon IA est très très bête. Je trouve cela bizarre de la part d'un algo qui explore (et pour le coûp c'est bien le cas!) *toutes* les coûps possibles.
Est-ce un comportement normal? J'aurais pensé qu'un tel algo serait "invincible".
NB: toute aide sera précieuse, mais ne cherchez pas à optimiser pour l'instant, je veux un algo qui reste très simple pour l'article. Il sera certainement refait plus tard avec AlphaBeta :)
#include <SDL/sdl.h>
#include <stdlib.h>
#define Maximum(a,b) ((a)>(b))?(a):(b)
#define Minimum(a,b) ((a)<(b))?(a):(b)
#define JOUEUR_IA CARRE
#define JOUEUR_HUMAIN ROND
enum e_case
{
VIDE=0,
CARRE=1,
ROND=-1
};
enum e_case TestGagnant(const enum e_case *plateau);
enum e_case MinMax(enum e_case *plateau, enum e_case joueur);
void IAJoue(enum e_case *plateau);
void DEBUT_PrintPlateau(enum e_case *plateau)
{
int i,j;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
switch(plateau[i*3+j])
{
case VIDE:
printf("-");
break;
case ROND:
printf("O");
break;
case CARRE:
printf("X");
break;
}
printf("\n");
}
}
enum e_case TestGagnant(const enum e_case *plateau)
{
int i;
/* Teste les lignes */
for(i=0;i<3;i++)
if( (plateau[(i*3)+0]==plateau[(i*3)+1]) && (plateau[(i*3)+0]==plateau[(i*3)+2]) )
if(plateau[(i*3)+0]!=VIDE)
return plateau[(i*3)+0];
/* Teste les colonnes */
for(i=0;i<3;i++)
if( (plateau[i]==plateau[3+i]) && (plateau[i]==plateau[6+i]) )
if(plateau[i]!=VIDE)
return plateau[i];
/* Teste les diagonales */
if( (plateau[0]==plateau[4]) && (plateau[0]==plateau[8]) )
if(plateau[0]!=VIDE)
return plateau[0];
if( (plateau[2]==plateau[4]) && (plateau[2]==plateau[6]) )
if(plateau[2]!=VIDE)
return plateau[2];
return VIDE;
}
enum e_case MinMax(enum e_case *plateau, enum e_case joueur)
{
unsigned char i, j, estNul;
enum e_case copie[9];
enum e_case res, tmp;
DEBUT_PrintPlateau(plateau);
/* teste s'il y a un gagnant */
tmp=TestGagnant(plateau);
if(tmp!=VIDE)
return tmp;
/* la partie est soit nulle, soit non-finie */
/* initialisation des variables */
estNul=1;
res=VIDE;
if(joueur==JOUEUR_IA)
tmp=-2;
else
tmp=2;
/* Copie du tableau */
for(i=0;i<9;i++)
copie[i]=plateau[i];
for(i=0;i<9;i++)
if(copie[i]==VIDE)
{ /* il s'agit d'un coûp possible, évaluons-le */
copie[i]=joueur;
tmp=MinMax(copie, (joueur==CARRE)?ROND:CARRE);
if(joueur==JOUEUR_IA) /* l'ia joue */
res=Maximum(tmp,res); /* on maximise le score quand nous jouons; */
else
res=Minimum(tmp,res); /* on le minimise quand l'adverssaire joue. */
/* Un coûp est possible, cette situation n'est donc pas finale */
estNul=0;
/* Réinitialisation du tableau */
for(j=0;j<9;j++)
copie[j]=plateau[j];
}
if(estNul) /* la partie est nulle! */
res=0;
return res;
}
void IAJoue(enum e_case *plateau)
{
unsigned char i,j;
enum e_case copie[9];
enum e_case score[9];
int score_max, coup_max;
/* Initialisation */
for(i=0;i<9;i++)
{
score[i]=-2;
copie[i]=plateau[i];
}
for(i=0;i<9;i++)
{
if(plateau[i]==VIDE)
{
/* On tente un coûp. */
copie[i]=JOUEUR_IA;
/* Si le coûp est gagnant, inutile d'aller chercher plus loin! */
if(TestGagnant(copie)==JOUEUR_IA)
{
plateau[i]=JOUEUR_IA;
return;
}
/* Evaluation du score avec cette action. */
score[i]=MinMax(copie, JOUEUR_HUMAIN);
/* Réinitialisation du tableau */
for(j=0;j<9;j++)
copie[j]=plateau[j];
}
}
/* Détermination du meilleur coûp */
coup_max=0;
score_max=-2;
for(i=0;i<9;i++)
if(score[i]>score_max)
score_max=score[i], coup_max=i;
/* On joue! */
plateau[coup_max]=JOUEUR_IA;
}
int main(int argc, char **argv)
{
SDL_Surface *screen, *fond, *carre, *rond;
SDL_Event event;
SDL_Rect dest;
int isdone;
int cx, cy, i;
enum e_case joueur, gagnant;
enum e_case plateau[9]=
{VIDE,VIDE,VIDE,
VIDE,VIDE,VIDE,
VIDE,VIDE,VIDE};
SDL_Init(SDL_INIT_VIDEO);
screen = SDL_SetVideoMode(640,480,32,SDL_HWSURFACE|SDL_DOUBLEBUF);
SDL_WM_SetCaption("Morpion - Games Creators Network (http://www.games-creators.org)",NULL);
/* chargement des médias */
fond=SDL_LoadBMP("fond.bmp");
carre=SDL_LoadBMP("carre.bmp");
rond=SDL_LoadBMP("rond.bmp");
isdone=0;
joueur=JOUEUR_HUMAIN;
gagnant=VIDE;
while((!isdone)&&(gagnant==VIDE))
{
/* Si c'est à l'ia de joueur... elle joue! */
if(joueur==JOUEUR_IA)
{
IAJoue(plateau);
joueur=JOUEUR_HUMAIN;
gagnant=TestGagnant(plateau);
continue;
}
while(SDL_PollEvent(&event))
{
switch(event.type)
{
case SDL_MOUSEBUTTONUP:
if(joueur==JOUEUR_IA) break;
if(event.button.x<100) break;
if(event.button.x>295) break;
if(event.button.y<100) break;
if(event.button.y>295) break;
/* Détermination de la case */
cx = (event.button.x-100)/65;
cy = (event.button.y-100)/65;
if(plateau[cx+3*cy]!=VIDE) break;
plateau[cx+3*cy]=joueur;
if(joueur==CARRE)
joueur=ROND;
else
joueur=CARRE;
break;
case SDL_QUIT:
isdone=1;
break;
}
}
/* Test du gagnant */
gagnant=TestGagnant(plateau);
/* affichage fond */
SDL_BlitSurface(fond, NULL, screen, NULL);
/* affichage de la carte */
dest.w=dest.h=64;
for(i=0;i<9;i++)
switch(plateau[i])
{
case VIDE:
break;
case CARRE:
dest.x=100+(i%3)*65, dest.y=100+(i/3)*65;
SDL_BlitSurface(carre, NULL, screen, &dest);
break;
case ROND:
dest.x=100+(i%3)*65, dest.y=100+(i/3)*65;
SDL_BlitSurface(rond, NULL, screen, &dest);
break;
}
/* inversion des tampons */
SDL_Flip(screen);
}
if(gagnant!=VIDE)
{
dest.w=dest.h=64;
while(!isdone)
{
while(SDL_PollEvent(&event))
if(event.type==SDL_QUIT) isdone=1;
dest.x=300+rand()%(640-64-300);
dest.y=rand()%(480-64);
if(gagnant==ROND)
SDL_BlitSurface(rond, NULL, screen, &dest);
else
SDL_BlitSurface(carre, NULL, screen, &dest);
SDL_Flip(screen);
}
}
/* Libération des médias */
SDL_FreeSurface(fond);
SDL_FreeSurface(carre);
SDL_FreeSurface(rond);
SDL_Quit();
return 0;
}