Chapitre 4
Recherche avec menaces
"La menace vaut mieux que l'exécution."
Aaron Nimzowitsch.
4.1 Introduction
Contrairement à I 'Alpha-Bêta qui envisage tous les coups possibles, les raisonnements
humains n'envisagent qu'un très petit nombre de coups et peuvent prévoir des séquences
très profondes en étant très sélectifs. Ils peuvent notamment lire des séquences de coups
forcés très profondes. Ce sont les algorithmes qui permettent d'effectuer ce type de recherche étroite et profonde que nous allons décrire dans ce chapitre.
Les algorithmes de recherche avec menaces [89, 21] sont efficaces dans les jeux pour
lesquels jouer quelques coups de suite du même joueur permet très souvent de gagner. La
notion de menace sera détaillée et formalisée au cours du chapitre.
Il peut être très utile dans les jeux complexes qui ont un grand nombre de coups
possibles à chaque position d'être sélectif et de ne considérer qu'un sous ensemble des
coups possibles. Lorsqu'on envisage tous les coups on a une explosion combinatoire qui
réduit la profondeur à laquelle on peut chercher dans un temps fixé. Il peut être bénéfique
de sélectionner les coups à envisager et d'éliminer des coups à priori inutiles. To utefois,
lorsqu'on choisit d'ignorer des coups on doit éviter deux revers :
- ne pas explorer des coups amis qui vont se révéler gagnants et donc sous évaluer
une position,
- ne pas explorer des coups ennemis qui nous font perdre, et donc croire qu' une
position n'est pas perdante alors qu'elle l'est.
Recherche avec menaces
"La menace vaut mieux que l'exécution."
Aaron Nimzowitsch.
4.1 Introduction
Contrairement à I 'Alpha-Bêta qui envisage tous les coups possibles, les raisonnements
humains n'envisagent qu'un très petit nombre de coups et peuvent prévoir des séquences
très profondes en étant très sélectifs. Ils peuvent notamment lire des séquences de coups
forcés très profondes. Ce sont les algorithmes qui permettent d'effectuer ce type de recherche étroite et profonde que nous allons décrire dans ce chapitre.
Les algorithmes de recherche avec menaces [89, 21] sont efficaces dans les jeux pour
lesquels jouer quelques coups de suite du même joueur permet très souvent de gagner. La
notion de menace sera détaillée et formalisée au cours du chapitre.
Il peut être très utile dans les jeux complexes qui ont un grand nombre de coups
possibles à chaque position d'être sélectif et de ne considérer qu'un sous ensemble des
coups possibles. Lorsqu'on envisage tous les coups on a une explosion combinatoire qui
réduit la profondeur à laquelle on peut chercher dans un temps fixé. Il peut être bénéfique
de sélectionner les coups à envisager et d'éliminer des coups à priori inutiles. To utefois,
lorsqu'on choisit d'ignorer des coups on doit éviter deux revers :
- ne pas explorer des coups amis qui vont se révéler gagnants et donc sous évaluer
une position,
- ne pas explorer des coups ennemis qui nous font perdre, et donc croire qu' une
position n'est pas perdante alors qu'elle l'est.