[HorsMath]Echec et Maths

"sachant que le nombre de parties est fini,"

Ah oui ? Et tu le démontres comment ?

Mes moyens mathématiques sont très limités mais sachant qu'il existe une partie parfaite ie où tous les coups joués de part et d'autre sont optimums il y a donc un camp qui gagne quelquesoit la réponse ou alors le résultat optimum est la nulle.Le problème est plutôt liée à prouver l'existence d'une telle partie.

Rien n'a encore été démontré concernant le jeu d'échecs, et de façon plus générale on ne sait pratiquement rien sur tous les jeux pouvant admettre plus que le basique gain/perte comme résultat possible. L'opinion la plus communément répandue est que l'avantage du trait crée un déséquilibre trop faible pour permettre aux blancs de gagner sur un jeu parfait.

"Ah oui ? Et tu le démontres comment ?"

sachant que le nombre de coups d'un partie est majoré par M (évalué à 5000 selon mes références), le nombres de parties est donc majoré au pire par (2*8*2*7)^M.

Bisam >

(...)à chaque coup il n'y a qu'un nombre fini de coups autorisés.(....)

Si à chaque demi-coups il y a 30 coups environs possibles, l'ordre du nombre de positions après n demi-coups est de l'ordre (grossièrement) de 30^n. De plus, même en finale (fin de partie avec peu de pièce), si le nombre de pièce est réduit, le nombre de cases pouvant être occupées est plus grand, d'où une "certaine" stabilité du nombre de coups possibles.
Même en ne comptant que les coups viables, rien n'oblige d'avoir un nombre fini de parties.

(...)De plus le nombre de coups est fini puisque la règle des 50 coups empêche que la partie s'éternise...(...)
La règle des 50 coups ne s'applique que si aucun coup de pion n'a été joué !!! Rien n'empeche une partie de "durer" 1256 coups, si tous les 50 coups, un pion est joué.

D'accord avec le reste, et j'ajouterais que le jour où les ordinateurs pourront "voir" (c'est à dire parfaitement évaluer) la position après 50 coups, je doute que beaucoup de parties de grand-maître puissent résister. Les grands joueurs penchent pour la nulle (Joel Lautier aimerait que ce soient les noirs qui gagnent, ce qui ferait du 1er coup, un affaiblissement!).

Le jeu qui a un nombre fini de parties possibles et dont le nombre est "facilement" majoré est l'Othello (ou reversi):
Il y a 64 cases dont les 4 centrales (e4, d4,e5,d5) sont déja occupées. Les Noirs et les Blancs posent alternativement un pion (selon certaines règles bien sur, et on peut être dans une situation où l'on est obligé de passer son tour). Un majorant grossier est 2^64.

Airy

Rémi, je ne pense pas que l'existence d'un arbre fini empêche les échecs d'être un jeu (encore faut-il d'abord s'entendre sur ce que l'on entend par jeu). La construction d'un tel arbre est impossible en pratique, et on peut conjecturer que la construction des seules sous-branches de cet arbre correspondant à un jeu parfait font elles aussi intervenir des grandeurs physiques totalement hors de portée.

Pour ma part, j'ai entendu tellement souvent ce genre de propos (par des personnes incompétentes en la matière, cela va de soi) que je n'y accorde plus aucun crédit, du moins sans source avisée.

Et tant bien même le jeu d'échecs serait résolu par un algorithme, sa richesse est suffisante pour que des générations de joueurs continuent de le pratiquer. De mémoire, Nigel Short a d'ailleurs déclaré à ce sujet, à l'époque où les ordinateurs commençaient à battre les GMI en blitz de façon régulière, quelque chose comme "l'apparition des ferrari n'a pas arrêté la course à pied..."

Juste une rectification: un majorant grossier du nombre maximal de parties au Reversi est plutôt 60! (2^64 est un majorant grossier du nombre de positions finales).

Airy

Kashmir, la seule chose de démontrée à ce jour est l'assertion de GPP29. Je pense que de l'eau coulera sous les ponts avant que l'on ne soit en mesure de déterminer quel est le résultat sur un jeu parfait...

Bonsoir,

j'avais lu un truc il y a fort longtemps là dessus : > (de mémoire, ça devait être sorti dans un \emph{La Recherche} ou un \emph{Pour la Science} dans les années 80). J'en donne la démonstration plus bas, et quelques réflexions personnelles avant.

En considérant arbitrairement que (par exemple) > quand ils gagnent ou font partie nulle, ce théorème entraîne que tout jeu avec un nombre fini de coups admet une stratégie non-perdante.

Après, c'est une résultat d'existence, qui n'est en aucun cas constructif : savoir que ça existe sans avoir la moindre idée du début du commencement d'une telle stratégie ne tue en rien le jeu, heureusement !

Cela me fait penser à la démonstration simplissime d'existence d'irrationnels : >. Une telle démonstration ne donne \emph{aucune} indication sur qui sont les irrationnels, ni sur le moindre moyen de les reconnaître. De même, la démonstration qui suit ne donne aucun moyen de connaître la stratégie (si ce n'est faire un arbre de toutes les possibliités, ce qui et impossible). Bref.


Montrons à présent que pour tout $n$, tout jeu sans partie nulle se jouant en au plus $n$ coups est à stratégie gagnate. On procède par récurrence sur $n$. L'idée de la démonstration est de remplacer > par >. Appelons Albertine la première joueuse, et Buxtehoude la deuxième (c'est plus joli que > et >, je trouve).

-- pour $n = 1$ : de deux choses l'une,
\quad -- ou bien Albertine a un coup qui la fait gagner, auquel cas elle n'a qu'à le jouer : elle a donc une stratégie gagnante ;
\quad -- ou bien quoiqu'elle fasse elle perdra : dans ce cas, c'est donc son adversaire qui a une stratégie gagnante.

-- Soit $n \geqslant 1$, supposons que tout jeu se jouant en au plus $n$ coups admet une stratégie gagnante et considérons un jeu se jouant en au plus $n+1$ coups.
Dès le premier coup joué par A, il ne restera qu'au plus $n$ coups à jouer, et l'une des deux joueuses aura donc une stratégie gagnante (hypothèse de récurrence). De deux choses l'une :
\quad -- ou bien quoique joue A à son premier coup, B aura une stratégie gagnante à partir du 2ème coup : dans ce cas, le jeu possède une stratégie gagnante pour B ;
\quad -- ou bien il existe un coup de A qui lui donne une stratégie gagnante à partir du 2ème coup : dans ce cas, le jeu possède une stratégie gagnante pour A.



Bonne nuit,
Daniel

Pour aviva et jaybe

Imaginons que le premier joueur avançant un pion affaiblisse sa position de façon déterminante. Alors chaque joueur dispose d'une stratégie non perdante qui consiste à balader indéfiniment ses cavaliers, sans jamais avancer aucun pion et sans les exposer à être pris. La partie se soldera par un nul par répétition de coups.

Guy, je ne suis pas d'accord avec ta remarque "chaque joueur dispose d'une stratégie non perdante qui consiste à balader indéfiniment ses cavaliers". Pour que cette stratégie soit effectivement non perdante, il faut qu'elle ne perde pas indépendemment de ce que va jouer l'adversaire. Or celui-ci n'est nullement obligé de transformer son camp en hippodrome.

bonjour aviva,

ton raisonnement est faux car à l'instant où tu rapatries ton cavalier, tu es bien dans une situation (sur l'échiquer) comme si noir avait commencé, MAIS ... maintenant c'est à Noir de jouer pas à Blanc d'où le problème ...

[aviva: lol évidemment, désolé pour la bêtise que j'ai dite... merci!]

Je vous recommande à nouveau la lecture de "l'assassin des échecs" de Benoît Rittaud.
La nouvelle en question illustre le fait que le jeu d'echec n'est pas un JEU au sens mathématique du terme (l'arbre n'a pas de boucles, il est fini, et les joueurs sont à chaque pas informés de la position des pions), mais la mise en evidence de ce caractère implique des conditions matérielles non réalisables aujourd'hui.

il ne me semble pas qu'il y ait une partie parfaite, mais qu'à chaque coup de l'adversaire, il est possible de choisir le coup suivant nous menant petit à petit à la victoire.
Autrement dit, quelle que soit la partie du deuxième joueur, le premier avancera dans l'arbre inexorablement vers la victoire, si à chaque coup, il s'oriente de façon optimale.

Mais cette connaissance n'est pas accessible à l'humain. Et les machines ne pourraient pas les contenir aujourd'hui...

Ainsi, les plus grand maîtres ont encore de beaux jours devant eux.

Mais du point de vue théorique, les echecs ne constituent pas un jeu.

PS : après, on peut discuter de la compétence de Benoît Rittaud en la matière...

Bonjour à tous,

Le mat le plus court est en fait en deux coups seulement et, comme le fait remarquer Oumpapah, sur une énorme faute des blancs.

Il y a des parties symétriques qui se terminent sur un mat par les blancs, avec une longueur de plus de 15 à 20 coups.

Sur la règle des 50 coups : sauf avance de pions ou prise de pièce.
De plus elle est aménageable : si un joueur peut prouver qu'il y a un résultat décisif en plus de 50 coups sans avancée de pions ni échange de pièces, on peut prolonger la partie (ça reste assez théorique).

Sur la répétition : il faut que la position se répète 3 fois, avec le trait (le droit de jouer) au même camp. Subtilité : on doit demander la nulle AVANT de jouer le 3ème coup fatidique. Curiosité : à l'époque du premier champion du monde, Steinitz, fin 19ème, la règle était valable avec 5 coups et on a vu des parties de Steinitz avec 4 répétitions.

J'aurais eu tendance à dire la même chose que Short : les Ferrari vont beaucoup plus vite que les hommes, mais on court toujours.

Kashmir, si je ne m'abuse, le seul lien unissant gagner et ne pas perdre est une implication. Si l'on veut se placer dans un cadre où il y a effectivement équivalence, alors il faut que l'ensemble des résultats possibles soit restreint à gain/perte, et ce n'est pas le cas ici.

Je suis bien d'accord, c'est la le noeud du problème. Je dirais que formaliser le mot "gagner" revient, en gros et selon les cas, à trouver un vecteur $X$ tel que $MX$ est à coordonnées strictement positives, à déterminer une combinaison de coups dont l'espérance est strictement positive, etc., et pour "ne pas perdre", on fait pareil mais avec des inégalités larges, d'où l'implication. Je pense que l'on doit pouvoir traduire ça d'une façon encore plus rigoureuse mais je ne la vois pas...