98
Recherche arborescente Monte-Carlo
#include
#include
#include
using namespace s td ;
const int Noir = O;
const int Blanc = 1 .
'
const int Vide = 2 ·
'
const int Exterieur
const int MaxCoups =
=
const int Taille = 9 ;
3;
300;
On définit ensuite une classe Intersection qui va permettre de représenter simplement
les intersections du goban et les coups. On aura souvent besoin de connaître les voisines
d' une intersection et parfois besoin des diagonales, on définit donc des fonctions voisine
et diagonale qui vont permettre de les parcourir avec une boucle :
class Intersection {
public :
} ;
int _X , _y ;
Intersection (int x = 0, int y= 0) {
X = X;
_y =y ;
}
Intersection voisine (int indice ) {
if (indice -- 0) return Intersection
if (indice -- l) return Intersection
if (indice -- 2) return Intersection
if (indice -- 3) return Intersection
}
Intersection diagonale (in t indice) {
if (indice -- 0) return Intersection
if (indice -- l ) return Intersection
if (indice -- 2) return Intersection
if (indice -- 3) return Intersection
}
(_x - l ' _y );
(_x '
_y - 1);
(_x + 1 '
_y );
(_x '
_y + 1);
(_x
l ' _y
1 ) ;
(_x + 1 '
_y
1);
(_x + 1 '
_y + 1);
(_x
l ' _y + 1);
La classe suivante dont nous avons besoin est une classe qui permet de savoir si une
intersection a déjà été visitée, ceci afin d'éviter les boucles infinies mais aussi afin de
ne compter qu' une seul fois chaque liberté. Le principe de cette classe est d' utiliser une
initialisation paresseuse. Les intersections qui ont pour valeur le marqueur courant sont
comptées comme marquées . Ceci permet d' initialiser très rapidementla marquage puis-