La définition de zugzwang de Pandolfini

[Sébastien Nadeau]

Si on veut démontrer que la position initiale est un zugzwang, alors il faut explorer toutes les possibilités et déterminer si, peu importe le coup joué au départ, les blancs perdent.

Pour l'instant, on ne peut pas résoudre le problème par la force brute, faute de hardware ou d'algorithme adéquat:

« Status: This is a finite game, but generalizations to n*n boards are EXPTIME-complete. »

Tiré de: http://www.ics.uci.edu/~eppstein/cgt/hard.html#chess

Sébastien

[Gabriel Boulianne]

Je vous voulais bien entendu que l'on démontre ma conjecture d'une manière plus réaliste.

[François Dorion]

Que dirais-tu de faire la chronique au lieu de t'attacher à résoudre un problème dont la solution ne t'empêchera jamais de jouer aux échecs?

FD

[Gabriel Boulianne]

J'ai fait ce que j'avais à faire François, Dom va poster ça partie et je posterai à la suite.

[benoitstpierre]

John,

Je crois que le "could" de Pandolfini concerne la possibilité de jouer, peu importe laquelle. C'est donc l'ensemble des possibilités qu'il caractérise par là, lequel contient uniquement des coups qui détériore la position.

Cette définition présuppose qu'on est obligé de jouer. Tu as raison de dire que sans cette présupposition, cette définition désigne une position perdante en général, i.e. une position où on ne peut parer la menace qui suit.

Mais je me demande bien pourquoi Pandolfini aurait besoin de définir la notion de zugzwang, sans cette obligation de jouer. Autrement dit, je ne vois pas le problème avec cette définition.

[benoitstpierre]

Sébastien,

Zermelo a démontré il y a de ça un bout que si le jeu d'échecs a un gagnant, c'est forcément les blancs.

[Sébastien Nadeau]

Benoît,

Merci de me citer tes références, ainsi je pourrai m'instruire.

Sébastien

[OxNumberNine]

Zermelo a démontré il y a de ça un bout que si le jeu d'échecs a un gagnant, c'est forcément les blancs.

???

Zermelo's Theorem
In chess either white can force a win, or black can force a win, or both sides can force at least a draw (Aumann, 1989, p.1)

[benoitstpierre]

Référence

Ulrich Schwalbe & Paul Walker. 2001. Zermelo and the Early History of Game Theory. Games and Economic Behavior, vol. 34, p. 123–137.

Résumé

In the modern literature on game theory there are several versions of what is known as Zermelo’s theorem. It is shown that most of these modern statements of Zermelo’s theorem [dont celle de Aumann] bear only a partial relationship to what Zermelo really did. [...] A translation of Zermelo’s paper is included in the Appendix.

[Sébastien Nadeau]

Référence

Ulrich Schwalbe & Paul Walker. 2001. Zermelo and the Early History of Game Theory. Games and Economic Behavior, vol. 34, p. 123–137.

Résumé

In the modern literature on game theory there are several versions of what is known as Zermelo’s theorem. It is shown that most of these modern statements of Zermelo’s theorem [dont celle de Aumann] bear only a partial relationship to what Zermelo really did. [...] A translation of Zermelo’s paper is included in the Appendix.

Je viens de lire en diagonale l'article, mais je n'ai pas trouvé précisément une preuve que les blancs gagnent ou annulent à partir de la position initiale. Par ailleurs, la conclusion affirme que la question est toujours ouverte. Ce que l'article semble démontrer, c'est que *SI* les blancs sont dans une position gagnante, alors ils peuvent le faire dans un nombre fini de coups, plus petit que le nombre total de positions possibles à partir de cette position.

Sébastien

[benoitstpierre]

Sébastien et Ox,

Merci donc de m'avoir fait douter. En relisant l'article, je vois que je commets la même erreur que Dimand & Dimand 1996 en accordant l'avantage aux blancs, alors qu'il est encore possible que tant l'ensemble de toutes les suites gagnantes que l'ensemble des suites nulles soient vides pour le premier joueur. (On convient qu'une partie infinie est nulle.)

Zermelo n'a jamais prouvé cela, mais bien qu'un joueur dans une position gagnante peut gagner dans un nombre de coups moindre que le nombre de positions admises par le jeu. Pour démontrer ce théorème, il aurait qu'il aurait prouvé la détermination du jeu d'échecs : ou bien ça gagne, ou bien ça perd, ou bien c'est nulle. Mais il ne s'agirait que d'un corollaire, loin d'être l'essentiel du papier de Zermelo. On commettrait aussi une autre erreur en attribuant à Zermelo le théorème du minimax du jeu d'échecs, car la première preuve reviendrait à Kalmar.

Cette recherche m'a fait découvrir un papier d'un certain Christian Ewerhart, intitulé **Backward induction and the game-theoretic analysis of chess**, que j'ai réussi à repêcher sur un site illicite et qu'il me ferait plaisir de vous faire parvenir.

[benoitstpierre]

À relire Zermelo, il n'est pas clair qu'on y trouve une preuve en tant que tel de la détermination du jeu. À relire Ewerhart, on dirait que la détermination du jeu est la même chose que le minimax.

C'est trop pour un gars qui venait juste niaiser sur Internet deux-trois heures avant de retourner à ses vacances !

[Sébastien Nadeau]

Pour démontrer ce théorème, il aurait qu'il aurait prouvé la détermination du jeu d'échecs : ou bien ça gagne, ou bien ça perd, ou bien c'est nulle.

Pour ceux qui trouvent bizarre cette affirmation évidente (un axiome, comme on dit) de Zermelo, il faut se mettre en contexte: celui-ci tente de le démontrer en ne tenant pas compte de la règle des 50 coups et généralisé à un échiquier de n*n. Là, c'est beaucoup moins évident. Mais de toute façon, ça ne règle toujours pas la question: les blancs sont-ils en zugzwang dans la position initiale?

Sébastien

[benoitstpierre]

Sébastien,

En réfléchissant aujourd'hui au problème, j'en suis arrivé à formuler certains arguments pour la thèse selon laquelle la position initiale n'est pas une situation de zugzwang (mutuel) :

1. S'il y avait zugzwang, cela contredirait la maxime de Steinitz, à la base de la pratique des échecs modernes : il ne sert à rien de chercher à combiner dès les premiers coups. Cette maxime présuppose un équilibre dynamique au départ entre les camps.

2. S'il y avait zugzwang, il faudrait qu'il y ait un avantage dynamique dès le départ pour les noirs, ne serait-ce que parce que les Blancs ne détériorent pas leur structure avec 1. Cf3. Mais si on avait une stratégie gagnante qui passait avant tout par des moyens dynamiques, il est difficile de croire que les Blancs ne puissent les implanter en premier.

3. S'il y avait zugzwang, il faudrait démontrer que les Blancs gagnent en jouant deux fois au premier coup. Sinon, 1. Cc3 et 2. Cb1 (entre autre) contre n'importe quoi ne perdrait pas. (En passant, la variante des échecs à deux coups est dénuée de zugzwang, parce que les Blancs pourraient jouer 1. Cf3-Cg1.) Il ne semble pas plausible de dire que les Blancs au trait perdent, alors qu'ils gagnent s'ils jouent deux fois.

4. Les données actuelles, assez imposantes pour être significatives d'un point de vue statistique, ainsi que notre propre expérience de joueur d'échecs, nous portent à croire que d'augmenter la mobilité de ses pièces (par exemple en les développant) favorise ses chances de gain. Les fonctions d'évaluation des joueurs artificiels prennent elles aussi cette mobilité, assez en tout cas pour effectuer certains sacrifices positionnels. Or, cela semble contredire l'idée que la situation initiale soit le seul seuil optimal, où les pièces et les pions sont placés de manière telle que tout coup détruirait l'harmonie préétablie.

Ce n'est pas une démonstration, simplement des arguments pour étayer ma thèse. J'ai hâte de voir quels arguments on peut apporter pour la thèse contraire, à l'effet que la position initiale s'agit bel et bien d'un zugzwang mutuel. Le seul qui me vient à l'esprit est qu'il s'agit d'un bel artifice rhétorique pour déstabiliser ses amis joueurs d'échecs. J'avoue qu'il m'est arrivé de m'en servir, du temps de ma jeunesse collégiale.

[Sébastien Nadeau]

Salut Ben,

Loin de moi la prétention de pouvoir contre argumenter à ce sujet. Je voulais simplement dire que lorsque:

En fait il est possible de démontrer que les blancs ne sont pas en zugzang au premier coup de la partie, sans avoir a résoudre le jeux.

Il y a loin de la coupe aux lèvres.

Sébastien

[Mathieu Cloutier]

@Ben : des arguments intéressants que tu avances là.

Personnellement, je ne crois pas que les blancs soient en zugzwang au premier coup. Et je ne crois pas non plus que ce premier coup des blancs soit suffisant pour donner un avantage gagnant. Donc, forcément, je penche plutôt pour dire que la partie jouée parfaitement serait une nulle. Encore là, on a un impressionnant tas de données qui pointent en ce sens!

Mais je garde l'esprit ouvert. Qui sait, peut-être que les blancs sont bel et bien en zugzwang. Le seul élément qui viendrait jouer contre ton idée sur 1.Cf3, c'est la transmission d'information. Les blancs ne compromettent pas leur structure en jouant 1.Cf3, mais les noirs peuvent peut-être utiliser cette information (mon adversaire a joué 1.Cf3) pour établir une stratégie gagnante. J'en doute, mais puisque nous somme dans une discussion ludique sur la zugzwangnitude, pourquoi pas?

C'est un peu comme le propos de John Watson sur les systèmes d'ouverture inversés. Par exemple, si la sicilienne (1.e4 c5) donne de bonnes chances aux noirs, pourquoi est-ce que l'anglaise 1.c4 e5 n'est pas tout simplement écrasante pour les blancs, qui se trouvent à jouer une sicilienne avec un tempo de plus? Watson a bien montré, exemples à l'appui, que l'avantage que les blancs retirent à jouer un demi-coup de plus est compensé par le fait que les blancs transmettent ainsi de l'information aux noirs sur leurs intentions. Ceci permet aux noirs de bien organiser la défense. Un autre exemple vient de la Benoni. Dans cette ouverture, les noirs doivent souvent attendre de voir ce que font les blancs pour réagir adéquatement. Les noirs laissent souvent leur fou c8 sur sa case originale pendant longtemps, attendant que les blancs se compromettent pour le sortir. Jouer une Benoni inversée devient à ce moment moins intéressant si le tempo de plus sert seulement à sortir un fou sans objectif précis.

C'est à peu près le seul argument solide que je verrais contre 1.Cf3. Les blancs transmettent une information aux noirs, qui eux peuvent l'utiliser pour contrer le jeu blanc de manière optimale. On est dans le zugzwang de haute voltige là!

A+

Mathieu

[benoitstpierre]

Mat,

Tu devrais lire de meilleurs livres. ;)

[benoitstpierre]

Sébastien,

En allant sur la page de Fraenkel, j'ai trouvé un article de 2006 qui m'a l'air intéressant :

http://www.wisdom.weizmann.ac.il/~fraen ... s/ICGA.pdf