Probléme avec l'algorithme negamax

**akkinaj** · 24/06/2008, 23h16

Bonjour a tous
Dans le cadre de programmer un jeu d'Othello j'ai choisi negamax :
ce pendant j'ai quelques soucis a m 'en sortir tout seul. j'expose :
j'ai deux modules:
1°module ===> fonction main
2°module contient la plus part des fonctions:
- la fonction joueur_ordinateur( )
. permet de determiner qui a le trait.
.obtient le nombre de coup possible en faisant appel a la fonction coup_possible ( )
et stocke ces coups dans un tableau.
. Si l'Ordinateur a le trait:
Appel de la fonction inviter_ordinateur ( ).
.sinon inviter joueur.
.mettre a jour le damier.
...etc .

- la fonction inviter_ordinateur ( )

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
   int inviter_ordinateur(int nb_coup_possible,int color_yes, int color_no)
      {
            char c;
            int plateau[100];
            int coup_legal[60];
           int nb_pions[2];
           int i,coup,meilleur_coup,score,meilleur_score,prof;
           int cy,cn;
          cy = color_yes;
         cn = color_no;
         memcpy(coup_legal,pos_legal,sizeof(pos_legal));
         memcpy(plateau,othellier->damier,sizeof(othellier->damier));
        memcpy(nb_pions,pions->nb_pions,sizeof(pions->nb_pions));
        printf("\ndans invite-ordinateur : nb_pion blanc = %d , nb_pion noir =    %d\n",nb_pions[1],nb_pions[0]);
        meilleur_coup = 0;

   for(prof = 1;;prof++)    //approfondissement iteratif.
  
     {
      // coup = coup_legal[i];
       cpt_noeuds = 1;
       //printf("\ncoup essayé par l'ordinateur : %c%c\n",'a'+((coup-11)%10),'1'+((coup-11)/10));
       for(i = 0; i <nb_coup_possible; i++)
               {
                     coup = coup_legal[i];
                     printf("\ncoup essayé par l'ordinateur : %c%c\n",'a'+((coup-11)%10),'1'+((coup-11)/10));

                    score = negamax(prof,&coup,&cy,&cn,plateau,nb_pions);

                    printf("\nscore = %d\n",score);
                    printf("profondeur atteinte = %d\n",prof);
                   printf("nombre de noeuds = %d\n",cpt_noeuds);
                   printf("apres negamax coup essayé par l'ordinateur : %c%c\n",'a'+((coup-11)%10),'1'+((coup-11)/10));
            if(score > meilleur_score)
               {
                 meilleur_score = score;
                 meilleur_coup = coup_legal[i];
               }
            if(cpt_noeuds > INFINI)
             return meilleur_coup;
          }
         printf("\nmeilleur score = %d\n",meilleur_score);
         memcpy(plateau,othellier->damier,sizeof(othellier->damier));
       }

  return(meilleur_coup);

}



int eval(int *nb_pions,int *plateau)
{
    char c;
    memcpy(plateau,othellier->damier,sizeof(othellier->damier));
    printf("\nnbre pions %d = %d, nbre pions %d = %d\n",couleur,nb_pions[couleur],autre_couleur,nb_pions[autre_couleur]);
    c = nb_pions[couleur] -nb_pions[autre_couleur];
    nb_pions[couleur]=pions->nb_pions[couleur];
    nb_pions[autre_couleur]=pions->nb_pions[autre_couleur];
    return (c);

}

int negamax(int prof,int *coup,int *color_yes,int *color_no,int *plateau,int *nb_pions)
{
    char c;
    int i,pos,score,meilleur_score,save,cy,cn;
    int othello[100];
    int nbr_pions[2],tab_legal[60];
    int nb_pions_retournes;
    int total_pions;
    int nbr_coup_possible;

    printf("\ncoup = %d\n",*coup);
    printf("\ncoup essayé : %c%c\n",'a'+((*coup-11)%10),'1'+((*coup-11)/10));
    printf("profondeur = %d\n",prof);

    cpt_noeuds++;

    for(i=0;i<100;i++) othello[i]=plateau[i];
    nbr_pions[NOIR] = nb_pions[NOIR];
    nbr_pions[BLANC] = nb_pions[BLANC];
    //memcpy(othello,plateau,sizeof(plateau));
    //memcpy(nbr_pions, nb_pions,sizeof(nb_pions));
     printf("\ndans negamax : nbr_pion blanc = %d , nbr_pion noir = %d\n",nbr_pions[1],nbr_pions[0]);
   // memcpy(tab_legal, pos_legal,sizeof(pos_legal));
    if ((nbr_pions[NOIR] + nbr_pions[BLANC] == 64)/* || prof <= 0*/)
        return eval(nbr_pions,plateau);
    meilleur_score = -INFINI;
    cy = *color_yes;
    cn = *color_no;
   // printf("nbr_coup_possible : %d\n",nbr_coup_possible);
    printf("color-yes = %d ,color-no = %d\n",*color_yes,*color_no);

                                                                   ////////////////////////
    nbr_coup_possible = coup_possible(othello,tab_legal,cy, cn);  // APPEL DE COUP-POSSIBLE
    printf("\nDANS NEGAMAX :\n");
    afficher(othello);/////////////////////////
    printf("\npress any key to continue ...\n");
    c = getchar();
    printf("\nnbr coup possible = %d\n",nbr_coup_possible);
    for(i=0;i < nbr_coup_possible;i++)
       {
           // printf("nbr_coup_possible : %d\n",nbr_coup_possible);
            pos = tab_legal[i];
                                                                                          
            nb_pions_retournes = maj_damier(othello,nbr_pions,&total_pions,pos,cy,cn); //APPEL DE MAJ-DAMIER
                                                                                      
            printf("\naffichage apres APPEL DE MAJ-DAMIER\n");
            afficher(othello);
            printf("\ndans la boucle negamax press any key\n");
            c=getchar();
            //save = *color_yes;
            //*color_yes = *color_no;
            //*color_no = save;

            score = -negamax(prof-1,&pos,&cn,&cy,othello,nbr_pions);


            printf("\ndans la boucle negamax score = %d\n",score);
            if (score >= meilleur_score)
                    {
                     meilleur_score = score;
                     *coup = pos;
                    }
            memcpy(plateau,othello,sizeof(othello));
            memcpy(nb_pions, nbr_pions,sizeof(nbr_pions));
          
       }
     
    return meilleur_score;
}

Resultat :

les coups legaux sont presentés par des croix
a b c d e f g h

1 . . . . . . . .

2 . . . . . . . .

3 . . . X . . . .

4 . . X B N . . .

5 . . . N B X . .

6 . . . . X . . .

7 . . . . . . . .

8 . . . . . . . .
nombre de coups possibles : 4

les coups possibles sont :
c4 e6 f5 d3

l'ordinateur a le trait :

dans invite-ordinateur : nb_pion blanc = 2 , nb_pion noir = 2

coup = 43

coup essayé : c4
profondeur = 1

dans negamax : nbr_pion blanc = 2 , nbr_pion noir = 2
color-yes = 0 ,color-no = 1

DANS NEGAMAX :
a b c d e f g h

1 . . . . . . . .

2 . . . . . . . .

3 . . . X . . . .

4 . . X B N . . .

5 . . . N B X . .

6 . . . . X . . .

7 . . . . . . . .

8 . . . . . . . .
press any key to continue ...

nbr coup possible = 4
a b c d e f g h

1 . . . . . . . .

2 . . . . . . . .

3 . . . X . . . .

4 . . N N N . . .

5 . . . N B X . .

6 . . . . X . . .

7 . . . . . . . .

8 . . . . . . . .
dans maj-damier nombre de pions retournés par computer = 1

affichage apres APPEL DE MAJ-DAMIER
a b c d e f g h

1 . . . . . . . .

2 . . . . . . . .

3 . . . X . . . .

4 . . N N N . . .

5 . . . N B X . .

6 . . . . X . . .

7 . . . . . . . .

8 . . . . . . . .
dans la boucle negamax press any key
coup = 43

coup essayé : c4
profondeur = 0

dans negamax : nbr_pion blanc = 1 , nbr_pion noir = 4
color-yes = 1 ,color-no = 0

DANS NEGAMAX :
a b c d e f g h

1 . . . . . . . .

2 . . . . . . . .

3 . . X . X . . .

4 . . N N N . . .

5 . . X N B . . .

6 . . . . . . . .

7 . . . . . . . .

8 . . . . . . . .
press any key to continue ...

......... ....... etc etc

et j'arrive a :

nbr coup possible = 1
a b c d e f g h

1 B B B B B B B B

2 N B N N B B B B

3 N B B B N B N B

4 N B B B B N N B

5 N B N N B B N B

6 N B N N B B B B

7 N N N N N N N B

8 N . N B N N N N
dans maj-damier nombre de pions retournés par computer = 1

affichage apres APPEL DE MAJ-DAMIER
a b c d e f g h

1 B B B B B B B B

2 N B N N B B B B

3 N B B B N B N B

4 N B B B B N N B

5 N B N N B B N B

6 N B N N B B B B

7 N N N N N N N B

8 N . N B N N N N
dans la boucle negamax press any key

coup = 88

coup essayé : h8
profondeur = -58

dans negamax : nbr_pion blanc = 34 , nbr_pion noir = 29
color-yes = 1 ,color-no = 0

DANS NEGAMAX :
a b c d e f g h

1 B B B B B B B B

2 N B N N B B B B

3 N B B B N B N B

4 N B B B B N N B

5 N B N N B B N B

6 N B N N B B B B

7 N N N N N N N B

8 N X N B N N N N
press any key to continue ...

nbr coup possible = 1
a b c d e f g h

1 B B B B B B B B

2 N B N N B B B B

3 N B B B N B N B

4 N B B B B N N B

5 N B N N B B N B

6 N B N B B B B B

7 N B B N N N N B

8 N B B B N N N N
dans maj-damier nombre de pions retournés par felix = 4

affichage apres APPEL DE MAJ-DAMIER
a b c d e f g h

1 B B B B B B B B

2 N B N N B B B B

3 N B B B N B N B

4 N B B B B N N B

5 N B N N B B N B

6 N B N B B B B B

7 N B B N N N N B

8 N B B B N N N N
dans la boucle negamax press any key

coup = 82

coup essayé : b8
profondeur = -59

dans negamax : nbr_pion blanc = 39 , nbr_pion noir = 25

nbre pions 1 = 39, nbre pions 0 = 25

dans la boucle negamax score = -14

dans la boucle negamax score = 14

dans la boucle negamax score = -14
a b c d e f g h

1 . . . . . . . .

2 . . . . . . . .

3 . . . X . . . .

4 . . X B N . . .

5 . . . N B X . .

6 . . . . X . . .

7 . . . . . . . .

8 . B . . . . . .
dans maj-damier nombre de pions retournés par felix = 0

affichage apres APPEL DE MAJ-DAMIER
a b c d e f g h

1 . . . . . . . .

2 . . . . . . . .

3 . . . X . . . .

4 . . X B N . . .

5 . . . N B X . .

6 . . . . X . . .

7 . . . . . . . .

8 . B . . . . . .
dans la boucle negamax press any key

et on peut continuer infiniment.

ça fait quelques semaines que je tourne en rond.
je suis vraiment fatigué.
si quelqu'un(e) remarque ou voit exactement ou je me gourre qu'il (elle) me le signale
s'il vous plait je vous remercie d'avance

najib ,cordialement