Discussion :

[gunsailor]

bonjour à tous,
jusqu'à lors, j'utilisais l'algorithme susmentionné sans l'avoir éprouvé par mon humble intellect.
j'ai voulu jeter un coup d’œil à un ancien programme qui l'utilisait et, ne voyant pas comment il se faisait que la valeur de alpha et de bêta soit reportées avant l'appel précédent à la fonction mère de l'algorithme, je me suis reporté à sa page wikipédia. Et voilà l'algo que j'en ai tiré:

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
 
fonction alphabeta(nœud, α, β) /* α est toujours inférieur à β */
   si nœud est une feuille alors
       retourner la valeur de nœud
   sinon si nœud est de type Min alors
           v = +∞
           pour tout fils de nœud faire
               v = min(v, alphabeta(fils, α, β))                
               si α ≥ v alors  /* coupure alpha */
                   retourner v
               β = min(β, v)           
    sinon
           v = -∞
           pour tout fils de nœud faire
               v = max(v, alphabeta(fils, α, β))                
               si v ≥ β alors /* coupure beta */
                   retourner v
               α = max(α, v)
    retourner v

Ma question est: Comment ces valeurs ( celles de alpha et de bêta ) peuvent être accessibles depuis l'appel récursif précédent afin d'effectuer la comparaison avec v ( et ainsi de rendre l'élagage efficient )?
Merci pour vos lumières... cordialement.

[anapurna]

salut

v est local a la méthode
ensuite selon le cas on compare le v à la résultante de la fonction sous jascente
a aucun moment on passe le v

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
 
fonction alphabeta(nœud, alpha, Beta) /* α est toujours inférieur à β */
  si nœud.isFeuille alors
    retourner nœud.Valeur
  sinon 
  si nœud est de type Min alors // Cas Negatif
    v = +999999999999  // Afectation
    pour tout fils de nœud faire
      v = min(v,alphabeta(fils, alpha, Beta)) // Affectation selon la résultante  (fils = branche )
      si alpha >= v alors /* coupure alpha */
        retourner v
     Beta = min(Beta, v)
  sinon  // Cas Possitif
    v = -999999999999  // Afectation
    pour tout fils de nœud faire 
      v = max(v, alphabeta(fils, alpha, Beta))  // Affectation selon la résultante (fils = branche )
      si v >= Beta alors /* coupure beta */
        retourner v
      alpha = max(alpha, v) 
retourner v