3.6 Utilisation de la table de transposition
53
différencier les positions qui ont le même indice dans la table de transposition mais
des valeurs de hachage différentes.
- Le meilleur coup trouvé dans cette position : c'est soit le coup qui a obtenu le
meilleur score, soit le coup qui a permis une coupe Alpha-Bêta. On l'essaiera en
premier la prochaine fois qu'on rencontrera la position.
- Le score : la valeur retournée par !' Alpha-Bêta dans cette position.
- Le drapeau : il indique si le score est le score exact, si c'est une borne maximale ou
une borne minimale.
- La profondeur : elle indique la profondeur du sous arbre exploré pour évaluer la
position.
Exercice : Définir une classe GenericTranspo qui représente les entrées de la table
de transposition. É crire ensuite un classe Table générique qui prend comme paramètres
template les classes Move, Board et Transpo. É crire les méthodes de cette classe pour
détecter les transpositions et pour aj outer une entrée dans la table en utilisant la stratégie
de la profondeur.
3.6 Utilisation de la table de transposition
Lorsqu'on utilise l'approfondissement itératif les tables de transposition réduisent
beaucoup l'effort de recherche. On a vu qu'on pouvait selon les cas couper directement la
recherche à l'aide des résultats stockés dans une entrée, ou de façon plus courante diriger
la recherche à l'aide des informations stockées.
Question : Lorsqu 'on atteint dans une recherche une position qui a une entrée dans
la table de transposition, comment utilise-t-on les informations stockées dans cette entrée
pour optimiser la recherche ?
Réponse :
Il y a trois possibilités :
- La profondeur qui reste a explorer est inférieure ou égale à la profondeur mémorisée
dans la table, et le score mémorisé est un score exact. La position ne doit alors pas
être explorée plus avant, la valeur retournée est le score contenu dans l'entrée de la
table de transposition.
- La profondeur qui reste à explorer est inférieure ou égale à la profondeur mémorisée
dans la table, et la valeur mémorisée n'est pas la valeur exacte. Le score est utilisé
pour aj uster la valeur de alpha (si le drapeau indique une borne minimale), ou pour
aj uster la valeur de bêta (si le drapeau indique une borne maximale). Si après cet
aj ustement alpha est supérieur à bêta on a une coupe. Sinon on effectue la recherche
et le meilleur coup stocké dans l'entrée de la table est utilisé comme premier coup
à essayer puisqu'il a déjà été évalué comme le meilleur dans cette position.
- La profondeur qui reste à explorer est plus grande que la profondeur mémorisée.
On n'utilise alors que le meilleur coup stocké pour l'essayer en premier. Il y a de
53
différencier les positions qui ont le même indice dans la table de transposition mais
des valeurs de hachage différentes.
- Le meilleur coup trouvé dans cette position : c'est soit le coup qui a obtenu le
meilleur score, soit le coup qui a permis une coupe Alpha-Bêta. On l'essaiera en
premier la prochaine fois qu'on rencontrera la position.
- Le score : la valeur retournée par !' Alpha-Bêta dans cette position.
- Le drapeau : il indique si le score est le score exact, si c'est une borne maximale ou
une borne minimale.
- La profondeur : elle indique la profondeur du sous arbre exploré pour évaluer la
position.
Exercice : Définir une classe GenericTranspo qui représente les entrées de la table
de transposition. É crire ensuite un classe Table générique qui prend comme paramètres
template les classes Move, Board et Transpo. É crire les méthodes de cette classe pour
détecter les transpositions et pour aj outer une entrée dans la table en utilisant la stratégie
de la profondeur.
3.6 Utilisation de la table de transposition
Lorsqu'on utilise l'approfondissement itératif les tables de transposition réduisent
beaucoup l'effort de recherche. On a vu qu'on pouvait selon les cas couper directement la
recherche à l'aide des résultats stockés dans une entrée, ou de façon plus courante diriger
la recherche à l'aide des informations stockées.
Question : Lorsqu 'on atteint dans une recherche une position qui a une entrée dans
la table de transposition, comment utilise-t-on les informations stockées dans cette entrée
pour optimiser la recherche ?
Réponse :
Il y a trois possibilités :
- La profondeur qui reste a explorer est inférieure ou égale à la profondeur mémorisée
dans la table, et le score mémorisé est un score exact. La position ne doit alors pas
être explorée plus avant, la valeur retournée est le score contenu dans l'entrée de la
table de transposition.
- La profondeur qui reste à explorer est inférieure ou égale à la profondeur mémorisée
dans la table, et la valeur mémorisée n'est pas la valeur exacte. Le score est utilisé
pour aj uster la valeur de alpha (si le drapeau indique une borne minimale), ou pour
aj uster la valeur de bêta (si le drapeau indique une borne maximale). Si après cet
aj ustement alpha est supérieur à bêta on a une coupe. Sinon on effectue la recherche
et le meilleur coup stocké dans l'entrée de la table est utilisé comme premier coup
à essayer puisqu'il a déjà été évalué comme le meilleur dans cette position.
- La profondeur qui reste à explorer est plus grande que la profondeur mémorisée.
On n'utilise alors que le meilleur coup stocké pour l'essayer en premier. Il y a de