Chapitre 3
Tables de Transposition
"Même si l'adversaire joue le coup analysé précédemment, recommencez l'analyse
en voyant la nouvelle position."
Benjamin Blumenfeld.
3.1 Introduction
Pour ne pas réexplorer un sous arbre qu'on a déj à exploré à partir d'une position déjà
rencontrée on peut stocker dans une table de hachage les positions déjà rencontrées et
évaluées au cours du parcours de l'arbre. Avant d'explorer une position, on commence
par regarder si elle n'a pas déjà été évaluée et stockée dans la table de hachage, ce qui
permet dans le meilleur des cas d'éviter de refaire une deuxième fois la recherche sur
cette position. Dans les autres cas cela permet tout de même de réutiliser les informations
stockées pour accélérer la nouvelle recherche.
Une table de transposition est une table de hachage dont chaque entrée contient des
informations sur la recherche effectuée à partir d'une position.
Les tables de transposition sont utiles aussi bien pour les problèmes à un joueur en
combinaison avec A * (voir chapitres 8 et 9) par exemple que pour les jeux à deux joueurs
en combinaison avec l' Alpha-Bêta.
On a vu que l'utilité de l'approfondissement itératif de la recherche avec l'algorithme
Alpha-Bêta est de mémoriser pour chaque position le meilleur coup de l'itération précédente pour pouvoir ensuite l'essayer en premier dans les positions de l'itération courante.
Il arrive souvent que le meilleur coup de la recherche à la profondeur précédente soit
aussi un bon coup de la recherche à la profondeur courante. Or le nombre de coupes
Tables de Transposition
"Même si l'adversaire joue le coup analysé précédemment, recommencez l'analyse
en voyant la nouvelle position."
Benjamin Blumenfeld.
3.1 Introduction
Pour ne pas réexplorer un sous arbre qu'on a déj à exploré à partir d'une position déjà
rencontrée on peut stocker dans une table de hachage les positions déjà rencontrées et
évaluées au cours du parcours de l'arbre. Avant d'explorer une position, on commence
par regarder si elle n'a pas déjà été évaluée et stockée dans la table de hachage, ce qui
permet dans le meilleur des cas d'éviter de refaire une deuxième fois la recherche sur
cette position. Dans les autres cas cela permet tout de même de réutiliser les informations
stockées pour accélérer la nouvelle recherche.
Une table de transposition est une table de hachage dont chaque entrée contient des
informations sur la recherche effectuée à partir d'une position.
Les tables de transposition sont utiles aussi bien pour les problèmes à un joueur en
combinaison avec A * (voir chapitres 8 et 9) par exemple que pour les jeux à deux joueurs
en combinaison avec l' Alpha-Bêta.
On a vu que l'utilité de l'approfondissement itératif de la recherche avec l'algorithme
Alpha-Bêta est de mémoriser pour chaque position le meilleur coup de l'itération précédente pour pouvoir ensuite l'essayer en premier dans les positions de l'itération courante.
Il arrive souvent que le meilleur coup de la recherche à la profondeur précédente soit
aussi un bon coup de la recherche à la profondeur courante. Or le nombre de coupes