[Jeu de Dames - La Rose et le Glaive]
L’informaticien Jonathan Schaeffer et son équipe de l’université d’Alberta au Canada ont annoncé le 19 juillet 2007 qu’ils avaient résolu le jeu de dames. Sur un jeu parfait de part et d’autre, c’est partie nulle.
Source:
http://www.sciam.com/article.cfm?articl … anID=sa007
Correction : il s’agit du jeu de dames anglaises (damier de 8x8), comme indiqué par L.S.G., et non des dames internationales (damier de 10x10).
j’espere qu’ils ont pas été payé pour ca quand meme…
y en a qui ont vraiment du temps a perdre 
Il ne faut pas dire ça.
Ca a effectivement pris dans les vingt ans pour calculer les 500 milliard de milliard de positions (5x10 puissance 20), mais ce genre de recherche fait progresser les connaissances et correspond en gros à une grosse démonstration mathémathique (genre théorème de Fermat). Donc ce n’est pas complètement inutile…
La mention de Tinsley dans l’article montre qu’il s’agit du jeu nommé Checkers, autrement dit, les dames anglaises, et non de celui qu’on appelle ici “le jeu de dames”.
Sacomplexité bien spérieure le laisse sans doute encore hors de portée des grands calculateurs … ce n’est qu’un sursis !
Mais des tas de jeux sont résolus, comme Babylone ou Puissance 4, sans que celà nous empêche de les pratiquer !
Merci Karis.
Les techniques de réduction de l’arbre des possibilités utilisées dans des cas comme celui-ci sont des résultats mathématiques en tant que tel. Bien plus applicables que le théorème de Fermat d’ailleurs (même si je pense quand même qu’elles sont d’une moins grande “profondeur” à la base).
À quand les échecs ? À quand le Go ?
En tout cas, c’est étonnant et impressionnant. Franchement, je suis épaté par ce type de démonstrations !
Je n’ai pas bien compris ce que veut dire “résoudre un jeu”.
Si un volontaire veut bien m’expliquer…
D’avance merci à lui !
goetzilla dit:Je n'ai pas bien compris ce que veut dire "résoudre un jeu".
Si un volontaire veut bien m'expliquer...
D'avance merci à lui !
J'allais poser la même question !
Je suis nul en théorie mathématique ou choses de ce genre. Alors, un jeu résolu, c'est quoi ?
Un jeu dont on peut déterminer toutes les issues possibles (sans approximation) à partir d’une situation donnée à l’aide d’un algorithme de prédiction, je crois.
goetzilla dit:Je n'ai pas bien compris ce que veut dire "résoudre un jeu".
Si un volontaire veut bien m'expliquer...
D'avance merci à lui !
Cela signifie qu'ils ont mathématiquement démontré, dans le cas des dames anglaises (8x8), que lorsque les deux joueurs jouent à la perfection, la partie est nulle.
Pour d'autres jeux, on a pu démontrer que l'un des deux joueurs (souvent le premier) gagne même si l'autre joue à la perfection.
Voir : http://en.wikipedia.org/wiki/Solved_board_games
Pyjam.
Hadoken_ dit:j'espere qu'ils ont pas été payé pour ca quand meme...
y en a qui ont vraiment du temps a perdre
+1
Je rejoins cet avis.
Y'en a vraiment qui se tripottent le nombril avec peu de choses quand meme
Personnellement ce genre d'info ne me fait ni chaud ni froid si ce n'est peut etre la provocation maladive et incontrolée d'un petit sourire en coin sur mon visage. ->
Chacun son truc, chacun son trip ...
cela signifie-t-il qu’ils sont en mesure de concevoir le meilleur logiciel pour jouer à ce jeu ou bien rien à voir ?
moonboots dit:cela signifie-t-il qu'ils sont en mesure de concevoir le meilleur logiciel pour jouer à ce jeu ou bien rien à voir ?
Oui. L'auteur de la démonstration est également l'auteur du meilleur programme de dames anglaises, champion du monde depuis 1994 :
http://en.wikipedia.org/wiki/Chinook_Checkers_Program
Maintenant, son programme ne peut plus perdre (mais ça fait semble-t-il très longtemps qu'il n'avait rien perdu).
grolapinos dit:À quand les échecs ?
Pas pour tout de suite.
grolapinos dit:À quand le Go ?
Pas pour tout de suite après la résolution des échecs.
Bascombe dit:grolapinos dit:À quand les échecs ?
Pas pour tout de suite.grolapinos dit:À quand le Go ?
Pas pour tout de suite après la résolution des échecs.
Oui, oui, je m'en doute, la complexité de ces deux jeux est tout autre que celle des dames !
Déjà, l'awalé avait été résolu il y a peu, c'était une belle performance.
Bascombe dit:grolapinos dit:À quand le Go ?
Pas pour tout de suite après la résolution des échecs.
Il y a plus de positions de Go que d'atomes dans l'Univers. Il va donc falloir attendre que l'Univers grandisse encore un peu afin de stocker toutes les informations nécessaires à la résolution du Go.
L’essentiel de la résolution d’un jeu consiste justement à réduire considérablement l’arbre des possibles.
Même pour un jeu aussi “simple” que l’Awalé, il serait impossible à une machine de calculer le coup optimal à chaque fois en explorant toutes les possibilités. Il faut donc mettre au point des algorithmes d’évaluation des positions qui permettent de classifier les positions pour en éliminer la plupart et n’en conserver qu’un “petit” nombre, analysable par un ordinateur en quelques mois au maximum.
Obtenir un tel résultat pour le Go ne me semble en rien impossible, même si c’est fort improbable.
Personnellement, je suis en admiration devant les capacités intellectuelles des humains quand ils s’en donnent la peine et qu’ils ne perdent pas du temps (car là pour moi c’est une perte de temps) à faire la guerre
En effet, l’homme s’amuse à inventer des jeux avec des regles, puis invente une machine (l’ordinateur) puis un algorithme compulsable par un ordinateur pour qu’il puisse jouer mieux que lui même à son propre jeu qu’il a inventé. Autrement dit, il cree un objet qui le dépasse et en même temps un outil pour majorer ce qui le dépasse (que ce soit par la puissance de calcul et d’évaluation ou par la mémoire des positions)
Bravo
Il y a quelque chose que je ne comprends pas dans l’histoire. En suivant le lien sur Wikipedia donné plus haut ( 
celui-là), je lis…
Wikipedia dit:Checkers (or Draughts) was weakly solved on April 29, 2007 by Jonathan Schaeffer.[3] The mathematical proof was calculated from an initial position of 10 pieces or less on the board, not from the beginning of the game.[4] The number of calculations involved were 1014 and were done over a period of 18 years. The process involved from 200 desktop computers at its peak down to around 50.[5] From the standard starting position, Black (who moves first) is guaranteed a draw with perfect play. White (moving second) is also guaranteed a draw, regardless of what Black plays as the opening move. Checkers is the largest game that has been solved to date, with a search space of 5x1020. [6]Les dames anglaises ont 2x12=24 pions. Alors c’est quoi la position normale de départ avec 10 pions en tout ?
En suivant la référence [4] de Wikipedia…
Référence [4] dit:It does not matter how the players make it to 10 checkers left because from that point on, the computer cannot lose, Schaeffer said. For two players who never make a mistake, every game would be a draw, he said.Faut-il comprendre que de manière évidente il est possible de passer de 24 pions à 10 sans diminuer les chances de l’un ou l’autre camp ? Non parce que s’il reste 9 pions blanc et 1 noir à l’issue de cette première phase, moi je veux bien jouer avec blanc contre le programme qui connaît la ligne idéale de jeu.
Bref, je n’ai rien compris… Help !
Syl dit:Faut-il comprendre que de manière évidente il est possible de passer de 24 pions à 10 sans diminuer les chances de l'un ou l'autre camp ? Non parce que s'il reste 9 pions blanc et 1 noir à l'issue de cette première phase, moi je veux bien jouer avec blanc contre le programme qui connaît la ligne idéale de jeu.
Apparemment, malgré un avantage aussi fort pour toi, le programme arrivera tout de même à ne pas perdre.
Personnellement, je préférerai éviter une situation aussi embarassante. Plus sérieusement, je crois qu'il a pris le problème par les deux bouts : les ouvertures d'une part, les finales d'autres part. Donc, je suppose qu'aucune ouverture convenablement jouée de part et d'autre ne peut forcer Noir à n'avoir plus qu'un pion en face de 9.
Il y a une vidéo et des slides de présentation sur le site de Chinnook :
http://www.cs.ualberta.ca/%7Echinook/news/media.html