2.8 L'heuristique de l'historique
21
différents de A, on essaiera en premier comme réponse noire, le coup en B, qui amènera
toujours à une coupe Alpha-Bêta sauf quand blanc a lui même joué en B à la racine.
L'arbre à droite de la position de la figure 2.4 montre le fonctionnement des coups qui
tuent. L' Alpha-Bêta commence par jouer le coup blanc A, puis lorsque noir lui répond en
B, il y a une coupe Alpha-Bêta. Le coup noir en B est donc stocké comme coup qui tue
à la profondeur de B. Lorsque blanc essaie un autre coup à la racine, noir lui répond en
premier le coup qui tue en B.
Exercice : Modifier l' Alpha-Bêta pour lui faire essayer en priorité deux coups qui
tuent. Commencez par déclarer la structure de données qui permettra de mémoriser les
coups qui tuent. Puis écrivez la fonction qui les mémorise, en écrasant le coup le plus
anciennement mémorisé. Modifiez enfin l' Alpha-Bêta pour qu'il joue en priorité deux
coups qui tuent tout en vérifiant qu'ils sont légaux. Faites attention à ce que l' Alpha-Bêta
ne les essayent pas deux fois ce qui serait inutile et coûteux.
2.8 L' heuristique de ) 'historique
L'heuristique de l'historique (history heuristic [75, 76]) consiste à tenir à jour une
note globale pour chaque coup légal rencontré dans l'arbre de recherche qui a amené à
au moins une coupe Alpha-Bêta. À chaque fois qu'un coup amène à une coupe AlphaBêta, sa note est aj ustée d'un montant qui est fonction de la profondeur du sous-arbre
exploré après ce coup. On peut par exemple aj outer 4depth à la note du coup ayant amené
à une coupe, depth étant la profondeur du sous arbre qui a été développé sous le coup.
On ordonne les coups à tester dans l' Alpha-Bêta en fonction de leur note. On commence
par essayer ceux ayant la note la plus élevée. Le principe d'ajouter 4depih à la note du
coup est de privilégier les coups qui ont amené à des coupes proches de la racine : ces
coupes sont plus importantes que les coupes plus éloignées de la racine car elles coupent
des arbres plus profonds et donc plus volumineux. L' heuristique de l'historique amène
à privilégier les coups qui coupent, et parmi ces coups, ceux qui ont coupé proche de
la racine. J. Schaeffer a montré que l'heuristique de l'historique associée aux tables de
transposition est responsable de 99% des réductions de recherche dans !' Alpha-Bêta [76).
En général on trie les coups avec l'heuristique de l 'historique après avoir essayé les autres
coup prioritaires comme le coup de transposition (voir chapitre suivant) et les coups qui
tuent.
Pour programmer l'heuristique de l'historique, on supposera que la classe Coup a
une fonction membre nombre ( ) qui renvoie un nombre associé au coup. Ce nombre
est compris entre 0 et une constante MaxNombre. Dans les jeux où cela est possible, on
programmera la fonction nombre ( ) pour qu'il y ait une bijection entre les coups et les
nombres (c'est par exemple possible au jeu du virus, au Go-Moku, au Go et aux É checs).
Quand ce n'est pas possible en pratique, par exemple aux Dames à cause du grand nombre
de coups de prise possibles, on fera correspondre le même nombre à des coups similaires,
par exemple aux dames en codant dans le nombre le type de pièce, la case de départ et la
case d'arrivée.
21
différents de A, on essaiera en premier comme réponse noire, le coup en B, qui amènera
toujours à une coupe Alpha-Bêta sauf quand blanc a lui même joué en B à la racine.
L'arbre à droite de la position de la figure 2.4 montre le fonctionnement des coups qui
tuent. L' Alpha-Bêta commence par jouer le coup blanc A, puis lorsque noir lui répond en
B, il y a une coupe Alpha-Bêta. Le coup noir en B est donc stocké comme coup qui tue
à la profondeur de B. Lorsque blanc essaie un autre coup à la racine, noir lui répond en
premier le coup qui tue en B.
Exercice : Modifier l' Alpha-Bêta pour lui faire essayer en priorité deux coups qui
tuent. Commencez par déclarer la structure de données qui permettra de mémoriser les
coups qui tuent. Puis écrivez la fonction qui les mémorise, en écrasant le coup le plus
anciennement mémorisé. Modifiez enfin l' Alpha-Bêta pour qu'il joue en priorité deux
coups qui tuent tout en vérifiant qu'ils sont légaux. Faites attention à ce que l' Alpha-Bêta
ne les essayent pas deux fois ce qui serait inutile et coûteux.
2.8 L' heuristique de ) 'historique
L'heuristique de l'historique (history heuristic [75, 76]) consiste à tenir à jour une
note globale pour chaque coup légal rencontré dans l'arbre de recherche qui a amené à
au moins une coupe Alpha-Bêta. À chaque fois qu'un coup amène à une coupe AlphaBêta, sa note est aj ustée d'un montant qui est fonction de la profondeur du sous-arbre
exploré après ce coup. On peut par exemple aj outer 4depth à la note du coup ayant amené
à une coupe, depth étant la profondeur du sous arbre qui a été développé sous le coup.
On ordonne les coups à tester dans l' Alpha-Bêta en fonction de leur note. On commence
par essayer ceux ayant la note la plus élevée. Le principe d'ajouter 4depih à la note du
coup est de privilégier les coups qui ont amené à des coupes proches de la racine : ces
coupes sont plus importantes que les coupes plus éloignées de la racine car elles coupent
des arbres plus profonds et donc plus volumineux. L' heuristique de l'historique amène
à privilégier les coups qui coupent, et parmi ces coups, ceux qui ont coupé proche de
la racine. J. Schaeffer a montré que l'heuristique de l'historique associée aux tables de
transposition est responsable de 99% des réductions de recherche dans !' Alpha-Bêta [76).
En général on trie les coups avec l'heuristique de l 'historique après avoir essayé les autres
coup prioritaires comme le coup de transposition (voir chapitre suivant) et les coups qui
tuent.
Pour programmer l'heuristique de l'historique, on supposera que la classe Coup a
une fonction membre nombre ( ) qui renvoie un nombre associé au coup. Ce nombre
est compris entre 0 et une constante MaxNombre. Dans les jeux où cela est possible, on
programmera la fonction nombre ( ) pour qu'il y ait une bijection entre les coups et les
nombres (c'est par exemple possible au jeu du virus, au Go-Moku, au Go et aux É checs).
Quand ce n'est pas possible en pratique, par exemple aux Dames à cause du grand nombre
de coups de prise possibles, on fera correspondre le même nombre à des coups similaires,
par exemple aux dames en codant dans le nombre le type de pièce, la case de départ et la
case d'arrivée.