Jeu parfait aux échecs

[enderalartic]

humm , j'avais mal compris le post précedent , qui du coup devient redondant , post a supprimer désolé
-----

[yat]

Je suis curieux de savoir où trouver telle démonstration. Homotopie semble toutefois apporter la sienne.

En fait, c'est un peu évident en raisonnant par l'absurde. Si on suppose qu'une telle stratégie n'existe pas, ça veut dire que quelle que soit la stratégie employée par un joueur, et quelle que soit sa couleur, il existe une seconde stratégie qui permette de mener la première à la défaite. La contradiction est donc immédiate.

[piwi]

Je suis pas un grand joueur d'echec , mais il me semble qu'une methode existe pour que les noirs fassent perdre l'avantage des blanc des le debut de la partie .

Non. C'est l'objectif des noirs durant l'ouverture, mais il n'y a pas de méthode qui conduisent nécessairement à l'égalisation.

[invite35452583]

Re,
sinon en ce qui concerne le problème de trouver une "stratégie" (je vais mettre des guillemets puisque le terme ne plaît pas à certains) gagnante, il n'est pas indispensable de connaître le graphe en entier.
Et oui, avez-vous eu besoin du graphe de toutes les parties possibles du tic-tac-toe (ou morpion) pour vous convaincre qu'aucun joueur ne peut forcer la gagne.
De même, tout joueur d'échecs ayant dépassé l'étape de "grand débutant" sait que des situations telles que roi+reine contre roi, roi+tour contre roi... sont gagnantes (à moins que le roi isolé ne puisse prendre immédiatement la reine ou la tour...) sans avoir pour cela regarder l'ensemble de tous les combinaisons possibles. De même, certains cas ont déjà été analysés comme nul (roi+2cavaliers contre roi par exemple si je ne me trompe pas)

Existe-t-il un moyen d'extraire l'information "la position initiale du jeu d'échecs classique est ..." avec des frais moindres (et de beaucoup, la description du graphe de Yat est plus simple mais relativement de peu par rapport à l'immensité du problème complet, certains posts ont montré à quel point cette immensité est immense ) ???
Par exemple, avec une fonction qui permettrait d'évaluer toute situation et une preuve qu'un joueur peut toujours améliorer la sienne jusqu'à la gagne ou les deux joueurs peuvent toujours maintenir celle-ci à un quasi statut quo sauf erreur de l'un d'eux.
Ou des études (genre celles pour les finales mais en milieu de partie montrant que telle ou telle situation serait d'un type ou d'un autre) qui permettraient de ramener l'étude systématique à quelque chose d'accessible.

Je doute que ça arrive prochainement (et tant mieux pour l'intérêt de ce très beau jeu) mais rien n'est prouvé à ma connaissance, ni dans un sens (preuve que le problème ne peut être simplifié) ni dans un autre (preuve que l'on peut très nettement simplifier le problème).

[Rhedae]

l n'y a pas de méthode qui conduisent nécessairement à l'égalisation

Pourtant j'ai lu le contraire sur un manuel d'echec ou la methode etait expliquée . Elle consiste en une ouverture speciale des noirs qui porte un nom; et en 2 ou 3 coups l'equilibre se fairai dans le jeu . MAis bon je me rappelle plus le coup et je retrouve pas l'info sur le net et le manuel etait a un ami ...

[Listo]

Bonjour.
Je suis un joueur de club faisant quelques tournois. Je suis loin d'un niveau de maître ( mon classement Elo est autour de 2100 ) mais j'ai lu assez de livres de forts GMI ou champions du monde pour avoir une idée de leur approche du jeu.
La quète "jeu parfait" quitte très tôt l'esprit de l'amateur cherchant à progresser et reste ,au mieux, une curiosité intellectuelle. En pratique, c'est celui qui commet le moins d'erreurs qui gagne et c'est vrai à tous les niveaux.
Quelques remarques pour nourrir la discussion.
-F. Lelyonnais, mathématicien et joueur éclairé affirmait qu'une position de milieu de jeu type offrait autour de 35 coups légaux. J'ai vérifié avec quelques positions.
La force d'un joueur d'expérience, cela a été dit, c'est de n'en envisager que 3 ou 4 qui méritent d'être approfondis.
-Dire que l'on "calcule", homme ou machine, 6,7 ou 10 coups à l'avance n'avance pas à grand chose. Au bout, il faut une évaluation pertinente des positions calculées pour choisir celle que l'on veut amener. Les ordinateurs ont beaucoup progressé mais restent parfois abérants pour certains types de position.Il y a des positions d'ouverture où l'on ne sait pas dire clairement qui est mieux, même après des années et même en utilisant l'ordinateur!
Il m'est arrivé si souvent d'amener , tout content de moi, la positions que j'avais calculée plusieurs coups auparavant, pour m'appercevoir trop tard qu'elle m'est défavorable
Enfin, le type de position change tout. Même moi, je peux calculer une variante sur 10 coups ou plus dans les positions ou beaucoup de coups sont forcés. Dans d'autres 4 ou 5 coups c'est très dur. Et pour les positions de nature stratégique il est inutile de beaucoup calculer, il faut suivre des principes généraux.

Je suis pas un grand joueur d'echec , mais il me semble qu'une methode existe pour que les noirs fassent perdre l'avantage des blanc des le debut de la partie . C'est ce qu'a fait Vladimir Kramnik contre Deep fritz . Cela ne l'a pas empeché pour autant de perdre . Et apparement cette année etait la deniere ou un humain pouvait gagner la machine .

Non, il n'y a pas de recette pour égaliser avec les noirs.
Ce qu'a fait Kramnik, c'est rechercher le type de position "stratégique" où le jeu dit " positionnel" est plus
important que le calcul.
Il a utilisé la même stratégie en match contre Kasparov et Topalov, deux joueurs particulièrement dangereux dans les positions dites "tactiques" qui réussissent aussi aux ordinateurs.Il a un style peu spectaculaire mais très subtil et efficace.
Dans la deuxième partie, Kramnik avec les noirs est parvenu à prendre l'avantage au bout d'une vingtaine de coups.Il a clairement dominé la machine mais a commis une première erreur grave au 33ème coup laissant filer l'avantage.Et au 34ème, alors qu'il avait un coup forçant la nulle...catastrophe!! il gaffe et se fait mater en un coup! Du jamais vu! Même à moi ça ne m'est jamais arrivé en tournoi!
Un tel passage à vide rend, à mon avis, ce match peu significatif.L'ordinateur a surtout montré que lui, il ne craque pas nerveusement

[shokin]

Pourtant j'ai lu le contraire sur un manuel d'echec ou la methode etait expliquée . Elle consiste en une ouverture speciale des noirs qui porte un nom; et en 2 ou 3 coups l'equilibre se fairai dans le jeu . MAis bon je me rappelle plus le coup et je retrouve pas l'info sur le net et le manuel etait a un ami ...

ça parlait de la défense française ?

Shokin

[Rhedae]

Salut Shokin,

Je sais plus du tout ca fait au moins dix ans que j'ai lu ca ..
MAis cet aprés midi je rencontre un ami problemiste, peut etre il me dira le nom du coup .. Ce que je me rappelle c'est qu'il faut ouvrir devant la tour si mes souvenirs sont exactes, mais bon c'est assez vague .

[shokin]

Salut Shokin,

Je sais plus du tout ca fait au moins dix ans que j'ai lu ca ..
MAis cet aprés midi je rencontre un ami problemiste, peut etre il me dira le nom du coup .. Ce que je me rappelle c'est qu'il faut ouvrir devant la tour si mes souvenirs sont exactes, mais bon c'est assez vague .

Du genre 1. ... a6 2. ... b5 ?

Shokin

[enderalartic]

l'equilibre, je verrais plutot une bonne vielle petrov, non?

[shokin]

Face à 1.e4, je préfère continuer par 1. ... c5 (défense sicilienne), ça donne des parties intéressantes parfois violentes. Par contre, c'est moins connu pour obtenir des ex aequo (= partie nulle, remis, draw).

PS : Revenons au sujet initial. Même moi me suis laissé envahir par la passion échiquéenne.

De même, certains cas ont déjà été analysés comme nul (roi+2cavaliers contre roi par exemple si je ne me trompe pas)

On s'entends-tu que, pour le cas roi+2cavaliers contre roi, le gain n'est pas forçable, mais non plus impossible. Alors que, pour le cas roi+2fous contre roi, le gain est forçable. Ainsi que pour le cas roi+fou+cavalier (moyennant un des deux coins de la couleur des cases du fou).

Shokin

[Listo]

R+C+C contre Roi tout seul c'est toujours nul. On ne peut pas arriver à une position de mat car il y a pat avant.
Par contre R+C+C contre R+pion ça gagne! On bloque le pion avec un C, on bloque le roi dans le coin avec R+C puis on débloque le pion et le deuxième cavalier rapplique pour mater mais il n'y a pas pat puique le pion peut avancer.Bien sûr il faut que le pion soit "bien" placé(pas trop avancé).

[shokin]

R+C+C contre Roi tout seul c'est toujours nul. On ne peut pas arriver à une position de mat car il y a pat avant.
Par contre R+C+C contre R+pion ça gagne! On bloque le pion avec un C, on bloque le roi dans le coin avec R+C puis on débloque le pion et le deuxième cavalier rapplique pour mater mais il n'y a pas pat puique le pion peut avancer.Bien sûr il faut que le pion soit "bien" placé(pas trop avancé).

Tiens, il faudra que j'essaie.

Shokin

[Listo]

Attention Shokin, ça peut être long et difficile, quand c'est possible.
J'ai sous les yeux un exemple où on y arrive en "seulement" 15 coups
Blancs: Re6,Cd3,Cf5
Noirs:Rh8,pf3
Bon courrage!

[Etorre]

Je viens de passer plus d'une heure a lire tous les post, et rien ne m'a convaincu. Je précise que j’avais moi même l'intime conviction que le joueur parait existe (je pencherai plus pour blanc) Mais la vos démonstration sont vraiment incomplète. Pour démontrer que le joueur parfait existe, vous partez d'un situation finale ou les blancs gagnes (par exemple). Or le nombre de parties possibles est d'environ 10^120. Pourquoi choisir une seul brindille de la fin de l'arbre, et remonter vers ses racines ? Qu'est ce qui empêche, à n’importe quel moment, a Noir de choisir la bifurcation qu'il souhaite, et de faire capoter tout vos plans ? Dans toute vos démonstration, on dirait que Noir ne choisit pas la direction.
La démonstration ne peut être rigoureuse que si on démontre qu'il existe un coup initiale, qui fait que Noir la plus la main, et que tout ses choix se solderai par un échec, Blanc ayant le réponse parfaite.

Le raisonnement par l’absurde me parait tout aussi incomplet. On suppose que le joueur joue sans être sur de gagner => On en déduit qu'il existe un chemin possible ou il est sur de perde. C'est un raccourci capillotracté !

[Etorre]

Ouffff je viens de comprendre... Je comprend vite, mais faut m'expliquer longtemps ! Si Celui qui joue n'est pas sur de gagner, ca veut qu'il existe un chemin ou il n'a pas le main qui va le mener a la défaite. le joueur parfait sera donc le joueur d'en face. A propos en lisant par mal d'article sur le net, je pense (et je ne suis pas le seul) que ca serait comme au morpion : nulle a tout les coups.

[interferences]

Bonjour,

Ce que l'expérience semble montrer :
- qu'il n'y a pas une partie parfaite mais plusieurs.
- que les parties parfaites se terminerait par des nulles.

Mais il me semble qu'il faudra attendre l'avènement de l'ordinateur quantique pour vérifier ces hypothèses (même si après près de mille ans d'analyse, la théorie échiquéenne semble assez bonne).

Au revoir

[Etorre]

même avec l’avènement de la mécanique quantique, certains problèmes notamment celui ci, resteront Non vérifiable. Ne pas oublier que l'ordinateur ne calcul qu'une solution approchée. Pratique pour décomposer rapidement en deux nombre premiers, pour casser un code RSA (nécessité de coupler avec un ordinateur classique), mais impossible d'envisager de tester TOUTES les parties possible au échec. N'oublions pas que la base de donnée est supérieur au nombre d'atome dans l'univers... Sinon (ca reste intuitif) je suis totalement d’accord : la partie mènerait a coup sur au nul, et chaque ordinateur te tenterait après chaque nœud de minimiser les branche perdante et maximiser les branches gagnantes=>A chaque demi-coup, l'avantage serait a celui qui vient de jouer=> d'un commun accord, cela finirait au nul.
Enfin ce pense qu'elle telle partie joué apparaitrai complément aberrante au GMI, mais cela ne restera a jamais que pure hypothèse.

[Tryss]

Après c'est toujours difficile de définir de façon unique une "partie parfaite"

Si le jeu d'échec donne nul, la partie parfaite est elle celle :
- qui amène au nul le plus vite possible
- qui amène au nul le plus tard possible
- qui amène au nul avec le meilleur avantage de pièces
- qui emprunte une branche qui mène à la défaite, mais pleine de piège
- une autre définition

Ceci dit, comme on ne peut pas passer aux échecs, il serrait possible (mais très improbable) que noir soit le gagnant en jeu parfait (la partie serrait donc un zugzwang géant ).

[interferences]

Pour moi la définition est très claire :
Partie parfaite = aucune erreur de la part des deux joueurs.

même avec l’avènement de la mécanique quantique, certains problèmes notamment celui ci, resteront Non vérifiable

Il me semblait pourtant avoir lu dans la recherche un article qui parlait de complexité algorithmique semblant dire qu'un tel problème serait solvable (mais ça fait longtemps il est très possible que je me sois trompé).

Enfin ce pense qu'elle telle partie joué apparaitrai complément aberrante au GMI, mais cela ne restera a jamais que pure hypothèse.

Moi je pense le contraire, je pense même que des parties parfaites ont déjà été jouées.

Ceci dit, comme on ne peut pas passer aux échecs, il serrait possible (mais très improbable) que noir soit le gagnant en jeu parfait (la partie serrait donc un zugzwang géant ).

Marrant comme idée, mais plus que très improbable.
La pratique ayant plutôt montré que les blancs ont l'avantage.

[Médiat]

Partie parfaite = aucune erreur de la part des deux joueurs.

Bonjour,

Et comment définissez-vous une erreur : un coup qui fait que la partie n'est plus parfaite ?

[Etorre]

Bonjour,

Et comment définissez-vous une erreur : un coup qui fait que la partie n'est plus parfaite ?

Bonjour,
je tente une réponse évidente : jouer parfaitement = jouer, prendre une décision, tout en connaissant parfaitement toutes les issues possibles.
Je reste vraiment intimement convaincu que joueur parfait versus joueur parfait mène au nulle. Je ne puis croire qu'il existe un chemin initial perdant, cad que pendants 40/60 coup a l'avance, Noir n'a pas la main.

Pour le coup de l’algorithmique, il me semblait que la MQ améliore drastiquement la convergence, mais ne donne jamais une solution exacte. je pensais avoir bien capté ça, mais peut être que je ne suis pas a jour moi aussi. J'aimerai tellement voir ça de mon vivant. si ça existe un jour,
Bonne fin de weekend end a tous !

[Tryss]

Pour le coup de l’algorithmique, il me semblait que la MQ améliore drastiquement la convergence, mais ne donne jamais une solution exacte.

L'informatique quantique donne des résultats aussi exacts que l'informatique "traditionnelle". C'est quelque chose de déterministe. L'intérêt de l'informatique quantique, c'est qu'avec n Qbits, on peut faire 2^n calculs en parallèles, le problème c'est que c'est délicat à manipuler les Qbits, et on est même pas sur d'y arriver un jour pour une utilisation réelle.

Résoudre un jeu nécessite une solution exacte, si on n'a qu'un truc bon "en moyenne", on n'a pas résolu le problème ^^

Par exemple, au go, on a résolu le 5x5, mais il est probable (j'ai pas testé) que sur 6x6 avec les programmes efficaces on soit d'un très très bon niveau. On devrait cependant pouvoir résoudre le 6x6 d'ici quelques années... le vrai go restant à tout jamais insoluble par l'informatique classique
http://erikvanderwerf.tengen.nl/5x5/5x5solved.html

[invite4492c379]

L'informatique quantique donne des résultats aussi exacts que l'informatique "traditionnelle". C'est quelque chose de déterministe. L'intérêt de l'informatique quantique, c'est qu'avec n Qbits, on peut faire 2^n calculs en parallèles, le problème c'est que c'est délicat à manipuler les Qbits, et on est même pas sur d'y arriver un jour pour une utilisation réelle.

Résoudre un jeu nécessite une solution exacte, si on n'a qu'un truc bon "en moyenne", on n'a pas résolu le problème ^^

Par exemple, au go, on a résolu le 5x5, mais il est probable (j'ai pas testé) que sur 6x6 avec les programmes efficaces on soit d'un très très bon niveau. On devrait cependant pouvoir résoudre le 6x6 d'ici quelques années... le vrai go restant à tout jamais insoluble par l'informatique classique
http://erikvanderwerf.tengen.nl/5x5/5x5solved.html

Hello,

juste pour préciser, tous les algos nommés quantiques dont on dispose actuellement sont dans la classe BQP : ils donnent une réponse en temps polynomial par rapport à l'entrée et avec une probabilité de réussite>2/3. On ne connaît aucun algorithme quantique exact (dans le sens qui donne en temps polynomial la bonne réponse avec une probabilité de 1).
Le fait de manipuler n qbits qui «seraient la superposition de 2ⁿ bits» ne signifie pas qu'il y a toujours une accélération exponentielle, il est même prouvé que certains problèmes ne peuvent pas bénéficier d'une accélération meilleure qu'une accélération quadratique (ce qui est une bonne nouvelle quand même, cf algo de Grover).
Cela ne signifie pas qu'ils sont inutiles, bien au contraire ; cela signifie qu'il ne faut pas s'attendre (dans l'immédiat) à un ordinateur quantique magique qui résoudrait tous les problèmes NP en temps polynomial.

[interferences]

Et comment définissez-vous une erreur : un coup qui fait que la partie n'est plus parfaite ?

Oui, je suppose que la partie parfaite est nulle, une erreur est donc un coup qui fait qu'un des deux joueur peut remporter à coup sûr la partie.

Sinon pour le calcul quantique, pour avoir un résultat "exact" ne pourrait-on pas utiliser la loi des grands nombres?

[Médiat]

Oui,

Si vous définissez une partie parfaite comme une partie sans erreur, et une erreur comme un un coup qui fait que la partie n'est plus partout, vous n'avez rien défini du tout, vous donnez deux définitions chacune nécessitant l'autre...

[interferences]

Une partie parfaite est une partie sans erreurs.
Une erreur est un coup qui fait que la partie n'est pas parfaite (définition équivalente mais qui défini l'erreur).
Une erreur est un coup qui fait qu'un des deux joueur peut remporter à coup sûr la partie (autre définition de l'erreur).

PS: lisez les phrases jusqu'au bout s'il vous plaît.

[Médiat]

Une erreur est un coup qui fait qu'un des deux joueur peut remporter à coup sûr la partie (autre définition de l'erreur).

Donc tout joueur qui gagne a fait une, voire plusieurs erreurs : belle définition. Sans compter que vous ne savez pas si les blancs (ou les noirs) n'ont pas une stratégie gagnante, car dans ce cas il faudrait que le joueur ne fasse que des erreurs pour gagner !

PS: lisez les phrases jusqu'au bout s'il vous plaît.

Un peu moins de condescendance et vous serz plus crédible !

[Etorre]

Hello,

juste pour préciser, tous les algos nommés quantiques dont on dispose actuellement sont dans la classe BQP : ils donnent une réponse en temps polynomial par rapport à l'entrée et avec une probabilité de réussite>2/3. On ne connaît aucun algorithme quantique exact (dans le sens qui donne en temps polynomial la bonne réponse avec une probabilité de 1).
Le fait de manipuler n qbits qui «seraient la superposition de 2ⁿ bits» ne signifie pas qu'il y a toujours une accélération exponentielle, il est même prouvé que certains problèmes ne peuvent pas bénéficier d'une accélération meilleure qu'une accélération quadratique (ce qui est une bonne nouvelle quand même, cf algo de Grover).
Cela ne signifie pas qu'ils sont inutiles, bien au contraire ; cela signifie qu'il ne faut pas s'attendre (dans l'immédiat) à un ordinateur quantique magique qui résoudrait tous les problèmes NP en temps polynomial.

C'est bien ce qu'il me semblait. Le calculateur quantique n'est pas exact, dans le sens ou il n'a qu'une probabilité différente de 1 de résoudre le problème. c'est dans ce sens la que je disais que la solution était approchée.
Ce que je veux dire, c'est qu'il soit quantique ou classique, jamais un ordinateur ne pourra exploré TOUTES les 10^128 partie possibles non ?. L'ordinateur quantique aura une certaine probabilité de converger vers la meilleurs solution, mais aura-t-il exploré toutes les solutions ? aura-t-il toutes les cartes en mains ?
Un de ces quatre faudra sérieusement que je m'y plonge, sur ces Q bit.
Bonne soirée a tous,

[interferences]

Excusez moi si j'ai pu vous paraître condescendant, ce n'était nullement mon intention.

Donc tout joueur qui gagne a fait une, voire plusieurs erreurs

Je ne comprend pas...tout joueur qui gagne peut avoir fait une ou plusieurs erreurs.
Mais une erreur est un coup qui donne à l'autre joueur (un des deux joueur cela reviens au même) la possibilité de gagner à coup sûr.

Sans compter que vous ne savez pas si les blancs (ou les noirs) n'ont pas une stratégie gagnante, car dans ce cas il faudrait que le joueur ne fasse que des erreurs pour gagner

Encore une phrase que j'ai du mal à comprendre (sans doute à cause de la définition de l'erreur).
Je ne sais pas en effet si les blancs ou les noirs ont une stratégie gagnante, mais "je suppose" que non.