Jeu parfait aux échecs

[martini_bird]

Salut,

Ne pourrait-on pas imaginé une partie sans fin où les pièces évoluraient indéfiniment?

Une partie où il ne reste que les deux rois pourraient se prolonger indéfiniment : mais en pratique on arrête la partie (c'est un pat).

Sinon, il me semble aussi que deux joueurs ne peuvent répéter trois fois de suite les même coups.

Le nombre a certainement dû être évalué en tenant compte de ces restrictions.

Cordialement.

[Yorg_06]

Salut,

Une partie où il ne reste que les deux rois pourraient se prolonger indéfiniment : mais en pratique on arrête la partie (c'est un pat).

Sinon, il me semble aussi que deux joueurs ne peuvent répéter trois fois de suite les même coups.

Le nombre a certainement dû être évalué en tenant compte de ces restrictions.

Cordialement.

Ha oui, j'avais oublié le pat aussi! Effectivement, en pratique la limitation est à trois coups.
Donc on peut le définir. Mais pour les calculer toutes, c'est une autre histoire...

D'ailleur en reprenant un lien du topic:

Avec 100 nanosecondes pour examiner chaque situation pour jouer un coup, il faudrait 10100 années de calcul pour une seule partie.

En aucun cas, un programme pour jeu d'échecs ne peut être exhaustif (algorithmique).

Il faut faire des choix arbitraires correspondant à des paris intuitifs (heuristiques).

Évidemment ce choix n'est pas infaillible!

[piwi]

Pour la partie nulle il y a plusieurs cas à ma connaissance:
pat:
aucun des deux joueurs n'a plus la possibilité materielle de mater.
un joueur ne peut pas jouer sans mettre son roi en echec. Donc impossibilité pour un joueur de jouer.

la même position se reproduit 3 fois à l'identique (même joueur de jouer)

il c'est passé 50 coups sans jouer un pion.


Cordialement,
piwi

[yat]

Chaque noeud de l'arbre peut avoir plus d'une 40aine de sous-branches etc.
On a donc effectivement environ 10¹²⁸ noeuds possibles. Un nombre Astronomique !

Tu es sur que tu ne confonds pas avec le nombre de parties possibles ? Présenter le graphe sous forme d'arbre est très contraignant, et fait exploser le nombre de noeuds nécessaires. En restant sur un graphe comportant une seule fois chaque situation possible on aboutit à un nombre de noeuds qui est négligeable devant ce 10¹²⁸.

Voici par exemple une borne supérieure caclulée avec une grosse louche :
Je code sur 64 bits les cases occupées. J'ai ensuite à remplir un tableau de 32 éléments au maximum. Il y a 6 types de pièces, auxquels j'ajoute le pion qu'on peut prendre en passant et la tour qui peut encore faire un roque, pour les deux joueurs ça me fait 16 pièces possibles, soit 4 bits. J'ajoute donc 128 bits, ce qui me donne une description complète de l'échiquier sur 192 bits, soit 10⁵⁸ situations différentes possibles. Le codage est très loin d'être optimal donc laisse énormément de marge. Et pourtant le rapport entre ton 10¹²⁸ et ma borne supérieure est bien plus grand que le rapport entre la masse du soleil et celle d'un atome d'hydrogène.

[bam823543]

Bonjour à tous, juste une chose je ne suis d'accord avec personne
plus sérieusement, je pense que la partie parfaite n'existe pas pour la simple raison que les "branches" se croisent continuellement.
Et à chaque croisement l'issue de la partie est remise en question.
Le jeu demande faute, avez vous vu un match de foot parfait ? l'équipe qui gagne a juste donnée la meilleure réponse à la défense proposée par l'adversaire.
Cependant cette équipe gagnante peut prendre un 0-15 en jouant de façon strictement identique (imaginons que cela soit possible) contre une autre équipe dont le jeu ne lui conviendrais pas.
Aux échecs, toutes les parties gagnantes sont parfaites.......vis à vis de la réponse de l'adversaire. Le joueur qui gagne, a donné la meilleure (une des meilleures) réponse au jeu de son adversaire.
Si l'adversaire avait changé un de ces déplacements le gagnant aurait lui aussi du changer et donc nous aurions changé de partie.
Je sais j'ai un esprit tordu mais j'y suis habitué


Pour la petite anecdote : à une interview Kasparov à répondu qu'il ne prévoyait que tres rarement plus de 3 coups à l'avance et que sa décision prenait en compte la position de sa pièce par rapport aux autres pièces mais aussi par rapport à l'échiquier (ex pour un déplacement de cavalier si il a 2 ou 3 solutions équivalentes il préfèrera toujours celle qui rapproche le cavalier du centre).

[yat]

Le terme "parfait" ici ne s'applique pas à une partie mais à une stratégie, une manière de jouer. Et effectivement, le déroulement de la partie sera très différent en fonction des coups de l'adversaire. Cela n'empèche que la stratégie dont on parle tient compte de tous les futurs coups possibles à chaque instant du jeu, et choisit le coup le plus avantageux.

[Pole]

On part de la fin.
Il y a beaucoup de positions possibles,mais toutes, ou sont gagnantes ou sont nulles ou sont perdantes (par rapport à toi).
Maintenant,on part de toutes les positions qui,en 1 déplacement mènent à une des solution du dessus. Si tous les déplacement mènent à une position perdante,cette position devient perdante. Si une seule position est gagnante alors cette position est gagnante. Sinon,elle est nulle.
Imagine que tu recommences,recommences,etc... A un moment,tu vas te retrouver à la position du début. Tu sais maintenant si elle est gagnante ou perdante ou nulle.

Il ne faut pas comparer au football.
Compare plutôt au même style de jeu comme le morpion,le puissance 4,etc...

Pole.

[bam823543]

Et si on comparait au jeu papier ciseaux pierre...
Tu vois ce que je veut dire ? applique la technique dont tu viens d'expliquer le mécanisme et applique la à ce jeu simple...

[bam823543]

Je me suis sans doute mal exprimé,
je voulais dire la partie parfaite gagnante selon moi n'existe pas. La stratégie parfaite si elle est appliquée par les noirs et les blancs conduit à un nul. La victoire d'un des 2 camps ne peut se faire que si l'un commet une erreur.
Mais ceci n'est que mon avis, mon intuition...je ne peux rien démontrer et comprend facilement que vous puissiez ne pas être d'accord avec.

[yat]

Et si on comparait au jeu papier ciseaux pierre...
Tu vois ce que je veut dire ? applique la technique dont tu viens d'expliquer le mécanisme et applique la à ce jeu simple...

Ca ne marche pas avec ce jeu puisque les deux joueurs jouent en même temps. Un arc du graphe ne correspond donc plus à un coup, mais à la combinaison des coups des deux joueurs.

[yat]

Je me suis sans doute mal exprimé,
je voulais dire la partie parfaite gagnante selon moi n'existe pas. La stratégie parfaite si elle est appliquée par les noirs et les blancs conduit à un nul. La victoire d'un des 2 camps ne peut se faire que si l'un commet une erreur.

On parle bien d'une stratégie qui permet au joueur d'assurer la victoire ou le nul. Comme je l'ai dit un peu plus tard, cela peut se manifester de deux manières différentes. Soit une stratégie garantissant la victoire existe pour un des deux joueurs, soit une partie assurant la victoire ou le nul existe pour les deux joueurs. Mais pour savoir si on est dans un cas ou dans l'autre, il faudrait connaitre le graphe dans son intégralité, ou bien avoir une démonstration qui tienne la route.

Mais ceci n'est que mon avis, mon intuition...je ne peux rien démontrer et comprend facilement que vous puissiez ne pas être d'accord avec.

Ah oui, ça, se baser sur ses intuitions pour nier des choses démontrées, tu as bien raison, on peut ne pas être d'accord. Même la charte du forum n'est pas d'accord.

[bam823543]

rien n'est démontré ici à part que la fin d'une partie est nulle ou pas.

[yat]

rien n'est démontré ici à part que la fin d'une partie est nulle ou pas.

le post 16 propose une démonstration par l'absurde, j'en donne une par construction de graphe en post 17, Argyre fait intervenir l'algo min-max en 24...

La seule chose qu'on ne sait pas, c'est si si la stratégie optimale assure la victoire aux blancs, aux noirs, ou seulement d'éviter la défaite aux deux (même si je penche personnellement pour la dernière possibilité, ce n'est pas l'intuition qui pourra nous le confirmer). Mais l'existence de cette stratégie optimale, elle, est bien démontrée.

[bam823543]

On part de la fin.
Il y a beaucoup de positions possibles,mais toutes, ou sont gagnantes ou sont nulles ou sont perdantes (par rapport à toi).
Maintenant,on part de toutes les positions qui,en 1 déplacement mènent à une des solution du dessus. Si tous les déplacement mènent à une position perdante,cette position devient perdante. Si une seule position est gagnante alors cette position est gagnante. Sinon,elle est nulle.
Imagine que tu recommences,recommences,etc... A un moment,tu vas te retrouver à la position du début. Tu sais maintenant si elle est gagnante ou perdante ou nulle.

Il ne faut pas comparer au football.
Compare plutôt au même style de jeu comme le morpion,le puissance 4,etc...

Pole.

J'ai l'impression que vous ne prenez pas tout en compte.
Bon je ne peux pas faire de shéma ici mais je vais tenter de démontrer quelquechose.
tu dis a toutes les positions correspond une issue G P N (gagnant perdant nulle) et c'est facile on remonte toutes les positions gagnantes et on arrive à cette fameuse partie parfaite gagnante...revoyons le mouvement au ralenti :
je pars de la fin de la partie que j'ai gagné: donc de ma position A j'ai choisi celle conduisant à G . en remontant à ce A je vois qu'il correspond à un P pour l'autre joueur.
D'ors et déjà je peux dire que si il mefaut trouver tout les G il faut que l'autre joueur joue tous les P.
Je continu...raisonnablement l'autre joueur jouera tous les G aussi puisqu'il connais le schéma de la partie parfaite. Il n'y donc pas DE P en fin de partie : la partie est nulle.
Qu'en pensez vous? au moins j'ai fais des efforts en démonstration...

[Argyre]

je pars de la fin de la partie que j'ai gagné: donc de ma position A j'ai choisi celle conduisant à G . en remontant à ce A je vois qu'il correspond à un P pour l'autre joueur.
D'ors et déjà je peux dire que si il mefaut trouver tout les G il faut que l'autre joueur joue tous les P.
Je continu...raisonnablement l'autre joueur jouera tous les G aussi puisqu'il connais le schéma de la partie parfaite. Il n'y donc pas DE P en fin de partie : la partie est nulle.
Qu'en pensez vous? au moins j'ai fais des efforts en démonstration...

Bonjour,

Je n'ai pas très bien compris.
D'abord si la stratégie parfaite existe avec un gain à la fin, elle n'existe que pour 1 joueur et pas pour l'autre.
Notons X ce joueur (blanc ou noir donc).
Si elle existe, cela veut dire qu'après chaque coup de l'adversaire de X, il est possibble de choisir un coup suivant qui va mener X à la victoire.
Si elle n'existe pas, cela veut dire que l'adversaire de X peut trouver un coup qui va obliger X à choisir un coup suivant qui ne le mènera, au mieux, que vers une partie nulle.
Remarque : l'adversaire de X ne peut pas gagner; s'il le pouvait, et ce, quels que soient les coups de X, cela voudrait dire que c'est lui qui a une stratégie de gain, ce qui est en contradiction avec l'hypothèse.
(en fait, on revient sur la 1ère démo qui a été proposée).

Cordialement,
Argyre