190
Méthodes de Monte-Carlo pour le s jeux à un joueur
Exercice : Écrire un programme qui calcule ces probabilités
Exercice : Écrire un programme qui joue au problème du nombre de coups à gauche
avec un Monte-Carlo imbriqué
11.4 SameGame
SameGame est un puzzle NP-complet [48]. Une position est une grille de cases colorées. Un coup consiste à retirer des régions connexes de la même couleur pour marquer
des points. Le nombre de points marqués par un coup est (nombre de cases retires-2) 2 .
Les cases au dessus des cases retirées tombent après un coup, de plus si une colonne devient vide, les colonnes sur sa droite sont décalées vers la gauche pour la combler. Lorsque
toutes les cases ont été retirées à la fin de la partie, on gagne un bonus de 1000 points.
SameGame se prête bien à une résolution par la méthode de Monte-Carlo imbriquée.
Une stratégie de playouts qui se révèle efficace est de ne jouer la couleur dominante que
lorsqu'il n'y a plus de coups d'autres couleurs [73]. De cette façon on retirera toutes les
cases de la couleur dominante à la fois amenant ainsi à un coup de score maximal.
Exercice : Utiliser le Monte-Carlo imbriqué pour résoudre des problèmes de SameGame.
11.5 Corrigés des exercices
11.5.1 Complexité de la recherche Monte-Carlo imbriquée
Le nombre de coups d'un playout est t0(h, l) = h. Le nombre de coups d'un playout
de niveau l est t1(h, a) = a x L o < i < h t1- 1 (i, a). Une recherche de niveau un jouera
a x h 2 /2 coups. Une recherche de niveau lest en O(a
1 hl+ 1 ).
11.5.2 Le nombre de coups sur le chemin le plus à gauche
Un playout a une probabilité 2-n de trouver la meilleure solution. Une recherche
imbriquée de niveau un a une probabilité un de trouver la meilleur solution. La complexité
de la recherche de niveau un est O(n 2 ).
Méthodes de Monte-Carlo pour le s jeux à un joueur
Exercice : Écrire un programme qui calcule ces probabilités
Exercice : Écrire un programme qui joue au problème du nombre de coups à gauche
avec un Monte-Carlo imbriqué
11.4 SameGame
SameGame est un puzzle NP-complet [48]. Une position est une grille de cases colorées. Un coup consiste à retirer des régions connexes de la même couleur pour marquer
des points. Le nombre de points marqués par un coup est (nombre de cases retires-2) 2 .
Les cases au dessus des cases retirées tombent après un coup, de plus si une colonne devient vide, les colonnes sur sa droite sont décalées vers la gauche pour la combler. Lorsque
toutes les cases ont été retirées à la fin de la partie, on gagne un bonus de 1000 points.
SameGame se prête bien à une résolution par la méthode de Monte-Carlo imbriquée.
Une stratégie de playouts qui se révèle efficace est de ne jouer la couleur dominante que
lorsqu'il n'y a plus de coups d'autres couleurs [73]. De cette façon on retirera toutes les
cases de la couleur dominante à la fois amenant ainsi à un coup de score maximal.
Exercice : Utiliser le Monte-Carlo imbriqué pour résoudre des problèmes de SameGame.
11.5 Corrigés des exercices
11.5.1 Complexité de la recherche Monte-Carlo imbriquée
Le nombre de coups d'un playout est t0(h, l) = h. Le nombre de coups d'un playout
de niveau l est t1(h, a) = a x L o < i < h t1- 1 (i, a). Une recherche de niveau un jouera
a x h 2 /2 coups. Une recherche de niveau lest en O(a
1 hl+ 1 ).
11.5.2 Le nombre de coups sur le chemin le plus à gauche
Un playout a une probabilité 2-n de trouver la meilleure solution. Une recherche
imbriquée de niveau un a une probabilité un de trouver la meilleur solution. La complexité
de la recherche de niveau un est O(n 2 ).