Rapport

Des neurones pour le Go

Maurin Benjamin, Giner Steve , Madi Wamba Gilles, Bouregba Amine

2013

2

Table des matières

1 Remerciements 3

2 Introduction 4

2.1 Présentation du rapport . . . . . . . . . . . . . . . . . . . . . 42.2 Présentation du groupe . . . . . . . . . . . . . . . . . . . . . . 5

3 Jeu de Go et l'IA 6

3.1 Jeu de Go . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63.2 Le Go, un dé� . . . . . . . . . . . . . . . . . . . . . . . . . . . 63.3 Etude de l'existant . . . . . . . . . . . . . . . . . . . . . . . . 9

3.3.1 MoGo . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.3.2 MachiaBot . . . . . . . . . . . . . . . . . . . . . . . . 10

3.4 Une nouvelle approche . . . . . . . . . . . . . . . . . . . . . . 113.4.1 L'apprentissage . . . . . . . . . . . . . . . . . . . . . . 113.4.2 Notre approche . . . . . . . . . . . . . . . . . . . . . . 11

4 UCT 12

4.1 Le problème du bandit Manchot . . . . . . . . . . . . . . . . 124.2 L'algorithme UCT . . . . . . . . . . . . . . . . . . . . . . . . 134.3 Notre implémentation de UCT . . . . . . . . . . . . . . . . . 14

5 L'algorithme RAVE 16

5.1 Présentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165.2 Notre implémentation . . . . . . . . . . . . . . . . . . . . . . 17

6 Réseau de neurones 19

6.1 Un système d'apprentissage . . . . . . . . . . . . . . . . . . . 196.2 FANN : une librairie C++ . . . . . . . . . . . . . . . . . . . . 206.3 Le parseur SGF . . . . . . . . . . . . . . . . . . . . . . . . . . 206.4 L'apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . 216.5 L'utilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1

7 Résultat et comparaison 24

7.1 Mécanisme des tests . . . . . . . . . . . . . . . . . . . . . . . 247.2 UCT : 2

50 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257.3 UCT + RAVE : 11

50 . . . . . . . . . . . . . . . . . . . . . . . . 257.4 UCT + Réseau de Neuronnes : 4

50 . . . . . . . . . . . . . . . . 257.5 UCT + RAVE + Réseau de Neuronnes : 9

50 . . . . . . . . . . 26

8 Outils Utilisés 27

8.1 Gogui . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278.2 Le dépôt SVN . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

9 Gestion du projet 29

9.1 Organisation du projet . . . . . . . . . . . . . . . . . . . . . . 299.1.1 Planning prévisionnel et réel . . . . . . . . . . . . . . . 299.1.2 Organisation avec les tuteurs . . . . . . . . . . . . . . 309.1.3 Organisation avec le groupe . . . . . . . . . . . . . . . 30

9.2 Le Gestionnaire de projet . . . . . . . . . . . . . . . . . . . . 30

10 Structure du programme 32

11 Conclusion 34

11.1 Bilan du projet . . . . . . . . . . . . . . . . . . . . . . . . . . 3411.2 Bilan personnel . . . . . . . . . . . . . . . . . . . . . . . . . . 3411.3 Notre apport dans le domaine de l'IA . . . . . . . . . . . . . . 3511.4 Travaux futurs . . . . . . . . . . . . . . . . . . . . . . . . . . 35

12 Annexes 36

12.1 La règle du jeux . . . . . . . . . . . . . . . . . . . . . . . . . . 3612.1.1 Apprendre à jouer . . . . . . . . . . . . . . . . . . . . 3612.1.2 Libertés . . . . . . . . . . . . . . . . . . . . . . . . . . 3612.1.3 Ko . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3812.1.4 Fin d'une partie . . . . . . . . . . . . . . . . . . . . . 3912.1.5 Territoires . . . . . . . . . . . . . . . . . . . . . . . . . 39

12.2 Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2

1 Remerciements

Tout d'abord, nous tenons à remercier tout particulièrement GuillaumeTisserant et Pierre Pompidor pour leur fort soutien tout au long du projet. Ilsétaient toujours disponibles pour nous aiguiller et répondre à nos nombreusesquestions. Ce projet étant compliqué et ambitieux, leur aide nous a été trèsprécieuse pour nous permettre d'avancer étape par étape dans notre travail.Ensuite, nous tenons à remercier toute l'équipe enseignante du départementinformatique de l'Université Montpellier 2 dont la majorité des cours a étéutile pour la réalisation de notre projet.

3

2 Introduction

2.1 Présentation du rapport

Ce rapport présente notre travail sur l'Intelligence Arti�cielle au jeu deGo. Ce projet s'est déroulé dans le cadre d'un TER de Master 1 en Informa-tique de Montpellier.Ce TER n'était pas de base dans la liste des projets proposés mais, étanttrès intéressés par ce sujet, nous avons proposé à Guillaume Tisserant derelancer et encadrer ce projet. Grâce à lui et Pierre Pompidor, nous avonsdonc pu nous lancer dans un projet qui nous tenait à coeur.

Le jeu de Go est le dernier jeu de plateau à résister à l'informatique. Ceserait une grande avancée d'avoir une Intelligence Arti�cielle (IA) à un bonniveau. Ce projet est donc un dé� pour l'informatique. Il existe des IA surle Net mais la plupart travaillent sur des systèmes de formes ou avec UCTet donc ne re�ètent pas le comportement humain.Nous avons donc décidé de faire une IA du jeu de Go. Pour ce faire, nousavons récupéré le projet Machiabot de Guillaume Tisserant pour avoir unebase pour travailler (nous n'avons gardé que peu de choses car nous ne tra-vaillons pas sur le même objectif).Le but de ce projet n'est pas de faire une IA parfaite, car ceci est impossiblepour nos machines, mais d'essayer d'avoir une IA meilleure ou en tout casde faire avancer ce domaine. Un autre objectif est d'en apprrendre plus surl'IA et les di�érentes approches pour résoudre ces problèmes.

Ce rapport décrira les di�érentes méthodes qui ont été implémentées parnotre groupe et les résultats obtenus. Dans ce projet, nous nous sommesconcentrés sur la combinaisons de 3 méthodes : UCT (upper con�dence ap-plied to trees), RAVE (Rapid Value Action Estimate), et les réseaux deneurones. Nous sommes les premiers à essayer de combiner ces 3 méthodes,nous n'avions donc aucune idée du résultat �nal.

4

Nous avons décidé de nous concentrer sur le plateau 9x9. Ceci pour deuxraisons. Tout d'abord, les algorithmes que nous avons implémentés sont trèsgourmands en mémoire et en temps de calcul, un plateau plus grand au-rait vite fait dépasser les capacité de nos machines. Ensuite, il est toujourspréférable de s'attaquer à un problème plus simple au début, surtout dansdes problèmes orientés recherche, pour éviter d'être submergé par les di�-cultés.

2.2 Présentation du groupe

Nous sommes un groupe de 4 étudiants en master 1 informatique deMontpellier, mais nous n'avons pas tous les mêmes options. En e�et, AmineBouregba et Gilles Madi Wamba font partie de l'option Moca qui est ori-enté optmisation, calculabilité et méthodes approchés alors que BenjaminMaurin et Steve Giner font partie d'Imagina qui est orienté images,jeuxvidéos, simulateur et IA des jeux. Nous avons donc des visions di�érentesde l'informatique et des compétences assez éloignées, mais nous étions tousintéressés par ce sujet d'une part la complexité des algorithmes en jeu etleurs optimisations et d'autre part pour la simulation d'intelligence humainepar l'apprentissage des réseaux de neurones. Nous avons pu partager nosconnaissances pour construire notre code et nos idées de développement.

5

3 Jeu de Go et l'IA

3.1 Jeu de Go

Le jeu de Go est un jeu d'origine chinoise vieux de quatre mille ans. Ilest très populaire au Japon, en Chine et en Corée où il existe des joueursprofessionnels. Il ne s'est développé que récemment aux Etats-Unis et en Eu-rope où il n'existe que de forts amateurs. Il se joue à deux avec des pierresnoires et blanches sur un damier de taille variable (en général 19X19, 9X9ou 13X13) appelé le goban. Le but du jeu est de dominer plus d'intersections(appelé alors territoire) que son adversaire en connectant ses propres pierreset en capturant les pierres adverses.Nous conseillons aux non-joueurs de Go de lire les règles du jeu de God'abord. Elles sont présentées en annexe.

3.2 Le Go, un dé�

De nos jours, les ordinateurs sont les champions incontestés aux dames,aux échecs, à l'Othello et à bien d'autres jeux. Cependant, le jeu de Go est unde ces jeux restant un dé� pour l'intelligence arti�cielle. En e�et, à ce jour,aucun programme ne peut battre des joueurs professionnels sans de nom-breuses pierres d'avance. Un des exploits les plus récents vient de MoGo, unprogramme qui a battu Li-Chen Chien (pro 1 dan) à 6 pierres de handicapen février 2009 (source : http://interstices.info/ [réf 1]).

Le Go reste un dé� pour plusieurs raisons :

� Un trop grand arbre des possibles

Un plateau en 19X19 possède 361 intersections, alors qu'un plateaud'échecs n'en possède que 64. De plus, chaque coup peut se poser surpresque toutes les cases. Aux échecs, seuls quelques mouvements sontpossibles. Ainsi, au premier coup, 361 coups sont possibles au Go con-tre 20 aux échecs. Ce trop grand nombre de possibilités rend impossiblel'utilisation d'algorithmes d'explorations, même pour des supercalcula-teurs. Ainsi, Les approches classiques ne marchent pas et les program-meurs doivent trouver de nouvelles pistes.

6

� L'estimation d'une situation est très compliquée

Sur d'autres jeux, il est en général possible d'évaluer chaque situa-tion pour determiner si elle est bonne ou mauvaise. Par exemple, onpeut évaluer une situation aux échecs en fonction du nombre de piècesrestantes et de leur position. Au Go, il n'existe pour le moment pas defonction d'évaluation. Un humain peut estimer à partir de son ressentisi telle situation est meilleure qu'une autre, mais sans avoir de formuleou calcul précis en tête. L'absence de fonction d'évaluation compliquebeaucoup la création d'algorithmes rapides.

� Le jeu de Go et la notion de compétition pour la survie

L'être humain dans son espace réel doit faire face à des situations dansson quotidien, l'appellant à faire usage de ses cinq sens.Il est ainsi chaque jour appellé à gérer des situations dans lesquelles ildoit percevoir des informations visuelles, auditives, tactiles, olfactiveset même gustatives, qu'il doit intégrer pour prendre des décisions.En outre, dans sa vie, tout être vivant, et l'être humain en particulier,est confronté à une compétition de survie face à ses congénaires.On peut ainsi transposer cette situation dans une partie de Go, pourlaquelle le Goban repésenterait l'espace vital, dans lequel le joueurserait en compétition avec son adversaire non pas pour la survie, maispour remporter la partie.Ceci dit, l'avantage d'être un humain dans une telle partie est indé-niable, tant du fait qu'il est habitué depuis sa naissance à ce genrede situation, mais aussi du fait que dans la vie réelle elles sont pluscomplexes. En e�et pour jouer au Go, le seul sens mis en contributionest la vue, pour notamment percevoir les positions des pières sur leGoban, contrairement à sa vie de tous les jours où il fait appel à tousses sens, souvent en même temps.

� La force de perception

Au jeu de Go, il est crucial pour le joueur d'avoir à tout momentdes informations précises sur l'état du Goban : Les formes, les sur-faces, les territoires, les frontières, les zones d'in�uence... Certes uneIA peut récuperer ces informations par un mécanisme de reconnais-sance de formes par exemple, mais celà demande un certain temps etdes ressources de calcul, là où un humain les perçoit quasiment incon-sciement.Cette faculté de perception quasi instantanée représente un gros avan-tage pour le joueur humain, et un véritable dé�s pour les concepteursd'IA.

7

� Le joueur humain est conscient et �exible

Le joueur humain perçoit des informations sur la situation actuelle duGoban, et en fonction de cela est capable de juger et de justi�er lapertinence d'un coup. En outre, il est capable d'adopter une stratégie,et de la changer plus tard lorsqu'il se rend compte que face au jeu del'adversaire elle n'est pas pertinente.En gros, le joueur de Go ne devrait pas se limiter pas à observer lacon�guration du Goban, mais il doit aussi être capable d'etudier lescoups de son adversaire, et en fonction de cela adopter la meilleurestratégie.Ce comportement requiert une certaine conscience et une �exibilité.Contrairement à un joueur humain, une IA n'en dispose pas.

� La façon de jouer au Go re�ète la personnalité du joueur

Au jeu de go, il arrive des situations où il faudrait décider quand jouerà l'o�ensive ou à la défensive,de manière active ou passive.Il est bien entendu insensé de dire que l'une ou l'autre de ces stratégiesest meilleure que l'autre, cependant, de façon inconsciente, certainsjoueurs, en fonction de leur personnalité s'orienteront vers un style dejeu o�ensif tandis que d'autre le feront vers un style de jeu plutôt de-fensif. "Go" en chinois se dit d'ailleurs "Wei-chi", qui signi�e "dialoguemanuel".

La programmation d'une IA de jeu de Go est donc un dé� pour l'intel-ligence arti�cielle.En e�et, jouer au Go requiert des facultés de perception,de décision,et d'adaptation dont dispose le joueur humain vivant dans lemonde réel,ce qui lui donne ainsi un avantage considérable sur la machine,dépourvue de ces facultés.Toutes ces di�cultés font du Go un jeu intéréssant du point de vue informa-tique. Beaucoup d'algorithmes utilisés par les programmeurs pour le jeu deGo, ne sont pas spéci�ques à ce domaine. Améliorer ces algorithmes perme-ttrait donc d'améliorer l'informatique dans son ensemble.

8

3.3 Etude de l'existant

Dans cette partie, on va s'intéresser à quelques programmes jouant auGo. Il existe plusieurs programmes jouant au go, mais la plupart ne sont paslibres et gratuit. On va donc étudier quelques programmes connus : MoGoet Machiabot.

3.3.1 MoGo

MoGo est le meilleur programme de joueur de Go actuellement. Il a étécrée par Sylvain Gelly et est développé par Olivier Teytaud au sein du LRI,dans l'équipe Apprentissage et Optimisation. En Juillet 2008, pour la pre-mière fois, un supercalculateur sur lequel tourne le programme MoGo bat unprofessionnel avec 9 pierres d'avance pour l'ordinateur. Plus tard, en Février2009, MoGo gagne une partie avec 7 pierres d'avance contre un des meilleursjoueurs de notre époque, Zhou Junxun. En aout 2009, Zhou Junxun pren-dra sa revanche, et vaincra les programmes Many Faces of Go, MoGo, et Zen.

Fonctionnement global

Le fonctionnement global de ce programme est de rechercher à chaquefois un coup à partir de parties générées aléatoirement. A chaque coup, leprogramme lance plusieurs parties. Puis il essaye de regarder leurs ratios devictoires pour estimer la valeur de ces coups. De plus, MoGo est amélioré parun module de reconnaissance de patterns. Les patterns ont été récupérés àpartir de bases de parties jouées par des professionnels. Et grâce à ce module,les parties sont plus réalistes et les probabilités de victoires, pour un coups,sont plus grandes.

MoGo a une bonne IA qui ré�ichit bien. Mais il a certaines faiblesses.Parmi ces faiblesses, le problème de simiai : Le semiai est une course devitesse entre deux groupes qui ne peuvent pas vivre sur place à moins decapturer le groupe adverse, où la mort de l'un entraîne automatiquement lasurvie de l'autre. Lorsque ce cas se présente il est bien de ne pas perdre detemps en allant jouer ailleurs sur le plateau. Il est absolument nécéssaire jouerce coup pour mieux avoir chance et gagner la partie. Mogo a énormement demal à gérer ce genre de situations car il s'intéresse à un grand nombres decoups possibles.

9

3.3.2 MachiaBot

Machiabot est un programme développé principalement par GuillaumeTisserant et Guillaume Maurin qui joue avec un style le plus proche possiblede celui d'un être humain.C'est le programme qui nous a servi de base pour développer notre applica-tion.

Fonctionnement global

Machiabot est basé sur trois modules :

-Un outil de reconnaissance de formes, basé sur les dictionnaires, capablede reconnaître dans la partie des formes données précédemment par un ex-pert.-Un gestionnaire de règles capable de transformer en code C++ des règleslogiques données par un expert.-Un module UCT/RAVE.

Le module de reconnaissance de forme fait la particularité de Machi-abot. Ce module améliore de mannière générale son niveau, dans le sens où,comme un humain, Machiabot est capable de reconnaître di�érentes formes,précemment fournies par un expert.

10

3.4 Une nouvelle approche

3.4.1 L'apprentissage

L'apprentissage est une des techniques utilisées dans l'intelligence arti�-cielle. Le principe est le suivant : Un programme adapte son comportementen fonction de données empiriques. Il existe plusieurs types d'apprentissage :

- Aprentissage supervisé : Il se passe en deux phases. Une phase d'ap-prentissage où un expert transmet des données rattachées à des étiquettesau programme, et une phase où le programme determine un comportementen fonction d'une situation et de ce qu'il a appris.

- Aprentissage non-supervisé : Le programme apprend sans expert enfonction des données non étiquettées qu'il perçoit lors de son exécution.

- Apprentissage par renforcement : l'algorithme apprend un comporte-ment étant donné une observation. L'action de l'algorithme sur l'environ-nement produit une valeur de retour qui guide l'algorithme d'apprentissage.

L'apprentissage est une manière d'imiter l'humain de ré�échir. Le Goétant un jeu qui demande une ré�exion très "humaine", l'apprentissage peutêtre une approche intéréssante. Un programme n'étant pour le moment pasvraiment capable d'analyser seul une situation, un apprentissage superviséoù un humain explique les bonnes et mauvaises situation au programmesemble être le plus pertinent.

3.4.2 Notre approche

De nombreuses méthodes et de nombreux algorithmes ont été utiliséspour tenter de trouver une IA e�cace pour le Go. L'algorithme UCT basésur Monte-Carlo est très utilisé depuis sa création en 2006. L'algorithmeRAVE est également très utilisé pour compléter UCT (ces deux algorithmessont expliqués dans le rapport). Nous avons implémenté ces deux algorithmestrès classiques pour avoir une base �able.L'apprentissage s'appliquant bien en théorie au jeu de Go, notre approcheest de compléter UCT-RAVE par de l'apprentissage. Ceci est plûtot novateurpuisque à notre connaissance, peu ou pas de programmeurs ont tenté cetteexperience. Les réseaux de neurones sont généralement utilisés seuls.Comme technique d'apprentissage, nous avons opté pour un apprentissagesupervisé via un réseau de neurones. Les réseaux de neurones s'appliquentbien au Go : il calque le comportement du cerveau humain. De plus, Lesréseaux de neurones ont déja été utilisés pour le jeu de Go (Par exemple parIlya Sutskever et Vinod Nair de l'Université de Toronto).

11

4 UCT

En 1997, le programme Deeper Blue de IBM remporte pour la premierefois une partie contre un champion du monde aux echecs, Gary Kasparov(Champion du monde d'échecs de 1985 à 2000), en utilisant une approchede recherche aborescente Minimax. Cependant le jeu de go est plus di�cileà programmer dans le sens où le nombre de mouvements à prévoir est quasi-illimité.L'algorithme UCT a été developpé pour des jeux comme le Go où l'approchede recherche arborescente par minimax est impossible. Elle est basée dansla resolution du problème du Bandit Manchot que nous décrivons dans lasection qui suit.

4.1 Le problème du bandit Manchot

Pour expliquer le problème du Bandit Manchot, considerons la situationsuivante : Un joueur en face de n machines à sous, chacune des machinesa une certaine probabilité ( constante ) de gagner. Le but du joueur, ayantun nombre limité de jetons est de trouver la machine o�rant la meilleureprobabilité de gagner, et ainsi maximiser les gains sur cette dernière.

Intuitivement, l'idée serait d'e�ectuer une série de tests (un certain nom-bre de mises ) sur chacune des machines, et de continuer après avec celleayant o�ert le plus de gains pendant la phase de tests. Cependant cettesolution qui semble interessante pose un dilemme, celui de l'exploration

contre l'exploitation.

En gros ici, le terme exploitation est un paramètre qui dépend desgains obtenus sur une machine, tandis que le terme exploration quand àlui dépend en gros du nombre de tests e�ectués sur une machine. Une foisde plus, il semble évident que, le but du joueur étant de maximiser ses gains,il devrait prendre en considération le paramètre d'exploitation. Le dilemmeest donc le suivant : En supposant avoir e�ectué un nombre k de tests ( kmises ) sur chacune des machines, une certaine machine x se montre la plusrentable, rien ne nous garantie que dans l'absolu, c'est cette machine x quiest en e�et la plus rentable.

12

Il se peut probablement qu'en fait la machine y soit la plus rentable, maisdû par exemple au faible nombre de tests, elle parrait être moins rentable.Ceci dit, il en demeure qu'il est impossible à l'avance de connaitre le nom-bre de tests à e�ectuer pour connaitre avec certitude la machine o�rant lameilleure probabilité de gains, le but de l'algorithme du Bandit Manchot estdonc de reduire au maximum le risque de se tromper, et de miser le plus surune mauvaise machine.

Auer et Al. ont proposé dans l'article [ACBF02] une methode de sélectionpour minimiser ce risque, de façon logarithmique, UCB1 , publié pour lapremière fois par Agrawal.

Le gain de chaque machine est compris dans l'intervalle [0; 1].Avant d'utiliser cette methode de sélection, on doit jouer au moins une fois(phase de tests) sur chaque machine, pour avoir des informations sur la dis-tribution des gains.

Initialisation jouer k fois sur chaque machine.

Loop : Jouer sur la machine qui maximise

x̄i + C ×√

lnnni

(Ratio UCB1 )

k est un nombre entier supérieur ou égal à 1.x̄i est la moyenne de gain obtenue jusqu'à présent à partir de la machine in c'est le nombre total de mises e�ectuées.La constante C est un paramètre qui peut être ajustée en fonction du prob-lème.

4.2 L'algorithme UCT

UCT est une extension de UCB1 pour la recherche dans un arbre. Lebut est de céer, itérativement un arbre de recherche dans lequel un noeudrepresente une con�guration du Goban, et ses �ls, des coups jouables à partirde cette con�guration, jusqu'aux feuilles, (chaque feuille représentant alorsune �n de partie) et s'en servir pour sélectionner les coups à jouer à chaquefois.Pour cela, l'idée en gros c'est, en partant du noeud racine, considérer chaquenoeud comme un problème (indépendant des autres) de Bandit Manchot,et de considérer ses noeuds �ls comme des machines indépendantes surlesquelles "miser un jeton" c'est explorer le noeud. L'algorithme consistealors à jouer plusieurs séquences de bandit manchot pendant une certainepériode de temps, chacune commençant de la racine et se terminant sur unefeuille.

13

Figure 4.1 � Algorithme UCT, extrait de l'article On the Huge Bene�t

of Decisive Moves in Monte-Carlo Tree Search Algorithms de FabienTeytaud et Olivier Teytaud[réf 6]

4.3 Notre implémentation de UCT

Fortement inspiré de l'articleMonte-Carlo Tree Search, UCT, computer-

Go and all that stu� de Olivier Teytaud [réf 7], le fonctionnement de UCTtel que nous l'avons implémenté peut être décris par les 6 étapes suivantes :

1. Au debut, on a en mémoire un arbre avec un seul noeud qui représentel'état actuel du Goban.

2. Ensuite, partant de la racine, on cherche un chemin jusqu'à une feuille ;Pour chaque noeud, on choisit le �ls ayant le meilleur ratio UCB1, pourle cas on parle du ration exploration/exploitation.

14

� Le paramètre exploitation c'est le pourcentage de simultions gagnées,en passant par ce �ls.

� Le paramètre exploration c'est la racine carré du ratiolog(nbdesimulationsdupere)/(nbdesimulationsdecefils)

3. Jouer ensuite aléatoirement de cette feuille jusqu'à la �n de partie.

4. Mettre ensuite à jour les statistiques dans l'arbre,le nombre de passagesur chaque noeud et le nombre de victoires de blanc et noir.

5. Si le temps imparti pour jouer n'est pas épuisé, on retourne a l'étape2

6. Finalement, jouer le coup le plus simulé à partir de la racine.

Figure 4.2 � Principe de fonctionnement d'UCT

15

5 L'algorithme RAVE

5.1 Présentation

UCT dispose d'une valeur pour chaque noeud dans son arbre. Il ne peutpas généraliser le cas d'un coup sur le goban. L'algorithme RAVE (Rapid Ac-tion Value Estimation) est un moyen rapide de faire une estimation généraled'un coup, indépendamment de sa position dans l'arbre. Son principe estsimple : Pour chaque coup est stocké le nombre de fois où un noeud corre-spondant à ce coup a été exploré lors des descentes et le nombre de victoirequi sont arrivées dans la même branche. Ces valeurs sont donc mises à jourà chaque fois que UCT �nit une simulation (par une victoire ou une dé-faite). Est ensuite calculé un ratio pour chaque coup en fonction de ces deuxparamètres (nous l'appelerons le "ratio RAVE").

Couplé à UCT, Il permet de mieux choisir les noeuds à explorer lorsdes descentes et/ou d'avoir une meilleure évaluation des noeuds de l'arbreUCT. Il est surtout e�cace dans les cas où l'on arrive sur des noeuds encorenon explorés (sans aucun �ls), ce qui représente la majorité des descentes. Ilpermet d'explorer en priorité le coup jouable ayant le meilleur ratio RAVEquelque soit la branche, lorsque l'on ne connait encore rien sur les noeuds.

Figure 5.1 � Rave couplé à UCT

16

5.2 Notre implémentation

Nous n'utilisons RAVE que pour le choix des noeuds non explorés lors desdescentes car nous avons remarqué après experimentation que l'évaluationpar RAVE dans l'arbre donnait de mauvais résultats. Nous avons stockésles ratios RAVE dans deux listes chainées triées (une pour noir, une pourblanc), a�n de toujours pouvoir connaitre le coup avec le meuilleur ratioRAVE. Pour le rendre fonctionnel et e�cace, nous avons utilisé plusieursastuces :

� A�n d'éviter que ne soit choisie une serie de coups qui soit toujours lamême lors des descentes (par exemple lors de double Ko), l'algorithmechoisit aléatoirement parmi les x meilleurs ratios RAVE (2 ou 3) celuiqui sera exploré.

� Lorsque une descente se �nie (la simulation est considérée gagnante ouperdante), les ratios Rave de la branche (de la feuille à la racine) sontmis à jour. Cependant, le fait qu'un coup est gagnant (ou perdant) justeavant la �n d'une simulation est bien moins intéressant et pertinent quela victoire ou défaite des coups juste après la situation initale. Ainsi,lors de la mise à jour, la défaite ou la victoire est plus ou moins priseen compte en fonction de sa hauteur dans l'arbre :

Figure 5.2 � Mise à jour ratios RAVE

17

� Les ratios RAVE sont mis à jour dès la première descente. Cependantils ne sont pas dessuite utilisables : des ratios qui n'ont été mis à jourque quelques fois ne sont pas pertinents, et ils le deviennent de plusen plus au fur et à mesure des descentes. C'est pourquoi nous avonsimplémenté un seuil à partir duquel les ratios RAVE sont utilisés. Deplus, l'importance des mises à jour devient de plus en plus importanteen fonction du nombre de passages pour chaque coup.

� Le bot ré�échit toujours de la même façon au cours de la partie . Maisen début de partie, il n'y a que peu de bons "patterns". Ainsi, pourremplacer un éventuel système de règles permettant de guider le boten début de partie, les ratios RAVE sont initialisés avec des valeurs enfonction des coups (Les bords avec de mauvais ratios). La communautéRAVE est divisée sur ce sujet : certains pensent que c'est une erreur,d'autres trouvent que c'est une bonne méthode. Nous avons en tout casvu une nette progression en début de partie grâce à cette initialisation.

18

6 Réseau de neurones

6.1 Un système d'apprentissage

Un réseau de neurones arti�ciels est un modèle inspiré du fonctionnementdes neurones biologiques. C'est un système permettant, à l'aide de di�érentsalgorithmes, à un programme informatique d'apprendre par l'expérience. Lesréseaux de neurones sont généralement utilisés pour des problèmes statis-tiques tel que la prise décision d'achat boursier.

Le principe d'un tel système est d'avoir, tout d'abord, un long apprentis-sage qui crée une sorte de boîte noire plutôt incompréhensible par un humain.Ensuite, on utilise cette boite en lui envoyant un jeu de données et la boiterenvoie rapidement une ou plusieurs valeurs.

La structure de ces réseaux est assez libre. En général, ils sont composésde plusieurs couches (souvent 3) : Une couche d'entrée, une ou des couchesintermédiaires et une couche de sortie. Les couches sont composées de neu-rones, le nombre étant à adapter selon le problème. Il faut savoir que pourles couches intermédiaires, le nombre de neurones est très arbitraire, il fautdonc en général tester de manière empirique pour trouver le bon compromis.

Figure 6.1 � Structure d'un réseau de neurones

19

6.2 FANN : une librairie C++

FANN est une librairie open source permettant d'implémenter des réseauxde neurones. Nous avons choisi celle-ci car elle est très utilisée, a une commu-nauté active et continue à être mise à jour régulièrement. (http://leenissen.dk/fann/wp/[réf 2])Il faut savoir que cette librairie n'est pas seulement disponible pour C++,elle est aussi développée dans 14 autres langages tels que Python ou Javapar exemple. Nous l'avons aussi choisi car elle est rapide et simple à utilisergrâce à la doc très complète disponible sur le site. Il y a aussi un exempled'utilisation disponible en français expliqué pas à pas. (http://fann.sf.net/fann_fr.pdf[réf 3])Cette librairie propose beaucoup d'options et notament di�érents algorithmesd'apprentissage.

6.3 Le parseur SGF

Pour l'apprentissage de notre réseau, nous avons décidé de l'entraîner surdes parties déjà existantes. Nous avons pu trouver plus 150 000 parties surKGS, un site de jeu de Go en ligne. Ces parties sont au format SGF (SmartGame Format : http://www.red-bean.com/sgf/[réf 4]). Etant donné quenous devions optimiser la temps de l'apprentissage (car il peut être trèslong), nous avons décidé de faire notre propre parseur SGF. En e�et, touteles informations du �chier ne nous étaient pas nécessaires, nous avions seule-ment besoin de savoir :- si la partie était valable (pas d'abandon,...),- le gagnant de la partie,- les coups joués au fur et à mesure de la partie.

Le parseur se lance sur un dossier accessible par l'exécutable. Par exem-ple, si le dossier avec les SGFs est dans le même dossier que l'exécutable, ilsu�t de taper le nom du dossier. Il faut savoir que ce programme lit tous les�chiers du dossier et récursivement les �chiers des dossiers du répertoire.

Un problème auquel risque d'être confronté des utilisateurs est le nombrelimite de �chiers ouvert par un processus. Cette limite est 1024 en généralde base sur un Linux. Pour passer outre cette limite, il faudra faire quelquesmanipulations dans le terminal : Tout d'abord, taper "sudo -i" ; ceci metl'utilisateur en tant que "root", a�n d'avoir tous les droits. Ensuite, taper"sudo ulimit -n 999999" modi�ra la limite molle et dure à 999999 �chiers pource terminal. En�n il ne reste plus qu'à lancer l'exécutable dans le terminalavec "./<chemin de l'exécutable>".

20

Figure 6.2 � Apprentissage via �chiers SGF

6.4 L'apprentissage

Notre réseau de neurones est composé de 81 neurones en entrée pourlui indiquer la valeur de chaque intersection d'un plateau 9x9. Ces neuronespeuvent prendre seulement 3 valeurs :- 0 si l'intersection est vide,- 1 si l'intersection contient une pierre noire,- 2 si l'intersection contient une pierre blanche.

Le nombre de neurones de la couche intermédiaire peut être modi�é carseul l'expérience peut aider à trouver le nombre de neurones intéressant pourcette couche. Un paramètre à prendre en compte dans le choix de ce nombreest le temps d'apprentissage. Ce temps sera beaucoup plus élevé si le nom-bre est lui aussi élevé. Avec l'algorithme d'apprentissage de base, nous avonsremarquer qu'un trop grand nombre(>100) ou un trop petit nombre(<20)donnait de très mauvais résultats lors de l'utilisation.

Les résultats peuvent aussi beaucoup varier en fonction du nombre departies que le réseau va étudier, il est donc nécessaire d'e�ectuer plusieurséchantillons de test pour voir quel est le nombre le plus intéressant.

L'apprentissage de notre réseaux de neurones se fait lorsque l'on parseles �chiers SGFs. On récupère un plateau, on le transforme en une suite de81 nombres et on l'écrit dans dans le �chier ".data" en précisant ensuite legagnant par 0 (noir) ou 1 (blanc).

21

Il faut aussi ajouter en début de �chier une ligne indiquant le nombrede parties dans le �chier, le nombre de neurones en entrée et le nombre ensortie comme ceci :

1 81 1

0 0 1 2 0 0 0 0 0 0 0 1 2 2 0 0 1 0 0 0 1 1 2 2 0 2 0 0 1 0 1 1 2 2 0 0 0 00 0 1 1 2 0 0 0 0 1 1 2 2 0 0 0 0 0 1 2 2 0 2 2 0 0 0 1 2 2 1 1 1 0 0 0 1 2 0 1 0 0 0

0

Nous avons expérimenté plusieurs approches sur la façon d'apprendre ànotre IA. En premier, nous avons récupéré les plateaux �naux de chaquepartie et nous les lui avons donnés mais cette méthode n'apportait pas debon résultats. L'IA n'arrivait à rien dès le début de partie car ces plateaux neressemblait pas du tout à ce qu'on lui envoyait puisque les plateaux étaientpresque vides.Nous avons donc opté pour lui donner tous les coups d'une partie. Mal-heureusement, les résultats n'étaient pas aussi bons que prévus.Nous avons testé deux algorithmes proposés par FANN : le RPROP et l'in-crémental. L'incrémental semble plus pertinent mais est beaucoup plus lent.En e�et, pour 130 000 �chiers il faut compter à peu près 15 heures de traite-ment alors qu'avec l'algorithme de base (RPROP) seulement 1 ou 2 heuressu�sent.

Nous avons commencé à tester en changeant le nombre de couche dansla partie intermédiaire. En prenant cette voie, un grand nombre de possibil-ité s'o�re à nous, pour l'instant les tests ne sont pas concluant, mais noussommes loin d'avoir tout essayé. En augmentant le nombre de couches, nousnous heurtons un gros problème : le temps d'apprentissage augmente de façonexponentielle avec le nombre de couches surtout si le le nombre de neuronespar couche est elevé. Il faut souvent compter plusieurs jours de calcul pourapprendre sur un peu plus de 100 000 �chiers.

A ce jour nous continuons à faire des tests pour trouver le meilleur nombrede neurones/couches et le meilleur algorithme. Nous essayons aussi de voirsi une autre approche de l'apprentissage pourrait être fructueuse. Les pistesenvisagées sont :- Une modi�cation des parties prises en compte en supprimant les partiesdont le score est trop serré car elles ne sont pas assez signi�catives.- Un changement de l'apprentissage des premiers coups car en général lescoups joués sont des bon coups, or ils sont considéré comme mauvais si lapartie est perdue.

22

6.5 L'utilisation

Figure 6.3 � Exécution Réseau de neurones

Le réseau de neurones a besoin qu'on lui envoie un tableau de "�oat" enparamètre. Ce tableau doit contenir les intersections du plateau (0,1,2). Audébut, nous utilisions une fonction de transformation de notre goban en untableau, mais ceci était beaucoup trop coûteux en temps. Nous avons doncdécidé de l'a�ecter au fur et à mesure de l'avancement de la partie pouroptimiser le temps de calcul.

Nous avons testé l'utilisation du réseau à di�érents endroits du pro-gramme. Mais son utilisation étant assez coûteuse, nous ne pouvions pasl'utiliser dans les descentes sans diviser par 20 le nombre de descentes ef-fectuées par UCT. Ensuite, nous avons essayé de mettre les neurones encomplétion de RAVE. RAVE selectionnait 5 noeuds puis on demandait auréseau de choisir parmis ces noeuds. Mais cela restait beaucoup trop coû-teux en nombre descentes perdu (division par 10 environ). Nous avons donc�nalement opté pour l'utiliser pour aider UCT lors de l'exploration de l'arbre.

Le réseau de neurones retourne une valeur car il a un neurone de sortie.Cette valeur est un �ottant compris entre 0 et 1. Plus cette valeur est grande,plus il pense que c'est un bon coup.

23

7 Résultat et comparaison

Dans cette section, nous présentons les résultats et l'évolution du niveaude notre IA au cours de l'avancement de notre projet.

Durant les di�érentes phases d'implémentation de notre IA, on la faisaitjouer contre nous même, ceci nous donnait des ressentis en ce qui concerneson niveau.Cependant, dû au fait qu'au jeu de Go, contrairement à certains autres jeuxde plateau comme les échecs, il n'existe pas de fonction d'évaluation exacte,qui à partir d'un plateau de jeu (un Goban dans notre cas ) soit capablede déterminer de façon exacte le joueur ayant l'avantage, notre jugement selimitait donc à apprécier les coups de notre IA.Nous étions juste capable de dire "C'est un coup intéressant", "Ce coup n'estpas du tout intéressant", "Il ne pouvait pas faire mieux" , "Alors là, il a jouécomme un pied" (expression favorite de Steve)...

Du coup , il était impossible de vraiment chi�rer le niveau de notre IA,de faire des comparaisons pour voir si vraiment il évoluait avec l'implémen-tation de nouveaux algorithmes.Pour pouvoir vraiment mesurer son niveau, nous avons fait s'a�ronter notreIA à la célèbre IA de Go GNUGO.

7.1 Mécanisme des tests

GNUGO est une IA très bien écrite, qui est paramétrable avec desniveaux de 1 à 10. La nôtre l'est aussi, on peut paramettrer son temps d'exé-cution (le temps qu'on lui donne pour trouver le coup à jouer) en secondes.

Nous avons commencé par parametrer GNGUGO au niveau 10, notreIA sur 10secondes, le résultat sur une trentaine de parties était sans appel,notre IA ( avec UCT uniquement, avec UCT + RAVE, UCT + Reseau deneurones, avec UCT+RAVE+Reseau de neurones ) se faisait très largementécraser à tous les coups, ceci n'etait pas bon car ça ne nous permettait pasde quanti�er le niveau de notre IA avec ou sans ses di�érents modules.

24

Nous avons dû descendre le niveau de GNUGO à 5, après à 2 et �nale-ment à 1, et nous avons augmenté le temps de re�exion de notre IA à 20secondes. Ces paramètres etaient corrects pour mettre en évidence le niveaude notre IA en fonction de ses di�érents modules.

Ainsi, considerant les modules UCT, UCT+RAVE, UCT+Réseau de neu-rones, UCT+RAVE+Réseau de neurones, et avec 20secondes de re�exion,on a e�ectué à chaque fois 50 parties contre GNUGO niveau 1.

7.2 UCT : 250

Les performances de UCT tout seul, comme prévu ne sont pas fameuses,sur 50 parties, MAU-GI-MA-BOU (c'est le nom de notre IA) n'a résussiqu'à remporter 2 parties...Ceci est un résultat très faible, mais en aucun cas, ces deux victoires nepourraient être attribuées à de la chance, car il faut le reconnaitre, GNUGO,meme au niveau 1 est un redoutable adversaire.

7.3 UCT + RAVE : 1150

Ici, bien que MAU-GI-MA-BOU ne sois toujours pas de taille face àGNUGO, il n'en demeure pas moins que, le module RAVE, sans surprisefait bien monter le niveau de notre IA.En e�et, le but de ces tests n'étant pas de prétendre avoir un niveau supérieurau géant GNUGO (du moins pas pour le moment), ces résultats étaient dejàsatisfaisants, et cette évolution était à la hauteur de nos attentes.

7.4 UCT + Réseau de Neuronnes : 450

Cette combinaison, était avant tout expérimentale, on n'avait pas d'at-tentes particulières...Cependant, il s'avère tres intéréssant de remarquer la grande régression dueau fait de l'absence de RAVE. En meme temps, il reste évident que le Réseaude neurones améliore, bien que tres faiblement, les résultats de UCT toutseul.Il en résulte à ce niveau des tests que UCT tout seul ne vaut pas grand chose,et si le réseau de neurone est capable de l'améliorer, RAVE reste un atoutde taille.

25

7.5 UCT + RAVE + Réseau de Neuronnes : 950

Inutile de rappeller que cette partie des tests est celle qu'on attendait autournant.Ici, Bien qu'au courant du fait que, l'usage du réseau de neuronnes, gourmanten ressources matérielles, réduit considérablement le nombre de déscentes,pénalisant ainsi RAVE, on s'attendait tout de même à un bond enorme desperformances de notre IA, peut être pas assez grand pour écraser GNUGO,mais quand même considérable. Par ces résultats on a recu un grande claque.En e�et, voilà nos acquis :

� Le réseau de neurones fait progresser le niveau de UCT� RAVE lui aussi fait progresser le niveau de UCT� avec UCT + RAVE on a un résultat de 11

50Donc c'est logique qu'en considérant UCT + RAVE + Réseau de

Neuronnes on s'attendait à un résultat peu être pas phénoménal (pour lemoment), mais en aucun cas inférieur à 11

50 .

Nous restons convaincus que, la combinaisonUCT + RAVE + Réseau

de Neuronnes devrait avoir un niveau supérieur à UCT + RAVE,nousmettons donc cette contradiction des résultats obtenus sur le compte de notreimplémentation du réseaux de neurones, ses paramètres d'apprentissage, etson usage dans nos algorithmes.

26

8 Outils Utilisés

8.1 Gogui

Jouer contre notre programme en mode console n'était pas satisfaisant,ni pour le faire évoluer, ni pour pouvoir prendre plaisir à jouer contre lui.Nous devions donc pouvoir jouer contre lui à travers une interface graphique.De la, il y avait deux solutions : Créer notre propre interface graphique, ouen utiliser une existante.Avant de choisir l'interface, (les interfaces se ressemblent beaucoup les unedes autres) nous avons choisi le protocole. GTP, ou Go Text Protocol, est unprotocole permettant de transmettre des coups d'un programme qui joue auGo vers un programme qui les interprète, comme une interface graphique, uneautre intelligence arti�cielle, ou un serveur de jeu en ligne. Ainsi, notre pro-gramme peut facilement être utilisé à travers des interfaces di�érentes. AinsiNous avons utilisé Gogui. Ce dernier est une interface utilisateur graphiquepour les programmes qui jouent le jeu de Go et qui supporte notre protocole.Il nous a aidé beaucoup a faire des test sur notre programme.

Figure 8.1 � Interface Gogui

27

8.2 Le dépôt SVN

Durant notre projet nous avons utilisé le gestionnaire de version SVNhébergé sur Google. Côté client nous utilisons le logiciel RabbitSVN ou Sub-version sous Unix . Subversion (SVN) est un logiciel agissant sur une ar-borescence de �chiers a�n de conserver toutes les versions des �chiers , ainsique leur di�érence .Il a permit ici de facilement mettre à jour et partagerles di�érent �chiers du notre projet. Si deux utilisateurs du dépôt modi-�ent des parties non-communes d'un �chier, les outils optimistes fusionnenttout simplement les modi�cations. Inversement, dans le cas de modi�cationscon�ictuelles, le con�it doit être résolu manuellement.

28

9 Gestion du projet

9.1 Organisation du projet

9.1.1 Planning prévisionnel et réel

Figure 9.1 � Planning prévisionnel

Notre projet étant très orienté recherche, nous ne pouvions pas très bienprévoir le temps que chaque étape nous prendrait.Au �nal la plupart des étapes nous ont demandé beaucoup plus de travailque ce que l'on pensait initialement et elles ont été beaucoup plus longuesque prévu. Nous n'avions surement pas conscience de la di�culté de la tâchequi nous incombait.

Fort heureusement pour nous, la date de rendu a été repoussé et nousavons pu faire le principal de ce que nous voulions faire. Ce qui nous ademandé beaucoup de temps était les phases de déboggage, que nous avonsau �nal fait au fur et à mesure. Etant donné que le programme e�ectueénormément d'actions, il était souvent très di�cile de trouver d'où venaientles bugs et la résolution était souvent très complexe.

29

UCT a tout particulièrement eu des problèmes au début, on a donc toustravaillé dessus puisque il était nécessaire que ce soit terminé et fonctionnelpour attaquer la suite. Ces phases de déboggages nous ont fait prendre duretard que l'on a ressentis plus tard dans l'avancement du projet.

9.1.2 Organisation avec les tuteurs

Nos tuteurs était très présent dans le projet. Nous avions souvent desquestions à leur poser et ils souhaitaient connaître notre avancement.Nous nous réunissions donc une semaine sur deux pour discuter et les autressemaines, nous envoyions un e-mail pour indiquer notre avancement et fairepart de nos problèmes rencontrés.

Ces réunions nous ont vraiment beaucoup apporté : elle nous permettaitde résoudre certains problèmes et de nous guidait sur le bon chemin. Leurexpérience nous a été très béné�que tout au long du projet.

9.1.3 Organisation avec le groupe

Notre groupe étant composé de quatre personnes, nous avons décidé derépartir le travail en deux groupes pour la plupart du développement. Cecinous a permis d'avancer plus vite et de faire du bon travail à la fois. Nousnous répartissions aussi les tâches dans les sous-groupes lorsque ceci étaitpossible et judicieux. Souvent le travail en binôme, même si il est plus lent,peut être de bien meilleur qualité. On arrive donc au �nal à un gain de tempscar le code est plus propre, clair et avec moins d'erreurs.Sur certains problèmes, nous avons eu besoin de travailler tous ensemble pourdiverses raisons. Nous faisions des séances ensembles tous les Mercredi après-midi. Ceci nous permettait de s'informer de l'avancement des travaux, deposer des questions et de travailler ensemble. C'était une façon de s'assurerque chacun remplissait sa part du contrat et de ne pas laisser quelqu'unbloqué sur un problème.Cete organisation nous a obligé à travailler régulièrement et à faire participerchaque membre du groupe.

9.2 Le Gestionnaire de projet

L'utilisation d'un SVN nous a permis de partager les di�érents avance-ments du projet et faire du versionning.Il nous a été très utile lorsque nous essayons di�érentes solutions et que l'onmodi�ait énormément le code. Assez souvent il était beaucoup plus facile derevenir à une version fonctionnelle précédente.

30

Dans notre situation, ce système était parfaitement adapté pour récupérerles modi�cations e�ectuées par les autres car nous ne travaillions que trèsrarement sur les mêmes �chiers.On avait donc toujours une version à jour de notre programme et si cetteversion était buggé ou mauvaise, nous pouvions facilement retourner à uneversion précédente.

31

10 Structure du programme

Le projet est composé de deux programmes :Il existe tout d'abord un programme (appelons le "Parseur") qui sert à parserles �chier de parties de Go (.sgf), à les transformer en format lisible pour leréseau de neurones, puis à les lui faire apprendre.Ensuite, un programme (appelons le "GoProjet") qui intéragit via le proto-cole sgf à une interface et e�ectue la ré�exion.Les programmes comprennent plus de 4500 lignes de codes uniques. Le pro-gramme "GoProjet" est composé de 3 packages :

� Un package "dossierGTP".

Il ne contient qu'une classe "PartieGTP". Cette classe se charge d'in-téragir via la protocole GTP avec l'interface.

� Un package "UCT". Il contient la classe "UCT" qui contient toutesles fonctions et les structures de données nécéssaires à la ré�éxion del'IA. C'est cette classe qui e�ectue les descentes, calcule les ratios, re-tourne un coup à jouer.Il contient également la classe "NoeudUCT", qui représente un noeudde l'arbre UCT. Un noeud dispose d'un pointeur vers son père, sonfrère gauche et son premier �ls. Chaque noeud dispose d'un nombre devictoires et de passages, a�n de pouvoir calculer son ratio.Ce package dispose en�n de la classe "coupRave", objet qui existepour chaque coup possible dans le goban, servant aux calculs de ratiosRAVE.

� Un package "Goprojet". Il qui contient de nombreuses classes. Laclasse "ReseauNeurones" contient le code nécéssaire à l'éxecution duréseau de neurones.La classe "Goban" gère le plateau et toutes les intéractions , telles queposer une pierre. Elle utilise les classes "Intersection", "Groupe" et"Tgroupe" pour son bon fonctionnement.Il contient aussi la classe IA qui fait l'intermédiaire entre la classe"Goban" et la classe "UCT" pour le choix d'un coup.

32

Figure 10.1 � Diagramme de classes du programme "GoProjet"

33

11 Conclusion

11.1 Bilan du projet

Le but de notre projet était avant tout de faire avancer la recherche surce problème. Même si nous n'avons pas réussi à avoir une IA exceptionnelle,nous avons apporté notre pierre à cet édi�ce. En e�et, par notre travailet notre persévérance, nous avons pu tester un bon nombre de possibilités(et nous continuons à chercher) ce qui permettra à d'autres d'explorer denouvelles idées et de s'inspirer de nos réussites comme de nos échecs pourpermettre un jour de réaliser le rêve de beaucoup d'informaticiens : avoirune intelligence arti�cielle un peu plus semblable à l'intelligence humaine.

Même si le résultat n'est pas à la hauteur de nos espérances initiales, onpeut donc dire que ce projet est une réussite. C'était notre premier projet ori-enté recherche et nous avions sûrement sous-estimé l'ampleur du problème.Nous avons utilisé tout ce que l'on pouvait pour aller le plus loin possible. Letemps imparti n'était pas su�sant pour tout ce que l'on voulait essayer. Sil'on devait recommencer, il faudrait mieux plani�er le projet (en demandantl'aide des tuteurs par exemple) pour consacrer plus de temps aux partiesimportantes du projet et éviter les retards que cela engendre.

11.2 Bilan personnel

Ce projet nous a beaucoup apporté que ce soit dans la capacité à gérerun projet ou dans les compétences et connaissances en informatique. En ef-fet, ce projet nous a permis de mettre en application tout ce qui nous a étéenseigner depuis le début de nos études, il nous a demandé diverses com-pétences (système, algorithmie, IA, conduite de projet,...), nous avons doncpu voir quelle était nos points forts et nos faiblesses, ce qui nous permetd'acquérir de l'expérience et de nous détacher de notre statut d'étudiant.Ceci nous a aussi permis d'améliorer nos compétences en matière de com-munication au sein d'un groupe.

34

Nous avons pu observer les di�érents problèmes qu'un travail en équipepeut amener et nous pourrons donc y faire face avec plus d'expérience dansnotre vie future.Ce projet a aussi attisé notre curiosité et nous a fait découvrir l'IA et nousa conforté dans l'idée d'un travail futur dans ce domaine.

11.3 Notre apport dans le domaine de l'IA

De par sa structure, mais aussi son fonctionnement, le réseau de neuronesarti�ciel est très semblable au réseau de neurones contenu dans un cerveauhumain, et l'apprentissage du Go passe par de nombreuses parties jouéesavec des personnes di�érentes a�n de rencontrer le maximum de situationsnouvelles, mais aussi être capable de prendre une décision cohérente face àune situation jamais rencontrée.Ceci, couplé à UCT + RAVE est une piste encore non explorée dans lesdocuments de recherche du domaine, mais pourrait cependant representerun pas de géant pour la l'intelligence arti�cille du jeu de Go, mais aussi pourde nombreux autres usages, dans de nombreux domaines.

Cependant à ce jour, nous avons une IA fonctionnelle, mais qui n'est pasdu tout a la hauteur espérée. Ceci sera probablement dû à notre implémenta-tion du réseau de neurones, et à nos paramètres d'apprentissage. Nous avonsprocédé de manière empirique, ce qui est une tâche assez longue.

11.4 Travaux futurs

Notre plan d'action pour le futur se ferait en deux étapes.La première tout naturellement consistera à mettre au point notre réseaude neurones, notamment en trouvant les bons paramètres pour son appren-tissage, mais aussi les moments stratégiques au cours de la partie pendantlesquels on y aura recours, sans amputer le mécanisme UCT et Rave.

Ceci fait, toujours dans notre ambition de l'IA parfaite, la prochaineétape serait l'apprentissage de formes. Ceci se fait par exemple dans deshopitaux, où des programmes sont capables de détecter la présence d'unetumeur dans une image au rayon X, en ayant au préalable, dans la phase d'ap-prentissage, rencontré plusieurs images présentant ou pas une (ou plusieurs)tumeur(s).

35

12 Annexes

12.1 La règle du jeux

Ce chapitre décrit plusieurs aspects du jeu de Go et de la program-mation du jeu de Go liés à la règle du jeu. Les règles viennent du sitehttp://www.weiqiban.fr/howtoplaygo/ [réf 5].Le jeu de go se joue sur un plateau comme sur le diagramme 1-1. Le matérielde go comprend le plateau ainsi que 180 pierres noires et autant de blanches.Le diagramme 1-1 montre le plateau standard en 19x19 (c-à-d une grille de 19lignes par 19 lignes), mais il existe aussi des jeux de 13x13 et 9x9. Cependantle plateau en 9x9 et 13x13 sont généralement pour les débutants, les joueursplus avancés préfèrent le plateau traditionnel en 19x19. En comparaison deséchecs internationaux ou chinois, le go a bien moins de règles. Pourtant ilpermet de poser une multitude de coups, donc le go est un jeu intellectuelle-ment plus riche que les deux autres types de jeux d'échecs. Cependant, le goest un jeu facile à apprendre, donc amusez-vous bien en y jouant avec vosamis.

12.1.1 Apprendre à jouer

La partie commence avec le plateau vide. Les pierres sont placées surles intersections du plateau. Le joueur qui a les pierres noires commence lapartie, et chaque joueur pose une pierre sur le plateau à son tour de jeu. Lesjoueurs ont le choix de poser des pierres sur le plateau sur n'importe quelleintersection inoccupée du goban.Cependant, lorsque les pierres sont posées sur le plateau, elles ne peuvent pasêtre déplacées ailleurs. Les pierres ne sont pas non plus retirées du plateauquand on le veut, elles obéissent aux règles présentées dans les sections suiv-antes. Les joueurs ne sont pas non plus autorisés à placer une pierre pardessus une autre. Ce sont ces règles qui rendent le go unique par rapportaux autres jeux d'échecs, y compris les échecs internationaux et chinois. Labeauté du go réside également dans la simplicité de ses règles.

12.1.2 Libertés

Les libertés sont les intersections (ou points) inoccupées adjacentes hor-izontalement ou verticalement à la pierre. Note : les points adjacents en

36

Diagramme 1-2 Diagramme 1-3 Diagramme 1-4

diagonale de la pierre ne sont pas des libertés de cette pierre. Les libertésdes trois pierres noires sont marquées X dans le Diagramme 1-2.Une pierre au centre a quatre libertés, une pierre sur les bords en a trois, etune pierre dans le coin a deux libertés.La règle dit que les pierres n'ayant plus de libertés sont retirées du plateau.Par exemple, dans le Diagramme 1-3, les trois pierres noires n'ont plus delibertés et doivent être retirées du plateau comme sur le Diagramme 1-4.Cependant l'inverse est également vrai : les pierres ayant au moins une lib-erté doivent rester sur le plateau.Poser un coup qui enlève la dernière liberté d'une de vos pierres (pas cellesde l'adversaire) est appelé un suicide. Habituellement le suicide est inter-dit, mais quelques variantes de règles le permettent, ainsi le coup de suicideoblige à enlever les pierres sans libertés , c'est alors à l'adversaire de jouer.

Figure 12.1 �

37

Une chaîne consiste en deux pierre ou plus connectées entre elles verticale-ment, ou horizontalement Les libertés communes de la chaîne sont comptéestoutes ensemble. Un exemple est le figure 12.1, où les deux pierres noires ontun nombre total de libertés communes de six, marquées X. Lorsque Blanc ajoué toutes les positions marquées X, de telle manière que les deux pierresnoires n'ont plus de libertés du tout, alors Blanc enlève les deux pierres enmême temps. Blanc ne peut pas enlever l'une des pierres noires isolément.Comme dit le proverbe, � Un pour tous, tous pour un ! �.

Diagramme 1-6 Diagaramme 1-7 Diagramme 1-8

Observons le Diagramme 1-6. Que se passe-t-il si Noir décide de jouer 1comme sur le Diagramme 1-7 ? Notez que la pierre noire marquée n'a pas deliberté, mais les trois pierres blanches (marquées d'un triangle) n'en ont paségalement. La règle suivante détermine le résultat : le joueur qui enlève lesdernières libertés de pierres des deux joueurs peut enlever les pierres de sonadversaire. Ainsi, Noir peut enlever les trois pierres blanches, ce qui donnecomme résultat le Diagramme 1-8.

12.1.3 Ko

Diagramme 1-9 Diagaramme 1-10 Diagramme 1-11

La situation commence avec le Diagramme 1-9, ensuite Noir prend lapierre blanche marquée dans le Diagramme 1-10, ce qui donne le Diagramme

38

1-11. Ainsi on peut observer que Blanc peut vouloir jouer au point A duDiagramme 1-11, revenant ainsi au Diagramme 1-9.Ensuite Noir décide de jouer en 1 du Diagramme 1-10 et cetera, et la partiene se �nira jamais. Cette situation est appelée un ko.Ainsi lorsque Noir prend le ko en 1 du Diagramme 1-10, la règle du koprécise que Blanc doit attendre un tour avant de pouvoir reprendre le ko.Cela signi�e simplement que Blanc ne peut pas jouer en A du Diagramme1-11 à son tour juste après que Noir ait pris le ko (Blanc peut jouer ailleurs),mais il peut jouer A à son propre tour. Si Blanc parvient à reprendre le ko,la même règle s'applique à Noir. Noir doit attendre un tour avant de pouvoirreprendre le ko.

Figure 12.2 �

Le figure 12.2 montre d'autres exemples valides de ko, impliquant lepoint A et la pierre noire marquée.

12.1.4 Fin d'une partie

La partie se termine lorsque les deux joueurs sont d'accord sur la �n dela partie � les deux joueurs passent leur tour consécutivement. Si un joueurpasse mais son adversaire décide de ne pas passer et de poser un coup surle plateau, alors la partie ne sera pas �nie. Lorsque la partie se termine, levainqueur est déterminé en comparant les territoires.Eventuellement, si un des joueurs abandonne, son adversaire gagne automa-tiquement la partie. Au go, un joueur ne peut pas placer plus d'une pierre surle plateau à son tour, donc il est habituel de poser deux pierres sur le plateaupour indiquer que l'on se rend. C'est particulièrement utile pour passer labarrière du langage qui peut exister entre joueurs de cultures di�érentes.

12.1.5 Territoires

L'objectif au go est d'obtenir plus de territoire que votre adversaire. Celaimporte peu quelle est la di�érence � tant que vous avez un plus gros territoireque votre adversaire, vous gagnez la partie.

Lorsqu'on compte les territoires, on compte le nombre de points entouréspas les pierres. Dans le figure 12.3, Noir possède un territoire de 9 points,

39

Figure 12.3 �

et Blanc possède également 9 points de territoire.

Figure 12.4 �

Comme les pierres peuvent être capturées et retirées du plateau, quand oncalcule qui est le vainqueur on peut également prendre en compte le nombrede pierres. Ainsi on cherche le total des territoire et du nombre de pierresd'un joueur, et on regarde si cela vaut plus que le total de l'adversaire.Observez le figure 12.4, une partie jouée sur un plateau 13x13, Blanc etNoir ont 39 pierres chacun. Noir a entouré 45 points de territoire, et Blancen a 46. En les additionnant, Noir a 84 points, et Blanc a 85 points. DoncBlanc gagne la partie.

40

12.2 Bibliographie

réf 1 : http://interstices.info/

Une revue de culture scienti�que sur la recherche en informatique. Desinformations sur les victoires des IA de Go y sont disponibles.

réf 2 : http://leenissen.dk/fann/wp/

Site de la communauté FANN.

réf 3 : http://fann.sf.net/fann_fr.pdf

Document expliquant pas à pas l'utilisation de la librairie FANN (réseaude neurones).

réf 4 : http://www.red-bean.com/sgf/

Site expliquant le format SGF.

réf 5 : http://www.weiqiban.fr/howtoplaygo/htpg01.pdf

Les règles du Go.

réf 6 : On the Huge Bene�t of Decisive Moves in Monte-CarloTree Search Algorithms (Fabien Teytaud et Olivier Teytaud)

Article qui nous a aidé pour l'implémentation de UCT.

réf 7 : Monte-Carlo Tree Search, UCT, computer-Go and allthat stu� de Olivier Teytaud

Article détaillé traitant de l'implémentation de UCT. Il est lisible par unnon-informaticien.

Learning To Play the Game of Chess (G. Tesauro, D. Touret-zky, and T. Leen, eds., 1995)

Cet article présente di�érents algorithmes d'apprentissage tels que leExplanation-Based Neural Network Learning, le Temporal Di�erence Learn-ing (DT) et mentionne le fait que ces algorithmes, bien qu'e�caces dansd'autres jeux comme le backgamon, ils le sont moins s'ils sont implémentéspour le jeu de Go ou aux échecs.

41

Achieving Master Level Play in 9 x 9 Computer Go (SylvainGelly Univ. Paris Sud, LRI, CNRS, INRIA, France ; David Sil-ver University of Alberta, Edmonton, Alberta, Canada,2008)

Cet article présente des applications de Monte-Carlo, UCT et Rave. Cesont des algorithmes très utilisés pour L'IA de Go (ex : MoGo). Ce sont lesbases de l'algorithme qui va être utilisé pour notre projet.

Move Prediction in the Game of Go (Brett Alexander Harri-son, 2010)

C'est une thèse générale qui porte sur les di�érents types d'algorithmesqui anticipent les prochains coups des joueurs.

Mimicking Go Experts with Convolutional Neural Networks,(Ilya Sutskever and Vinod Nair, Department of ComputerScience, University of Toronto, 2008)

Cet article décrit un programme permettant de prédire les mouvementd'un joueur expert à l'aide d'un réseau de neurones.

L'intelligence arti�cielle pour le jeu de Go (Guillaume Tisser-ant, Guillaume Maurin, Jérome Dorado, Basile Fabre, 2010)

Le rapport de TER du Machiabot. C'est le programme que nous avonsreprit comme base.

http://chessprogramming.wikispaces.com/Sylvain+Gelly

Site du créateur de MoGo.

https://www.lri.fr/~teytaud/

Site du developpeur de MoGo.

42