Match nul

[José]

Après avoir fait tourner leurs ordinateurs pendant 18 ans, des chercheurs de l'Université d'Alberta au Canada prouvent qu'il est impossible de gagner au jeu de dames, à moins que l'adversaire ne commette une erreur :

  Citation

Alberta professor crowns ultimate checkers king

KATHERINE HARDING

From Friday's Globe and Mail

July 19, 2007 at 2:54 PM EDT

EDMONTON — In 1989, Jonathan Schaeffer, a computer scientist at the University of Alberta, punched a calculation into his computer and set it crunching numbers.

For 18 years, the computer dubbed Chinook kept running, on as many as 200 processors at once.

Prof. Schaeffer got married. He had a baby girl. He bought a bigger house. He received tenure. But at least twice a day — less a two-year period when he had to wait for the technology that could handle numbers that big — he checked his computer, lest the smallest error creep into the calculation. One number off, one tiny blip, and he'd have to start over.

He never went anywhere without his laptop. His friends suggested "he get a life." His wife began losing patience. He was, he admits, obsessed.

And then this spring — more precisely, on April 29 at 6:03 p.m. — the computer stopped.

It popped out a single word: Draw.

Prof. Schaeffer and his team had solved checkers.

While Chinook had easily beaten humans in games since the mid-90s, it can now perfectly play every game to a win or a draw.

"If I had have known it was going to take this long, I probably wouldn't have done it," Prof. Schaeffer said yesterday, the same day their ground-breaking research appeared in the academic journal Science.

Mathematicians had long assumed that checkers, if played perfectly, would end in a draw, but it was a theory that could never be proven. It would take more than a lifetime to do that kind of math.

Checkers has roughly 500 billion billion possible positions. Only a computer could answer the question, but not even Prof. Schaffer imagined it would take nearly two decades. The solution for checkers is roughly one million times more complex than Connect Four, until now the most complicated mathematical solution for a game.

Many devout checkers players around the world were wondering yesterday what Marion Tinsley would have made of the discovery coming out of Edmonton. Nicknamed "Terrible Tinsley," the American mathematician and academic is widely considered the greatest checkers player of all time.

He died of cancer in 1995, a year after he played against Chinook in Boston. Mr. Tinsley had beaten the computer in 1992, but left the 1994 match halfway through due to medical problems.

"At one time, [Mr. Tinsley] made the statement that no computer would ever beat him," Al Lyman, a lifetime member of the American Federation of Checkers, recalled in a telephone interview.

Mr. Lyman, who also runs checkerworld.com, a website dedicated to promoting the game, said Prof. Schaeffer and his colleagues' research will likely help checkers gain badly needed publicity and recognition.

"Checkers is a poor, poor world," the 67-year-old said with a sigh. "Chess has television coverage, corporate sponsorship and big prizes. Checkers simply doesn't have that and therefore it's a very small, small family."

While the game is played around the world, and there are associations in several countries including Canada and England (where it's call draughts), it has long struggled to be taken as seriously as its arch-rival, chess.

Prof. Schaeffer said people often consider the game — which uses 12 red and black pieces called checkers — simple because it is easy to learn the rules.

"It took me less than a minute to teach it to my daughter," he said. "But just because the rules of checkers are simple does not mean it's a simple game. It's a beautiful game with incredibly deep strategy."

He said their research is a major breakthrough in the field of artificial intelligence and that computer scientists have often used popular games such as chess and checkers as an experimental test bed because the "characteristics of intelligent behaviour are fundamental in those games."

While he's done computer research on chess in the 1980s, he has no immediate plans to try to solve that game unless there are major advancements in technology. "No, it's too big," he said. To put it in perspective: Checkers has roughly the square root of the number of positions in chess.

Instead, Prof. Schaeffer and his team have got their eye on another popular game: poker. Next week, Polaris, a poker-playing computer program they built will challenge two poker professionals in a $50,000 game at an artificial-intelligence conference in Vancouver.

http://www.theglobeandmail.com/servlet/sto…y/National/home

[Patrick Smets]

Manifestement, il a testé sur un damier à l'anglaise avec 12 pions et non un damier français à 15 pions.

Donc, confirmation des résultats dans 18 ans

Ceci étant, ca ne m'étonne pas. J'imagine que c'est valable pour n'importe quel jeu de ce type (échec, etc) où il n'y a pas de hasard dans la situation de début. Logiquement (enfin, il me semble), si aucun joueur ne commet jamais aucune faute, il n'y a que trois possibilités

-tjs match nul

-tjs celui qui commence gagne

-tjs celui qui commence perd

me trompe-je ?

[José]

  Schnappi a dit :

J'imagine que c'est valable pour n'importe quel jeu de ce type (échec…

Je pense que ce n'est pas vrai pour les échecs. Par contre, pour le jeu de Marienbad…

[Patrick Smets]

  Lucilio a dit :

Je pense que ce n'est pas vrai pour les échecs. Par contre, pour le jeu de Marienbad…

Pourquoi ne serait-ce pas le cas pour les échecs ?

Hormis que ca doit être horriblement complexe à calculer, qu'est-ce qui fait la différence avec les allumettes ?

[Yozz]

Ca n'a peut-être rien à voir, mais n'est-il pas plus difficile d'évaluer ce qu'est une faute pour les échecs? Autre manière de poser le même type de question, y-a-t'il une notion de gambit aux dames?

[José]

  Schnappi a dit :

Pourquoi ne serait-ce pas le cas pour les échecs ?

Hormis que ca doit être horriblement complexe à calculer…

Je pense que c'est impossible à calculer car, contrairement aux dames ou aux allumettes, aux échecs, puisque les pièces (sauf les pions) peuvent reculer, il n'existe pas de position "clic" qui force la suite des mouvements dans un sens et empêche d'autres possibilités.

  Yozz a dit :

…y-a-t'il une notion de gambit aux dames?

Je ne pense pas. Par ailleurs, il n'existe pas non plus cette notion de qualité et force de pièce : aux dames, un pion = un pion.

[Patrick Smets]

  Lucilio a dit :

Je pense que c'est impossible à calculer car, contrairement aux dames ou aux allumettes, aux échecs, puisque les pièces (sauf les pions) peuvent reculer, il n'existe pas de position "clic" qui force la suite des mouvements dans un sens et empêche d'autres possibilités.

Je ne pense pas. Par ailleurs, il n'existe pas non plus cette notion de qualité et force de pièce : aux dames, un pion = un pion.

ben, tu ne reviens pas vraiment en arrière vu que l'autre à bouger une pièce et donc la partie n'est plus la même.

les options possibles dans l'arbre décisionnel sont très nombreuses, mais c'est toujours un nombre fini -> amha, simple problème de processeur pour établir "la" stratégie optimale.

[Yozz]

  Lucilio a dit :

Je pense que c'est impossible à calculer car, contrairement aux dames ou aux allumettes, aux échecs, puisque les pièces (sauf les pions) peuvent reculer, il n'existe pas de position "clic" qui force la suite des mouvements dans un sens et empêche d'autres possibilités.

Ca ne rend pas le calcul impossible, mais simplement exagérément complexe à caculer. Le nombre de possibilités reste fini, mais a une valeur obscènement élevée. En admettant que personne ne joue aux échecs en se contentant d'un va-et-vient incessant des deux mêmes pièces.

EDIT: grillé par Schnappi

[Patrick Smets]

  Yozz a dit :

Ca n'a peut-être rien à voir, mais n'est-il pas plus d'évaluer ce qu'est une faute pour les échecs? Autre manière de poser le même type de question, y-a-t'il une notion de gambit aux dames?

Il manque un mot dans la première phrase et je ne sais pas ce qu'est un gambit, donc, difficile de te répondre

[Yozz]

  Lucilio a dit :

Je ne pense pas. Par ailleurs, il n'existe pas non plus cette notion de qualité et force de pièce : aux dames, un pion = un pion.

Ca je pense que ça doit être modélisable relativement facilement.

Bon, où sont tous les experts en IT quand on a besoin d'eux?

  Schnappi a dit :

Il manque un mot dans la première phrase et je ne sais pas ce qu'est un gambit, donc, difficile de te répondre

Quel crétin, en plus c'était le mot le plus important évidemment! Il s'agissait de "difficile", je viens d'éditer.

Un gambit, c'est un sacrifice stratégique. On perd une pièce pour gagner un avantage positionnel/stratégique sur l'adversaire.

[José]

  Yozz a dit :

Un gambit, c'est un sacrifice stratégique. On perd une pièce pour gagner un avantage positionnel/stratégique sur l'adversaire.

Et ça, je vois vraiment pas comment on peut le modéliser. Pour autant que je sache, les ordinateurs qui font le gambit, ne le font qu'à l'occasion des ouvertures qui sont stockées dans leur mémoires.

[Patrick Smets]

  Yozz a dit :

Un gambit, c'est un sacrifice stratégique. On perd une pièce pour gagner un avantage positionnel/stratégique sur l'adversaire.

Alors, ca existe aux dames. c'est même la base du jeu vu que il y a obligation de prendre une pièce.

Difficile à expliquer sans dessin, mais j'avance mon pion de façon à ce qu'en le prenant tu te mettes dans une situation telle que je vais en prendre plusieurs d'affilé et éventuellement aller à Dame.

[Yozz]

  Lucilio a dit :

Et ça, je vois vraiment pas comment on peut le modéliser. Pour autant que je sache, les ordinateurs qui font le gambit, ne le font qu'à l'occasion des ouvertures qui sont stockées dans leur mémoires.

De fait, c'est ce qui me paraît le plus difficile. Néanmoins, il y a peut-être des solutions. Par exemple, avec les pièces en jeu dans leurs positions actuelles, examiner toutes les positions finales possibles dans l'absolu, et voir s'il existe des chemins pour y arriver (en partant de la fin). Evidemment, un truc pareil prendrait des ressources de calcul énormes, mais bon, c'est le jeu.

[Patrick Smets]

  Lucilio a dit :

Et ça, je vois vraiment pas comment on peut le modéliser.

Je n'ai évidemment absolument aucune idée de comment on peut le modéliser, mais je ne vois pas pourquoi on ne pourrait pas le faire…

[Yozz]

  Schnappi a dit :

Alors, ca existe aux dames. c'est même la base du jeu vu que il y a obligation de prendre une pièce.

Difficile à expliquer sans dessin, mais j'avance mon pion de façon à ce qu'en le prenant tu te mettes dans une situation telle que je vais en prendre plusieurs d'affilé et éventuellement aller à Dame.

Ok. C'est donc bien la même idée, il doit y avoir moyen de le prendre en compte aux échecs aussi j'imagine.

  Schnappi a dit :

éventuellement aller à Dame

Pour pécho du chichon? Waw z'y va, trop défonce le jeu!

[José]

  Schnappi a dit :

Alors, ca existe aux dames. c'est même la base du jeu vu que il y a obligation de prendre une pièce.

Aux échecs, c'est différent : tu n'es pas obligé d'accepter le gambit offert, ni même de prendre une pièce d'ailleurs (autre facteur qui me dit qu'il est impossible de modéliser à 100% les échecs).

  Schnappi a dit :

…mais je ne vois pas pourquoi on ne pourrait pas le faire…

Si c'était le cas, en faisant jouer deux ordinateurs l'un contre l'autre, on devrait systématiquement arriver à des parties nulles. Or ce n'est pas le cas.

[Patrick Smets]

  Yozz a dit :

Un gambit, c'est un sacrifice stratégique. On perd une pièce pour gagner un avantage positionnel/stratégique sur l'adversaire.

Puisque, contrairement aux dames, il n'est pas obligé de prendre, pourquoi ton adversaire prendrait-il une pièce qui renforce ta position stratégique ?

Tu comptes sur le fait qu'il va commettre une erreur.

Dans le cas du jeu sans erreur dont on parle, la notion de gambit a-t-elle encore un sens ?

[José]

  Schnappi a dit :

Puisque, contrairement aux dames, il n'est pas obligé de prendre, pourquoi ton adversaire prendrait-il une pièce qui renforce ta position stratégique ?

Parce que, lui, estime que tu t'es planté dans ton calcul et que ton sacrifice sera inutile. Mais aussi, parce qu'il prévoit une meilleure parade.

[Patrick Smets]

  Lucilio a dit :

Si c'était le cas, en faisant jouer deux ordinateurs l'un contre l'autre, on devrait systématiquement arriver à des parties nulles. Or ce n'est pas le cas.

Ca a pris 18 ans pour les dames qui est un jeu très simple par comparaison aux échecs, donc je ne suis pas convaincu ?

[Yozz]

  Lucilio a dit :

Si c'était le cas, en faisant jouer deux ordinateurs l'un contre l'autre, on devrait systématiquement arriver à des parties nulles. Or ce n'est pas le cas.

Je n'ai pas conscience qu'on ait déjà fait jouer deux ordinateurs identiques l'un contre l'un. Mais peut-être suis-je juste trop peu informé (ce qui est certainement le cas dans l'absolu, je connais mal ces domaines).

  Lucilio a dit :

Parce que, lui, estime que tu t'es planté dans ton calcul et que ton sacrifice sera inutile. Mais aussi, parce qu'il prévoit une meilleure parade.

C'est juste, mais Schnappi a un point valide: un gambit qui marche repose sur une erreur de l'adversaire, un gambit qui ne marche pas repose sur une erreur de celui qui tente un gambit.

[José]

  Yozz a dit :

Je n'ai pas conscience qu'on ait déjà fait jouer deux ordinateurs identiques l'un contre l'un.

C'était un argument publicitaire du premier Mephisto qu'avait acheté mon père. Justement pour vanter l'étendue des possibilités de l'appareil et prouver quil n'était pas bêtement répétitif. Bon, c'était de la pub…

[Yozz]

  Lucilio a dit :

C'était un argument publicitaire du premier Mephisto qu'avait acheté mon père. Justement pour vanter l'étendue des possibilités de l'appareil et prouver quil n'était pas bêtement répétitif. Bon, c'était de la pub…

Bon, déjà, c'est intéressant, je ne savais pas!

Mais je pensais surtout aux machines de pointe style Deep Blue.

[José]

  Yozz a dit :

…un gambit qui marche repose sur une erreur de l'adversaire, un gambit qui ne marche pas repose sur une erreur de celui qui tente un gambit.

Pas vraiment, on peut faire le même gambit à partir de la même position et perdre ou gagner pour d'autres développements ultérieurs de la partie.

[Patrick Smets]

  Lucilio a dit :

Parce que, lui, estime que tu t'es planté dans ton calcul et que ton sacrifice sera inutile. Mais aussi, parce qu'il prévoit une meilleure parade.

Mais là encore, tu pars d'une situation où le calcul n'a pas mis en évidence toutes les combinaisons, situation actuelle.

Je te demande pouquoi tu estimes que nul ne sera jamais assez fort pour ce calcul (putain de concordance des temps )

Si le nombre de coups possibles est fini, on arrivera forcément un jour à tous les calculer. Et je ne vois pas ce qui ferait que le nombre de coup est infini.

[José]

  Yozz a dit :

…je pensais surtout aux machines de pointe style Deep Blue.

Là, mon père n'avait pas les moyens

[Patrick Smets]

  Yozz a dit :

Je n'ai pas conscience qu'on ait déjà fait jouer deux ordinateurs identiques l'un contre l'un.

Peut-être qu'ils comprendraient trop vite que ca n'a aucun intérêt, qu'ils arreteraient la partie et qu'ils iraient boire un pot.

[Yozz]

  Lucilio a dit :

Là, mon père n'avait pas les moyens

Pff, petit joueur!

Pas comme un certain NL, qui a les trois dernières générations de Deep Blue dans son salon pour amuser ses invités.

  Schnappi a dit :

Peut-être qu'ils comprendraient trop vite que ca n'a aucun intérêt, qu'ils arreteraient la partie et qu'ils iraient boire un pot.

"Hé Robert, une tournée de 220V !"

[Calembredaine]

  Yozz a dit :

Un gambit, c'est un sacrifice stratégique. On perd une pièce pour gagner un avantage positionnel/stratégique sur l'adversaire.

Ha ben merci, je suis en train de lire le "Le gambit du magicien" et suite à ton explication, les quelques chapitres que j'ai lus s'éclairent enfin.

[Patrick Smets]

Pauvre Rocou. Dire qu'il l'avait acheté parce qu'il avait lu "la grande bite du magicien"…

[José]

  Schnappi a dit :

…il avait lu "la grande bite du magicien"…

Ce que l'on comprend vu la couverture :