Puissance4 - Algo MinMax - problème heuristique
Bonjour,
Alors voilà, j'essaie de faire un Puissance 4 client/serveur en C avec implémentation de l'algorithme MinMax pour le serveur.
J'ai lu quelque-part (je ne sais plus ou) qu'une heuristique gagné/perdu suffisait largement pour un jeu comme le puissance 4 même avec une profondeur de 6.
Mais ça fait deux jours que j'essaie de faire marcher mon algo et rien à faire. :?
J'ai même essayé d'afficher la grille du jeu à chaque situations final, mais je peux pas tous les voir car sous dos le nombre de lignes dans la fenêtre est limité.
Du coup, je n'arrive pas vraiment à savoir d'où vient mon problème. A mon avis, ça vient de mon heuristique ou de quelque chose directement lié à elle, seulement je ne trouve pas.
La fonction choix_colonne():
Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
|
int choix_colonne(int jeu[7][6], int profondeur, int joueur){
printf("entrer dans choix colonne\n");
int valeurMax = -10000;
int valeurtmp;
int colonneOptimal = 0;
int c, l;
srand(time(NULL));
int colonneHasard;
if(profondeur==0||situationFinale(jeu, joueur)){ // Si profondeur atteinte ou situationFinale (grille remplie, bot joueur gagne, adversaire gagne)
valeurMax = evaluationHeuristique(joueur, jeu, profondeur);
printf("valeur max = %d\n", valeurMax);
}
else{
for(c=0;c<=6;c++){ // Pour chaque colonnes
if(!colonneRemplie(jeu, c)){ // Si la colonne n'est pas pleine
ajouterJeton(jeu, c, joueur); // simulation ajout jeton
valeurtmp = IAmin(jeu, profondeur-1, inverserJoueur(joueur));
if(valeurtmp>valeurMax){ // On veut la plus grande valeur des neuds de profondeur -1
valeurMax = valeurtmp;
colonneOptimal = c;
}
retirerJeton(jeu, c); // simulation retire jeton
}
}
}
if(valeurMax==0){
colonneHasard = rand()%7;
colonneOptimal = colonneHasard;
}
printf("valeur max total : %d", valeurMax);
return colonneOptimal;
} |
la fonction IAmin() :
Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
|
int IAmin(int jeu[7][6], int profondeur, int joueur){
int valeurMin = 10000;
int valeurtmp;
int c;
if(profondeur==0||situationFinale(jeu, joueur)){
valeurMin = evaluationHeuristique(joueur, jeu, profondeur); // -evaluation car joueur adversaire
printf("valeur max = %d\n", valeurMin);
}
else{
for(c=0;c<=6;c++){
if(!colonneRemplie(jeu, c)){
ajouterJeton(jeu, c, joueur);
valeurtmp = IAmax(jeu, profondeur-1, inverserJoueur(joueur));
if(valeurtmp<valeurMin)
valeurMin = valeurtmp;
retirerJeton(jeu, c);
}
}
}
return valeurMin;
} |
La fonction IAmax :
Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
|
int IAmax(int jeu[7][6], int profondeur, int joueur){
int valeurMax = -10000;
int valeurtmp;
int c;
if(profondeur==0||situationFinale(jeu, joueur)){
valeurMax = evaluationHeuristique(joueur, jeu, profondeur);
printf("valeur max = %d\n", valeurMax);
}
else{
for(c=0;c<=6;c++){
if(!colonneRemplie(jeu, c)){
ajouterJeton(jeu, c, joueur);
valeurtmp = IAmin(jeu, profondeur-1, inverserJoueur(joueur));
if(valeurtmp>valeurMax)
valeurMax = valeurtmp;
retirerJeton(jeu, c);
}
}
}
return valeurMax;
} |
la fonction heuristique :
Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
|
int evaluationHeuristique(int joueur, int jeu[7][6], int profondeur){
int c, l;
int valeur = 0;
if(joueurGagne(joueur, jeu)){
valeur = 100*(profondeur+1);
printf("joueur gagne\n");
printf("profondeur : %d\n", profondeur);
printf("valeur : %d\n", valeur);
}
if(joueurGagne(inverserJoueur(joueur), jeu)){
valeur = -100*(profondeur+1);
printf("inverse joueur gagne\n");
printf("profondeur : %d\n", profondeur);
printf("valeur : %d\n", valeur);
}
return valeur;
} |
Toutes mes autres fonctionnent correctement normalement. Puisqu'elles fonctionnaient avant que je n'ajoute l'algo MinMax.
Je précise que ce n'est pas un devoir à rendre ou quelque chose comme ça, juste moi qui fait ça pour m’entrainer et comprendre l'IA. C'est mal parti apparemment... Un peu d'aide serait la bienvenue :roll:
Merci d'avance!