5.9 Corrigés des exercices
97
de coups aléatoires aux feuilles de l ' arbre UCT et de remonter l 'évaluation de la position
après ces quelques coups aléatoires. Cela a donné de très bons résultats à Lines of Action
[92) et Amazons [58).
De plus on peut utiliser la recherche arborescente Monte-Carlo en combinaison avec
un résolveur de positions (un programme qui calcule la valeur exacte d'une position).
Cela a donné de bons résultats à Line of Actions [93) et pour la résolution de Seki au Go
[28).
Il existe toutefois des jeux pour lesquels la recherche Monte-Carlo ne donne pas de
bons résultats. C 'est le cas par exemple pour Dots and Boxes car il arrive souvent que des
positions aient un grand nombre de coups possibles et un seul coup gagnant. La recherche
Monte-Carlo qui fait la moyenne sur tous les coups des positions suivantes considère
la position comme perdue alors qu' il y a un coup gagnant. Dans ce type de positions,
l ' Alpha-Bêta n' a pas de problème pour trouver le coup gagnant.
De même au Go, les échelles sont des séquences très simples mais très profondes : il
n ' y a qu' un seul coup à envisager à chaque noeud et on atteint couramment la profondeur
60. La recherche Monte-Carlo qui développe tous les coups possibles d' un noeud avant
de développer plus profondément un coup est aussi perdue dans ces situations.
Toujours au Go, il existe des situations tactiques appelées Semeai pour lesquelles la
seule issue pour un groupe G1 est de tuer un groupe G2 , et la seule issue pour le groupe
G2 est de tuer le groupe G1. Dans les Semeais simples, compter le nombre de libertés des
groupes permet de connaître le gagnant du Semeai. Cependant les simulations MonteCarlo perdent ou gagnent le Semeai dans approximativement 50% des cas si le nombre de
libertés des deux groupes est proche alors que le combat devrait toujours être gagné par
celui qui a le plus de libertés.
5.9 Corrigés des exercices
5.9.1 Parties aléatoires de Go
La classe pour les parties aléatoires de Go que nous présentons n 'est pas une classe
optimisée pour jouer très rapidement. Le choix qui a été fait est plutôt d' avoir un code
aussi simple que possible au détriment parfois de l 'efficacité. Pour le lecteur qui veut aller
plus avant dans la programmation du Go, Fuego [35) est un bon exemple de programme
de Go de haut niveau, qui est de plus un logiciel libre dont on peut lire de code.
Le code que nous allons utiliser commence par les en-têtes et les déclarations de
constantes :
#include
#include
#include
97
de coups aléatoires aux feuilles de l ' arbre UCT et de remonter l 'évaluation de la position
après ces quelques coups aléatoires. Cela a donné de très bons résultats à Lines of Action
[92) et Amazons [58).
De plus on peut utiliser la recherche arborescente Monte-Carlo en combinaison avec
un résolveur de positions (un programme qui calcule la valeur exacte d'une position).
Cela a donné de bons résultats à Line of Actions [93) et pour la résolution de Seki au Go
[28).
Il existe toutefois des jeux pour lesquels la recherche Monte-Carlo ne donne pas de
bons résultats. C 'est le cas par exemple pour Dots and Boxes car il arrive souvent que des
positions aient un grand nombre de coups possibles et un seul coup gagnant. La recherche
Monte-Carlo qui fait la moyenne sur tous les coups des positions suivantes considère
la position comme perdue alors qu' il y a un coup gagnant. Dans ce type de positions,
l ' Alpha-Bêta n' a pas de problème pour trouver le coup gagnant.
De même au Go, les échelles sont des séquences très simples mais très profondes : il
n ' y a qu' un seul coup à envisager à chaque noeud et on atteint couramment la profondeur
60. La recherche Monte-Carlo qui développe tous les coups possibles d' un noeud avant
de développer plus profondément un coup est aussi perdue dans ces situations.
Toujours au Go, il existe des situations tactiques appelées Semeai pour lesquelles la
seule issue pour un groupe G1 est de tuer un groupe G2 , et la seule issue pour le groupe
G2 est de tuer le groupe G1. Dans les Semeais simples, compter le nombre de libertés des
groupes permet de connaître le gagnant du Semeai. Cependant les simulations MonteCarlo perdent ou gagnent le Semeai dans approximativement 50% des cas si le nombre de
libertés des deux groupes est proche alors que le combat devrait toujours être gagné par
celui qui a le plus de libertés.
5.9 Corrigés des exercices
5.9.1 Parties aléatoires de Go
La classe pour les parties aléatoires de Go que nous présentons n 'est pas une classe
optimisée pour jouer très rapidement. Le choix qui a été fait est plutôt d' avoir un code
aussi simple que possible au détriment parfois de l 'efficacité. Pour le lecteur qui veut aller
plus avant dans la programmation du Go, Fuego [35) est un bon exemple de programme
de Go de haut niveau, qui est de plus un logiciel libre dont on peut lire de code.
Le code que nous allons utiliser commence par les en-têtes et les déclarations de
constantes :
#include
#include
#include