Chinook a trouvé la solution du jeu de dames

Après 5000 ans de réflexions, le jeu de dames à 8 cases est résolu, il n'a plus de mystère. Les adeptes de ce jeu de société peuvent ranger leur boîte et trouver une autre occupation.
Depuis 1910, les maîtres de cette variante du jeu de dames ont toujours dit que les blancs gagneraient dans la situation de jeu présentée à droite. Le programme informatique Chinook vient de prouver qu'ils se trompaient, et ce en moins d'une seconde. Nous allons y revenir.

Jonathan Schaeffer et ses collègues de l'Université d'Alberta ont créé un programme imbattable de jeu de dames appelé Chinook. "Il n'y a plus un être humain vivant aujourd'hui qui puisse gagner contre le programme", a déclaré Schaeffer, laissant toutefois une ouverture possible à une personne capable d'accomplir l'improbable scénario de jouer un jeu parfait. Non seulement Chinook est imbattable, mais au dire de son inventeur, il exécute tous les mouvements et toutes les configurations de jeu possible, de sorte qu'il ne sera jamais, jamais surpris par son adversaire.
Abandonne, pauvre humain !
Schaeffer a commencé son projet sur un ordinateur en 1989. Il s'est rapidement passionné pour son projet, au point qu'il utilisa finalement plus de 200 ordinateurs pour ses recherches. A l'image des programmes distribués (SETIathome, Climateprediction, Predictor, etc), dont la puissance de calcul dépasse 200 TFLOPS, trois fois celle des derniers superordinateurs, Chinook tire profit d'un réseau d'ordinateurs massivement parallèles afin d'obtenir la plus grande puissance de calcul pour résoudre les phases les plus complexes du jeu. "Nous avons un département informatique, nous avons donc beaucoup d'ordinateurs" explique Schaeffer. "La plupart des ordinateurs sont juste là et disponibles."
Pour faire de Chinook un joueur de dames parfait, Schaeffer a dû analyser tous les scénarii possibles et faire calculer par Chinook le meilleur mouvement pour chacun d'eux. Il y a enregistré 500 milliards de milliards de configurations différentes de jeu.
Schaeffer, qui se considère comme un "mauvais" joueur de dames, a fait appel à la communauté des joueurs de dames pour apprendre au programme ce que constituait les subtilités du jeu, comme les mouvements contre-intuitifs.

En 1992, Chinook perdit contre le Dr. Marion Tinsley, maître du jeu de dames. Mais le programme évolua vite et Chinook gagna en 1994. Ceci dit, Schaeffer n'était pas encore satisfait car son objectif était de créer un programme complet et parfait, le seul pouvant "résoudre" le jeu de dames.
En 1997, les ordinateurs 32 bits (genre Pentium) étaient communs mais incapables d'effectuer assez rapidement les calculs de Schaeffer. Il a donc attendu quatre années pour que s'applique la Loi de Moore (qui veut que la technologie double la puissance des processeurs en moins de 18 mois). En 2001, il recommença donc son projet avec des processeurs de 64 bits.
"Je me rappelle qu'au début du projet original, il pensait que c'était un jeu d'enfant", dit Richard Beckwith, représentant la Fondation américaine des joueurs de dames (ACF). "Il ne pensait pas qu'il y avait autant de choses en jeu. Et nous sommes 20 ans plus tard."
Schaeffer reconnaît qu'il mit du temps à réaliser que le problème du jeu de dames était finalement compliqué, à sa plus grande surprise.
Le succès de Chinook marque un pas de plus vers la longue marche des machines vers la domination de tous les jeux d'adresse. Cela a commencé avec la programmation du Backgammon, du Scrabble, et bien sûr du jeu d'échecs. C'est en 1997 que le "Deep Blue" d'IBM a battu un grand-maître humain. Prochainement, Schaeffer reculera probablement les limites du poker.
Au delà du jeu
Apprendre aux ordinateurs à jouer et les opposer ensuite aux humains, est plus qu'un simple divertissement. Des programmes comme Chinook permettent de réaliser des calculs très lourds, offrant aux chercheurs la possibilité de s'attaquer à des problèmes plus "sérieux" comme l'analyse de la structure des protéines ou essayer de comprendre le fonctionnement des gènes.
Apprendre aux ordinateurs à jouer montre également aux scientifiques comment modéliser l'esprit humain plus efficacement. "Je suis un chercheur en intelligence artificielle" précise Schaeffer. "Je m'intéresse à la construction d'ordinateur se comportant comme des êtres humains. j'ai toujours choisi de travailler avec des jeux parce que leurs règles sont simples et c'est amusant."
De manière inattendue, Chinook pourra aider les joueurs de dames, en posant à l'ordinateur leurs énigmes afin que Chinook les résolve. Dans un cas, Chinook a déjà disputé une partie qui remontait à plus de deux siècles.

La position de 197 ans
En effet, en 1800, un article publié dans un journal consacré au jeu de dame présentait une situation particulière et prétendait que, sauf erreur, les blancs gagnaient toujours la partie. D'autres joueurs qui, évidemment avaient du temps à perdre, n'étaient pas d'accord, ce qui ouvrit un large débat autour de la question : dans cette configuration de jeu (Cf. haut de page), si les deux joueurs jouent sans commettre d'erreur, les blancs vont-ils gagner ou perdre ?
Pendant un siècle, d'innombrables articles ont débattu la question, souvent en allant jusqu'à des centaines de mouvements d'avance dans des jeux hypothétiques pour prouver leurs arguments. En 1900, un article convaincut la communauté que les blancs gagneraient. Le scénario sera connu sous le nom de "La position de 100 ans".
En 1997, le grand-maître du jeu de dames Don Lafferty demanda à Schaeffer de confirmer l'hypothèse de 1910. En une fraction de seconde, se rappelle Shaeffer, Chinook a trouvé que les blancs allaient perdre, et non pas gagner. Lafferty examina le résultat et l'accepta de fait, car la preuve communément acceptée présentait une erreur dans le troisième mouvement que des dizaines d'experts du jeu de dames n'ont pas remarquée. La position a depuis été rebaptisée "La position de 197 ans" ("197-year Position" dans la littérature anglo-saxonne).
Le Go, dernier refuge de l'intelligence humaine
Maintenant que les jeux de dames et d'échecs n'ont (presque) plus de secret, d'autres chercheurs du groupe de Schaeffer, dont notamment Martin Muller et Akihiro Kishimoto tournent leurs regards vers ce qui semble, dans l'esprit de nombreux joueurs, comme le test ultime de l'intelligence artificielle : le jeu traditionnel du Go.

Ne pas confondre le Go, "igo" en japonais, avec ses versions simplifiées que sont le go-moku ou le go-ban et le reversi (Othello), qui sont des variantes du morpion où il faut aligner une couleur.

Malgré l'optimisme des chercheurs et une abondante littérature scientifique sur ce jeu de stratégie, des joueurs passionnés comme Roy Laird, président de l'Association Américaine de Go (AGA) restent sceptique à l'idée qu'un ordinateur puisse jamais battre un humain au Go. "Le Go est réellement le seul jeu qui n'a pas encore été plus ou moins résolu par un ordinateur", nous dit Laird. "C'est trop difficile. J'aime appeler le Go le dernier refuge de l'intelligence humaine." Si ce jeu vous intéresse, voyez le site de la Revue Française de Go.
En attendant cet éventuel simulateur parfait de Go, essayez d'affronter Chinook. Pour ne pas vous démoraliser, c'est la version "débutant" du jeu; il perd parfois.
Pour plus d'information, consultez la page de Wikipedia et le site Internet des fédérations belges (FRBJD) et françaises (FFJD) du jeu de dames.