Jeu de Dames - Site officiel de la Fédération Française de Jeu de Dames

http://fmjd.org/bb/viewtopic.php?t=1925&start=0

Voir page pour plus d'infos.

Bonjour,

Non Chinook n'a pas (encore) en mémoire toutes les positions jouables mais il n'en est pas très loin.
Pour être précis il y a, d'un point de vue théorique, 156 façons de jouer les 3 premiers coups et Chinook en a complètement résolu 20, à savoir les 20 débuts considérés par les forts joueurs comme les meilleurs débuts.

Amitiés
Gérard

Ah bon, mais pourquoi disent-ils que c'est résolu alors ?

WASHINGTON (AFP) - Après plus de 18 ans d'efforts, des scientifiques canadiens sont parvenus à programmer la totalité des 500 milliards de milliards de combinaisons possibles du jeu de dames, réalisant une avancée jugée importante en intelligence artificielle.

(Publicité)
Ce logiciel impossible à battre aux dames, baptisé Chinook, a été conçu par le détenteur de la chaire de sciences informatiques à l'université d'Alberta (Canada), Jonathan Schaeffer, avec une équipe d'informaticiens de cet établissement.

Cette percée fait l'objet d'une étude publiée jeudi dans la revue américaine Science datée du 20 juillet.

Achevé fin avril, Chinook permet de jouer jusqu'à une impasse si son opposant joue parfaitement mais sans jamais pouvoir être battu, explique ce chercheur. "C'est une véritable avancée dans le domaine de l'intelligence artificielle", selon Jaap van den Herik, éditeur de la revue de référence "International Computer Games Journal".

"Nous avons monté la barre de plusieurs échelons dans ce qu'il est possible de faire en matière de technologie informatique et d'intelligence artificielle", a estimé Jonathan Schaeffer.

"Piètre joueur de dames" de son propre aveu, ce scientifique a expliqué avoir créé Chinook pour exploiter les capacités actuelles de traitement et de mémoire des ordinateurs mais aussi pour déterminer le meilleur moyen d'incorporer les principes de l'intelligence artificielle pour jouer aux dames.

Il a recouru à l'expérience des meilleurs joueurs mondiaux pour élaborer ce programme.

Quelque 50 ordinateurs ont été mobilisés en moyenne quotidiennement depuis 1989 pour cette recherche avec dans les moments d'activité maximum plus de 200 ordinateurs fonctionnant à plein régime, précise ce chercheur.

"Nous avons poussé les connaissances actuelles dans l'application de l'intelligence artificielle aux limites extrêmes en remplaçant les connaissances humaines empiriques par des données mathématiques", a précisé Jonathan Schaeffer.

Cet informaticien avait lancé le projet Chinook avec le but initial de gagner le championnat du monde de dames.

En 1990, il a obtenu le droit d'y participer. En 1992, Chinook a perdu en finale mais a gagné en 1994 devenant le premier logiciel à remporter un titre mondial dans tous les jeux objet d'une compétition. Cette victoire sans précédent est inscrite dans le livre Guinness Book des records.

Chinook est resté invaincu au championnat du monde jusqu'à sa mise "à la retraite" en 1997.

Mais Jonanthan Schaeffer souhaitait mettre au point un programme absolument imbattable et s'est remis au travail en 2001 pour atteindre cet objectif, considérant que les capacités des nouveaux ordinateurs s'étaient considérablement accrues.

"Percer toutes les combinaisons du jeu de dames a été mon obsession pendant près de vingt ans et il est très satisfaisant d'y parvenir", a relevé l'informaticien.

Il n'est pas encore question de s'attaquer à toutes les combinaisons du jeu d'échecs dont le nombre astronomique occuperait les ordinateurs d'aujourd'hui les plus puissants pendant plusieurs siècles, selon les scientifiques.

Il existe des programmes spécialisés aux échecs dont le premier est "Deep Blue" qu'a affronté le champion du monde du moment, Garry Kasparov, en 1996. Ce dernier a triomphé, mais pour perdre une année plus tard contre le successeur de Deep Blue, Deeper Blue.

Le poker est la dernière passion de Jonathan Schaeffer. Avec son logiciel de jeu Polaris, il devait affronter deux joueurs professionnels les 24 et 25 juillet à Vancouver (Canada) lors de la conférence annuelle de l'organisation pour la promotion de l'intelligence articielle

Bonjour Nicloas,

Tu sais bien que ce n'est pas incompatible de dire d'une part que le jeu est résolu et d'autre part de dire que l'on n'a pas toutes les positions en mémoire.

Pour les non initiés aux algorithmes utilisés en informatique et en prenant comme exemple les dames internationales :
pour montrer que le jeu conduit forcément à la nulle il serait suffisant de prouver :
1) Que sur le premier coup blanc les noirs ont au moins la nulle en jouant par exemple 19-23
2) Que les noirs ne peuvent pas gagner si les blancs commencent par exemple par 32-28.

Vous voyez clairement qu'il n'est pas nécessaire d'avoir en mémoire toutes les positions possibles pour "résoudre" le jeu.
Dans mon exemple ci-dessus le début 1.33-28 18-23 n'a jamais été regardé et il n'est pas nécessaire de le regarder pour prouver la nulle.

Amitiés
Gérard

OK. D'accord, donc on a bien prouvé la nulle.

J'ai cru un instant qu'on avait utilisé la connaissance humaine des 20 meilleures variantes pour faire la démonstration.

J'ai lu ton post trop vite.

Amitiés.

Dr. Schaeffer, an author of Chinook, told me that they solved GAYP (GO-AS-YOU-PLEASE) - major 3-move 20 openings of game. This is less than 13% of the whole game - 156 3-move sound openings.

However, GAYP is classic freestyle form of game which is played professionally more than 200 years, including more than 150 years of human fighting for title.

I think it was a great accomplishment for Chinook team to solve GAYP, but there is long way to go

Respectfully,

Alex Moiseyev
3-move Checkers World Champion