52
Ta bles de Transposition
3.4 Stratégies de remplacement
Il existe différentes stratégies de gestion de la table de transposition. Le problème de
la stratégie à employer se pose quand on a une collision dans la table. Une possibilité est
de mémoriser dans une entrée de la table toutes les positions rencontrées. On se place
plutôt dans le cas où l'on décide de ne garder qu' une seule position par entrée de la table.
On doit alors décider si on remplace l'ancienne entrée par la nouvelle ou si on garde
l'ancienne entrée.
Question : Quelles stratégies de remplacement peut-on envisager ?
Réponse :
Les stratégies usuelles de remplacement sont :
- L' ancienneté : garder la position la plus ancienne.
- La nouveauté : garder la position la plus récente.
- La profondeur : garder la position dont le sous-arbre qui a permis d'établir la valeur
est le plus profond.
- La taille : garder la position dont le sous-arbre est le plus gros.
L'expérimentation de ces différentes stratégies (13] montre que la stratégie de remplacement la plus performante est la taille, suivie par la profondeur, puis la nouveauté et
enfin l'ancienneté. Les différences entre les stratégies s'amenuisent avec la taille de la
table de transposition. Une autre optimisation efficace est d'utiliser deux tables de transposition : la première contient la position choisie par la stratégie, alors que la deuxième
reçoit l'autre position. On peut avoir deux stratégies différentes pour les deux tables de
transposition ou la même stratégie.
3.5 Entrées de la table de transposition
En général on utilise la valeur de hachage pour calculer l'indice dans la table de transposition en tronquant la valeur de hachage aux n bits de poids faible. On obtient alors un
indice dans une table de transposition de taille 2".
Pour chaque entrée de la table de transposition on a une structure qui contient des
informations sur la position correspondante déjà explorée.
Question : Dans le cadre de l'Alpha-Bêta, quelles informations est-il utile de stocker
dans une entrée de la table de transposition ?
Réponse : Les informations suivantes sont généralement stockées dans une entrée de
la table de transposition :
- La clé : elle contient les bits tronqués de la valeur de hachage. Elle est utilisée pour
Ta bles de Transposition
3.4 Stratégies de remplacement
Il existe différentes stratégies de gestion de la table de transposition. Le problème de
la stratégie à employer se pose quand on a une collision dans la table. Une possibilité est
de mémoriser dans une entrée de la table toutes les positions rencontrées. On se place
plutôt dans le cas où l'on décide de ne garder qu' une seule position par entrée de la table.
On doit alors décider si on remplace l'ancienne entrée par la nouvelle ou si on garde
l'ancienne entrée.
Question : Quelles stratégies de remplacement peut-on envisager ?
Réponse :
Les stratégies usuelles de remplacement sont :
- L' ancienneté : garder la position la plus ancienne.
- La nouveauté : garder la position la plus récente.
- La profondeur : garder la position dont le sous-arbre qui a permis d'établir la valeur
est le plus profond.
- La taille : garder la position dont le sous-arbre est le plus gros.
L'expérimentation de ces différentes stratégies (13] montre que la stratégie de remplacement la plus performante est la taille, suivie par la profondeur, puis la nouveauté et
enfin l'ancienneté. Les différences entre les stratégies s'amenuisent avec la taille de la
table de transposition. Une autre optimisation efficace est d'utiliser deux tables de transposition : la première contient la position choisie par la stratégie, alors que la deuxième
reçoit l'autre position. On peut avoir deux stratégies différentes pour les deux tables de
transposition ou la même stratégie.
3.5 Entrées de la table de transposition
En général on utilise la valeur de hachage pour calculer l'indice dans la table de transposition en tronquant la valeur de hachage aux n bits de poids faible. On obtient alors un
indice dans une table de transposition de taille 2".
Pour chaque entrée de la table de transposition on a une structure qui contient des
informations sur la position correspondante déjà explorée.
Question : Dans le cadre de l'Alpha-Bêta, quelles informations est-il utile de stocker
dans une entrée de la table de transposition ?
Réponse : Les informations suivantes sont généralement stockées dans une entrée de
la table de transposition :
- La clé : elle contient les bits tronqués de la valeur de hachage. Elle est utilisée pour