Problème avec un alphabeta en C pour othello

Problème avec un alphabeta en C pour othello - C - Programmation

Marsh Posté le 03-05-2011 à 12:03:37    

Bonjour,  je suis étudiante en maths-informatique et on nous a donné comme premier projet le jeu d'othello.
Cependant il semble que l'alphabeta soit mal programmé (il me semble qu'il gère mal les scores dans le cas où un joueur doit passer son tour mais je me trompe peut être).
Etant un peu à court d'idée j'espère que vous pourrez m'aider et me dire ce qui ne va pas dans ce code :
 

Code :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. #include "structures.h"
  5. #include "main.h"
  7. int game_over(partie battle, int couleur){
  8.     if((possibilite(&battle, battle.plateau, couleur)==-1) || (battle.nb_coupsjoues>MAX_COUPS))//si il n'y a plus de coups possible ou si on ajoue 60 coups, la partie est terminee
  9.         return -1;
  10.     else
  11.         return 1;
  12. }
  14. int alphabeta(int profondeur, int alpha, int beta, partie* b){
  15. partie battle=(*b);
  16.     coup coups;
  18. int i=11, couleur, legal, score, avant, dir;
  19. int pass=0;//nous servira a avoir les bons scores pour les cas ou un joueur doit sauter son tour
  20. coup meilleur_coup;
  21. if (battle.nb_coupsjoues==0){//si aucun coup n'a ete joue (l'ordi commence), la couleur est  initialisee a noir
  22.  couleur=NOIR;
  23. }
  24. else if(battle.coups[battle.nb_coupsjoues-1].couleur==NOIR)//sinon on regarde la couleur du cop precedent pour savoir quel couleur prendre
  25.  couleur=BLANC;
  26. else
  27.  couleur=NOIR;
  28.     if(possibilite(&battle, battle.plateau,couleur)==0){
  29.         couleur=(couleur+1)%2;
  30.         pass=1;
  31.     }
  33. if(game_over(battle, couleur)!=1){//si la partie est termine on regarde si le joueur actuel a gagne
  34.         if (battle.plateau->materiel[couleur]>battle.plateau->materiel[(couleur+1)%2])//si oui, on renvoit un grand nombre
  35.   {
  36.    return +1000000;
  37.   }
  38.   else if(battle.plateau->materiel[(couleur+1)%2]>battle.plateau->materiel[couleur])//sinon un tres petit nombre
  39.   {
  40.    return -1000000;
  41.   }
  42.   else
  43.   {
  44.    return 0;//pour l'egalite, on renvoit 0
  45.   }
  46. }
  47. else if(profondeur<=0){//si on a atteint la profondeur souhaite, on lance la fonction d'evaluation
  48.         return evaluation(battle, couleur);
  49.     }
  50.     else{//sinon on parcourts le damier afin de tester les coups legaux
  51.         while(i<=88){
  52.             for (dir=0;dir<DIRECTIONS;dir++)
  53.                 coups.retournement[dir]=0;
  54.             coups.position=i;
  55.             coups.couleur=couleur;
  56.             legal=coup_legal(battle.plateau, coups);
  57.             if(legal==-1)
  58.                 i++;
  59.             else{
  60.                 battle.plateau->damier[coups.position]=coups.couleur; // on "pose le pion sur le plateau" = on attribu a la case de l'othellier la valeur de la couleur
  61.                 coups=new_plateau(battle.plateau, coups); // on retourne les pions adverses
  62.                 battle.coups[battle.nb_coupsjoues]=coups; // on enregistre le coup joue
  63.                 couleur=(couleur+1)%2;//on change couleur
  64.                 battle.nb_coupsjoues++;
  65.                 if (battle.nb_coupsjoues>battle.longueur)
  66.                     battle.longueur++;
  69.                 if(pass==1){//si pass egal a 1, on ne change pas alphabeta a par la profondeur (pas d'alternance minmax)
  70.                     score=alphabeta(profondeur-1, alpha, beta, &battle);
  71.                 }
  72.                 else{//sinon on fait l'alternance minmax, (un joueur cherche a minimiser et l'autre a maximiser)
  73.                     score=-alphabeta(profondeur-1, -beta, -alpha, &battle);
  74.                 }
  75.                 avant=couleur;
  76.                 battle=annuler(battle.plateau, battle, (coups.couleur+1)%2);
  78.                 couleur=battle.coups[battle.nb_coupsjoues].couleur; //permet de passer au joueur precedant
  81.                 if(score>=alpha){//si score >= alpha, ce dernier coup est le meilleur
  82.                     alpha=score;//on change alpha
  83.                     meilleur_coup=coups;//on sauvegarde ce coup
  84.                     (*b).coups[battle.nb_coupsjoues]=coups;//on le sauvegarde egalement ici pour pouvoir le faire passer dans le jeu principal
  85.                     if(alpha>=beta){//si alpha >= beta, c'est inutile de continuer plus loins dans cette branche
  86.                         break;
  87.                     }
  88.                 }
  89.                 i++;
  90.             }
  91.         }
  92.     }
  93. return alpha;
  94. }


 
 
 
 
<config>Windows 7 / Firefox 3.6.17</config>


Message édité par Liarina le 03-05-2011 à 13:57:10
Reply

Marsh Posté le 03-05-2011 à 12:03:37   

Reply

Marsh Posté le 03-05-2011 à 13:51:30    

Salut,
 
J'ai pas encore trop regardé en détail, mais je pense qu'ajouter le contenu de tes fichiers d'entête structures.h et main.h aiderait à la compréhension générale du code (notamment les structures que tu utilises). Utilise aussi le bouton "C/C++" quand tu postes du code ici, ça ajoute la coloration syntaxique et ce genre de choses qui facilitent la lecture.
 
À mon avis, l'erreur vient de la complexité de ta fonction alphabeta, la découper en plus petites fonctions (chacune faisant une chose relativement simple) te permettra de mieux comprendre chaque partie de ton code et donc de ne pas devoir chercher où se cache l'éventuelle erreur dans une longue fonction. Mais déjà, avoir le contenu des structures que tu utilises permettra de mieux comprendre le fonctionnement de ton programme.

Reply

Marsh Posté le 03-05-2011 à 13:56:53    

Désolée pour la première édition. j'avais pas fait attention au bouton c/c++
 
main.h

Code :
  1. #include <SDL/SDL.h>
  2. #include <SDL_image.h>
  3. #include <SDL/SDL_ttf.h>
  5. void save(partie battle);
  6. partie load(FILE *save);
  7. int coup_legal(othellier plateau, coup coups);
  8. othellier initialisation(othellier plateau);
  9. int possibilite(partie *battle, othellier plateau, int couleur);
  10. coup new_plateau(othellier plateau,coup coups);
  11. partie annuler(othellier plateau,partie battle,int couleur);
  12. partie suivant(othellier plateau,partie battle,int couleur);
  13. int alphabeta(int profondeur, int alpha, int beta, partie *b);
  14. int game_over(partie battle, int couleur);
  15. int evaluation(partie battle, int couleur);
  16. int mobilite(partie battle, int couleur);
  17. int materiel(partie battle, int couleur);
  18. int coins(partie battle, int couleur);
  19. void affiche_menu(SDL_Surface *ecran);
  20. void affiche_oth(SDL_Surface* ecran, partie battle, int couleur, char choix[10]);
  21. int main();


 
structures.h
 

Code :
  1. #ifndef __STRUCTURES__
  2. #define __STRUCTURES__
  3. #include "definitions.h"
  5. struct othellier{
  6. int damier[MAX_CASE];
  7. int materiel[NB_JOUEURS];
  8. };
  9. typedef struct othellier * othellier;
  12. typedef struct{
  13. int position;
  14. int couleur;
  15. int retournement[DIRECTIONS];
  16. }coup;
  19. struct joueur{
  20. char nom[10];
  21. int type;
  22. int couleur;
  23. int niveau;
  24. };
  25. typedef struct joueur * joueur;
  27. typedef struct{
  28. int longueur;
  29. int nb_coupsjoues;
  30. joueur joueurs[2];
  31. int nbcoups_possible[2];
  32. coup coups[MAX_COUPS];
  33. othellier plateau;
  34. }partie;
  37. #endif

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed