54
Ta bles de Transposition
bonnes chances qu 'il soit le meilleur dans la recherche en cours puisqu'il a déjà été
le meilleur dans une recherche précédente moins profonde.
Exercice : Adapter l'algorithme Alpha-Bêta appliqué au jeu du virus à l'aide des
classes GenericTranspo et Table pour qu'il utilise une table de transposition.
3. 7 Coupes de transposition améliorée s
Les coupes de transposition améliorées consistent à tester pour chaque fils de la position courante s'il est présent dans la table de transposition et si ses valeurs stockées
permettent de faire une coupe. Pour cela on va jouer chaque coup possible, voir si la position résultante est contenue dans la table de transposition et, si c'est le cas, regarder les
informations stockées pour savoir si elles permettent de faire une coupe. Les coupes de
transposition améliorées permettent de maximiser l'utilisation de l'information contenue
dans les tables de transposition.
Cette optimisation a été utilisée dans Chinook [78] le meilleur programme de Checkers (Dames anglaises). Les arbres de recherche de Chinook ont 22% de noeuds en
moins pour des recherches de profondeur 17 lorsqu'il utilise les coupes de transposition
améliorées [79]. Toutefois, si on essaie les coupes améliorées à tous les niveaux de l'arbre,
la réduction du nombre de noeuds est contrebalancée par le temps additionnel passé dans
chaque noeud à tester les coupes possibles. Les coupes améliorées ne sont donc pas testées dans les deux dernières profondeurs de l'arbre, ce qui permet de réduire le temps
d'exécution tout en gardant les coupes les plus importantes.
Exercice : Intégrer les coupes de transposition améliorées dans l' Alpha-Bêta avec
tables de transpositions.
3.8 La recherche ave c partition
L' idée de la recherche avec partition [37] est de mémoriser un groupe de positions
qui ont des caractéristiques communes plutôt qu' une position à la fois. Si par exemple,
on veut colorier une carte avec trois couleurs et qu'une impossibilité impliquant 5 pays
est détectée, on peut se souvenir de la configuration des 5 pays qui donne toujours une
impossibilité. On peut alors déclarer impossible toutes les cartes qui contienne cette configuration et arrêter la recherche dès que la configuration est reconnue.
Au Bridge on stocke dans une partition les relations d'ordre entre les cartes plutôt que
les cartes elles mêmes. Ainsi une entrée de la table représente de nombreuses positions
pour lesquelles le résultat de la recherche est le même. La résolution de donnes ouvertes
au Bridge va de IO à 100 fois plus vite lorsqu'on utilise les partitions.
Cette technique est liée à l'apprentissage par généralisation [67, 63, 31] qui sélec-
Ta bles de Transposition
bonnes chances qu 'il soit le meilleur dans la recherche en cours puisqu'il a déjà été
le meilleur dans une recherche précédente moins profonde.
Exercice : Adapter l'algorithme Alpha-Bêta appliqué au jeu du virus à l'aide des
classes GenericTranspo et Table pour qu'il utilise une table de transposition.
3. 7 Coupes de transposition améliorée s
Les coupes de transposition améliorées consistent à tester pour chaque fils de la position courante s'il est présent dans la table de transposition et si ses valeurs stockées
permettent de faire une coupe. Pour cela on va jouer chaque coup possible, voir si la position résultante est contenue dans la table de transposition et, si c'est le cas, regarder les
informations stockées pour savoir si elles permettent de faire une coupe. Les coupes de
transposition améliorées permettent de maximiser l'utilisation de l'information contenue
dans les tables de transposition.
Cette optimisation a été utilisée dans Chinook [78] le meilleur programme de Checkers (Dames anglaises). Les arbres de recherche de Chinook ont 22% de noeuds en
moins pour des recherches de profondeur 17 lorsqu'il utilise les coupes de transposition
améliorées [79]. Toutefois, si on essaie les coupes améliorées à tous les niveaux de l'arbre,
la réduction du nombre de noeuds est contrebalancée par le temps additionnel passé dans
chaque noeud à tester les coupes possibles. Les coupes améliorées ne sont donc pas testées dans les deux dernières profondeurs de l'arbre, ce qui permet de réduire le temps
d'exécution tout en gardant les coupes les plus importantes.
Exercice : Intégrer les coupes de transposition améliorées dans l' Alpha-Bêta avec
tables de transpositions.
3.8 La recherche ave c partition
L' idée de la recherche avec partition [37] est de mémoriser un groupe de positions
qui ont des caractéristiques communes plutôt qu' une position à la fois. Si par exemple,
on veut colorier une carte avec trois couleurs et qu'une impossibilité impliquant 5 pays
est détectée, on peut se souvenir de la configuration des 5 pays qui donne toujours une
impossibilité. On peut alors déclarer impossible toutes les cartes qui contienne cette configuration et arrêter la recherche dès que la configuration est reconnue.
Au Bridge on stocke dans une partition les relations d'ordre entre les cartes plutôt que
les cartes elles mêmes. Ainsi une entrée de la table représente de nombreuses positions
pour lesquelles le résultat de la recherche est le même. La résolution de donnes ouvertes
au Bridge va de IO à 100 fois plus vite lorsqu'on utilise les partitions.
Cette technique est liée à l'apprentissage par généralisation [67, 63, 31] qui sélec-