2.11 La recherche avec variation pr inc ipale
23
[68), développe les feuilles de l'arbre dans le même ordre qu'un algorithme en meilleur
d'abord qui a été prouvé meilleur qu' Alpha-Bêta : SSS * [84).
2.11 La recherche ave c variation principale
La recherche avec variation principale (Principal Variation Search) permet une petite
amélioration sur l' Alpha-Bêta simple en utilisant des recherches avec fenêtres nulles. Pour
cela, on divise les noeuds de la recherche Alpha-Bêta en trois types distincts :
- Les noeuds alpha pour lesquels tous les coups retournent une valeur plus petite ou
égale à alpha.
- Les noeuds bêta pour lesquels au moins un coup retourne une valeur supérieure ou
égale à bêta.
- Les noeuds de la variation principale (noeuds PV) pour lesquels au moins un des
coups a une valeur supérieure à alpha, mais aucun des coups ne retourne une valeur
supérieure ou égale à bêta.
En supposant que les coups sont envisagés des meilleurs aux moins bons, on peut
essayer de deviner le type d'un noeud en fonction de la valeur retournée par la recherche
sur le premier coup envisagé. Si la valeur est supérieure à bêta, on est sûr qu'on a un
noeud bêta. Si la valeur est inférieure à alpha, et que l'on fait l'hypothèse que le premier
coup a de grandes chances d'être le meilleur, on peut estimer qu'on a de grandes chances
d'être en présence d'un noeud alpha. Si la valeur est comprise entre alpha et bêta, on a de
grandes chances d'être en présence d'un noeud PV.
Le principe de la recherche avec variation principale est de faire une recherche normale jusqu 'à ce qu'on trouve un coup qui a une valeur comprise entre alpha et bêta. On
fait alors l'hypothèse que ce coup est le meilleur et on ne cherche plus qu'à prouver que
les coups suivants sont moins bons. Si ce n'est pas le cas, il faudra refaire une recherche
pour le coup qui se révèle être meilleur. Faire des recherches avec une fenêtre nulle pour
prouver que les coups qui suivent le coup de la variation principale sont moins bons, est
moins coûteux que de faire des recherches avec la fenêtre normale. To utefois, quand un
coup suivant le coup de la variation pincipale est meilleur, il faut refaire une recherche et
la recherche avec fenêtre nulle est du temps perdu. En pratique les gains apportés par les
recherches avec fenêtre nulle sont plus importants que les pertes dues aux coups qui se
révèlent être meilleurs que prévu.
Exercice: Ajouter la recherche avec variation principale à l'algorithme Alpha-Bêta.
2.12 L' heuristique du coup nul
L' heuristique du coup nul permet de détecter avec une recherche beaucoup moins
coûteuse que la recherche normale les positions qui vont très probablement amener à des
23
[68), développe les feuilles de l'arbre dans le même ordre qu'un algorithme en meilleur
d'abord qui a été prouvé meilleur qu' Alpha-Bêta : SSS * [84).
2.11 La recherche ave c variation principale
La recherche avec variation principale (Principal Variation Search) permet une petite
amélioration sur l' Alpha-Bêta simple en utilisant des recherches avec fenêtres nulles. Pour
cela, on divise les noeuds de la recherche Alpha-Bêta en trois types distincts :
- Les noeuds alpha pour lesquels tous les coups retournent une valeur plus petite ou
égale à alpha.
- Les noeuds bêta pour lesquels au moins un coup retourne une valeur supérieure ou
égale à bêta.
- Les noeuds de la variation principale (noeuds PV) pour lesquels au moins un des
coups a une valeur supérieure à alpha, mais aucun des coups ne retourne une valeur
supérieure ou égale à bêta.
En supposant que les coups sont envisagés des meilleurs aux moins bons, on peut
essayer de deviner le type d'un noeud en fonction de la valeur retournée par la recherche
sur le premier coup envisagé. Si la valeur est supérieure à bêta, on est sûr qu'on a un
noeud bêta. Si la valeur est inférieure à alpha, et que l'on fait l'hypothèse que le premier
coup a de grandes chances d'être le meilleur, on peut estimer qu'on a de grandes chances
d'être en présence d'un noeud alpha. Si la valeur est comprise entre alpha et bêta, on a de
grandes chances d'être en présence d'un noeud PV.
Le principe de la recherche avec variation principale est de faire une recherche normale jusqu 'à ce qu'on trouve un coup qui a une valeur comprise entre alpha et bêta. On
fait alors l'hypothèse que ce coup est le meilleur et on ne cherche plus qu'à prouver que
les coups suivants sont moins bons. Si ce n'est pas le cas, il faudra refaire une recherche
pour le coup qui se révèle être meilleur. Faire des recherches avec une fenêtre nulle pour
prouver que les coups qui suivent le coup de la variation principale sont moins bons, est
moins coûteux que de faire des recherches avec la fenêtre normale. To utefois, quand un
coup suivant le coup de la variation pincipale est meilleur, il faut refaire une recherche et
la recherche avec fenêtre nulle est du temps perdu. En pratique les gains apportés par les
recherches avec fenêtre nulle sont plus importants que les pertes dues aux coups qui se
révèlent être meilleurs que prévu.
Exercice: Ajouter la recherche avec variation principale à l'algorithme Alpha-Bêta.
2.12 L' heuristique du coup nul
L' heuristique du coup nul permet de détecter avec une recherche beaucoup moins
coûteuse que la recherche normale les positions qui vont très probablement amener à des