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

Bonjour Arnaud,

Pour info : Damy trouve en moins de 15 secondes un gambit qui lui semble avantageux. Il approfondit ensuite cette voie et en moins de 1'30" il vérifie que ce gambit mène au gain de pion : pour éviter les combinaisons extraordinaires qui trainent, Damy, après le gambit des blancs, donne immédiatement 2 pions en jouant 18-23 !

Magnifique !

Gérard

Hum, moins de 15 secondes, c'est vraiment une brute !!
Ecoeurant. Je pense que l'auteur y a pourtant passé des jours voire des semaines...

La relative lenteur de Buggy pour trouver la solution m'a intrigué. J'ai donc ressorti mes sources pour essayer de comprendre. A priori, cette lenteur ne me paraissait pas incroyable, car j'avais déjà eu un problème similaire avec le coup énorme manqué par Tchizov dans la partie qu'il avait perdu contre Fennema. Buggy avait eu toutes les difficultés pour trouver ce coup qui ne devait être qu'une formalité pour un logiciel. J'avais à l'époque, si mes souvenirs sont bons, modifié légèrement Buggy pour qu'il trouve la solution un peu plus rapidement.

Ceci étant, je me doutais que Buggy n'était pas une bête de concours pour les problèmes et les combinaisons où il faut donner beaucoup de pièces. Je ne m'en étais jamais inquiété, sans doute avec raison, car dans les milliers de parties qu'il avait joué contre d'autres logiciels (surtout Dam 2.2 et Flits, et je vous rassure, c'était automatisé), jamais je n'ai vu Buggy perdre à cause d'un aveuglement tactique.

J'ai creusé un peu le problème ce soir pour comprendre et en fait, je n'ai pas mis longtemps à trouver le réglage à modifier pour que Buggy trouve le problème plus rapidement. Avant modification, Buggy indiquait 2/3 de pion d'avantage au bout de 10 minutes, puis finalement il moulinait encore 50 minutes pour aller à la profondeur suivante et donner un pion d'avance.

Après modification, Buggy indique les 2/3 de pions au bout de 7 secondes et le pion au bout de 20 secondes. Cette fois, il fait mieux que Damy. Mais cela ne veut pas dire que Damy ne peut pas faire mieux. Il y a fort à parier que si Gérard regarde ça un peu, il pourra très rapidement modifier Damy pour qu'il trouve ce problème là en moins de temps encore.

Alors, quel est ce réglage qui peut faire changer les choses si nettement ? Eh bien, il est simple, il tient sur une seule ligne de code.

Dans un programme de dames, pour pouvoir trouver les coups, on considère que les prises ne sont pas des coups normaux et ainsi les prises ne comptent pas dans la profondeur. Ainsi, 10 coups de profondeur peuvent en réalité cacher 6 ou 7 prises, pour un total réel de 16 ou 17 coups de profondeur.

Buggy fait cela aussi. Seulement au-delà d'un certain nombre de pions de retard, il considère que les chances de trouver une combinaison sont devenues faibles et pour éviter de passer son temps à calculer des variantes où on donne tous ses pions (ça pourrait peut-être arriver dans certaines positions), il commence alors à compter les prises comme des coups normaux.

La conséquence est immédiate. Les combinaisons, comme celle proposée par Arnaud, où on doit temporairement accuser un grand retard (jusqu'à 10 pions si on compte la dame adversaire pour 3 pions), sont trouvées moins rapidement. En l'occurence, cela implique que Buggy doit regarder non plus 12 mais 17 coups plus loin. Pour aller un coup plus loin, il faut 2,5 fois plus de temps en moyenne. Donc pour 4 coups, 2,5 puissance 5, soit 100 fois plus de temps. Et c'est à peu près l'ordre de grandeur entre une heure et 20 secondes comme observé.

Comme je l'indiquais plus haut, si le logiciel était modifié pour chercher uniquement des problèmes, il pourrait probablement même trouver la solution en une fraction de secondes.

Maintenant, Gérard, j'ai une question. Est-ce que cette idée que j'ai eu un jour est une lubie ou est-ce que c'est un plus dans le programme ? Ai-je raison d'avoir peur de positions où le logiciel passerait son temps à donner des pions au détriment des variantes normales ou bien n'est-ce pas significatif ? Je n'ai pas de souvenir de cela, mais probablement un jour, je me suis retrouvé confronté à cette solution et que j'en suis arrivé à cette solution.

Qu'en penses-tu ?

En tout cas, bravo pour le problème. Difficile de faire beaucoup plus difficile et surtout beaucoup plus long.

J'ai mis Buggy à tourner. J'avoue être assez fasciné par la position. Et ce qu'il est en train de montrer me laisse perplexe. J'attends impatiemment le coup suivant pour en savoir plus. Là ça fait bientôt un quart d'heure qu'il tourne et son évaluation a grimpé au bout de 6 minutes... Et un début de variante étonnant, sans aucun sens pour moi.

Pour l'auteur la solution est la suivante:
37-31 27x36
35-30 (menace 29-24)
... 09-14 (20-24 29x20 25x35 est sanctionné par 26-21 16x27 38-32 27x38 39-33 38x29 34x03 tandis que 19-23 permet 29-24 20x29 47-42 36x47 42-37 47x33 39x28)
30-24 19x30
47-42 36x47
42-37 47x24
26-21 16x27
38-32 27x38
34-29 24x33
39x10 05x14
49-43 38x49
40-35 49x40
35x24 20x29
45x01 (maintenant les noirs doivent préparer des crochets pour capturer la dame blanche tandis que les blancs filent avec le pion 48)
... 14-19
48-42 19-24
42-37 04-09
37-31 09-13
01-45 24-30
31-26 13-19
26-21 19-24
45-01 30-35
21-17 25-30
17-11 35-40
01x45 30-34
45x20 15x24
11-07 24-29
07-01 29-33
01-34 33-38
34-48
Avec gain par opposition (28 temps au total).
Quand on pense que Damy trouve en 15 secondes... ça vaut bien la majuscule sur le D :-)

Comment çà en 15 secondes ??? Pas avec un début gambit !

Bonjour,

Ce n'est pas si compliqué que cela pour Damy car son analyse se termine à 45x01! (il a alors atteint sa base de données à 6 pièces avec un résultat incontestable)

Amitiés
Gérard

Même si Damy n'analyse que les 13 premiers temps, il y a quand même gambit, forcing... et une profondeur importante.
Je crois que maintenant c'est un fait avéré: on a vraiment franchi la ligne et les humains (y compris des cadors comme GEORGIEV, TCHIZJOV...) ne seront plus du tout en mesure de rivaliser avec les logiciels (bon, aux échecs c'est pareil si on reprend les derniers résultats homme-machine avec la défaite de Kramnik 4-2 contre Deep Fritz ou le massacre de ADAMS par Hydra 5,5-0,5).
Se faire planter un truc comme ça en blitz, il y a de quoi arrêter de jouer :o)

A noter qu'il serait intéressant d'organiser un match Damy-Humain avec les conditions du match ADAMS-Hydra (150000$ pour ADAMS pour le match répartis de la façon suivante : pour chaque partie (6) 25000$ par victoire, 10000$ par nulle et 0$ par défaite. Autant dire qu'il n'a pas touché lourd :o)...)

Si la base de débuts de partie de Damy est à l'image du reste, qui pourra lui prendre une partie ? Buggy peut-être ?

Ok Gérard, tu as gagné !

Il est commercialisé ton machin ? Combien ça coûte et ou puis-je l'acheter ? Faut pas rigoler, je me trouve à quatre années-lumière de l'Héxagone et de vos *#@!!! de technologies de pointe !

Sinon, je voudrais aussi des renseignements sur les autres : Buggy, Truus, Damage… forces, faiblesses, prix, disponibilités, etc (c'est des concurrents, mais le jeu passe d'abord)

J'ai déjà Flits (pas une trop ancienne version, j'espère).

à quand une rencontre DAMY-BUGGY ?
peut-être à Allinges ?
---
@bientôt
Patrick

DAMY ne pourrait'il pas jouer contre BUGGY sur Kurnik ?

Si çà continue, çà va être pire qu'on scrabble où la machine te fait le top à tous les coups. Ca fait chier quand même de se faire sytèmatiquement tanner par une machine qu'on a soi-même conçue. Heureusement que l'humain n'est pas la machine (comme on dit chez nous), parce que t'imagines un cdm où tous les cyber-joueurs…

Le computer doit rester à sa place de subordonné, moi je dis. Il y va de notre amour-propre de génie (auto-proclamé) de la création.

Bonjour,

J'ai de plus en plus de demande (en France comme à l'étranger) pour l'acquistion de Damy mais (pour l'instant) je fais toujours la même réponse. Je ne le cmmercialise pas pour au moins 3 raisons :

1) Je continue d'améliorer Damy quasiment tous les jours (sur l'algorithme d'exploration, sur la fonction d'évaluation, sur la base de données de fin de partie pour passer à 7 pièces etc.) C'est très excitant pour moi et n'ai pas du tout envie de faire une pause pour travailler à mettre au point une version vraiment commercialisable (il me faudrait par exemple créer différents niveaux de jeu, améliorer l'ergonmie en général, faire des test avec plusieurs version de système d'exploitation etc.)
2) Damy travaille dans un environnement informatique que très peu de joueurs de dames ont à leur disposition : d'abord j'ai 2 Go de mémoire centrale et ensuite Damy travaille avec 2 processeurs en parallèle, chacun calculant des variantes différentes. Pour info j'ai noté à Hamel que le logiciel Dragon travaillait avec 4 Go et un quadri-processeurs et donc je prépare dès maintenant une nouvelle extension de Damy pour travailler avec plus de 2 processeurs.
3) Je n'ai fait jusqu'à maintenant qu'un seul tournoi international d'ordinateurs; il y a encore beaucoup de chose à prouver et je n'ai pas envie aujourd'hui de mettre Damy à disposition et donner ainsi à mes adversaires l'occasion de trouver les faiblesses de Damy

Amitiés
Gérard

Tu as raison, Gérard ! Fais-nous du bon boulot, nous patienterons.

Il a failli avoir une rencontre Damy-Buggy à Hamel mais un malheureux problème matériel sur Buggy à tout gâcher.
Mon prochain tournoi sera normalement celui de Culemborg en fin d'année. Je ne sais pas si Buggy pourra être présent mais ce serait évidement une très bonne occasion de voir ce que font ces programmes entre eux et aussi contre les autres (il faut bien sûr être très efficace contre les programme sensés moins forts).
Amitiés
Gérard

Bonsoir, en ce qui concerne l'évaluation des logiciels de jeu de dames ou la comparaison de ceux-ci en tournoi, cela est surprenant de voir que certains programmes fonctionnent sur des ordinateurs surpuissants comportant plusieurs processeurs et que d'autres fonctionnent sur des portables lambda. Il faudrait faire tourner les programmes sur des P.C. équivalents en mémoire RAM et en vitesse de calcul (fréquence du processeur). Daniel

Tu as bien sûr tout à fait raison. Le seul hic c'est que comme pour le jeu de dames des humains, le jeu de dames des logiciels n'a pas grand budget. En conséquence, ta requête est difficilement applicable. A moins de trouver un sponsor bien rare.

Aux échecs, le problème est le même, et il est rare que les tournois se fassent à égalité. C'est arrivé néanmoins.

Bonsoir Nicolas. Un grand bravo à toi et à Gérard Taille et aux autres joueurs de dames qui passent beaucoup de temps sur leur programme. Je ne fais pas une demande mais intellectuellement c'est tout de même surprenant de classer des logiciels avec des ordinateurs totalement différents (même s'il ne faut pas en faire un drame c'est sûr). Dans un message précédent, vous comparez le temps de recherche des logiciels pour trouver une solution à un problème, mais vous savez mieux que moi que celui-ci dépend de la puissance de calcul de l'ordinateur. Damy d'ailleurs est impressionnant !Il peut faire des trouvailles ! Amitiés.

Bonsoir,

Il y a du pour et du contre dans la proposition d'avoir le même environnement informatique pour tout le monde.

Une des premières difficultés serait de choisir la configuration de référence sur laquelle tourneraient tous les programmes : faut-il imposer le système d'exploitation, la mémoire centrale, le nombre de processeurs et leur type, la taille des mots manipulables (32eb , 64eb etc.) la mémoire cache, le type de disque dur ...
Ce serait un vrai casse tête qui n'aurait aucun sens vue l'évolution rapide de la technologie et qui aurait pour conséquence que les programmeurs ne seraient pas incités à explorer les voies nouvelles offertes par la technologie.
Sur le fond l'idée est séduisante mais en pratique ce serait très difficile et même nuisible si cela bride les programmeurs.
Tous les sports utilisant du matériel ont le même problème, de la course à pied (avec certain qui courent pieds nus à côté d'autres avec des chaussures très performantes) à la formule 1, en passant par le vélo, la voile etc.
Je pense qu'il faut accepter cela.
En ce qui concernen Damy je pense qu'il a une bonne configuration pour un laptop mais il est bien sûr inférieur aux configurations des desktops que j'ai vu à Hamel ... ce qui ne l'a pas empêché de gagner :-)

Amitiés
Gérard

Bonsoir Gérard, ce n'est pas une proposition et tu as raison si on ne va pas au delà du raisonnable (genre 6 processeurs sur le PC!!! Il fait déjà chaud dans les salles de jeu ...) D'ailleurs il faudrait alors des personnes compétentes pour évaluer les caractéristiques du pc genre passage aux mines pour les voitures avant les compétitions !!! Amitiés Daniel

Bonjour,

Ma version biprocesseurs de Damy se met gentiment au point et j’ai regardé ce que cela donne avec le problème de Sijbrands présenté par Arnaud

Damy commence par choisir la variante :
1.29-24 19x30 2.35x24 20x29 3.34x23 18x29 4.37-31 27x36 5.47-42 36x47 6.42-37 47x33 7.39x19 09-14 8.19x10 05x14 9.37-32 14-19 10.44-39 et décrète l’avantage blanc

Au bout de 5" Damy trouve que le coup 37-31 donne également l’avantage aux blancs mais en restant inférieur à 29-24.
Au bout de 25" Damy trouve que le coup 37-31 est définitivement meilleur que 29-24

Belle amélioration par rapport à ma version mono-processeur, ce qui est très motivant pour continuer à travailler sur l'algorithme que j'ai trouvé pour gérer le biprocesseur et sur lequel je travaille maintenant depuis 2 mois.

Amitiés
Gérard

Gérard, que penses-tu de mon message "élagages" ?

Par ailleurs, quel facteur gagnes-tu avec un bi-processeur ? 1,6, 1,7, 1,8 ?

Bonjour Nicolas,

Je ne peux qu'être d'accord avec ce que tu dis sur les élagages. On sait que toute la puissance de l'algorithme d'exploration réside dans sa capacité à passer du temps sur les coups intéressants et donc à passer le moins de temps possibles sur les coups qui ne le sont pas. Le paramètrage est empirique (en ce qui me concerne) et il y a un savant mélange entre les aspects combinatoires (se mettre en désavantage matériel) et les aspects positionnels.

Comme Buggy, Damy donne ses pions jusqu'à une certaine profondeur et ensuite il s'arrête en décrétant qu'il s'agit d'un cul-de-sac. Pour Damy cette profondeur est assez importante car je n'ai pas observé une très grosse perte de temps du fait de ces prises.

Par contre il est évident que la profondeur d'exploration est très pénalisée en cas de gambit.

Je ne sais pas répondre à ta question du gain obtenu avec un bi-processeur car l'algorithme d'exploration est totalement différent; le problème est en effet de faire en sorte que les 2 processeurs travaillent le moins possible sur les mêmes données car il est très pénalysant de gérer des exclusions d'accès. En conséquence j'ai dû complètement revoir l'algorithme alpha-beta ainsi que la gestion de la table de hashage.

Pour les non informaticiens imaginez que vous faite une partie à 2 contre 2. Comment répartissez-vous la tâches de réflexion entre les 2 partenaires ? Comment, en cours de réflexion, échangez-vous les informations déjà trouvées et comment prenez-vous en compte une nouvelle information donnée par le partenaire ? Comment éviter de ne pas être sans arrêt dérangé par l'information venant du partenaire ? Comment traiter le cas où la variante analysée par l'un des partenaires a pu être menée avec une profondeur plus grande ? etc. etc.
Ce n'est pas simple du tout mais c'est très intéressant à étudier.

Amitiés
Gérard

Pour info avec le logiciel Virtual Draughts:

en 27 secondes la variante choisi : 1.29-24 19x30 2.35x24 20x29 3.34x23 18x29 4.37-31 27x36 5.47-42 36x47 6.42-37 47x33 7.39x19 09-14 8.19x10 05x14 9.44-39

Mais il trouve la bonne solution en 1 minute et 29 secondes sur un ordinateur portable athlon 3200+ avec 1Go de ram donc rien a voir avec la configuration de Gérard.

Bonjour
Ou peut-on télécharger le logiciel virtual Draughts ?
Merci

Bonsoir.
Truss trouve aussi la solution en plus de temps mais avec une vieille machine.