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).Ne pourrait-on pas imaginé une partie sans fin où les pièces évoluraient indéfiniment?
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.Envoyé par martini_bird
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!
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
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 10128.
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 1058 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 10128 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.
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).
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.
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.
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...
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.
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.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...
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.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.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.
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.
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...
Bonjour,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...
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
C'est là le point clé de la construction de l'arbre : si un joueur est sur un noeud P, c'est que toutes les possibilités qui s'offrent à lui mènent son adversaire à un noeud G. La seule manière qu'a un joueur de passer de son sous-graphe P à son sous-graphe G au cours de la partie, c'est que son adversaire fasse une erreur et passe d'un noeud G à un noeud P. La stratégie optimale consiste précisément à ne jamais faire ce genre d'erreurs.Le problème c'est que l'autre joueur n'aura jamais de G à jouer, puisqu'il n'y était pas au départ et qu'il joue contre une stratégie qui ne fait pas d'erreur.Comme ça au moins on peut en discuter. Tu trouves pas que c'est préférable à une discution du type "moi je pense que..." et "moi mon intuition me dit le contraire" ?Qu'en pensez vous? au moins j'ai fais des efforts en démonstration...
Impossible. Ce n'est pas le même type de jeu car on joue en même temps.
L'erreur est qu'un joueur commence ou pas.
On part d'une position de morpion (* c'est moi,+ c'est toi).
*+*
+*+
. . .
Quoique tu fasses,je gagne.
On remonte.
*+ .
+*+
. . .
Si je la mais en bas à gauche,quoique tu fasses,je gagne.
En haut à droite je gagne aussi.
En bas à droite, je gagne directe.
Si je l'a met au milieu,c'est une partie nulle.
Tu comprends donc que c'est une position gagnante.
Après,il faut remonter et encore,et encore.
Pole.
mais bien SUuuuuur yat ,tu doutais de ma bonne volonté?
en fait je me suis mal exprimé dans les messages précédents et c'est vraiment pas mon habitude de me mettre en avant et d'affirmer des choses c'est pour cette raison que j'ai utilisé "je pense, mon opinion..." pour signifier "je vous propose..." honte à moi, mea culpa je le ferai plus. L'incident est clos.
Donc ma position A ne peut donner que G ou N alors que si on remonte d'une position on aura P ou N pour l'autre joueur.Soit dans le graph les lignes impaire G et N et les lignes paires P et N.
Si ta position A mène vers des noeuds P et des noeuds N, alors c'est un noeud N. Il y a plein de manières de reponter d'une position, et la seule chose dont on peut être sur, c'est que parmi toutes ces positions qui peuvent mener à A, aucune n'est P pour l'autre joueur.Pas compris, là...
le premier joueur joue une position G ou N (ligne 1 (impaire)) la réplique du deuxieme joueur est forcément P ou N (ligne2 paire)...etc non?
Effectivement si la position initiale est G pour les blancs, alors le premier joueur joue G, le deuxième P, et ainsi de suite. Si elle est N, tout le monde joue N...
C'est sur, en prenant les choses comme ça, ça n'arrète pas d'osciller entre gagnant et perdant. C'ets pour ça que j'avais présenté les choses différemment : il y a le graphe de victoire des noirs, le graphe de victoire des blancs, et le graphe nul. Comme ça, ça t'embrouillera peut-être un pue moins : dans le pire des cas, on reste toute la partie dans le graphe de départ. L'adversaire (celui qui ne connait pas la stratégie optimale), par contre, peut faire des erreurs, et sortir de son graphe pour aller dans un graphe moins avantageux pour lui.
Les échecs ne sont pas que calculs de coups à l'avance. Je suis un grand joueur moi-même.. et je peux vous en donne rici le secret :
Les Échecs sont un jeu de stratégie. Et la stratégie ne se calcule pas mathématiquement. Le calcul entre en compte lorsqu'on veut calculer la "tactique" qu'on va utiliser pour mettre notre "stratégie" en oeuvre. Voilà.. on peut calculer comme on veut, être un super-ordinateur, pouvoir calculer la tactique, si elle ne s'appuie pas sur une bonne stratégie (qui ne se calcule pas) et bien c'est foutu
je ne reviendrai pas ici, pour ceux qui voudraient m'estiner, on peut régler ça sur une partie d'échecs.. LOL
############
Dernière modification par martini_bird ; 25/12/2006 à 15h10. Motif: Supression d'une adresse électronique, conformément à la charte.
Il doit il y en avoir pour sacré bout de temps non?Lorsque toutes les parties auront été calculées (environ 10 puissance128) les Echecs ne seront plus que maths.(arf arf).
Si 1 milliard de machines, qui font chacune un milliard de calculs de parties à la seconde, travaillent pendant un siècle, elles auront fait un millième du milliardième du milliardième du milliardième du milliardième du milliardième du milliardième du milliardième du milliardième du milliardième du milliardième du milliardième du travail...
Il est temps de se mettre au boulot!
Good Night, and Good Luck!
Désolé, j'avais lu en diagonale, et n'avais pas vu que cette réflexion avait été faite sur la page 2: http://forums.futura-sciences.com/post849638-29.html
Good Night, and Good Luck!
Pour le raisonnement qui consiste à partir des fins de partie et à remonter le graphe, il faut démontrer aussi qu'en remontant comme ça, on arrive aussi à la position de départ... Ca ne me semble pas si évident que ça, non, voire même j'ai l'impression qu'on n'a pas progressé d'un pouce. On a identifié toutes les positions de départ avec une stratégie gagnante mais comment prouver que LA position de début est dans ce graphe là (ou le graphe des nuls, ou celui des défaites...) ?
Ca, comme ça a déjà été dit plusieurs fois ici, on n'en sait rien. Mais quel que soit le sous-graphe dans lequel la position initiale est contenue, l'hypothèse dont on parle est bien respectée : il existe une stratégie permettant à un joueur d'assurer la victoire ou le nul. Si la situation de départ est dans le sous graphe nul, elle permet bien à un joueur d'assurer la victoire ou le nul, et même aux deux joueurs. Dans le cas contraire, elle permet bien à un joueur d'assurer la victoire ou le nul, et même plus précisément d'assurer la victoire.
Salut,
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 . Meme si celle ci est desavantagée par un manque de strategie, sa capacité de calcul (a 9 coups pour deep fritz ) l'avantage sur les capacités de calcul a 6 coups pour un grand champion . Ces chiffres tinnent surement compte d'une configuration complexe du jeu .
Je pense que pour voir une partie parfaite il faudrait faire jouer Deep fritz VS Deep fritz . Et plus ses capacités de calcul augmenteraient avec le temps plus la partie se perfectionerait , mais cela n'aurait pratiquement aucun interet pour nous puisque nous ne pourrions pas comprendre le pourquoi du jeu , etant donné que nous ne pourrions nous projeter dans les calculs de la machine . Le jeu nous parraitrai certainement absurde . Par exemple une fois deep fritz a sacrifié une tour contre un humain , car il avait prevu la possiblité d'un mat a 8 tours s'il ne se sacrifiait pas , mais l'homme etant incapable de prevoir a si long therme, il aurait du jouer le bluf .
"Le monde contient bien assez pour les besoins de chacun, mais pas assez pour la cupidité de tous."
Bonjour,
j'y vais de ma démo, longue mais, je pense, plus compréhensible notamment pour ceux qui ont du mal à comprendre "on part de la fin" ou "pourquoi revient-on nécessairement à la position initiale".
On construit le graphe de toutes les parties possibles :
position initiale (n=0)
est reliée à 8x2(pions)+2x2(cavaliers)=20 "positions" (n=1)
Ces 20 "positions" sont elles-mêmes reliés à 20 "positions" (n=1). 20x20=400 "positions" n=2
Et on continue ainsi en allant toujours de l'avant et décrivant ainsi toutes les parties conformes aux règles d'échec (une partie d'échec est donc une suite de "positions" reliés par des liens formant une sorte de chemins allant de la position initiale jusqu'à une position finale*) Un même "échiquier" va donc se retrouver plusieurs fois sur ce graphe (mais on n'y sera pas parvenu de la même façon et la partie ne se déroulera ensuite pas nécessairement de la même manière).
* : position finale il y a toujours grace à la règle des 50 coups : un pion ne peut avancer que de 6 cases, il n'y a que 16 pions, il n'y a que 2x15 pièces ou pions qui peuvent prises, au pire (96+30)x50=6300 coups. En fait certainement moins (je ne suis ps sûr que l'on puisse amener les 16 pions au bout de l'échiquier en respectant les règles), deux adversaires même tétus s'arrêteront avant (mais ça on ne peut le présumer) mais c'est en tout cas fini (ce n'est pas indispensable mais ça va aider).
Un max de 6300 coups et pour chacun d'entre eux au plus 16(nombre de pièces ou pions qui vont bouger)x63(on peut faire mieux
Maintenant, on peut remonter ce graphe en partant de la fin.
>6300 pas possible
6300 : finalement il n'y en a pas
6299 : y a pas non plus
...
M : plus longue(s) partie(s) possible(s)
Pour chacune d'entre elles, la situation est claire :
soit nul (N) (selon une des règles quelconques : pat, règle des 3 suites de coups, ègle des 50 coups...)
soit victoire des blancs (W)
soit victoire des noirs (B)
N,W,B en anglais, le français ayant des initiales redondantes sur ce problème.
Positions M-1 :
il y en a désormais deux types possibles :
position finale, idem soit W, soit N, soit B
position non finale (pour simplifier supposons trait aux blancs) :
les positions n=M possibles à partir de la position n=M-1 considérée ne peuvent pas être des victoires de noirs pour l'instant (selon les règles blanc ne peut pas se mater même volontairement)
i) toutes les positions n=M possibles sont des nuls : blanc ne peut pas faire mieux que nul cette position est elle-aussi N.
ii) il existe une position n=M donnant la victoire à blanc, cette position est W (blanc joue bien)
Maintenant, pour les positions n=M-2
position finale => W,N ou B
position non finale :
a) toutes les positions suivantes (n=M-1) sont W (kézako : tout simplement blanc a donc joué en n=M-2 un coup "mat en 2 coups"), cette position est W
b) il existe des coups possibles donnant N ou B
bi) il existe au moins un coup débouchant sur une position B, la position n=M-2 est elle-aussi B (si noir joue bien il peut forcer la victoire)
bii) il n'existe que des positions N, cette position est elle-aussi N : ni noir ni blanc ne peuvent forcer la victoire mais chacun peut l'éviter (éventuellement si un joueur fait une erreur l'autre peut gagner mais chacun a au moins une suite de coups lui évitant la défaite)
Et on continue ainsi :
toutes les positions de n=M à n=I+1 ont été analysées W,N ou B.
position n=I
finale, c'est vu
non finale
il existe une position possible gagnante en n=I+1 cette position est W (si trait aux blancs) ou B (si trait aux noirs) : exemple mats en 42 coupsles noirs ont perdu "bêtement" leur reine sans contrepartie en début de partie et il se trouve que blancs peuvent (mais avec patience) forcer la gagne.
tous les coups possibles du joueur donnent des positions gagnantes à l'adversaire cette position est B (si trait aux blancs) ou W (si trait aux noirs)
Sinon, le joueur n'a aucune possiblité de forcer la gagne mais peut éviter la défaite (en jouant bien il peut empêcher noir de forcer la gagne)=>position N.
Toutes les positions n=I ont elles-aussi été analysées W,N ou B.
A force de faire baisser n, on aboutit à n=0 la situation initiale qui est donc soit W, soit N, soit B.
Maintenant, lors d'une partie réelle, la partie va suivre une zone du graphe qui n'est pas forcément la "meilleure" pour un des deux joueurs. Ainsi, ceux-ci peuvent tomber sur une position W, N ou B (mais car plus simple à analyser) qu'il, elle, ils ou elles analyse(nt) comme tels, exemple : mat en 5 coups pour noirs (blancs s'en est rendu compte après) ou Roi+fou+pion contre roi+pion+fou en position telle qu'il ne peut y avoir que nulle. La position initiale est en fait dans la même situation objective que ces dernières (elle est soit W, soit N, soit B) mais dans une situation subjective différente (personne, ni humain ni machine connu(e), ne sait dans laquelle elle est réellement).
"évalué" mais avec erreur : en fait il existe des suites infinies de coups aux échecs ne contenant aucune répétition de trois suites finies de coups (quelque soit la longueur évidemment de cette suite). Surprenant, non ?
Sur ce je m'en vais lancer un nouveau topic.
Autrement dit, entre une position initiale (présente et réelle), on conçoit une situation but, aussi précisément que possible. Puis on essaie de "nouer les deux bouts" par des positions intermédiaires (des buts intermédiaires).
Avant de procéder à l'analyse stratégique, on pourrait déjà s'évertuer à l'analyse rétrograde (= démarche scientifique aux échecs qui consiste à analyser le passé d'une position, avec ou sans autres informations que la position), laquelle est déjà fort ardue. Sherlock Holmes en échecs La situation initiale pouvant être (mais pas seulement) la position de départ des règles du jeu actuellement standard d'échecs.
Je suis curieux de savoir où trouver telle démonstration. Homotopie semble toutefois apporter la sienne.
Il y a nul sur l'échiquier - selon les règles de la FIDE - dans les cas suivants :
- Impossibilité stricte technique (scientifique) de mater (manque de matériel, pions bloqués et bloqueur) pour chacun des deux joueurs.
- Pat : Un joueur est mis pat quand les trois conditions sont remplies simultanément : il a le trait (les blancs ont le trait = c'est aux blancs de jouer) ; son roi n'est pas mis en échecs (il n'est pas menacé par une pièce adverse) ; il ne peut jouer aucun coup légal (càd, il ne peut jouer aucun coup qui ne mette son roi sous la menace d'une pièce adverse).
- La règle des 50 coups :
NB : Un "coup" signifie un coup des blancs et un coup des noirs. Ces deux derniers sont souvent appelés "demi-coups", notamment en analyse rétrograde.10.8 La partie est nulle lorsque le joueur ayant le trait le demande et peut démontrer que 50 coups consécutifs au moins ont été exécutés par chacun des joueurs sans prise de pièces ni mouvement de Pion. Ce nombre de 50 coups peut être augmenté dans certaines positions, pour autant que le nombre de coups et ces positions soient explicitement mentionnées dans les Règles du Jeu d'Echecs (Article 10.9).
10.9 Le nombre de 50 coups mentionné à l'Article 10.8 est porté à 75 coups dans les positions suivantes:
(a) Roi + Tour + Fou contre Roi + Tour
(b) Roi + deux Cavaliers contre Roi + Pion
(c) Roi + Dame + Pion à une case de la promotion contre Roi + Dame
(d) Roi + Dame contre Roi + deux Cavaliers
(e) Roi + Dame contre Roi + deux Fous
(f) Roi + deux Fous contre Roi + Cavalier.
Shokin
Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.
