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

Permettez-moi de ne pas être tout-à-fait d’accord.

Pour démontrer que le position initiale est nulle, il convient de prouver que, quelles que soient les réponses de noir, blanc est en mesure d'assurer la nulle ! Cela suppose donc, sinon d'avoir inventorié l’ensemble des ramifications de l’arbre des possibilités, d’avoir démontré que certaines d’entre-elles sont irrémédiablement dominées et peuvent donc être écartées...

Quant à réaliser un programme mettant en œuvre cette stratégie du jeu de Dames assurant au moins la nullité, c’est évidemment une autre question, sinon résolue, du moins en mesure de l'être.

La résolution de cette question, somme toute subsidiaire, ne serait d'ailleurs pas facilitée, si de surcroît, elle devait couvrir la résolution des problèmes issus des positions exhibées, sans aucun rapport avec le jeu de Dames traditionnel. Gardons-nous d’assimiler celles-ci à des positions pratiques prises au hasard !

À cet égard, deux dernières remarques :
1/- la grande mobilité des Dames est toute relative, elle est limitée par la règle de la prise maximale en présence de prise et ne dépasse jamais 19 cases dans le cas contraire (comparable à celle des échecs 20 possibilités initiales et sensiblement autant lors des finales fou cavalier par exemple),
2/- Même si cela peut permettre d’avancer, en attaquant le problème par les deux bouts, la résolution du jeu ne passe pas nécessairement par l’étude exhaustive des (j'allais dire innombrables) multiples finales éventuelles comportant de nombreuses dames accompagnées ou non de plusieurs pions, les parties de l'Open International de Cannes 2013 se terminent d’ailleurs avec un nombre restreint de dames...

Distinguons donc, d'abord, la démonstration de l'existence d'une stratégie de résolution du jeu de celle de la construction d'un programme la mettant en œuvre, ensuite celle de la résolution du jeu, de celle de la résolution de tous les problèmes susceptibles d'être posés avec le matériel du jeu de Dames.

Bonjour Julien,

Je n'ai pas compris avec qui ou avec quoi tu n'es pas d'accord.

Je vois que nous sommes d'accord sur le fond et en partcicuier qu'il faut bien distinguer:
1) Démontrer que la position initiale est nulle (c'est ce qui a été fait pour les checkers)
2) Avoir un programme qui assure la nulle contre toute stratégie
3) Avoir un programme qui donne le résultat de n'importe quelle position
sur la grosse diférence qu'il y a entre démontrer que la position est nulle

Ceci dit il faut bien comprendre qu'un programme qui serait capable d'assurer la nulle serait en fait un très mauvais programme dont personne ne voudrait car il est évident qu'un tel programme pionnerait systématiquement tout ce qui bouge afin d'arriver le plus rapidement possible à cette nulle. En ce sens en dehors de la satisfaction intellectuelle de faire un programme difficile je ne vois pas trop l'intérêt. Dans Damy quand je suis dans une situation ou la nulle est complétement démontrée j'essaye (ce n'est pas facile du tout!) de trouver des coups qui pourraient piéger mon adversaire et j'évite autant que faire se peut de faire des échanges simplificateurs prouvant la nulle.

Sur la notion de position pratique prise au hasard, pour moi c'est simplement une position du style (je n'ai pas trouver mieux comme définition) de toutes celles qui ont déjà été rencontrées en partie réelle. Cela exclut donc quantité de positions exotiques qui font le bonheur des problémistes et des amoureux des combinaisons les plus diaboliques.

Il y a un point qui m'interpèle dans ton discours: bien qu'un programme assurant la nulle ne m'intéresse pas beaucoup, j'aimerais bien savoir ce qui te fait dire qu'un programme mettant en œuvre cette stratégie existe ou du moins est en mesure d'exister ?

Amitiés
Gérard

Démontrer que la position initiale est nulle veut dire que quelles que soient les qualités de blanc, il ne peut qu'assurer une partie nulle devant un jouer parfait. Mais la propriété caractéristique de la stratégie optimale à mettre en oeuvre par les deux joueurs, tient au fait que tout joueur qui s'en écarte ne peut que réduire son gain. Un programme qui mettrait en œuvre cette stratégie irait donc bien au delà de l'assurance de la nulle devant un joueur humain.

La théorie des jeux nous enseigne l'existence de cette stratégie sur tous les jeux à deux joueurs, à somme nulle (les gains de l'un sont les pertes de l'autre) et à information complète (les positions sont parfaitement connues des deux joueurs) se déroulant sur un graphe (des positions ou sommets reliés par des arcs définis par la règle du jeu) sans cycles. Les Échecs, les Dames (avec des règles limitant les situations répétitives), l'Othello, le Go et bien d'autres sont donc des jeux qui seront c'est démontré résolus un jour ou l'autre...

Autrement dit, il existe pour tous ces jeux une stratégie optimale assurant soit le gain, la nulle ou la perte pour le joueur ayant le trait initial.

Résoudre le jeu signifie donc avoir, d'une manière ou d'une autre, complètement inventorié l'arbre des possibilités pour s'assurer que l'adversaire ne pouvait pas faire mieux. Cela suppose donc que l'on dispose des moyens d'apporter cette démonstration pour toutes les situations susceptibles d'être rencontrées au cours d'une partie. De là à mettre en œuvre un programme, il n'y a qu'un pas dont le franchissement devrait être accompli très rapidement compte tenu du rythme des progrès récents (voir par exemple cette page).


Ceci n'a aucun rapport avec le comportement des programme qui, non susceptibles d'aller voir loin dans l'arbre des possibilités, s'en remettent, fautes d'indicateurs stratégiques plus pertinents, à des fonctions d'évaluations basées sur des nombre de prises ou de pions restants pour préférer des gains à courte vue tant qu'il avancent à dans le noir...

Mais, des progrès conséquents ont été accomplis (des jeux comme l'Othello ont mis à jour l'intérêt de notions telles que les degrés de liberté des joueurs) et plus généralement les fonctions d'évaluations et méthodes ont beaucoup évolué ces dernières années, les programmes sont maintenant capables, comme les humains (qu'ils imitent avec des bibliothèques d'ouvertures), de repérer des situations pseudo-cycliques comme dans la partie de Douvres.

Maintenant, s'il est à craindre qu'une machine joue mieux que les humains dans quelques années, et que des jeux comme les Échecs ou les Dames perdent un peu de leur mystérieux attraits (comme les femmes voilées ?), il est peu probable que la stratégie optimale puissent être exhibée aisément. Sa complexité ne pourrait donc être rendue intelligible que par les grands maîtres ou experts qui seuls sauront nous éclairer sur les lignes directrices et stratégies mises en œuvre...

Bien à vous.

Il y a en fait trois types de jeux "résolus" d'après la page wikipedia citée par julien007 :

les jeux dits "très faiblement résolus", le 1er coup des blancs donne le gain (ou la nulle, ou la perte) si les deux joueurs jouent le meilleur coup à chaque fois.

les jeux dits "faiblement résolus", où il existe une stratégie qui assure le gain pour l'un des deux joueurs, ou la nulle, à partir de la position initiale (en gros, il existe une partie "idéale") : c'est le cas des checkers.

les jeux dits "fortement résolus", comme précédemment, mais à partir de n'importe quelle position donnée : exemple, le puissance 4.


Au passage, et sauf erreur de ma part, les positions au jeu de dames international avec 8 pièces sont entièrement résolues, il faudrait donc mettre à jour cette page wikipedia qui s'arrête à 7 :)
http://en.wikipedia.org/wiki/Solved_game#Partially_solved_games


SG

Bonsoir,

Concernant les bases de données de fin de partie à 8 pièces ou plus du jeu de dames international la situation est la suivante:

Kingsrow a les bases de données complètes 4x4 et 5x3 et quelques bases de données partielles à 9 pièces
Dragon a les bases de données complètes 4x4 et 5x3
Damy a les bases de données complètes 4x4, 5x3 et 6x2

Personne à ma connaisance n'a construit la base de données 7x1 tout simplement parce que personne n'a vu l'intérêt de cette base.

Donc, à l'exception de la base marginale 7x1, les positions à 8 pièces sont résolues.

Pour information il y a environ 20 000 milliards de positions à 8 pièces et la base de données correspondante (bien compressée!) prend environ 400 Go.

Amitiés
Gérard

Merci pour ces précisions Gérard.

SG