Programmer le jeu GO

Je commence par vous inviter à lire cet article :

L'intelligence artificielle au banc d'essai du jeu de go

L'intelligence artificielle au banc d'essai du jeu de go
LE MONDE | 06.03.09

Le monde, dit un proverbe chinois, est un jeu de go dont les règles ont été inutilement ompliquées." Né dans l'empire du Milieu il y a quelque 4 000 ans, ce jeu est faussement simple : pierre après pierre, posées sur les intersections d'un plateau quadrillé de 19 lignes par 19 colonnes, il consiste à créer des archipels, à les connecter et à les protéger des visées coloniales de l'adversaire.
Le
jeu d'échecs, avec ses pièces aux mouvements multiples et variés, peut sembler plus complexe. Il n'en est rien - du moins du point de vue des machines : depuis que Garry Kasparov a dû s'incliner sur l'échiquier devant le programme Deeper Blue, en 1998, le go est, dans l'univers des jeux, l'ultime refuge de l'intelligence humaine, face à la puissance du silicium. Car dans le go, il n'y a pas d'ouvertures codifiées, la valeur d'une pièce donnée n'est pas fixée à l'avance. Et le nombre de
combinaisons possibles (10¹⁷¹) dépasse de beaucoup le nombre d'atomes dans l'Univers - et donc les capacités de calcul des ordinateurs.

Mais ces dernières années, ceux-ci ont tout de même progressé à pas de géant. Alors qu'il leur fallait une trentaine de coups de handicap pour rivaliser avec des humains médiocres il y a encore dix ans, il leur suffit désormais de sept pierres d'avance pour battre des grands maîtres : "Lors de l'Open de Taïwan, à la mi-février, notre programme MoGo l'a emporté dans ces conditions face au joueur professionnel taïwanais Zhou Junxun, classé au neuvième dan, le grade le plus élevé de la discipline", se félicite Olivier Teytaud, de l'Institut national de recherche en informatique et automatisme à Saclay (Essonne).

"Cette progression a surpris tout le monde", indique Tristan Cazenave (université Paris-Dauphine), un des pionniers de la programmation du jeu de go en France. La révolution est née de l'importation de techniques de physique statistique dans ce domaine de programmation. Ce système s'appelle le Monte Carlo adaptatif. Il consiste, à partir d'une position donnée, à faire jouer à l'ordinateur le maximum de parties aléatoires, et, dans l'arbre des possibles ainsi engendré, à choisir la solution qui est en moyenne le plus souvent gagnante.

Ce principe, proposé par le physicien en 1993, s'est révélé très fécond, après de multiples raffinements, toujours en cours. Une rivalité sportive oppose notamment MoGo à Crazy Stone, un programme développé par Rémi Coulom, maître de conférence à l'université Lille-III. "Nous publions nos méthodes après les compétitions, où on les met à l'épreuve, raconte-t-il. Mais dans l'ensemble, nos programmes ont tendance à converger."

Ils conservent des points aveugles, par rapport à des positions où l'ordinateur peut croire que ses pierres sont vivantes, alors qu'elles sont mortes (Semeai). Si bien qu'un humain averti peut facilement profiter de ce talon d'Achille. Résoudre le Semeai sera la prochaine étape. Mais aussi appliquer cette forme d'intelligence artificielle à la résolution de processus industriels - assemblage des milliers de pièces d'avion, gestion d'un réseau électrique ou de flottes de bus...
Les perspectives sont prometteuses : "Jusqu'ici, les algorithmes Monte Carlo ont toujours conduit à de bonnes surprises", note Tristan Cazenave.

Hervé Morin

Source

C'est l'un des jeux les plus complexe du point de vue IA.