Le jeu de Dames bientôt résolu?

L'origine du jeu de Dames reste bien mal connu, les historiens ayant préféré s'attarder à son populaire grand frère, le jeu d'Échecs. Il reste que des études sérieuses prétendent que le jeu de Dames lui est antérieur et daterait au moins de 2 siècles avant J-C. Il est même possible que ce jeu ait été connu des anciens grecs ou des anciens égyptiens.

Chose certaine, si on ne sait trop où et comment le jeu de Dames a été inventé, il y a de bonnes chances pour que nous vivions à l'époque où il aura livré son dernier secret. En effet, le jeu de Dames fait partie de la famille des jeux à deux joueurs à information complète; une famille qui compte aussi les Échecs, le Go, le Jeu du Moulin et le Mancala entre autres. Tous ces jeux ont ceci de particulier qu'il existe une façon de jouer de manière optimale. C'est-à-dire qu'ils se classent nécessairement dans une de ces trois catégories:

• Le joueur qui commence, s'il ne commet aucune erreur, trouvera toujours une façon pour remporter la partie;
  
• Peu importe le coup joué par le premier joueur, le second joueur, s'il ne commet aucune erreur, pourra toujours remporter la partie;
• Si aucun des deux joueurs ne commet une erreur, la partie sera nulle.

Il est possible de construire une preuve mathématiques, généralement en s'aidant d'un ordinateur, permettant de classer un jeu dans une de ces catégories. On dira alors du jeu qu'il est résolu.

Si ça a été fait depuis longtemps pour les jeux simples, comme le Jeu du Moulin, le Mancala ou le récent Babylone de Bruno Faidutti (la discussion est ici, le joueur idéal est ici), les poids lourds comme les Échecs ou le Go sont encore très loin d'être résolus. On doute d'ailleurs que ce dernier le soit un jour compte tenu du grand nombre de parties possibles, qui dépasse largement le nombre d'atomes dans l'univers!

Le jeu de Dames occupe quant-à-lui un terrain intermédiaire. Son plateau de 8x8 cases (pour les dames anglaises) permet un grand nombre de positions, mais les pièces toutes identiques et les captures obligées réduisent de façon importante les possibilités. C'est d'ailleurs grâce à ces caractéristiques que Chinook, une intelligence artificielle mise-au-point à l'université de l'Alberta à Edmonton, a réussit en 1994 à décrocher le titre de champion du monde du jeu de Dames.

Aujourd'hui, Chinook s'occupe à résoudre le jeu de Dames. Il y arrive d'ailleurs très bien! En janvier 1995, il était parvenu à faire un pas important en prouvant que les trois coups de l'ouverture White Doctor menait à une nulle si les deux joueurs ne faisient aucune erreur. Depuis, Chinook a résolu 5 nouvelles ouvertures de trois coups... Dont trois en juillet de cette année! Toutes ces ouvertures mènent à des parties nulles.

Cette accélération de la vitesse à laquelle l'intelligence artificielle parvient à résoudre des ouvertures nous permettent de croire qu'il ne reste que peu de temps avant qu'on ne soit fixé sur la véritable nature du jeu de Dames. D'ici là les paris sont ouverts...