56
Ta bles de Transposition
3.9.2 Hachage d'une position aux É checs et au jeu du virus
- Aux Échecs, on utilise 12 nombres al éatoires par cas e (u n par pièce différente), plus
4 nombres pour les droits de roques, pl us 16 nombres pour les captures en passant,
et un pour la couleur qui joue. So it 64 x 1 2 + 4 + 16 + 1 = 789 nombres al éatoires.
- Au jeu du virus, on utilise seuleme nt 98 nombres al éatoires, deux par case. Il est
inutile d'avoir un nombre pour la couleur du joueur puisqu'il est impossible d'avoir
deux positions ide ntiques avec deux coul eurs à jouer différentes lorsque le mê me
joueur comme nce à jouer (c haque cou p aj ou te une pièce).
3.9.3 Hachage incrémental au Tic-Tac-Toe
void joue ( int x, int y, int coul eur) {
damier [x] [y] = couleur ;
}
if (couleur == Noir)
hash "= Ha shA rray [x] [y] [0] ;
el se if (couleur == Blanc)
hash "= Ha shA rray [ x] [y] [ 1] ;
void dejoue ( int x, int y, int coul eur) {
damier [x] [y] =V ide ;
}
i f ( c o u 1 e u r == Noir )
hash "= Ha shA rray [x] [y] [0] ;
else if (coul e ur == Blanc)
hash "= Ha shA rray [x] [y] [1] ;
3.9.4 Probabilité d'erreur
p = ( 1 - -k) X ( 1 - il) X ... X ( 1 - M N l )
Si M est petit par rap port a N, on peut faire l'ap proximat ion suivante:
P ,... .., l
_
1+2+ ... +(M-1) ,... .., l
_
M 2
-
N
-
2N
Pour les x positifs proches de 0, on a log( l - x) '.::: :'. -x, donc log(P) '.::: :'. - M( � - l )
,
M(M-1)
M2
d'où, pour des M as sez grands P '.::: :'. e - ----v v- '.::: :'. e - 2N
La probabilité d'avoir au moi ns une erreur est de 1 - P. Pour une valeur de hachage
sur 32 bits et une recherche qui utilise 10 millions de fois la table de trans position, la
10 1 4
probabil ité d'avoir au moi ns une erreur de ty pe 1 est E '.::: :'. 1 - e - 23l"' '.::: :'. 1, ce qui veut
dire qu'on est presque certai n d'avoir une erreur. Pour 64 bits, on obtient E '.::: :'. 2.7 * 10-6
ce qui est bie n meilleur. En pratique pour des recherches de pl usieurs millions de noeuds,