20
Minimax, Alpha-Bêta et heuristiques assoc iées
A
B
position
arbre
FIGURE 2.4 - La réponse noire Ba u coup blanc A est un coup qui tue au Go-Moku.
importantes pour maximiser le nombre de coupes Alpha-Bêta dans la recherche courante.
En effet, les coups qui ont été les meilleurs dans la recherche à la profondeur précédente
ont de bonnes chances d'être aussi les meilleurs pour la profondeur courante, et en essayant les meilleurs coups en premier, on augmente le nombre de coupes Alpha-Bêta.
Nous reviendrons sur cette optimisation dans le chapitre sur les tables de transposition.
Exercice : Programmer l'approfondissement itératif pour le jeu du virus.
2. 7 L' heuristique des coups qui tuent
L'ordre dans lequel on considère les coups a une grande influence sur l'efficacité de
l'algorithme Alpha Bêta. Les coups·qui tuent (killer moves) amènent souvent à des coupes
Alpha-Bêta. Le principe des coups qui tuent est d'essayer en priorité pour une position
à profondeur donnée des coups qui ont déjà amenés à une coupe Alpha-Bêta pour des
positions à cette profondeur. On peut mémoriser un ou plusieurs coups qui tuent pour
chaque profondeur de recherche.
La figure 2. 4 donne un exemple de coup qui tuent au Go-Moku (le but est d'aligner
5 pierres en jouant chacun son tour sur une grille carrée). Si blanc joue en A, la réponse
noire en B gagne la partie. Elle amène donc à une coupe Alpha-Bêta, et on mémorise à la
profondeur de B le coup noir B comme coup qui tue. Pour tous les coups blancs à la racine
Minimax, Alpha-Bêta et heuristiques assoc iées
A
B
position
arbre
FIGURE 2.4 - La réponse noire Ba u coup blanc A est un coup qui tue au Go-Moku.
importantes pour maximiser le nombre de coupes Alpha-Bêta dans la recherche courante.
En effet, les coups qui ont été les meilleurs dans la recherche à la profondeur précédente
ont de bonnes chances d'être aussi les meilleurs pour la profondeur courante, et en essayant les meilleurs coups en premier, on augmente le nombre de coupes Alpha-Bêta.
Nous reviendrons sur cette optimisation dans le chapitre sur les tables de transposition.
Exercice : Programmer l'approfondissement itératif pour le jeu du virus.
2. 7 L' heuristique des coups qui tuent
L'ordre dans lequel on considère les coups a une grande influence sur l'efficacité de
l'algorithme Alpha Bêta. Les coups·qui tuent (killer moves) amènent souvent à des coupes
Alpha-Bêta. Le principe des coups qui tuent est d'essayer en priorité pour une position
à profondeur donnée des coups qui ont déjà amenés à une coupe Alpha-Bêta pour des
positions à cette profondeur. On peut mémoriser un ou plusieurs coups qui tuent pour
chaque profondeur de recherche.
La figure 2. 4 donne un exemple de coup qui tuent au Go-Moku (le but est d'aligner
5 pierres en jouant chacun son tour sur une grille carrée). Si blanc joue en A, la réponse
noire en B gagne la partie. Elle amène donc à une coupe Alpha-Bêta, et on mémorise à la
profondeur de B le coup noir B comme coup qui tue. Pour tous les coups blancs à la racine