Algorithme alpha-beta pruning
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:
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.
