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

Bonjour Laurent,

Pour ton info je suis à peu prêt certain qu'aucun ordinateur (au moins ceux qui étaient à Hamel) n'utilise la procédure minimax. Cette méthode est bien trop basique pour être performante. La procédure de base utilisée est la procédure alpha-beta à laquelle on peut rajouter tout un tas de rafinements pour la rendre encore plus efficace.

Pour répondre maintenant à ta question il faut distinguer 2 cas suivant qu'il s'agit de faire jouer un ordinateur contre un autre ordinateur ou un ordinateur contre un humain.

Contre un autre ordinateur il faut à mon avis toujours jouer le coup considéré par le programme comme le plus fort, à moins bien sûr d’avoir des informations sur les faiblesses du programme adverse.

Contre un humain la situation est très différente. Je n'ai pas programmé Damy pour jouer spécifiquement contre un humain mais il est assez facile de faire des modifications en ce sens en fonction de la connaissance que l'on a de l'adversaire : personnalisation de la bibliothèque d'ouverture, valorisation plus ou moins importante de la notion de temps d'avance pour inciter l'ordinateur à jouer plus ou moins agressivement, valorisation plus ou moins importante de l'occupation du centre suivant que l'adversaire est plus ou moins à l'aise face à des stratégies d'encerclement, pénalisation des échanges pour limiter les possibilités d'échanges simplificateurs etc.

Pour aller dans le sens des pièges dont tu parles j’ai déjà réfléchi à cette question. Je ne l’ai pas programmé sur Damy mais je pense sérieusement le faire un jour car ce n’est pas très compliqué. L’idée est très vicieuse : supposons que, outre le coup considéré comme le plus fort, Damy trouve un deuxième coup qui n’est pas trop éloigné du premier. Damy regarde alors quel est selon lui la meilleure réponse adverse en faisant le calcul sur une profondeur N. Si maintenant il trouve que cette réponse adverse est en fait très mauvaise en analysant à une profondeur N+1 on peut en déduire qu’il y certainement un beau piège (surtout si N est grand !) à tenter et on peut décider en connaissance de cause de jouer le coup qui est analytiquement un peu inférieur.
J’imagine facilement qu’un humain, face à une telle version de Damy, serait très mal à l’aise !

Cela répond-t-il à ta question ?

Amitiés
Gérard

Salut Gérard et Laurent,

Même en dehors de ces subtilités, les anticipations sur une grande profondeur par Damy peuvent déjà surprendre.

En ce qui me concerne, je persiste néanmoins à vouloir faire un résultat contre Damy dans un style risqué (pas encore le cas jusqu'ici...). Quitte à atténuer un peu la complexité.


Mais, bien entendu, il convient de ne pas craindre de faire évoluer Damy !

En jouant contre Damy, comme dans les exercices proposés par Laurent ou Arnaud, la chose que l'on travaille le plus, c'est la profondeur d'évaluation.

Très bien donc

Bonjour à tous,

Concernant la remarque de Gérard sur le résultat entre humain et ordinateur sur une partie (qui tend vers la nulle si le joueur humain ne prend pas de risques), ce serait effectivement un beau challenge que d'organiser non pas un match homme-machine mais un tournoi fermé avec présence d'une machine. Avec des critères de façon à motiver les humains lors de leur rencontre face à l'IA.
Par exemple tournoi 9 joueurs + 1 PC avec des prix de la 1ère à la 5ème place + prime de victoire (ex:30€). Et pour le PC, prime de résultat (avec différence relativement entre gain et nulle et faible écart entre nulle et perte. Par exemple pour un ordre de grandeur, perte:20€, nulle 30€, gain 60€).
A mon avis il y aurait de quoi faire un bon petit tournoi...
Si je parle argent, c'est parce qu'il n'y a que ça pour vraiment motiver les joueurs du top mondial (ça et un titre majeur bien entendu), et la formule prime de victoire permet de motiver même ceux qui sont à la traîne au classement général.

Dans une formule tournoi, on serait en effet un peu mieux fixé sur la force de l'ordinateur, non seulement sa capacité à ne pas perdre, mais surtout celle à prendre chaque opportunité de gain à fond (voir l'exemple SCHWARTZMAN-THIJSSEN)

Bonjour Gérard, Faustin et Arnaud.
Je connais (le principe) des techniques d'élagage, comme l'élégage sélectif sans risque, ou alfa béta, qui permet des économies de calcul. Mais j'ai cru comprendre que c'était une optimisation du minimax. Est-ce que je me trompe?

Je crois effectivement que Damy serait encore plus redoutable contre l'homme en introduisant un facteur psychologique, peut être en prenant compte la pendule. Paradoxalement, et c'est une idée qui me fascine, un ordinateur deviendrait plus fort (ou productif) en "s'humanisant"!

L'homme essaye tant bien que mal de faire du minimax, mais comme l'avait remarqué Thierry Delmotte lors d'un stage, il est souvent victime d'un réflexe de paresse.
Les forts joueurs ont une autre technique d'élagage, qui consiste à générer des coups plausibles, comme dans Schwarzman-Thijssen:


Après la cassure 29...18-22 30.29×18 22×31 31.26×37 13×22 32.37-31 24-29 33.33×24 20×29 34.34×23 22-28 35.41-37 28×19



Schwarzman a sans doute procédé de cette façon en recherchant une position calme, c’est à dire une structure connue: 36.39-33 9-13 37.33-28 3-8 38.44-39 8-12 39.40-34 13-18 40.31-27 2-8 41.37-31 8-13 42.31-26 19-24




Je reconnais bien le côté miremax de Faustin :) pour qui le regret maximum serait de faire une partie terne. La semi ouverte est peut être une stratégie intéressante, car elle est difficilement "lisible" par plusieurs programmes (test perso et discussion avec Nicolas). Est-ce que Damy est à l'aise dans ce style?

Le match ordinateur-homme (son meilleur représentant) crée une sorte de fantasme pour le grand public, mais sportivement, une formule comme celle d’Arnaud me paraît plus intéressante.

Amitiés
Laurent

Bonjour Laurent,

Non c’est la procédure alpha-beta qui est une amélioration da la procédure mini-max.

Je vais prendre un exemple pour ceux qui veulent un peu savoir ce qui se cache derrière ces procédures

Prenons la position après :
1.32-18 18-23 2.37-32 donnant un coup de mazette
Supposons que le programme soit bien inspiré pour regarder en premier le coup 2…23-29. Il trouve alors un gain de 2 pions. Le programme va ensuite regarder un autre coup que 2…23-29 pour essayer de faire encore mieux.
Supposons qu’il commence par 2…20-24. Quelle sera alors la différence entre minimax et alpha-beta ?

En minimax il va regarder tous les coups blancs possibles pour chercher le meilleur coup blanc et ensuite il va constater que, sur le meilleur coup blanc il ne gagne pas 2 pions, ce qui veut dire que 2…20-24 est inférieur à 2…23-29.

En alpha-beta il commence par regarder le premier coup blanc. Supposons que ce soit le coup parfaitement stupide 3.35-30?? il verra alors que noir gagne certes 1 pion mais par contre qu’il ne peut pas gagner 2 pions. Fort de cette information il va en déduire qu’il est parfaitement inutile de regarder les autres coups blancs et il va immédiatement conclure que 2…23-29 est strictement meilleur que 3…20-24 car 2…23-29 gagne 2 pions alors que 2…20-24 permet 3.35-30! qui ne donne qu’un seul pion !!!

En résumé la procédure alpha-beta permet d’éviter de chercher à tout moment le meilleur coup ce qui conduit en définitive à des gains de temps absolument considérables.

Amitiés
Gérard

Gérard,
Ton exemple est lumineux!
Mais c'est bien ce que voulais dire dans mon post: l'alpha béta est une optimisation du minimax.
Amitiés
Laurent

Bonjour Laurent et les autres,

J’ai essayé de réfléchir à la possibilité de programmer proprement des tentés de pièges face à un adversaire humain.

Je suis intéressé par tous vos commentaires sur l’idée que j’ai en tête

Prenons l’exemple donné par Laurent

Trait aux blancs

Pour info, Damy (comme je pense la plupart des programmes) essaye d’évaluer les possibilités adverses en allant à des profondeurs de plus en plus grandes.
Sans chercher à savoir ce que veut dire une profondeur de calcul pour Damy (ce n’est pas exactement la profondeur en nombre de demi-coups mais cela y ressemble néanmoins), j’ai trouvé les résultats suivants (toutes les évaluations sont donnés du point de vue des blancs) pour le premier coup blanc :

Profondeur 14 (le calcul a duré 7") : 6 coups jouables avec les évaluations suivantes :
45-40 : +0,38
49-44 : +0,32
39-33 : +0,25
38-33 : +0,19
49-43 : +0,07
27-21 : +0,00
Etc.

Si j’analyse les opportunités de piège sur les 3 meilleurs premiers coups je trouve :
Position après 45-40
Profondeur 12 : 4 coups jouables
24-29 : 0,18
16-21 : 0,30
24-30 : 0,48
14-20 : 0,55
Profondeur 13 : 4 coups jouables
14-20 : 0,30
24-30 : 0,30
24-29 : 0,44
16-21 : 0,65
Donc pas vraiment de piège liés au coup 45-40

Position après 49-44
Profondeur 12 : 3 coups jouables
24-30 : 0,40
24-29 : 0,48
14-20 : 0,55
Profondeur 13 : 4 coups jouables
Position après 45-40
24-30 : 0,25
14-20 : 0,30
24-29 : 0,42
15-20 : 0,51
Là non plus pas de piège liès au coup 49-44

Position après 39-33 :
Profondeur 12 : 4 coups jouables
14-19 : +0,26
14-20 : +0,26
24-30 : +0,41
24-29 : + 0,52
Profondeur 13 : 2 coups jouables
14-19 : +0,25
14-20 : +0,25
Le coup 39-33 crée donc un double piège puisque les coups 24-30 et 24-29 disparaissent des coups jouables quand on passe de la profondeur 12 à la profondeur 13

Ainsi pour apprendre à Damy à jouer « humainement » il faudrait que dans de telles situations je fournisse à Damy un algorithme disant qu’il est préférable de jouer 39-33 (valeur 0,25) plutôt que 45-40 (valeur 0,38) car le premier coup à l’avantage de tenter un piège (et même un double piège) de niveau 13 donc assez caché (même pour un très fort joueur).

Programmer cela n’est pas du tout insurmontable mais demande un peu de temps. Il faut que j’y réfléchisse un peu plus et je suppose que je paramétrerais alors Damy pour s’adapter au niveau de l’adversaire dans la conception des pièges.
Contre un joueur débutant je peux accepter de ne pas jouer le meilleur coup afin de tenter un coup de mazette (piège de niveau 1) alors que ce sacrifice n’aurait pas de sens contre un joueur non débutant.

Contre un GMI je note qu’un piège de niveau 13 peut à l’occasion fonctionner !

Ceci dit, dans la position considérée le piège 39-33 (au lieu de 45-40) n’est pas vraiment optimum car, au niveau 12, le meilleur coup noir n’est pas 24-30 mais 14-20 ou 14-19.

Le meilleur piège serait un cas ou le meilleur coup au niveau 12 serait largement en tête mais s’avérerait très mauvais au niveau 13. La probabilité de réussite doit être alors à son maximum et donc justifierait pleinement le choix d’un coup moins fort.

Dernière remarque : il faut que le coup moins fort que l’on choisit pour faire un piège ne soit pas trop éloigné du meilleur coup et cela pour 2 raisons : la première est qu’il ne faut pas prendre des risques inconsidérés et la deuxième est qu’il ne faut pas mettre la puce à l’oreille à votre adversaire. Si un fort joueur vous joue un coup qui ne vous semble pas très bon n’êtes vous pas naturellement enclin à penser qu’il vous tend à piège si vous jouez la réponse naturelle ?

Que pensez-vous de cette approche ?

Amitiés
Gérard

Gérard,
Cette approche me semble très intéressante, et je vais chercher quelques diagrammes pour tester la démarche. A bientôt donc!
Amitiés
Laurent

Bonjour,

Partant du diagramme d’Arnaud j’ai rajouté un pion blanc en 47 car il manquait un pion blanc et j’ai mis le pion noir 10 en 4 pour me positionner avant un tenté de piège.


Trait aux noirs

Evaluations (données vue des blancs) de Damy des 3 meilleurs coups à la profondeur 14 :
06-11 : -0,06
12-17 : -0,03
04-10 : -0,01

Sur 04-10 le meilleur coup blanc jusqu’à la profondeur 9 est 27-22 et, à partir de la profondeur 10, Damy démontre que 27-22 est erroné.
Voilà un piège que je qualifierais d’idéal car premièrement la différence entre les évaluations de 06-11 et 04-10 est complètement négligeable (et bien inférieure à la marge d’erreur) et deuxièmement le piège est de niveau 10 (dans l’échelle de Damy) ce qui n’est donc pas si facile à voir ! Contre un très fort joueur ce piège de niveau 10 sera probablement éventé mais comme il ne coûte rien …

Je suis de plus en plus motivé pour programmer ce style de jeu sur Damy !

Amitiés
Gérard

L'idée est bien sûr intéressante. J'ai l'impression qu'elle a été sous-exploitée jusqu'ici par les programmeurs d'échecs ou de dames.

Elle me semble tout à fait utilisable, même si elle a de gros défauts. Tout ce que Gérard décrit a un coût, non négligeable quand même. Si l'on veut implémenter l'algorithme de Gérard, il faut avoir l'information selon laquelle deux coups sont jouables (peu différents en évaluation), il faut avoir la valeur exacte de ces deux coups et non pas se contenter de prouver que le premier est meilleur que l'autre (ce qu'on fait jusqu'ici). Typiquement, je pense que cela pourrait causer un doublement du temps de réflexion nécessaire. On voit bien que si on va peut-être gagner d'un côté, en particulier dans les confrontations contre des humains, on va le perdre de l'autre. Comme dans tout, l'affaire est une question de compromis et il faut trouver où placer l'équilibre. Vu ce que je viens de dire, j'aurais tendance à penser que l'investissement ne sera pas rentable dans les combats entre logiciels. Contre les humains bien sûr, un coup de profondeur en moins n'est pas aussi important et en conséquence l'idée a plus de chances d'aboutir.

J'aimerais signaler aussi que la mise en place d'un algorithme plus complexe répondant au même objectif pourrait rapidement tomber face à un écueil de taille (non !! Pas de Taille :)). L'Alpha-Beta est une optimisation du Minimax, mais il y a encore pas mal d'autres algorithmes qui ont été inventés ensuite (Negamax...) sans parler des extensions singulières. Ces algorithmes sont loin d'être simples. Ils sont surtout très fragiles et l'ajout du moindre raffinement peut être délicat, voire impossible. Je parle d'expérience, j'ai aussi fait mes propres optimisations qui se sont greffés plus ou moins facilement sur une base disons standard. De même que la gestion multi-processeur est un casse-tête (on l'a bien vu avec les arguments avancés par Gérard récemment à ce sujet), la modification de l'algorithme pour viser un objectif différent (tenter les fautes) peut être extrêmement difficile si même réalisable. L'idée avancée par Gérard est suffisament simple pour ne pas nécessiter de mettre les mains dans le cambouis à l'intérieur de l'arbre et n'entre donc pas dans ce cadre. Elle donnera d'ailleurs sûrement des résultats à moindre frais. Je dis simplement que si l'on voulait vraiment pousser cette idée, on buterait à mon avis rapidement sur des murs. En résumé, il est impossible d'avoir un algorithme à la fois optimisé pour trouver le meilleur coup d'un point de vue analytique et optimisé pour trouver le coup le plus "vicieux". Ce sont deux objectifs différents.

http://fmjd.org/bb/viewtopic.php?t=1925&postdays=0&postorder=asc&start=15

Voir aussi ce sujet FMJD animé notamment par G. TAILLE.
Ce sujet contient trois pages. Pensez à cliquer sur PAGE SUIVANTE ou NEXT PAGE.

Bonsoir Gérard,
La position ci-dessous est très vicieuse. Quel coup, peut être pas le plus fort dans l'évaluation, tente une faute.
Je précise que Flits, c'est le plus étonnant pour moi, commet la faute et livre la manoeuvre de Scholma! (sans doute un oubli dans la programmation)
Amitiés
Laurent

Super cette nouvelle fonctionnalité pour insérer les diagrammes, si on clique sur insérer!
Voilà la position:

Bonsoir Laurent,

Analyse de Damy :
Profondeur 14 : 7 coups jouables
38-32 : +0,07
41-36 : +0,05
47-42 : +0,00
44-40 : -0,01
43-39 : -0,01
44-39 : -0,04
41-37 : -0,05

Sur 38-32 il y a le piège 23-29? (niveau 1)
Sur 44-40 il y a le piège 23-29? (niveau 4)
Sur 43-39 il y a le piège de la combinaison 26-21,38-32 (niveau 1)
Sur 44-39 il y a le piège de la combinaison 26-21,38-32 (niveau 1) mais aussi les pièges 17-22? (niveau 9), 09-13? (niveau 9) et 23-29 (niveau 4)
Sur 41-37 il y a le piège 23-29? (niveau 5)

A la vue des résultats précédents on a envie de jouer 44-39 mais il faut encore faire une dernière vérification : si après 44-39 je mets Damy au niveau 8 (donc dans l’incapacité de voir les 2 pièges de niveau 9) alors Damy trouve que 17-22 est précisément le meilleur coup !!!
La situation est donc idéale, il faut absolument jouer 44-39 !! (contre un humain).

Amitiés
Gérard

Pour les damistes, 44-39!



introduit la menace 26-21 et 38-32
interdit 23-29 par 27-22 38-32 et 47-42
interdit 17-22 par 38-32 11-17 26-21 etc.
interdit 9-13 (nous retrouvons la composition de Scholma) par 27-22!! 18x36 33-28 23x32 38x27 avec menaces imparables 27-21ou22 et 47-42

Bonjour Laurent et Gérard,
En effet après 2mn30 Flits joue 0.9-13 avec une profondeur de calcul de 14 temps et indique que la position est égale.
Donc ce type de programmation peut même être utile contrte un ordinateur ! qui semble laissé de côté la variante de gambit de 2 pions.
Amitiés
Serge
PS maintenant 5mn30 tjrs 09-13?

Bonjour,

Serge je crois que tu peux revendre flits pour 1€ ou alors ton micro manque de ram

Je viens de faire le test sur mon PC
Analyse de la position de départ
Coup Prof. Score Coup Adverse
38-32 14 -0.042 8-13
44-40 14 -0.046 10-14
41-37 14 -0.046 10-14
43-39 14 -0.062 9-13
47-42 14 -0.070 9-13
44-39 14 -0.073 8-13
41-36 14 -0.080 9-13
27-21 14 -0.761 16x27x36
33-29 13 -1.207 24x33x42
33-28 13 -2.093 23x32x21
27-22 12 -4.668 17x28x39x50
26-21 12 -5.570 17x26x37x46

Comme Gérard 7 réponses possibles. Sur 44-39
Dragon indique

Coup Prof. Score Coup Adverse
8-13 11 0.082 49-44
17-22 11 -0.595 38-32
9-13 11 -1.080 27-22
10-15 11 -1.168 26-21
8-12 9 -1.873 26-21
24-30 10 -1.892 26-21
10-14 10 -2.266 26-21
9-14 10 -2.283 26-21
18-22 10 -2.311 27x18x29x20
16-21 9 -4.400 27x16x7
17-21 9 -4.426 26x17x6
23-28 9 -6.549 33x22x13x4x15
24-29 9 -6.556 33x24x13x4x15
23-29 8 -200.000 27-22

Il bascule 9-13 non jouable lorsque la profondeur est à 7. Il lui faut à peine 10s pour s'orienter sur 8-13 P4 1,7Ghz.

Le piège est à priori éventé par Dragon d'ou ma remarque sur flits?
suaf erreur de ma part (le facteur humain)
j'obtiens après 1.44-39 9-13? 2.27-22 18x36 3.33-28 23x32 4.38x27 une position perdante pour les noirs

Bonsoir Jacky
Flits joue très bien, mais a quelques défauts de programmation, comme sur le diagramme suivant que j'avais proposé sur l'Effort:



Après 23-29, 4-10, 14-20, 19-23, 13x35, 5-10, 3-9, 6x46*:



Flits ne voit pas le blocage 38-33 21x32 42-37 32x41, et donc le gain par 33-28 16-21 49-43 21-27 43-38 26-31 28-23 31-37 38-32 37x19 36-31 27x36 44-39 19-24 39-34 35-40 34-30 24x35 45x34 +

Il doit ignorer ou élaguer assez vite les variantes d'offres avec perte d'inititive (gambits)

Malgré ce défaut, il demeure très fort, comme le disait Gérard lors des anciennes confrontations contre Damy

Amitiés
Laurent

Bsr Laurent,

moi aussi je conserve flits mais aussi Dragon bien que sur le problème que tu expose il n'y voit rien. Il bloque aussi sur 38-33

En fait pendant longtemps il lui donne un score de 0,200 soit un léger avantage puis en passant à 19 de profondeur il dit remise!!!

Ouf heureusement il est gratuit et pratique pour l'analyse

A+

Comme quoi, il faut relativiser les performances de nos cauchemards numériques!
Amitiés
Laurent

Je vous rassure, Buggy ne trouve pas non plus en un temps raisonnable. Il ne trouve d'ailleurs même pas après avoir joué pas mal de coups. C'est un problème anti-logiciel type.

Buggy trouve en revanche le gambit de Scholma. Là, Flits souffre visiblement d'un bug car la profondeur nécessaire pour trouver ce coup est insuffisante. visiblement il élague brutalement à 2 pions de retard.

Bonjour Nicolas,
Apparemment, Damy trouve la solution immédiatement, si je me souviens bien d'un échange avec Gérard. Pourquoi?
Amitiés
Laurent

Bonjour Laurent,



Je ne sais pas comment est programmé Buggy mais quand Damy voit la formation ci-dessus il défavorise énormément la valeur de la dame noire. En conséquence Damy fait jouer les blancs de telle sorte de précisément enfermer la dame noire (on peut aussi remplacer le pion blanc en 36 par un pion noir et la pénalisation est encore plus elevée)
Si Buggy ne recherche pas cette configuration précise l'explication devient évidente.

Amitiés
Gérard

J'allais proposer plusieurs explications. Celle que tu donnes en faisait partie, bien que je ne pensais pas que ce soit la bonne.

Cette configuration est très rare et je n'ai jamais eu l'occasion de la croiser dans les parties de Buggy. Je pense que tu dois être l'un des seuls à l'avoir dans ton programme. Bravo.

Pour mes autres explications, voyons :

D'abord, il faut parler de la façon habituelle de calculer des logiciels. En général, c'est la profondeur de coups qui est utilisée comme mesure, et on va de plus en plus loin, dans cette profondeur. Pour calculer la profondeur en cours de variante, on n'utilise pas un compte de profondeur, mais plutôt un compte raffiné où sont ajoutés et retranchés des coups (ou des fractions de coups) s'il y a :
- trop de pions de retard
- des prises (les prises ne comptent pas)
- un coup unique (bien meilleur que les autres appelé extension singulière)
- un passage à dame
- une pion qui vient de damer
- une combinaison reconnue
- une attaque sur un pion précis (taquin, canadien, kherkhov typiquement)
- tout autre événement digne d'intérêt.
- un nombre restreint de coups pour un des joueurs

Le dernier critère est particulièrement intéressant : pour résoudre le problème proposé, il est évident que si le logiciel va plus loin lorsqu'il y a peu de coups noirs (ce qui est le cas souvent dans ce problème après les différents gambits), il a beaucoup plus de chances de trouver rapidement la solution. Ce genre de cas est assez rare à mon avis (là encore, j'ai rarement vu Buggy dominer tactiquement par un autre logiciel, et je n'ai donc jamais été forcé à regarder tout ça de près, bien que je sois convaincu qu'il y ait matière à trouver des choses fort positives) et de ce fait, je ne sais pas si cette approche est intéressante (en tout cas, je ne crois pas toute seule, peut-être mixée avec la méthode traditionnelle).

Il y a enfin une dernière idée, voisine de la dernière d'ailleurs. C'est de ne plus baser la répartition du temps sur la profondeur (ou la profondeur raffinée comme vu plus haut), mais plutôt sur le nombre de coups cherchés. On répartirait ainsi 10000 noeuds (=positions) sur chaque coup au début, puis 100000, puis 1000000, etc. Ainsi une variante où il y a peu de coups à chercher (comme ici la variante après gambits) sera mécaniquement vue à une profondeur plus élevée. Séduit au départ par cette approche, j'ai l'impression qu'elle est néanmoins difficile à mettre en oeuvre, car comment répartir le nombre de noeuds entre les variantes ? Sachant qu'on ne connaît jamais à l'avance la vitesse à laquelle on va pouvoir calculer une variante (car d'une part on ne connaît pas le nombre de coups jouables dans la variante, et d'autre part, car on ne saît pas si on va pouvoir prouver rapidement que la variante est mauvaise ou au contraire si la variante est très bonne).

Si j'avais eu à parier, j'aurais dit que Gérard avait implémenté l'option la plus simple à savoir "chercher plus loin lorsque le nombre de coups est limité pour un des joueurs".

Mais apparemment, je me suis trompé :)

Bonsoir Nicolas,

Incontestatblement la gestion de la profondeur d'analyse est une partie très intéressante du programme. Dans mes premières versions de Damy je m'étais basé sur la dernière idée que tu as exposée.
Chaque noeud avait un crédit en nombre de positions qu'il pouvait générer, et ce noeud répartissait comme il voulait ce crédit sur les différents coups possibles. Je faisais à cet effet une évaluation rapide des coups possibles et je donnais d'autant plus de crédit que l'évaluation d'un coup était élevée.
J'ai finalement abandonné cette approche quand j'ai introduit une table de hachage. J'ai vu en effet que je ne pouvais pas profiter pleinement des positions atteintes par interversion de coup du fait que les crédits associés étaient toujours différents puisque dépendant des autres coups possibles.
Je suis donc revenu à une fraction de profondeur (demi-coup) avec une gestion dépendant effectivement d'un certain nombre d'événements dont le principal est le gambit.
Dernier point, ma gestion de la profondeur est différente quand j'approche d'une feuille de l'arbre car il faut essayer de limiter le plus possible l'effet horizon.

Amitiés
Gérard

Amitiés
Gérard

Ce débat sur la possibilité de prendre des risques pour l'ordi est spécialement évocateur surtout lorsqu'il est agrémenté d'un moment de la formidable partie entre Thijssen et Schwarzman.

On le sait, le Damier Niçois a le privilège d'inviter régulièrement des champions du monde, grâce à la force d'attraction du tournoi de Cannes.

Schwarzman est l'un des invités réguliers et l'un des plus appréciés. Lors de son dernier séjour niçois, cette année, il avait été invité à commenter trois de ses parties cannoises : contre Ndjofang, contre Gulubieva et contre Ndonzi.

Ce fut un festival !

Dans la partie contre Ndjogang, il nous montra que positionnellement, Ndjofang avait pris l'avantage positionnel à cause d'un projet de combinaison loupé que Schwarzman avait fomenté (un truc giga compliqué). Il s'attacha alors à nous montrer qu'ensuite, il ne joue pas les meilleurs coups, délibérément ! choisissant des coups spécialement risqués dans le but de cacher la combinaison victorieuse qui traînait. Certes, reconnaît-il, Ndjofang s'est relâché probablement. Mais, selon Schwarzman, si Ndjofang avait joué les meilleurs coups, la seule chose Schwarzman avait prévu, c'était un gambit défensif qui donnait une compensation dont il n'avait pas pu évaluer la force dans la partie.

Il nous précisait que dans certains cas, le coup logique appelle une réaction logique et que c'est pour éviter cela que parfois il accepte des chemins risqués, voire aventureux ! Le chemin le plus susceptibles d'exposer l'adversaire à des erreurs ou approximations : mais redisons-le, chez lui, cela est délibéré, même si, parfois, il le reconnaît, il ne sait pas forcément où il s'engage !

Il évoqua aussi les coups pseudo défensifs de Ndonzi. Selon lui, Ndonzi est très bon tacticien et, même en défense, il recherche des positions qui peuvent permettre d'appuyer ensuite une manace ou une combi. Il nous a montré comment dans leur partie ouverte les choses étaient délicates, Ndonzi recherchant aussi la dissimulation de ses menaces !

L'un de ces moments avait été commenté sur le forum après Cannes.