50
Ta bles de Transposition
de I' Alpha-Bêta est plus grand quand on cherche les meilleurs coups en premier. Les
tables de transposition associées à l'approfondissement itératif permettent de se souvenir,
pour chaque position cherchée, du meilleur coup trouvé par la recherche précédente sur
cette position. En utilisant les tables de transposition on peut alors essayer en priorité le
meilleur coup trouvé lors de l'itération précédente ce qui permet d'augmenter le nombre
de coupes Alpha-Bêta.
3.2 Hachage d' une position
On veut stocker, au cours d'une recherche arborescente, toutes les positions rencontrées afin de ne pas refaire plusieurs fois les mêmes calculs. On se heurte à un problème
de mémoire, la place nécessaire pour stocker toutes ces positions est généralement trop
grande pour la mémoire disponible. De plus, on veut pouvoir vérifier très rapidement si
une position a déjà été rencontrée. On doit donc associer une position à un nombre qui
sera stocké dans une table de hachage.
La méthode la plus courante pour hacher une position est le hachage de Zobrist [94] .
On associe un nombre aléatoire, fixé une fois pour toutes, à chaque valeur possible de
chaque emplacement possible du damier. On peut aussi utiliser un nombre aléatoire pour
coder la couleur du joueur qui a la main ainsi que d'autres propriétés de la position particulières au jeu. On code la position physique mais aussi certaines propriétés dûes à l'historique de la position (par exemple les droits de roque aux É checs). La valeur de hachage
d'une position est le XOR de tous les nombres aléatoires associés à la position.
L' indice auquel seront stockées les informations liées à une position est la valeur de
hachage tronquée aux n derniers bits pour une table de transposition de taille 2n.
Au Tic-Tac-Toe on a deux nombres aléatoires par case : un pour coder le cas où la case
est blanche, un autre pour coder le cas où elle est noire. On ne fait pas d'opérations pour
les cases vides. On utilise donc 9+9 = 18 nombres aléatoires. Le hachage d'une position
de Tic-Tac-Toe est égal au XOR de tous les nombres aléatoires correspondant à chaque
case.
Exercice : Représenter un damier de Tic-Tac-Toe, écrire une fonction d'initialisation
des nombres aléatoires ainsi qu'une fonction qui calcule la valeur de hachage d'une position.
Exercice : Combien de nombres aléatoires utilise-t-on aux É checs et à quoi correspondent ils ? Qu'en est il pour le jeu du virus ?
Une position est représentée par le XOR des nombres aléatoires qui correspondent aux
propriétés de la position et à la valeur de chaque emplacement. Chaque nombre aléatoire
peut être codé sur 32 ou 64 bits selon la probabilité de collision et d'erreur que l'on
accepte (voir la section suivante sur la probabilité d'erreur).
Ta bles de Transposition
de I' Alpha-Bêta est plus grand quand on cherche les meilleurs coups en premier. Les
tables de transposition associées à l'approfondissement itératif permettent de se souvenir,
pour chaque position cherchée, du meilleur coup trouvé par la recherche précédente sur
cette position. En utilisant les tables de transposition on peut alors essayer en priorité le
meilleur coup trouvé lors de l'itération précédente ce qui permet d'augmenter le nombre
de coupes Alpha-Bêta.
3.2 Hachage d' une position
On veut stocker, au cours d'une recherche arborescente, toutes les positions rencontrées afin de ne pas refaire plusieurs fois les mêmes calculs. On se heurte à un problème
de mémoire, la place nécessaire pour stocker toutes ces positions est généralement trop
grande pour la mémoire disponible. De plus, on veut pouvoir vérifier très rapidement si
une position a déjà été rencontrée. On doit donc associer une position à un nombre qui
sera stocké dans une table de hachage.
La méthode la plus courante pour hacher une position est le hachage de Zobrist [94] .
On associe un nombre aléatoire, fixé une fois pour toutes, à chaque valeur possible de
chaque emplacement possible du damier. On peut aussi utiliser un nombre aléatoire pour
coder la couleur du joueur qui a la main ainsi que d'autres propriétés de la position particulières au jeu. On code la position physique mais aussi certaines propriétés dûes à l'historique de la position (par exemple les droits de roque aux É checs). La valeur de hachage
d'une position est le XOR de tous les nombres aléatoires associés à la position.
L' indice auquel seront stockées les informations liées à une position est la valeur de
hachage tronquée aux n derniers bits pour une table de transposition de taille 2n.
Au Tic-Tac-Toe on a deux nombres aléatoires par case : un pour coder le cas où la case
est blanche, un autre pour coder le cas où elle est noire. On ne fait pas d'opérations pour
les cases vides. On utilise donc 9+9 = 18 nombres aléatoires. Le hachage d'une position
de Tic-Tac-Toe est égal au XOR de tous les nombres aléatoires correspondant à chaque
case.
Exercice : Représenter un damier de Tic-Tac-Toe, écrire une fonction d'initialisation
des nombres aléatoires ainsi qu'une fonction qui calcule la valeur de hachage d'une position.
Exercice : Combien de nombres aléatoires utilise-t-on aux É checs et à quoi correspondent ils ? Qu'en est il pour le jeu du virus ?
Une position est représentée par le XOR des nombres aléatoires qui correspondent aux
propriétés de la position et à la valeur de chaque emplacement. Chaque nombre aléatoire
peut être codé sur 32 ou 64 bits selon la probabilité de collision et d'erreur que l'on
accepte (voir la section suivante sur la probabilité d'erreur).