Jeu parfait aux échecs

[invite6acfe16b]

Bonjour,

Je ne joue pas très souvent aux échecs, mais comme je m'y intéresse du point de vue de la théorie des jeux, je me suis posé une question. On sait qu'en théorie, il existe une façon parfaite de jouer pour un des deux joueurs (vraisemblablement blanc), c'est-à-dire une manière de jouer qui mêne forcément à une victoire ou à un nul. Ce que je me suis demandé c'est si les meilleurs joueurs ou les meilleurs programmes sont proches de cette stratégie ou bien en sont éloigné. Et de combien en sont-ils loins ? Par exemple, est-ce que tous les 10 coups ils font une erreur qui mène un joueur parfait à la victoire. Ou bien est-ce tous les 20 coups ou tous les 2 ou même 1 ?!
Voilà, s'il y a des personnes s'intéressant aux échecs ici, je serais très heureux d'entendre leurs commentaires.
-----

[invitef8cab1ed]

Vu qu’on n’est pas sûr de ce à quoi ressemble le jeu du joueur parfait (n'est-ce pas ?), comment pourrait-on en déterminer la distance avec celui des meilleurs joueurs humains ou artificiels ?

[Dieu_fr]

est-ce que tous les 10 coups ils font une erreur qui mène un joueur parfait à la victoire. Ou bien est-ce tous les 20 coups ou tous les 2 ou même 1 ?!

Comment (pré)dire si un coup, isolé, est une erreur ? à moins d'être soi-même un joueur parfait ?

[invite06fcc10b]

Ce que je me suis demandé c'est si les meilleurs joueurs ou les meilleurs programmes sont proches de cette stratégie ou bien en sont éloigné. Et de combien en sont-ils loins ? Par exemple, est-ce que tous les 10 coups ils font une erreur qui mène un joueur parfait à la victoire. Ou bien est-ce tous les 20 coups ou tous les 2 ou même 1 ?!

Bonjour,

Le forum a planté ... je suis obligé de tout réécrire ... grrrr...
Bon, tout d'abord, le nombre de coups possibles croît de manière trop forte, même si on élimine les coups jugés trop faibles ou menant rapidement à la victoire de l'adversaire. Je pense qu'à l'heure actuelle, sans contrainte de temps, un ordinateur peut sans doute arriver à calculer une dizaine de coups à l'avance, pas plus. Or, entre très bons joueurs, un partie peut souvent aller vers une quarantaine de coups ...
En fait, la partie se joue souvent sur des détails de positionnement qu'il est bien difficile de prévoir à l'avance. On peut noter que les grands joueurs décident assez rapidement d'un abandon, alors qu'il reste encore la moitié des pièces sur l'échiquier. En effet, si une position est trop défavorable, ils n'espèrent pas l'erreur bête de l'adversaire, ils font comme si celui-ci jouait parfaitement et décident d'abandonner. On peut donc considérer, en gros, qu'il y a abandon dès la détection de la 1ère erreur ...
Celle-ci résulte toutefois en général du choix des 5 derniers coups. CAD, si on rejouait les 5 derniers coups, l'issue du match pourrait changer (expérience personnelle, ça vaut ce que ça vaut ...).

Une question intéressante se pose néanmoins pour les parties nulles. En effet, si on cherche la nulle, on peut tenter d'aller rapidement vers des échanges de pièces, ce qui réduit fortement le nombre de coups possibles. Dans ce cas, peut-être est-on assez proche de pouvoir trouver un algorithme "pseudo-parfait" qui trouverait à coup sûr la séquence qui mène vers la partie nulle.
Je ne sais pas si des études poussées ont été faites sur ce point.

Cordialement,
Argyre

[A voir en vidéo sur Futura]

[invite07302ad5]

Bonjour,
Le jeu d'echecs parfait sera atteind lorsque la puisance de calcul des ordinateurs donnera une prevision de coups superieure à l'homme.
Estimation d'environ 14 coups.
Les meilleurs joueurs et programes sont actuellement à environ une dizaine de coups.
Lorsque toutes les parties auront été calculées (environ 10 puissance128) les Echecs ne seront plus que maths.(arf arf).
(voir excellent cite:http://perso.orange.fr/yoda.guillaume/index.htm)
Il y a fort à parier que les blancs gagneront à chaque fois et l'on apprendra "la partie parfaite" comme une récitation.
J'espere que les progrès nous laisseront encore quelques années de jeu....
De toute manière, cette récitation je ne l'apprendrai pas
en esperant que d'autres feront de même....
Bien à vous
Alain

[invite06fcc10b]

Bonjour,
Le jeu d'echecs parfait sera atteind lorsque la puisance de calcul des ordinateurs donnera une prevision de coups superieure à l'homme.
Estimation d'environ 14 coups.

Bonjour,
Il y a à mon avis une erreur d'appréciation : la puissance de calcul de l'ordinateur est très très au-dessus des capacités humaines, même celle des grands maîtres. Ces derniers ne parviennent à faire jeu égal avec les ordis (à peu près) que parce qu'ils ont une stratégie bien affutée, mais ils utilisent une large bibliothèque d'ouvertures et ne réfléchissent que sur quelques variantes environ 5 coups à l'avance et laissent tomber toutes les autres possibilités, ce que ne fait pas un ordinateur.

Les meilleurs joueurs et programes sont actuellement à environ une dizaine de coups.

Jamais de la vie, en tout cas pas en milieu de partie, ou alors il faut laisser 10 jours à l'ordinateur (et encore ...) et je ne parle même pas de l'être humain.

Lorsque toutes les parties auront été calculées (environ 10 puissance128) les Echecs ne seront plus que maths.(arf arf).

Je ne sais pas si tu te rends compte du nombre que tu annonces. A 10¹², on a déjà besoin de plusieurs jours de calcul, et à 10²⁰, on est complètement dépassé, alors je ne vois pas comment on pourrait un jour atteindre 10¹²⁸, même si les ordinateurs gagnaient un facteur 1000000 en puissance, c'est hors de notre portée.

Cordialement,
Argyre

[danyvio]

Bonjour,
Il y a fort à parier que les blancs gagneront à chaque fois

Pas d'accord ! Le jeu d'échec est un jeu de stratégie. Le premier joueur n'est pas obligatoirement avantagé. Exemple simpliste : le jeu où, alternativement on pose de façon réfléchie un dé sur la table, et on cumule les points vus dessus. Le gagnant est celui qui, après cumul, annonce exactement 21. Il existe la stratégie gagnante qui consiste, pour le deuxième joueur, à afficher systématiquement le complément à 7 de ce que le joueur 1 a mis. Les cumuls successifs sont évidemment 7 puis 14 puis 21.

Quant à la capacité des ordinateurs, attendons-nous à une véritable révolution le jour où les machines quantiques seront au point....

[invite06fcc10b]

Quant à la capacité des ordinateurs, attendons-nous à une véritable révolution le jour où les machines quantiques seront au point....

C'est à dire quand les poules auront des dents. Perso, je ne crois pas aux calculateurs quantiques. Les travaux actuels ne prouvent rien : le qubit n'est ni réalisable en pratique, ni conceptualisable en théorie, il reste virtuel.
Et le problème, c'est que les échecs ne se passent pas dans un monde virtuel ...
A+,
Argyre

[invite116a953a]

Jamais de la vie, en tout cas pas en milieu de partie, ou alors il faut laisser 10 jours à l'ordinateur (et encore ...) et je ne parle même pas de l'être humain.

Tu dois pas jouer aux échecs souvent...
En début de partie, pas trop de surprise, les grands maitres voient à 5 coups voir moins ça suffit; les ouvertures étant toutes plus ou moins les mêmes. Va voir une blitz entre deux maitres, tu comprendra ce que c'est que de connaitre les ouvertures
En milieu de partie, ça se corse, c'est là où il faut "voir" le plus loin, et 5 coups ne suffisent pas mon jeune ami!
C'est bien 10 coups et plus!

Enfin oui la puissance de calcul pur est bien meilleur chez l'ordinateur, mais les humains "éclaircissent" le terrain, un bon nombre de combinaisons ne sont même pas étudiées. Alors que l'ordinateur, lui, calcul tout bêtement... Et l'homme(enfin les Grands Maitres...) ne sont pas si loin des machines, ils ont encore quelques tours dans leurs sacs. Reste aux programmeurs à intégrer toutes ces parties et un beau jour l'ordinateur sera, peut-être, imbattable...

Quand au "jeu parfait", bonne chance à Alain67 pour apprendre par coeur toutes les solutions

[invite0db6221b]

Je pense personnellement qu'a un certain niveau, on ne calcule plus vraiment au sens strict du terme, calculer 10 coups à l'avance en tenant compte de toutes les possibilité adverses et des siennes, ça deviens vite une situation ingérable.
Je ne suis pas une "star", loin de la, mais je joue plus sur les positions, sur l'expérience des parties jouées et des positions, des développements possibles, que sur le calcul pur des coups, lequel a la fâcheuse manie de vous montrer que vous avez oublié une éventualité de l'autre coté de l'échiquier.
Le blitz est parfait pour ça, pas le temps en 5 ou 10 minutes par joueur de tout calculer, et tant mieux, ça évite les maux de tête carabinés.

Quant à savoir si la machine peux battre l'humain, je n'en sais fichtre rien. La machine est supérieure par son coté précision, mais le cerveau humain dépasse la machine pour ce qui est de l'approximation, de l'intuition.

[invite116a953a]

calculer 10 coups à l'avance en tenant compte de toutes les possibilité adverses et des siennes, ça deviens vite une situation ingérable.

Tout a fait, j'en suis pas capable moi-même...
Et il n'y en a pas beaucoup d'ailleur...

... lequel a la fâcheuse manie de vous montrer que vous avez oublié une éventualité de l'autre coté de l'échiquier.

Et oui, c'est la différence entre les bons et très bons joueurs...

Quant à savoir si la machine peux battre l'humain, je n'en sais fichtre rien. La machine est supérieure par son coté précision, mais le cerveau humain dépasse la machine pour ce qui est de l'approximation, de l'intuition.

Oui "l'intuition" est très puissante chez l'homme, difficile de "programmer" ça sur une machine...

[piwi]

En milieu de partie ca n'est certainement pas 10 coups et +!
Ce qui fait la différence comme cela a deja été dit est la reconnaissance (theorique ou intuitive)de positions, de schémas. Le jeu etant d'amener la position telle qu'elle est au plus pres de la position théorique. On connait tres bien les ouvertures et l'on sait transposer une position issue d'une ouverture vers une une autre (ca fait des ponts théoriques). Ca c'est pour le principe de jeu des très grands joueurs. La partie calculatoire ne se fait donc pas sur l'ensemble du jeu vers une sorte d'absolu mais sur une partie de l'echiquier vers un but définit. Ca change tout! Nettement moins de choses à apréhender. Beaucoup plus de logique possible.

Vers la fin de la partie on arrive en finale. On connait pas mal de type de final gagnantes (comprendre que l'on sait qu'en arrivant à une telle position un des deux camps va gagner à coup sur si il joue au mieux) ou nulle. Pour le reste il s'agit de jouer! Et là c'est difficile. Bien qu'il n'y ait plus beaucoup de pieces sur l'echiquer, le timing et la précision des mouvements est capitale. Une erreur conduit souvent à la chute. Du coup il faut voir bien des coups à l'avance et c'est là que 10 coups ne sont pas de trop.

Vous comprenez donc qu'il y a une stratégie engagée en début de partie avec prise de position. Ensuite il faut se confronter au réel et essayer de forcer les evenements avec un plan stratégique ponctué d'éléments tactiques. Le tout avec l'idée de retomber sur quelque chose de connu et maitrisé. On comprend donc les abandons rapides. Quand on est dans une position connue ouvrant sur une finale nulle inutile de continuer si l'on estime que l'autre joue au mieux (en général un grand maitre estime qu'un autre grand maitre joue au mieux). Donc nulle en quelques coups. Si une erreur ou un piege tactique vous conduit à déséquilibrer la position, exemple typique perte d'une piece, en considérant que l'autre joue au mieux vous aurez une piece de moins en final. inutile de poursuivre, c'est perdu.

[inviteb5e76414]

Au tout début de ce fil de discussion, Sylvestre a écrit :
"On sait qu'en théorie, il existe une façon parfaite de jouer pour un des deux joueurs (vraisemblablement blanc), c'est-à-dire une manière de jouer qui mêne forcément à une victoire ou à un nul."

Je n'ai jamais rien lu de semblable. As tu des références bibliographiques qui détaille un peu cela ?

Par ailleurs, sur la question du calcul à 5 ou 10 coups, si je peux essayer de réconcilier tout le monde : bien sûr qu'on peut prévoir une suite de 10 coups à l'avance, et à toute les phases du jeu mais on n'examine jamais toutes les combinaisons à 10 coups d'avance. Comme quelqu'un l'a déjà dit, la plupart des branches combinatoires ne sont pas explorées car on connait leur issue. Par ailleurs, il y a aussi certaines situation en finale où le nombre de coups possibles est très restreint. Donc la notion de prévision à 10 coups à assez floue.

Oui on peut envisager 10 coups d'affilée vraisemblables, non on ne calcule toutes les combinaisons à 10 coups pour être certains mathématiquement que la suite qu'on envisage est la meilleure.

A 3 coups, 5 coups, 10 coups ou 20, c'est d'ailleurs ce qui fait le piment de bon nombre de partie : des coups improbables (donc inexplorés à fond par l'adversaire) qui mènent pourtant à la victoire (les sacrifices en sont un bon exemple).

[invite4793db90]

Salut,

Je n'ai jamais rien lu de semblable. As tu des références bibliographiques qui détaille un peu cela ?

Désolé pour le post un peu inutile, mais il a été démontré qu'il existe une stratégie gagnante aux échecs, ce qui veut dire qu'un joueur peut gagner ou obtenir un nul, quelque soient les coups de son adversaire (comme au jeu du morpion).

Là où mon post est inutile, c'est qu'il est tard (la bonne excuse) et que je ne saurais pas te retrouver des références à ce sujet...

Cordialement.

[invite06fcc10b]

Tu dois pas jouer aux échecs souvent...

Et toi tu ne dois pas avoir souvent de bonnes notes en analyse de textes ...
En tout cas, t'as tout faux, j'ai pas mal joué aux échecs il y a quelques années. Par ailleurs, j'enseigne l'informatique et les algorithmes minimax et alpha-beta, qui sont typiquement utilisés dans les programmes de jeux d'échecs ... donc je suis assez bien placé pour savoir où sont les limites des ordis et comprendre comment ils déterminent le meilleur coup.
Pour en revenir au problème des 5 ou 10 coups à l'avance, relis le 1er message et tu comprendras qu'on s'intéresse à un joueur parfait, et qui dit parfait dit prise en compte de tous les coups possibles. Donc, je persiste, même si un grand joueur peut effectivement s'intéresser à une séquence de 10 coups, ce n'est qu'une séquence et comme cela a été dit par d'autres, il oublie volontairement de considérer un grand nombre de variantes qui peuvent le mener à sa perte. Et cependant, un grand maître envisage environ 5 coups à l'avance toutes les variantes. Donc sa vision est quasi-exhaustive sur 5 coups et c'est de cela que je parlais.

Enfin oui la puissance de calcul pur est bien meilleur chez l'ordinateur, mais les humains "éclaircissent" le terrain, un bon nombre de combinaisons ne sont même pas étudiées. Alors que l'ordinateur, lui, calcul tout bêtement...

N'exagérons rien, si tu connaissais l'algo alpha beta, tu saurais que l'ordinateur élimine lui aussi un grand nombre de variantes de façon très efficace.
Bon, mais nous sommes dans le forum des jeux, donc soyons fairplay ... bons jeux !

A+,
Argyre

[inviteb5e76414]

Salut,
Désolé pour le post un peu inutile, mais il a été démontré qu'il existe une stratégie gagnante aux échecs, ce qui veut dire qu'un joueur peut gagner ou obtenir un nul, quelque soient les coups de son adversaire (comme au jeu du morpion).
Cordialement.

J'y ai un peu réflechi parce que ça m'intrigue. Ce qui m'intrigue c'est que si c'est vrai aux échecs, c'est vrai pour tous les jeux équivalents (je veux dire jeux déterministes, à coups alternés, à issue gain/nul ou perte, il faudrait d'ailleurs préciser). C'est vrai pour tous les jeux car le raisonnement qui conduira à ça ne pouvant pas reposer sur une étude combinatoire (sinon on l'aurait cette partie parfaite), ça ne dépend pas des règles non plus. Donc c'est vrai pour les dames, etc.

J'ai essayé de trouver la démonstration (désolé pour la grammaire, mais c'est pour être plus clair:

• On veut prouver : "il existe un joueur, quel que soit les coups de son adversaire, il peut gagner ou faire nul".
• Ca revient au même de dire : "il existe un joueur, quel que soit ses coups, il perd ou fait nul".
• On raisonne par l'absurde. Le contraire de la proposition précédente est "quels que soient les joueurs, ils ont une suite de coup qui gagne". Et ça c'est évidemment faux.
• Cqfd.

Ca me parait bien simple. Quelqu'un voit-il une erreur dans le raisonnement ?

En tout état de cause, je suis d'accord avec quelqu'un qui a dit plus haut qu'on ne pouvait absolument pas dire si c'était les blancs. Le jeu est asymétrique, rien ne prouve que jouer le premier conduit à la victoire.

[yat]

J'y ai un peu réflechi parce que ça m'intrigue. Ce qui m'intrigue c'est que si c'est vrai aux échecs, c'est vrai pour tous les jeux équivalents (je veux dire jeux déterministes, à coups alternés, à issue gain/nul ou perte, il faudrait d'ailleurs préciser). C'est vrai pour tous les jeux car le raisonnement qui conduira à ça ne pouvant pas reposer sur une étude combinatoire (sinon on l'aurait cette partie parfaite), ça ne dépend pas des règles non plus. Donc c'est vrai pour les dames, etc.

Ce qui parait un peu évident quand on y réfléchit. On a un nombre fini de situations possibles qui peuvent se présenter au cours d'une partie, et des coups qui relient ces différentes situations. Tout cela forme un graphe. On peut en extraire trois sous-graphes, qui correspondent respectivement à la victoire des blancs, la victoire des noirs, et le nul. Chaque situation fait nécessairement partie d'un de ces sous-graphes. La connaissance de ces graphes revient à disposer d'une stratégie optimale pour chacun des deux joueurs. Maintenant, je ne sais pas dans quel sous-graphe se trouve la position initiale de l'échiquier.

C'est effectivement valable pour les jeux de ce type quand l'information est complète. Du go aux dames en passant par les échecs, le jeu de Marienbad ou le morpion. Mais par exemple pas pour le backgammon, puisque les joueurs ne connaissent pas à l'avance les résultats des dés, ni à la belotte puisque chaque joueur ignore ce que les autres ont dans les mains.

J'ai essayé de trouver la démonstration (désolé pour la grammaire, mais c'est pour être plus clair:

• On veut prouver : "il existe un joueur, quel que soit les coups de son adversaire, il peut gagner ou faire nul".
• Ca revient au même de dire : "il existe un joueur, quel que soit ses coups, il perd ou fait nul".

Je ne pense pas que ça soit équivalent. Dans la première situation, on a une stratégie gagnante. On emploie le terme joueur, mais on parle de sa manière de jouer, de sa stratégie. Gagnante ou nulle contre toutes les autres stratégies. Dans la deuxième proposition, on a plutôt l'impression d'avoir un type maudit, et quelle que soit la stratégie qu'il utilise, il ne gagne jamais. Ca n'a pas grand chose à voir je pense.

[invite3d7be5ae]

C'est à dire quand les poules auront des dents. Perso, je ne crois pas aux calculateurs quantiques. Les travaux actuels ne prouvent rien : le qubit n'est ni réalisable en pratique, ni conceptualisable en théorie, il reste virtuel.
Et le problème, c'est que les échecs ne se passent pas dans un monde virtuel ...

Faux, les qubits existent.On arrive à en gérer quelques-uns. Mais même si on a un ordi quantique, ça ne veut pas dire que tout va plus vite dessus. Il faut élaborer un algorithme spécifique à ce type d'ordi.

Je ne pense pas que ça soit équivalent. Dans la première situation, on a une stratégie gagnante. On emploie le terme joueur, mais on parle de sa manière de jouer, de sa stratégie. Gagnante ou nulle contre toutes les autres stratégies. Dans la deuxième proposition, on a plutôt l'impression d'avoir un type maudit, et quelle que soit la stratégie qu'il utilise, il ne gagne jamais. Ca n'a pas grand chose à voir je pense.

Non,il y a une stratégie gagnante pour les blancs ou les noirs et ce joueur pourra toujours gagner. L'autre perdra toujours.Non pas parce qu'il est maudit mais parce qu'il commence (ou pas).

Le 3ème point est faux, il faut prendre en compte le fait qu'un joueur commence ou pas.
Je fais un exemple avec les noirs gagnant.

• "Les noirs quel que soit les coups des blancs, il peut gagner ou faire nul".

• "Les blancs, quel que soit ses coups, il perd ou fait nul".

• "Les noirs, ils ont une suite de coup qui gagne" car le contraire de les blancs,c'est les noirs.

Plus de contradiction.
C'est évidemment la même chose pour les blancs gagnants.

Pour l'alpha-bêta,il élimine des coups,mais très peu.

Pole.

[yat]

Non,il y a une stratégie gagnante pour les blancs ou les noirs et ce joueur pourra toujours gagner. L'autre perdra toujours.Non pas parce qu'il est maudit mais parce qu'il commence (ou pas).

Pas beaucoup plus clair. Mon propos est que les deux premières propositions, sensées être équivalentes, ne le sont pas puisque la deuxième ne veut rien dire.

Le 3ème point est faux, il faut prendre en compte le fait qu'un joueur commence ou pas.
Je fais un exemple avec les noirs gagnant.

• "Les noirs quel que soit les coups des blancs, il peut gagner ou faire nul".

• "Les blancs, quel que soit ses coups, il perd ou fait nul".

Ca non plus ce n'est pas bon : dans la deuxième proposition, il faut préciser que le joueur qui a les blancs dont on parle, affronte un joueur qui a les noirs ET dispose de la stratégie gagnante citée juste au dessus.

• "Les noirs, ils ont une suite de coup qui gagne" car le contraire de les blancs,c'est les noirs.

Plus de contradiction.

Et là, j'ai complêtement perdu le fil. Je me permets d'essayer de formuler un raisonnement par l'absurde équivalent à ce que vous semblez vouloir faire.

Admettons qu'il n'existe pas de stratégie optimale permettant d'assurer la victoire ou le nul à un des deux joueurs. On en déduit que, quelle que soit les coups joués par un joueur donné, il existe forcément un enchainement de coups qui permettent de le battre. La contradiction est donc immédiate, puisque employer cet enchainement de coups face à toute stratégie adverse constitue une stratégie optimale assurant la victoire.

[invite06fcc10b]

Faux, les qubits existent.On arrive à en gérer quelques-uns.

Rien du tout, il n'y a rien qui permet de le dire. Les rares algorithmes qui ont été proposés et qui exploitent la superposition d'états sont obligés de prendre en compte les statistiques d'états des particules, ce qui supprime le pouvoir calculatoire des qubits. En effet, à aucun moment il n'est possible de mesurer plusieurs états de cette superposition d'états. Or, pour faire des qubits réels (pas virtuels), il faut pouvoir accéder à chacun des états de cette superposition ... ce qui est impossible dans l'état actuel de nos connaissances en MQ.
Donc en résumé, les qubits n'existent pour l'instant qu'en virtuel !
De plus, est-ce que la superposition d'états est équivalente à l'existence de plusieurs états simultanés ? Il me semble que ce point là est également polémique. Un visage peut être vu de face ou de profil, mais pas les 2. La superposition d'états n'existe que parce que le système n'est pas encore déterminé, comme si, pour reprendre l'exemple du visage, la personne baissait la tête et refusait de choisir. Mais il n'y a toujours au bout du compte qu'1 seul état possible et mesurable, d'où l'imposture des qubits.

Bon, euh, pardonnez ma digression, tout ceci mériterait d'être discuté ailleurs ..

Sinon, ce qu'a dit Yat : <<Ca non plus ce n'est pas bon : dans la deuxième proposition, il faut préciser que le joueur qui a les blancs dont on parle, affronte un joueur qui a les noirs ET dispose de la stratégie gagnante citée juste au dessus.>> me parait juste, il fallait le rajouter.
A+,
Argyre

[invite3d7be5ae]

Pas beaucoup plus clair. Mon propos est que les deux premières propositions, sensées être équivalentes, ne le sont pas puisque la deuxième ne veut rien dire.

C'est presque juste, way-jouannes a oublié de dire "Dans la même partie,..." ce qui rend la phrase vraie.
C'est le contraire de cette phrase qui est faux.

Ca non plus ce n'est pas bon : dans la deuxième proposition, il faut préciser que le joueur qui a les blancs dont on parle, affronte un joueur qui a les noirs ET dispose de la stratégie gagnante citée juste au dessus.

Oui .

Et là, j'ai complêtement perdu le fil. Je me permets d'essayer de formuler un raisonnement par l'absurde équivalent à ce que vous semblez vouloir faire.

Admettons qu'il n'existe pas de stratégie optimale permettant d'assurer la victoire ou le nul à un des deux joueurs. On en déduit que, quelle que soit les coups joués par un joueur donné, il existe forcément un enchainement de coups qui permettent de le battre. La contradiction est donc immédiate, puisque employer cet enchainement de coups face à toute stratégie adverse constitue une stratégie optimale assurant la victoire.

Je voulais juste montrer qu'il n'y avait pas de contradiction en corrigeant quelques petites erreurs,pas de démontrer qu'il y avait une solution gagnante.

Argyre: Je ne connais que très peu la mécanique quantique mais dans http://fr.wikipedia.org/wiki/Algorithme_de_Shor on lit que 15 a été factorisé avec un ordi quantique.Peut-être est-ce des qubits virtuels,mais en tout cas, ils arrivent à faire des calculs avec. Pourquoi pas avec les échecs?

Pole.

[inviteb5e76414]

Chaque situation fait nécessairement partie d'un de ces sous-graphes.

Tes sous-graphes ne sont pas disjoints. La position initiale fait partie des trois par exemple. Je ne suis pas ton raisonnement. Avec cette analogie, tu as effectivement un graphe sur lequel tu positionne des sous-graphes non disjoints et la proposition que tu dois prouver c'est : en te déplaçant dans ce graphe en ne controlant qu'un mouvement sur deux, tu peux nécessairement arriver à un noeud du graphe qui appartient au sous-graphe gagnant ou au sous-graphe perdant. Ca me parait pas si évident.

On emploie le terme joueur, mais on parle de sa manière de jouer, de sa stratégie. Gagnante ou nulle contre toutes les autres stratégies. Dans la deuxième proposition, on a plutôt l'impression d'avoir un type maudit, et quelle que soit la stratégie qu'il utilise, il ne gagne jamais.

Non ce n'est pas du tout ce que je voulais dire bien sûr. Quand je dis "il existe un joueur" je veux dire "les noirs ou les blancs, un des deux". Quand je dis "tous les joueurs", c'est les noirs et les blancs. J'ai utilisé une formulation trop générale, et ce n'était pas clair.

Je ne me réfère pas à un joueur en particulier. Ou alors j'aurai dit Woody Allen pour le type maudit qui perd tout le temps.

[yat]

Tes sous-graphes ne sont pas disjoints. La position initiale fait partie des trois par exemple. Je ne suis pas ton raisonnement.

Ta troisième phrase explique les deux premières. Les deux graphes de victoire sont distincts, et les noeuds qui ne sont dans aucun des deux sont les noeuds du sous graphe nul.

Mais j'explique comment je définis ces sous-graphes, parce que je pense que c'est ça que tu n'as pas compris. Les situations de mat sont les premiers noeuds des sous-graphes de victoire. Le reste se construit récursivement : Tout noeud qui permet à un joueur d'atteindre son graphe de victoire en un coup fait lui aussi partie de ce graphe. Même chose pour les autres noeuds qui lui permettent d'atteindre en un coup le graphe nul, et ceux qui ne mènent qu'aux noeuds du graphe de victoire de l'autre joueur en font aussi partie. C'est une construction un peu simplifiée, puisqu'on n'a pas affaire à un arbre, mais à un graphe. Comme on est dans le cadre d'une démonstration, et que l'on n'a que faire de la multiplication du nombre de noeuds que va engendrer une telle méthode, il suffit d'inclure dans le noeud le nombre de coups joués avant. On supprime ainsi tous les cycles du graphe, et le problème est résolu, les sous-graphes peuvent être définis rigoureusement.

Il est immédiat que les sous-graphes ainsi définis sont disjoints, et encore plus que tout noeud du graphe global est compris dans un des trois sous-graphes. La situation de départ est donc comprise dans un seul de ces sous-graphes, ce qui confirme qu'on se trouve dans un des deux cas suivants :
-il existe une stratégie permettant d'assurer la victoire à un des deux joueurs (si la situation initiale est dans un des sous-graphes de victoire)
-il existe une stratégie permettant d'assurer la victoire ou le nul à n'importe quel joueur (si la situation initiale est dans le sous-graphe nul).

Dans les deux cas, on respecte l'affirmation qui dit que "il existe une stratégie gagnante aux échecs, ce qui veut dire qu'un joueur peut gagner ou obtenir un nul, quelque soient les coups de son adversaire"

[invite06fcc10b]

Ta troisième phrase explique les deux premières. Les deux graphes de victoire sont distincts, et les noeuds qui ne sont dans aucun des deux sont les noeuds du sous graphe nul.

Oui. En fait, on peut également exploiter l'algo min-max pour démontrer la chose : on évalue chaque fin de partie possible et on remonte dans l'arbre des coups alternativement le max des coups joués en dessous, puis le min, jusqu'à la racine de l'arbre (ou le min puis le max, ça dépend de qui joue le dernier coup). Et bien sûr il n'y a que 3 valeurs possibles, celle du gain, celle de la nulle et celle de la perte. Donc de 3 choses l'une, soit la note obtenue à la racine est maximale, cela veut dire qu'il existe une stratégie gagnante à tous les coups pour les blancs (1er à jouer c'est donc lui qui est à la racine), soit c'est la note de la nulle, donc on peut faire au mieux une nulle si les noirs jouent parfaitement, soit c'est la note de la perte, donc quoi qu'on fasse, il existe une stratégie pour les noirs qui leur permet de gagner.

A+,
Argyre

[invite06fcc10b]

Argyre: Je ne connais que très peu la mécanique quantique mais dans http://fr.wikipedia.org/wiki/Algorithme_de_Shor on lit que 15 a été factorisé avec un ordi quantique.Peut-être est-ce des qubits virtuels,mais en tout cas, ils arrivent à faire des calculs avec. Pourquoi pas avec les échecs?

Voici ce qui est dit dans Wikipédia pour cet algo :

Pourtant, la physique quantique ne nous permet pas d'accéder à toute l'information directement. Une mesure fournira seulement une parmi toutes les valeurs possibles en détruisant toutes les autres. Par conséquent nous avons à transformer avec précaution la superposition en un autre état qui retournera la réponse correcte avec une haute probabilité.

Si on réduit un qubit à 1 seule valeur, où est le gain de travailler avec des qubits ?
De plus, à part cet algo pour trouver la factorisation, je ne vois pas ce qu'on peut faire avec ça.
Ceci étant dit, je me suis renseigné sur ces calculateurs quantiques, mais je ne suis pas non plus un expert du domaine, donc je m'abstiendrais d'être trop vindicatif sur le sujet ...
A+,
Argyre

[invite116a953a]

Bonjour à tous, de retour sur le forum après quelques jours d’absences.
La discussion devient forte intéressante ! Je vais tenter de répondre aux différents points abordés d’une façon constructive en me basant uniquement sur mon expérience d’ancien joueur de tournoi.

PIWI : En milieu de partie ca n'est certainement pas 10 coups et +!
Ce qui fait la différence comme cela a deja été dit est la reconnaissance (theorique ou intuitive)de positions, de schémas.

D’abord il faudrait définir ce qu’est le milieu de partie. Pour ma part, je l’estime à peu prêt au début des prises de pièces. Dans cette situation, 5 coups sont bien fort peu, il y a beaucoup de risques. En particulier le risque de succomber à la tentation d’un « sacrifice ». J’ai perdu un certain nombre de parties en me laissant aller à chercher un hypothétique avantage numérique en oubliant les conséquences. Attention également au moment ou il y a échange, il faut bien imaginer l’état de l’échiquier après le combat pour commencer « la fin de partie » dans de bonnes conditions. Après oui la reconnaissance de schéma a complètement sa place.

Argyre :
1) Donc, je persiste, même si un grand joueur peut effectivement s'intéresser à une séquence de 10 coups, ce n'est qu'une séquence et comme cela a été dit par d'autres, il oublie volontairement de considérer un grand nombre de variantes qui peuvent le mener à sa perte.
…
2) N'exagérons rien, si tu connaissais l'algo alpha beta, tu saurais que l'ordinateur élimine lui aussi un grand nombre de variantes de façon très efficace.

1) Je ne suis pas d’accord. Les solutions écartées sont plutôt celle qui ne mènent à rien(avancer un pion isolé, etc…). Celles menant au mat ou au nul doivent être absolument prisent en compte.
2) Effectivement, je ne connaît pas l’algo alpha beta, je te remercie pour cette information. Est-ce que tu peux en dire un peu plus sur le type de combinaisons éliminé par cet algo?

En revenant sur le jeu « parfait », il serait peut-être plus facile de calculer toutes les parties possibles en admettant de restreindre la longueur de la partie en nombre de tours… En effet, le nombre de solutions de mouvements à chaque tour n’est pas si grand que ça, entre une vingtaine et une cinquantaine(au pifomètre). Ainsi tout les cas seraient pris en compte. Il suffirait alors de remonter « les branches » à partir des mats et nuls. Gros calcul quand même !

PS : Ceci dit, mon cœur de joueur est quelque peu frustré pas cette recherche mathématique sur un jeu aussi énigmatique que passionnant.

Enfin, je suis bien heureux de voir que la bonne humeur soit revenue sur ce topic

[invite3d7be5ae]

1)On écarte des solutions,la plus part du temps qui ne servent à rien sur le coup.
Et c'est comme ça qu'on en rate plein et qu'on rate aussi celle qui peuvent mener à la victoire.
2)Le min-max pour chaque position prend le maximum (ou le minimum) de toutes les possibilitées. Au feuille de l'arbre, on évalue la position en donnant un nombre.
Le meilleure possibilitée en haut est celle que l'ordi joue.
L'alpha-bêta a 2 variable,une la plus petite et l'autre la plus grande et si une des feuilles est plus petite que l'une (ou plus grande que l'autre) elle ne sert à rien. On peut aussi enlever des branches entières. Pour le reste,c'est le même principe que le min-max.

http://fr.wikipedia.org/wiki/%C3%89lagage_alpha-beta

Pole.

[invite116a953a]

1)On écarte des solutions,la plus part du temps qui ne servent à rien sur le coup.

Oui pour un "pré-traitement" des combinaisons. Cependant sur la suite du traitement des positions, ce coup, qui semble ne servir "à rien" peut faire partie intégrante d'une combinaison très évoluée. Sur ce point, l'ordinateur n'est pas si fort je pense. Le fait que l'homme enlève une combinaison rapidement n'induit pas qu'elle ne sera pas jouer "finalement". C'est flagrant pour un débutant qui va regarder une partie de grand maitres: il n'y comprend pas grand chose jusqu'au moment ou la partie est finie(j'exagère un peu pour l'exemple).

L'algo alpha-beta est très intéressant mais l'évaluation des noeuds me semblent difficiles non? On peut effectivement calculé le nombre de point(pièces), évalué les risques d'échec, de clouage etc... mais en prennant en compte ce que j'ai dit ci-dessus, à dire que telle ou telle situation est meilleure ou moins bonne...

[invite7a0a8d2e]

Bonjour,

pour en revenir au "Jeu Parfait" aux echecs.

Sachant que le jeu d'echec est un jeu à solutions finies.
La serie des coups joués peut alors etre écrite sous forme d'un arbre dont les branches se terminent par trois valeurs possibles.
Mat pour blanc
Nul
Mat pour noir
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 !

Blanc joue en premier et donc choisi une des n sous-branches. Il choisira la sous-branche qui contient une valeur finale "blanc gagne" mais qui ne contient pas, lorsque c'est au tour de noir de jouer une branche qui mene vers la valeur "noir gagne" sans que blanc puisse inflechir vers une branche blanche gagnante....
Car il ne faut pas oublier que noir aussi choisi l'orientation du jeu à chaque tour.

Et donc à chaque tour blanc devra faire ce choix, ceci etant uniquement possible s'il connait les 10¹²⁸ possibilités....

Seule la determination exhaustive de toutes ces possibilités permet de dire que blanc ou noir sera vainqueur à coup sur grace à un "Jeu Parfait".
En admetant que l'on calcule un noeud en 1 femtoseconde soit 10^-15seconde
il nous faut 10¹¹³ secondes pour calculer toutes ces possibilites. Soit environ 10⁹⁶ Milliards d'années....

Oui pour un "pré-traitement" des combinaisons. Cependant sur la suite du traitement des positions, ce coup, qui semble ne servir "à rien" peut faire partie intégrante d'une combinaison très évoluée

Exact, et c'est pour cette raison que dans l'absolu, on ne peut donc pas donner de "Valeur" à une piece.
Un pion peut être decisif au bon endroit au bon moment, tout comme la reine.

Conclusion : Le jeu parfait c'est pas pour demain

[invite116a953a]

Bonjour,

En admetant que l'on calcule un noeud en 1 femtoseconde soit 10^-15seconde
il nous faut 10¹¹³ secondes pour calculer toutes ces possibilites. Soit environ 10⁹⁶ Milliards d'années....

Effectivement vue comme ça, c'est une utopie

en revenant à ce 10¹²⁸:
Comment ce nombre a-t-il été déterminé? Qu'est-ce qui permet de déduire la notion de "nombre de combinaisons finies"?. Ne pourrait-on pas imaginé une partie sans fin où les pièces évoluraient indéfiniment?(un peu absurde dans le cadre du jeu mais pas dans un traitement purement mathématique)