Algo Alpha Beta qui ne fonctionne pas.

Fermé
landboa - 12 mars 2014 à 11:23
Bonjour,

J'essaie de réaliser un jeu de puissance 4 en C avec une partie IA. Pour ce faire j'utilise un algo alpha beta qui doit construire l'arbre des solutions en place de manière récursive. Mais lorsque je test l'algo l'arbre ne se créer pas comme il faudrait et je n'arrive pas à comprendre ce qu'il fait. Voici mon code que j'espère suffisamment commenté :


// Box** jeu est une matrice 7*6 de Box (enumération : VIDE, Joueur1, Joueur2).
// Box player est le joueur qui va jouer le prochain coup.
static Arbre createArbre (Box** jeu, Box player, int profondeur, int alpha, int beta, int k){
int i;
int s, tmp;
Etat e;
int compteur = 0;


/* -- On regarde si on est sur une feuille de l'arbre : -- */
for (i=0;i<COLONNES;i++){
// la fonction colPleine renvoie 0 si la colonne i de la grille jeu est pleine et -1 sinon :
if (colPleine (i, jeu) == -1){
compteur = 1;
}
}
// Si oui on renvoit au père :
if (compteur == 0 || profondeur <= 0){
return NULL;
}
/* -- -- */


/* -- -- */
Arbre result = malloc (sizeof (Noeud));
if (result == NULL){
fprintf (stderr, "Erreur d'allocation mémoire d'un arbre, fonction createArbre\n");
exit (EXIT_FAILURE);
}

result -> fils = malloc (COLONNES * sizeof (Arbre));
if (result -> fils == NULL){
fprintf (stderr, "Erreur d'allocation mémoire d'un arbre fils, fonction createArbre\n");
exit (EXIT_FAILURE);
}
for (i=0;i<COLONNES;i++){
result -> fils [i] = NULL;
}

e = etatJeu (jeu, player==J1?J2:J1, &ptA);
result -> grille = jeu;
// On attribut un poids si on a une grille qui fait perdre un joueur :
result -> poids = 0;
if (e == PERDRE && player == J1){
result -> poids = -1000;
}
if (e == PERDRE && player == J2){
result -> poids = 1000;
}
/* -- -- */


/* -- Si on est sur un minimiseur : -- */
if (k % 2 == 0){
s = beta;
for (i=0;i<COLONNES;i++){
if (colPleine (i, jeu) == -1){
result -> fils [i] = createArbre (addInJeu(i,jeu,player), player==J1?J2:J1, profondeur-1, alpha, s, k+1);
if (result -> fils [i] != NULL){
tmp = (result -> fils [i]) -> poids;
if (s > tmp){
s = tmp;
}
}
if (s <= alpha){
result -> poids = s;
return result;
}
}
}
}
/* -- -- */

/* -- Si on est sur un maximiseur : -- */
else {
s = alpha;
for (i=0;i<COLONNES;i++){
if (colPleine (i, jeu) == -1){
result -> fils [i] = createArbre (addInJeu(i,jeu,player), player==J1?J2:J1, profondeur-1, s, beta, k+1);
if (result -> fils [i] != NULL){
tmp = (result -> fils [i]) -> poids;
if (s < tmp){
s = tmp;
}
}
if (s >= beta){
result -> poids = s;
return result;
}
}
}
}
/* -- -- */

result -> poids = s;
return result;
}