Discussion :

[nanosoft]

Bonjour,

Je voudrais une explication par rapport à ce code :

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
 
 
int alphabêta(int depth, int alpha, int bêta)
{
   if (game over or depth <= 0)
      return winning score or eval();
   move bestmove ;
   for (each possible move m) {
      make move m;
      int score = -alphabêta(depth - 1, -bêta, -alpha)
      unmake move m;
      if (score >= alpha){
         alpha = score ;
         bestMove = m ;
         if (alpha >= bêta)
            break;
      }
   }
   return alpha;
}

En première lecture je pensais à une erreur d'indentation en ligne 6 , mais j'ai trouvé la même chose en différents endroits sur internet.
Je ne comprend pas : la première fois que l'on appelle alphabeta() on ne passe pas dans le if ligne 4 donc on commence systématiquement par jouer "bestmove" mais d'où sort-il ? On n'a pas encore déterminé m !

Je vous remercie par avance pour une explication éclairée

[Jimmy91]

Bonjour,

Ligne 5 : En premier lieu je dirais qu'il y a un problème par rapport à ce code, je n'ai jamais vu de return a or b si a et b ne sont pas des booléens...

Ensuite, comme votre variable bestmove est utilisée dans votre boucle, il faut la déclarer avant la boucle, dans laquelle sa valeur sera affectée.

L'indentation du code semble donc correcte. Sinon je vous recommande un article de wikipedia qui m'a été très utile dans mes études et que je trouve un peu plus clair :

http://fr.wikipedia.org/wiki/%C3%89lagage_alpha-beta

[nanosoft]

OK,

C'est possible qu'il y ait un problème par rapport à ce code, mais comme je l'ai dit j'ai trouvé des choses identiques sur internet.

C'est un pseudo code proche du langage C puisque la fonction est typée en int, c'est le langage avec lequel je travaille.
Mais cela ne sert à rien que je commence à coder tant que je n'aurais pas compris l'algo !
Je ne m'étais pas arrêté sur la ligne 5 mais c'est vrai que ce n'est pas logique : il ne faut pas prendre "or" comme un opérateur !
En ligne 5 je comprends qu'il faut retourner le résultat de la fonction eval() donc un int.

Pour moi "move bestmove" (ligne 6) c'était jouer le meilleur coup parmi les m explorés et déterminé justement par l'algo : voir bestmove = m en ligne 13.

Ensuite, comme votre variable bestmove est utilisée dans votre boucle, il faut la déclarer avant la boucle, dans laquelle sa valeur sera affectée.

Je ne suis pas d'accord avec cette phrase : comment affecter cette variable avant l'appel à la fonction alphabeta() ?
Aucun algo alpha-beta en negamax n'a besoin d'une telle variable.

Revenons à wikipédia (merci pour le lien):

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
 
fonction ALPHABETA(P, A, B) /* A < B */
   si P est une feuille alors
       retourner la valeur de P
   sinon
       Meilleur = –INFINI
       pour tout fils Pi de P faire
           Val = -ALPHABETA(Pi,-B,-A)
           si Val > Meilleur alors
               Meilleur = Val
               si Meilleur > A alors
                   A = Meilleur
                   si A ≥ B alors
                       retourner Meilleur
                   finsi
               finsi
           finsi 
       finpour 
       retourner Meilleur
   finsi
fin

A partir de ce pseudo-code je voudrais faire apparaître les notions de simuler le coup et de déjouer le coup (exploration de l'arbre) ainsi que celle de jouer le meilleur coup une fois déterminé.
Ces 3 notions existent dans le premier pseudo-code indiqué et c'est pour cela que j'ai retenu celui-ci.
Selon wikipédia il me manque le pseudo-code qui appelle la fonction alphabeta() pour jouer le coup.

Merci si vous pouvez me donner le complément

[Jimmy91]

OK,

Je ne suis pas d'accord avec cette phrase : comment affecter cette variable avant l'appel à la fonction alphabeta() ?
Aucun algo alpha-beta en negamax n'a besoin d'une telle variable.

En fait, la variable bestmove est affectée pendant l'appel suivant à la fonction alphabeta() ; ensuite elle persiste durant toute l'exécution de l'intégralité du code. En effet, alphabeta() est une fonction récursive qui va être initialisée au sommet et s'appeler elle-même jusqu'à la condition d'arrêt.

Selon wikipédia il me manque le pseudo-code qui appelle la fonction alphabeta() pour jouer le coup.

Merci si vous pouvez me donner le complément

Le pseudo-code dont vous avez besoin ici n'est donc autre que la fonction alphabeta(P,A,B) elle-même, initialisée pour tous les fils P du sommet de votre arbre, et avec A = - inf et B = + inf.

Hope it helps !

[nanosoft]

Merci mais je voudrais savoir si le premier pseudo-code de la discussion est correct ou non.
Et s'il n'est pas correct, cela serait super que quelqu'un puisse le corriger.

En l'état je ne le comprends pas puisqu'on commence par jouer le meilleur coup avant l'exploration et avant toute récursivité !

En fait, la variable bestmove est affectée pendant l'appel suivant à la fonction alphabeta()

Mais au premier appel : elle n'est pas affectée !!!!

[jouana]

Bonjour,

Un if qui n'a pas d'accolade donc pas de corp.
le ; signifie la fin de l'instruction ça revient donc à écrire ceci.

Code :

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

1
2
3
 
   if (game over or depth <= 0) return winning score or eval();
   move bestmove ;

Il n'y a donc pas de probléme d'indentation.