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

beau travail gérard.
Le nombre de positions est impressionnant quand on voit un maximum de 8 pièces sur le damier.

Peux tu nous dire le % de gains sur ces 24 482 960 766 420 positions ?

Pour générer des bases de données plus importantes , tu n'as pas envisagé de créer un générateur de positions à diffuser à des damistes. Chacun sur son ordinateur génère une partie de la base de données . Ensuite tu n'as plus qu'à rassembler ces bases partielles pour n'en faire qu'une.

Bonjour Pascal,

Michel Grimminck développeur de Dragon Draughts a fait une page à ce sujet :

http://www.xs4all.nl/~mdgsoft/draughts/stats/index.html

Cordialement,

Eddy

Bonjour Pascal, Eddy

Concernant des statistiques diverses et variées Eddy a parfaitement raison de donner ce lien qui donne beaucoup de détail. La base 6x2 n'est pas complète mais tout le reste de la base à 8 pièces est bien là et j'ai exactemant les mêmes compteurs avec Damy.

Pour répondre sur la question très générale de Pascal je dirais que les 24 482 960 766 420 positions de la base de données se répartissent comme suit:

nb Pertes : 3 928 665 685 269 => 16%
nb Nulles : 11 619 559 171 802 => 47%
nb Gains : 8 934 735 909 349 => 36%

Ceci dit il faut noter que la majorités de ces positions donnent lieu à une capture :

nb positions sans capture : 6 114 521 650 163 => 25%
nb positions avec capture : 18 368 439 116 257 => 75%

Pour gagner de la place je n'ai pas réellement stocké les positions avec capture dans la base. En conséquence je finis toujours une capture avant d'interroger la base de données.

Amitiés
Gérard

Cher Gérard
Comme toujours beau travail
pendant le tournoi international en rentrant les parties dés que la position sera de 8 pièces je noterais le résultat final et je te donnerais la statistique des résultats des parties penses tu que je serais dans le même pourcentage que tu as donné sur les résultats ??
il faut penser que dans le cas de 6 pièces contre 2 le pourcentage de gain pour les 6 pièces doit être plus qu'important peut être même = à 100%
dans ce cas ta statistique est un peu faussée il faudrait se pencher sur 4 contre 4 ou 5 contre 3
une série à 32 joueurs sur 10 Tours cela fait 160 Parties la statistique pourra donner quelque chose Amitiés
et dans l'attente que ton chiffre de combinaisons soit aussi le montant des subventions pour le jeu de dames bonne continuation

Oui Michel il est difficile de sommer les résultats de la base données à 4dames contre 4dames avec la base de données à 6 dames contre 2 pions! J'ai l'impression d'ajouter des choux et des carottes.
Pour plus de détails chacun peut aller sur le site de Michel Grimmick rappelé par Eddy

Amitiés
Gérard

Bonjour,

24 482 960 766 420 positions, cela defie dejà l'imagination.....

En complément et pour satisfaire ma curiosité, pouvez vous donner le temps (moyen, max) que met le "Damy actuel" pour retrouver une position dans une telle base 2-8 pièces compressée ?



Je remarque aussi que l'on se rapproche des capacités des PC "lambda" du moment:
- stockage (400 Go / qqs To).
- temps de calcul (142j)


2 pièces ~ 9.000 posit.
3 pièces ~ 800.000 posit.
4 pièces ~ 42.000.000 posit.
5 pièces ~ 1.500.000.000 posit.
....
8 pièces ~ 24 000 000 000 000 posit.

Le facteur de progression est nettement superieur à x10;

D'où ma deuxième question :

Ne va-t-on pas atteindre rapidement les limites d'un PC, aussi performant sera-t-il en 2012 -2013 ?

Amitiés

Jean-François.

Bonjour Jeff,

La réponse à ta première question est très facile :
"En complément et pour satisfaire ma curiosité, pouvez vous donner le temps (moyen, max) que met le "Damy actuel" pour retrouver une position dans une telle base 2-8 pièces compressée ?"
Du fait que je n'ai pas une mémoire de 400Go le temps d'accès à la mémoire dépend quasiment que du temps d'accès au disque. Donc environ 0,01s avec des disques classique et 0,0001s avec des disques SSD.

Les chiffres exacts sur le nombre de position en fonction du nombre de pièces sont les suivants:
2 pièces : 13 280
3 pièces : 806 300
4 pièces : 48 734 800
5 pièces : 1 570 600 750
6 pièces : 50 871 133 150
7 pièces : 1 119 691 797 720
8 pièces : 23 310 777 680 620
pour un total de : 24 482 960 766 420

Oui Jeff, le facteur de progression étant d'environ 20 quand on passe de 6 à 7 pièces puis de 7 à 8 pièces on ne peut guère aller plus loin si on conserve l'idée de fabriquer des bases complètes.
Pour aller plus loin il y a cepandant une autre voie, ce sont les bases de données incomplètes.
Prenons par exemple la base de données à 5x4 pièces. Au lieu de prendre toutes les positions possibles et imaginables (du genre 3 dames et 2 pions contre 2 dames et 2 pions etc.) il est possible de se concentrer sur les positions les plus intéressantes en pratique c'est-à-dire les positions avec au plus une dame sur le terrain. Le nombre de positions à considérer est alors de :

1 dame et 4 pions contre 4 pions : 1 327 372 256 700
5 pions contre 1 dame et 3 pions : 1 058 849 637 720
5 pions contre 4 pions : 236 918 517 630

Les chiffres deviennent beaucoup plus raisonables et il devient possible de passer en revue toutes ces positions.
Que va-t-il alors se passer? En analysant par exemple les positions à 1 dame et 4 pions contre 4 pions on va se retrouver très souvent avec des possibilités de promotion qui vont conduire aux bases de données 5x4 avec deux dames sur le terrain alors que ces bases de données n'existeront pas. On ne pourra donc pas donner le résultat de ces promotions ce qui fait qu'un certaine nombre de positions ne vont pas pouvoir être résolues.
Est-ce grave ? Pas forcément si beaucoup de positions parviennent cependant à être résolues. Toutes les positions théoriquement gagnantes à 5 pions contre 4 pions pour lesquels il existe un chemin de gain évitant les bases de données inexistantes à 5x4 avec 2 dames seront ainsi trouvées. Dans certains cas on pourra obtenir un résultat partiel : on peut par exemple démontrer que telle position n'est pas perdante mais on ne sait pas si elle gagnante ou nulle.

Ed. Gilbert est très avancé sur le sujet puisqu'il a déjà fait cet exercice avec les résultats suivants sur les positions 5 pions contre 4 pions :
Positions résolues : 74.0%
Position partiellement résolues : 24.0%
Positions inconnues : 2.0%

Vous voyez donc que l'on peut ainsi résoudre 3/4 des positions et pour le 1/4 restant on peut dire si elle est au moins nulle ou au plus nulle.

Par cette méthode j'ai l'intuition qu'il doit être possible d'aller jusqu'à la base à 6 pions contre 5 pions avec un taux de résolution d'environ 50%. L'avenir me dira si cela est vraiment faisable. C'est un projet pour 2012-2013!

Amitiés
Gérard

Bonjour Gérard,

Merci pour votre réponse rapide, c'est clair maintenant.

Cependant un point m'échappe encore dans votre 1re reponse: quand je fais une recherche sur mon disque de 500 Giga octets, il me faut plusieurs secondes, voire plusieurs minutes car cela nécessite de très nombreux accés disques... D'autre part 24 482 960 766 420 positions = 24 482 Giga positions sauf erreur de ma part, soit env 60 fois plus que le nombre d'octets du disque de 400 Go.. Est-ce une base simplifiée qui est en memoire disque? Et je suis curieux de connaitre son organisation pour n'obtenir qu'un seul accès disque...

Bon courage pour le projet 2012-2013.

JF Latapie

Jef,

Tes questions sont plus informatiques que damiques et donc je ne vais donc pas trop m'étendre sur le sujet. Pour plus d'informations tu peux aller sur le forum fmjd (http://laatste.info/bb3/viewforum.php?f=53) où tout ces sujets ont été beaucoup développés.
Pour répondre tout de même succinctement.
1) afin de n'avoir qu'un seul accès disque j'ai divisé mes 400Go en blocs d'environ 8ko ce qui me fait 50 M blocs. J'ai construit ensuite un fichier d'environ 1,2Go qui me permet deux choses : premièrement d'identifier à partir de n'importe quelle position le bloc concerné, deuxièmement de connaître pour tout bloc le fichier disque et l'offset dans le fichier qui permet l'accès au bloc.
2) compresser 24 000 G positions dans 400 Go n'est pas une mince affaire et il y a plusieurs façons de faire. La plupart des programmeurs ont stocké les résulats de chaque position sur 2eb ce qui représente 6000 Go et ensuite ils ont appliqué des techniques de compression purement informatiques pour gagner le facteur 15 ramenenant la taille de la base à environ 400 Go. J'ai adopté de mon côté une approche totalement différente en prenant plus de place pour chaque position mais en ne stockant dans la base de données que les positions intéressantes (à titre d'exemple pour la base à 5 dames blanches contre 2 dames noires avec trait aux blancs je ne stocke que les pertes et les nulles).

Amitiés
Gérard