Table des matières
9.5 Les heuristiques admissibles
9.6 L'algorithme A * ..
9.7 L'algorithme IDA * ..
9.8 Le Rubik's cube ....
9.9 Corrigés des exercices
9.9. 1 Le voyageur de commerce
9.9.2 L'algorithme A * pour le Taquin
9.9.3 L'algorithme IDA * pour le Taquin
9.9.4 Le Rubik's cube ........ .
10 Bases de patterns
10. 1 Le Taquin . .
10.2 Le Rubik's cube ....... .
10.3 Les bases de patterns additives
10.4 La compression de bases de patterns
10.5 Sokoban . . . . . . . . . . . .
10.6 La vie et la mort au jeu de Go .
10.7 Corrigés des exercices .
10. 7 .1 Le Taquin . . . .
10.7.2 Le Rubik's cube
10.7.3 Bases additives .
11 Méthodes de Monte-Carlo pour les jeux à un joueur
11. l Introduction . . . . . . . . . . . . . . .
11.2 Recherche Monte-Carlo imbriquée . . . . . . . .
11.3 Le problème du choix du coup à gauche . . . . .
11.3.1 Le nombre de coups sur le chemin le plus à gauche
11.3.2 Le nombre de coups à gauche
11.4 SameGame ............. .
11.5 Corrigés des exercices . . . . . . . .
11.5.1 Complexité de la recherche Monte-Carlo imbriquée .
11.5.2 Le nombre de coups sur le chemin le plus à gauche
11.5.3 Le nombre de coups à gauche
11.5.4 SameGame . . . . . . . . . .
12 Problèmes de satisfaction de contraintes
12. 1 Introduction . . . . . . .
12.2 Exemples de Problèmes .
12.3 Le Backtrack ..... .
vii
171
172
173
173
174
174
175
179
179
181
181
182
183
183
183
183
184
184
186
186
187
187
187
188
188
189
190
190
190
190
191
195
203
203
204
204