Chapitre 11
Méthodes de Monte-Carlo pour
les jeux à un joueur
11.1 Introduction
Les applications des méthodes de Monte-Carlo sont nombreuses et vont de la physique
à la finance. Utiliser les méthodes de Monte-Carlo pour les jeux à un joueur consiste à
faire de nombreuses parties aléatoires et à mémoriser la partie qui a amené au meilleur
score. Elles ont permis par exemple d'établir des records du monde au Morpion Solitaire.
Elles s'appliquent aussi à SameGame, au Sudoku ou au Kakuro.
11.2 Recherche Monte-Carlo imbriquée
La recherche Monte-Carlo imbriquée [25] comporte plusieurs niveaux de recherche.
Au niveau le plus bas, elle joue des parties aléatoires. Pour les niveaux supérieurs, le coup
d'un niveau est choisi de la façon suivante : chaque coup possible est essayé et suivi d'un
recherche de niveau inférieur qui donne un score ; le coup qui amène au meilleur score est
choisi.
Au niveau zéro, la recherche Monte-Carlo joue des parties aléatoires (des playouts,
cf algorithme 10). Lorsqu'une partie aléatoire est terminée l'algorithme renvoie le score
obtenu.
Pour les niveau supérieurs à zéro, !'algorithme est !'algorithme 11. A chaque coup de
niveau n, on joue le coup qui a donné le meilleur résultat au niveau n - 1.
Exercice: Calculer la complexité d'une recherche Monte-Carlo imbriquée de niveau
Méthodes de Monte-Carlo pour
les jeux à un joueur
11.1 Introduction
Les applications des méthodes de Monte-Carlo sont nombreuses et vont de la physique
à la finance. Utiliser les méthodes de Monte-Carlo pour les jeux à un joueur consiste à
faire de nombreuses parties aléatoires et à mémoriser la partie qui a amené au meilleur
score. Elles ont permis par exemple d'établir des records du monde au Morpion Solitaire.
Elles s'appliquent aussi à SameGame, au Sudoku ou au Kakuro.
11.2 Recherche Monte-Carlo imbriquée
La recherche Monte-Carlo imbriquée [25] comporte plusieurs niveaux de recherche.
Au niveau le plus bas, elle joue des parties aléatoires. Pour les niveaux supérieurs, le coup
d'un niveau est choisi de la façon suivante : chaque coup possible est essayé et suivi d'un
recherche de niveau inférieur qui donne un score ; le coup qui amène au meilleur score est
choisi.
Au niveau zéro, la recherche Monte-Carlo joue des parties aléatoires (des playouts,
cf algorithme 10). Lorsqu'une partie aléatoire est terminée l'algorithme renvoie le score
obtenu.
Pour les niveau supérieurs à zéro, !'algorithme est !'algorithme 11. A chaque coup de
niveau n, on joue le coup qui a donné le meilleur résultat au niveau n - 1.
Exercice: Calculer la complexité d'une recherche Monte-Carlo imbriquée de niveau