MoGo, maître du jeu de Go ?
« Le monde est un jeu de Go, dont les règles ont été inutilement compliquées »
(Proverbe chinois)
Jeu de Go au XVIe siècle. Détail des « Quatre accomplissements ». Dans la Chine ancienne, le Go était en effet considéré comme l’un des quatre accomplissements de toute personne cultivée, à l’égal de la poésie, de la musique et de la peinture.Source : Kano Eitoku / Wikipédia[/caption]
Si tout le monde considère actuellement que les programmes joueurs d’échecs sont beaucoup plus forts que la plupart des humains, on ne peut pas en dire autant pour un jeu comme le Go. Les programmes joueurs de Go peinent à atteindre un niveau moyen, très loin des amateurs forts et encore plus des professionnels ! Pourquoi ? Deux raisons à cela : tout d’abord, il y a beaucoup plus de coups possibles au Go qu'aux échecs. Le jeu de Go se joue traditionnellement sur un plateau de jeu (goban en japonais) de 19 lignes et 19 colonnes, ce qui fait plus de 200 coups possibles dans une position typique, contre une quarantaine aux échecs. La combinatoire est donc beaucoup plus grande au Go. Ensuite, la taille de l’arbre des possibilités du jeu de Go est de l’ordre de 10170 positions possibles (c'est-à -dire beaucoup plus grande que le nombre d’atomes dans l’univers) tandis que celle du jeu d’échecs n’est « que » de 1050 environ.
Pour les informaticiens en général et les chercheurs — en modélisation statistique et en intelligence artificielle — en particulier, le jeu de Go est un problème très intéressant, qui soulève des problématiques difficiles dont les solutions pourraient s'appliquer dans d'autres domaines. C’est un défi de s’attaquer à un tel problème, d’autant plus que les techniques utilisées sont très proches de leurs domaines de recherche. Ainsi, ces travaux de recherche sont appliqués à un problème concret, difficile et ludique.
Le Go, un jeu plus complexe que les échecs
Né en Chine il y a plus de 4 000 ans et apparu depuis un millier d’années au Japon, le Go n’est arrivé que très récemment en Occident. Pour y jouer, on utilise un matériel très sommaire : un goban (plateau quadrillé) sur lequel on place des pierres noires et blanches. Il existe trois formats différents de gobans : le très populaire 19x19 intersections, le 13x13 (taille intermédiaire) et le 9x9 principalement utilisé pour les parties d’initiation. Les professionnels ne jouent qu’en 19x19, les autres tailles étant parfois choisies par les amateurs pour des parties plus rapides.
Au Go, on joue sur les intersections et non à l’intérieur des cases comme c’est le cas aux dames ou aux échecs. Deux joueurs s’affrontent, l’un aux pierres blanches, l’autre aux noires, le joueur aux pierres noires commençant toujours la partie. Une fois la première pierre (noire) posée, elle ne bouge plus. C’est ensuite au tour de l'adversaire de jouer. Le but du jeu ? Se constituer des territoires — un territoire, c’est le nombre d’intersections entourées de pierres de la même couleur — en prenant les pierres de l’adversaire.
[caption id="" align="aligncenter" width="455"]
Partie de Go sur un goban de 19x19 intersections. Les pierres blanches marquées par des croix rouges (vers le haut du goban) sont voisines de proche en proche. Elles constituent une chaîne qui a quatre libertés (intersections marquées par des cercles verts). Sur le plateau, on a également délimité un territoire blanc (cercles bleus, en bas du goban), c'est-à -dire un groupe d'intersections entourées par des pierres de la même couleur.Source : © INRIA / Photo : Christian Tourniaire[/caption]
Pour gagner, un joueur doit dominer plus d’intersections que son adversaire en constituant des chaînes, c’est-à -dire en connectant ses propres pierres et en capturant des pierres adverses. Et attention, les diagonales ne comptent pas au Go ! Une chaîne reste sur le plateau de jeu tant qu’elle a au moins une liberté. On appelle liberté le nombre d’intersections vides autour d’une chaîne. À partir du moment où une chaîne n'a plus aucune liberté, le joueur concerné récupère les pierres. La partie se déroule alors jusqu’à ce que les deux joueurs passent leur tour. De plus, le ko simple interdit de jouer un coup tel que la position après capture serait exactement identique à la position précédente. Très importante, cette règle permet d'éviter de faire des parties infinies. À la fin, on compte le nombre de territoires possédés par chaque joueur et celui ayant le plus de territoires remporte la partie. Chaque intersection du territoire d'un joueur lui rapporte un point, ainsi que chacune de ses pierres encore présentes sur le goban. En outre, comme le joueur aux pierres noires commence toujours la partie, on considère que ce dernier a un avantage. Dans une partie à égalité, on attribue alors quelques points d’avance à son adversaire. C’est ce qu’on appelle le komi. Vous avez là 80% des règles du Go. Le reste, ce sont des règles qui diffèrent selon les pays, notamment pour le décompte exact du score.
Par ailleurs, les joueurs sont classés selon différents niveaux : ils s'échelonnent de 30e Kyū (débutant) à 1er Kyū, puis de 1er dan à 9e dan pour les joueurs amateurs. Les joueurs professionnels sont classés de 1er à 9e dan. Un niveau de 1er dan professionnel correspond environ à un niveau de 7e dan amateur. Entre amateurs, un niveau d'écart correspond à peu près à une pierre de handicap (pierre d'avance accordée au joueur le plus faible) alors qu'entre joueurs professionnels, c'est environ trois niveaux d'écart qui correspondent à une pierre de handicap.
Quand les joueurs s’affrontent…
[caption id="" align="alignright" width="230"]
Source : © INRIA / Photo : Jonathan Dumont[/caption]
Plusieurs compétitions permettent de mesurer les forces relatives des programmes joueurs de Go. Deux outils sont principalement utilisés pour se comparer aux autres programmes : le Computer Go Server et le Kiseido Go Server (KGS).
Le Computer Go Server est un serveur sur Internet à partir duquel les programmes peuvent se connecter à n’importe quel moment, 24h/24 et 7 jours/7. Les programmes y jouent entre eux et on leur attribue un Elo au bout de plusieurs jours de parties. Très connu aux échecs, le Elo est utilisé pour classer les joueurs : ce chiffre permet de savoir la probabilité de gagner d’un joueur sur un autre. Un exemple : si un joueur a un Elo 2000 et un autre un Elo 1800, on va simplement calculer la différence de Elo entre les deux joueurs puis en déduire la probabilité de gagner du premier sur le second. Plus la différence de Elo est grande, plus la probabilité de gagner est forte. Par la suite, on applique une formule qui, à partir des victoires de chacun — par exemple, X a joué contre Y dix fois et a gagné cinq fois, Z a joué contre Y etc. —, permet de calculer le Elo de chacun. Le Elo détermine donc la force du joueur.
Sur le Computer Go Server, les parties se font sur des gobans de 9x9, les parties en 19x19 prenant beaucoup trop de temps, même pour faire jouer les programmes ! Faire un programme en 9x9 permet donc de le tester plus vite. De plus, les programmes étant assez faibles, ils sont meilleurs sur des petites tailles. Il est intéressant de développer les programmes sur des petites tailles afin de suivre leur progression, voir leurs forces ou faiblesses ainsi que leur niveau par rapport aux humains, d’autant plus que le nombre illimité de parties sur le Computer Go Server permet une évaluation plus précise des programmes.
Quant au KGS (Kiseido Go Server), c’est un serveur très populaire sur lequel des milliers d’humains se connectent et jouent. Tous les premiers week-ends du mois, un tournoi est organisé entre ordinateurs et dans les différentes tailles de goban. Sur KGS, le nombre de parties est fixe — entre 6 et 10 en moyenne — et au bout de ces parties, le joueur qui a gagné le plus souvent remporte le tournoi. Par ailleurs, l’évaluation des programmes est plus précise sur le Computer Go Server que sur le KGS. Sur un tournoi, le facteur chance est non négligeable : même le meilleur peut perdre parce qu’il n’a pas eu de chance. Mais c'est aussi ce qui fait le charme des tournois, le spectacle étant alors au rendez-vous. Les humains, professionnels ou amateurs, peuvent également affronter les programmes joueurs de Go dans une salle spéciale.
Certains joueurs se sont d’ailleurs mesurés à MoGo, le programme développé par le projet TAO (Thème Apprentissage et Optimisation) de l’INRIA Futurs et l'École Polytechnique. Les techniques utilisées par MoGo sont inspirées de la stratégie de Crazystone, un autre programme joueur de Go développé par Rémi Coulom, à Lille (projet SEQUEL, Inria Futurs). L'été dernier, aux Olympiades informatiques, Crazystone remportait la médaille d'or en 9x9 quand MoGo n'en était encore qu'à sa phase de conception !
« Le monde est un jeu de Go, dont les règles ont été inutilement compliquées »
(Proverbe chinois)
Jeu de Go au XVIe siècle. Détail des « Quatre accomplissements ». Dans la Chine ancienne, le Go était en effet considéré comme l’un des quatre accomplissements de toute personne cultivée, à l’égal de la poésie, de la musique et de la peinture.Source : Kano Eitoku / Wikipédia[/caption]
Si tout le monde considère actuellement que les programmes joueurs d’échecs sont beaucoup plus forts que la plupart des humains, on ne peut pas en dire autant pour un jeu comme le Go. Les programmes joueurs de Go peinent à atteindre un niveau moyen, très loin des amateurs forts et encore plus des professionnels ! Pourquoi ? Deux raisons à cela : tout d’abord, il y a beaucoup plus de coups possibles au Go qu'aux échecs. Le jeu de Go se joue traditionnellement sur un plateau de jeu (goban en japonais) de 19 lignes et 19 colonnes, ce qui fait plus de 200 coups possibles dans une position typique, contre une quarantaine aux échecs. La combinatoire est donc beaucoup plus grande au Go. Ensuite, la taille de l’arbre des possibilités du jeu de Go est de l’ordre de 10170 positions possibles (c'est-à -dire beaucoup plus grande que le nombre d’atomes dans l’univers) tandis que celle du jeu d’échecs n’est « que » de 1050 environ.
Pour les informaticiens en général et les chercheurs — en modélisation statistique et en intelligence artificielle — en particulier, le jeu de Go est un problème très intéressant, qui soulève des problématiques difficiles dont les solutions pourraient s'appliquer dans d'autres domaines. C’est un défi de s’attaquer à un tel problème, d’autant plus que les techniques utilisées sont très proches de leurs domaines de recherche. Ainsi, ces travaux de recherche sont appliqués à un problème concret, difficile et ludique.
Le Go, un jeu plus complexe que les échecs
Né en Chine il y a plus de 4 000 ans et apparu depuis un millier d’années au Japon, le Go n’est arrivé que très récemment en Occident. Pour y jouer, on utilise un matériel très sommaire : un goban (plateau quadrillé) sur lequel on place des pierres noires et blanches. Il existe trois formats différents de gobans : le très populaire 19x19 intersections, le 13x13 (taille intermédiaire) et le 9x9 principalement utilisé pour les parties d’initiation. Les professionnels ne jouent qu’en 19x19, les autres tailles étant parfois choisies par les amateurs pour des parties plus rapides.
Au Go, on joue sur les intersections et non à l’intérieur des cases comme c’est le cas aux dames ou aux échecs. Deux joueurs s’affrontent, l’un aux pierres blanches, l’autre aux noires, le joueur aux pierres noires commençant toujours la partie. Une fois la première pierre (noire) posée, elle ne bouge plus. C’est ensuite au tour de l'adversaire de jouer. Le but du jeu ? Se constituer des territoires — un territoire, c’est le nombre d’intersections entourées de pierres de la même couleur — en prenant les pierres de l’adversaire.
[caption id="" align="aligncenter" width="455"] Partie de Go sur un goban de 19x19 intersections. Les pierres blanches marquées par des croix rouges (vers le haut du goban) sont voisines de proche en proche. Elles constituent une chaîne qui a quatre libertés (intersections marquées par des cercles verts). Sur le plateau, on a également délimité un territoire blanc (cercles bleus, en bas du goban), c'est-à -dire un groupe d'intersections entourées par des pierres de la même couleur.Source : © INRIA / Photo : Christian Tourniaire[/caption]
Pour gagner, un joueur doit dominer plus d’intersections que son adversaire en constituant des chaînes, c’est-à -dire en connectant ses propres pierres et en capturant des pierres adverses. Et attention, les diagonales ne comptent pas au Go ! Une chaîne reste sur le plateau de jeu tant qu’elle a au moins une liberté. On appelle liberté le nombre d’intersections vides autour d’une chaîne. À partir du moment où une chaîne n'a plus aucune liberté, le joueur concerné récupère les pierres. La partie se déroule alors jusqu’à ce que les deux joueurs passent leur tour. De plus, le ko simple interdit de jouer un coup tel que la position après capture serait exactement identique à la position précédente. Très importante, cette règle permet d'éviter de faire des parties infinies. À la fin, on compte le nombre de territoires possédés par chaque joueur et celui ayant le plus de territoires remporte la partie. Chaque intersection du territoire d'un joueur lui rapporte un point, ainsi que chacune de ses pierres encore présentes sur le goban. En outre, comme le joueur aux pierres noires commence toujours la partie, on considère que ce dernier a un avantage. Dans une partie à égalité, on attribue alors quelques points d’avance à son adversaire. C’est ce qu’on appelle le komi. Vous avez là 80% des règles du Go. Le reste, ce sont des règles qui diffèrent selon les pays, notamment pour le décompte exact du score.
Par ailleurs, les joueurs sont classés selon différents niveaux : ils s'échelonnent de 30e Kyū (débutant) à 1er Kyū, puis de 1er dan à 9e dan pour les joueurs amateurs. Les joueurs professionnels sont classés de 1er à 9e dan. Un niveau de 1er dan professionnel correspond environ à un niveau de 7e dan amateur. Entre amateurs, un niveau d'écart correspond à peu près à une pierre de handicap (pierre d'avance accordée au joueur le plus faible) alors qu'entre joueurs professionnels, c'est environ trois niveaux d'écart qui correspondent à une pierre de handicap.
Quand les joueurs s’affrontent…
[caption id="" align="alignright" width="230"] Source : © INRIA / Photo : Jonathan Dumont[/caption]
Plusieurs compétitions permettent de mesurer les forces relatives des programmes joueurs de Go. Deux outils sont principalement utilisés pour se comparer aux autres programmes : le Computer Go Server et le Kiseido Go Server (KGS).
Le Computer Go Server est un serveur sur Internet à partir duquel les programmes peuvent se connecter à n’importe quel moment, 24h/24 et 7 jours/7. Les programmes y jouent entre eux et on leur attribue un Elo au bout de plusieurs jours de parties. Très connu aux échecs, le Elo est utilisé pour classer les joueurs : ce chiffre permet de savoir la probabilité de gagner d’un joueur sur un autre. Un exemple : si un joueur a un Elo 2000 et un autre un Elo 1800, on va simplement calculer la différence de Elo entre les deux joueurs puis en déduire la probabilité de gagner du premier sur le second. Plus la différence de Elo est grande, plus la probabilité de gagner est forte. Par la suite, on applique une formule qui, à partir des victoires de chacun — par exemple, X a joué contre Y dix fois et a gagné cinq fois, Z a joué contre Y etc. —, permet de calculer le Elo de chacun. Le Elo détermine donc la force du joueur.
Sur le Computer Go Server, les parties se font sur des gobans de 9x9, les parties en 19x19 prenant beaucoup trop de temps, même pour faire jouer les programmes ! Faire un programme en 9x9 permet donc de le tester plus vite. De plus, les programmes étant assez faibles, ils sont meilleurs sur des petites tailles. Il est intéressant de développer les programmes sur des petites tailles afin de suivre leur progression, voir leurs forces ou faiblesses ainsi que leur niveau par rapport aux humains, d’autant plus que le nombre illimité de parties sur le Computer Go Server permet une évaluation plus précise des programmes.
Quant au KGS (Kiseido Go Server), c’est un serveur très populaire sur lequel des milliers d’humains se connectent et jouent. Tous les premiers week-ends du mois, un tournoi est organisé entre ordinateurs et dans les différentes tailles de goban. Sur KGS, le nombre de parties est fixe — entre 6 et 10 en moyenne — et au bout de ces parties, le joueur qui a gagné le plus souvent remporte le tournoi. Par ailleurs, l’évaluation des programmes est plus précise sur le Computer Go Server que sur le KGS. Sur un tournoi, le facteur chance est non négligeable : même le meilleur peut perdre parce qu’il n’a pas eu de chance. Mais c'est aussi ce qui fait le charme des tournois, le spectacle étant alors au rendez-vous. Les humains, professionnels ou amateurs, peuvent également affronter les programmes joueurs de Go dans une salle spéciale.
Certains joueurs se sont d’ailleurs mesurés à MoGo, le programme développé par le projet TAO (Thème Apprentissage et Optimisation) de l’INRIA Futurs et l'École Polytechnique. Les techniques utilisées par MoGo sont inspirées de la stratégie de Crazystone, un autre programme joueur de Go développé par Rémi Coulom, à Lille (projet SEQUEL, Inria Futurs). L'été dernier, aux Olympiades informatiques, Crazystone remportait la médaille d'or en 9x9 quand MoGo n'en était encore qu'à sa phase de conception !