Jeu parfait aux échecs

[interferences]

Ma définition de l'erreur sert à déterminer la rupture d'équilibre si vous voulez.
-----

[Brakebein]

quelqu'un a la petite formule pour dénombrer le nombre de parties (tous coups confondus, débiles ou divins) menant à la victoire de blancs, de noirs, ou de nul ?

[Tryss]

On ne connait pas exactement le nombre de parties, et c'est clairement non trivial à dénombrer.

Il y aurait environ 10^120 parties logiques possibles, mais beaucoup plus de parties légales

[Etorre]

On ne connait pas exactement le nombre de parties, et c'est clairement non trivial à dénombrer.

Il y aurait environ 10^120 parties logiques possibles, mais beaucoup plus de parties légales

Oui tout a fait d'accord, sauf qu'on est pas a un facteur 1000 prés. 10^120 ou 10^123, c'est du pareil au même. C'est l'ordre de grandeur qui compte.
Le nombre de partie légale doit être environ 10^30 fois plus élevé (genre a chaque coup on s'amuse a bouger chacune des pièces, une fois, ou deux ou trois fois, puis revenir a la position initiale, ou pas...)soit une vingtaine de demi-coup possible ou on peut revenir en arrière, pareil pour l'adversaire donc 20^6 (le 6 vient de 6 démi-coup avant le nul possibilité de compliquer, ce a chaque coup. enfin ça n'a aucun sens ! Et puis ca ne change pas tant que ca le nombre colossal, le plus important c'est que le nombre de partie possible reste finit.
Et puis en faite si c'est facile a calculer, il suffit d'envisager toute les configuation possibles pour les pieces, sachant que 3 configurations identique entraine un pat.

[Tryss]

Non, si il y a 10^120 parties sensées, il n'y en a pas juste 10^30 fois plus de légales... Wikipedia donne plus de 10^6000 parties légales.

Par exemple pour une partie de 50 coups donnée, si on choisi ou non de faire 2 coups idiots à chaque demi coup (toujours les mêmes), il y a déjà 10^30 parties correspondantes, si il y a 3 possibilité de "chemins idiots"+coup normal à chaque demi coup, c'est 10^60 parties

Il est en effet facile de faire des parties de plusieurs milliers de coups : il suffit de jouer des coups "idiots" entre les prises en évitant les répétitions.

Si ce qui t’intéresse juste c'est de savoir que le nombre de partie reste fini, la règle de la répétition des 3 coups suffit, à partir du moment ou échiquier est de taille finie et le nombre de type de pièces fini (même si on pouvait rajouter des pièces, ou les transformer).

De même, ça n'est pas parce que tu connais toutes les positions légales que tu peux calculer facilement le nombre de parties possible, juste une borne supérieure.

[Etorre]

Non, si il y a 10^120 parties sensées, il n'y en a pas juste 10^30 fois plus de légales... Wikipedia donne plus de 10^6000 parties légales.

Par exemple pour une partie de 50 coups donnée, si on choisi ou non de faire 2 coups idiots à chaque demi coup (toujours les mêmes), il y a déjà 10^30 parties correspondantes, si il y a 3 possibilité de "chemins idiots"+coup normal à chaque demi coup, c'est 10^60 parties

Il est en effet facile de faire des parties de plusieurs milliers de coups : il suffit de jouer des coups "idiots" entre les prises en évitant les répétitions.

Si ce qui t’intéresse juste c'est de savoir que le nombre de partie reste fini, la règle de la répétition des 3 coups suffit, à partir du moment ou échiquier est de taille finie et le nombre de type de pièces fini (même si on pouvait rajouter des pièces, ou les transformer).

De même, ça n'est pas parce que tu connais toutes les positions légales que tu peux calculer facilement le nombre de parties possible, juste une borne supérieure.

Bonjour,
Oui et franchement quel est l"intérêt ? que ce soit 10^90, 10^120, ou 10^60000000, le nombre reste impossible a stocker dans une mémoire physique, puisque supeieur u nombre d'atome dans l'univers.. le probleme reste entier. et la question était : Si on connait toutes les parties... donc le nombre de partie, peu importe. Et il s'agit également d’éviter toutes les partie a coup unitile, puisque qu'elle reviennent au même et ont le même résultat P, N ou G.
Cordialement,

[Médiat]

Bonjour,

Ma définition de l'erreur sert à déterminer la rupture d'équilibre si vous voulez.

Je vous propose d'autres définitions :

A chaque position (y compris le début de partie) on associe la valeur 1 si le joueur devant jouer a une stratégie gagnante, 0 s'il a, au mieux, une stratégie qui mène à une partie nulle, -1 si, quoi qu'il fasse, son adversaire a une stratégie gagnante.

Si la valeur associée est 1 ou 0 on associe aussi la longueur la plus courte, en maximisant les qualités de l'adversaire, qui amène à ce résultat.
Si la valeur associée est -1 on associe aussi la longueur la plus longue, en maximisant les qualités de l'adversaire, qui amène à ce résultat.

Bien sur, aujourd'hui, nous ne sommes capable de calculer ces valeurs que dans de très rares cas.

Une erreur est un coup tel que la valeur de la position pour ce joueur après le coup est inférieure à la valeur avant le coup, ou, si la position ne change pas, si la longueur augmente dans les cas 1 et 0, ou diminue dans le cas -1.

Une partie parfaite pour un joueur, est une partie ou la valeur de sa position n'a jamais baissée, et la longueur n'a jamais été dégradée ; avec cette définition, un joueur peut faire une partie parfaite, mais pas l'autre.

Une partie parfaite est une partie ou les deux joueurs font une partie parfaite.

Il va de soi que ces définitions ne servent pas à grand-chose, si on ne sait pas calculer les caractéritiques d'une position.

[Tryss]

Hum, Médiat, l'idée qu'une partie "parfaite" est la plus courte possible est discutable : si le meilleur résultat pour les deux joueurs est le nul, la partie parfaite aurait pour but de se mettre en pat le plus vite possible, ce qui serrait fort peu naturel.

D’ailleurs on connait la partie la plus courte qui se finit par une nulle? Il y a plus court que 4 coups ? (8 demi coups, avec les cavaliers qui vont et vienne pour activer la règle des 3 coups)

[Médiat]

Bonjour,
Pour que la partie précédente soit parfaite, il faudrait être sur qu'aucun des deux joueurs n'ai une stratégie gagnante à partir de n'importe laquelle des 4 positions qui apparaissent dans cette partie, si c'est bien le cas, en mettant face à face deux joueurs parfaits qui ne peuvent espérer qu'un nul (si c'est bien le cas), pourquoi choisiraient-ils une autre possibilité que de jouer la partie la plus rapide ?

Maintenant, si on préfère dire que la meilleure partie nulle est la plus longue et non la plus courte, ma définition marche toujours avec une modification mineure.

[Médiat]

Je complète le post précédent :
1) il me semble qu'entre deux coups qui vont me placer dans une position gagnante, c'est celui qui donne le chemin le plus court qui est le meilleur
2) entre deux coups qui vont me placer dans une position perdante (sans qu'il y ait de cas me plaçant dans une position gagnante ou de nul), c'est celui qui donne le chemin le plus long qui me paraît le meilleur (ne serait-ce que pour donner plus de circonstances pour une erreur de l'adversaire)
3) dans le cas où, au mieux, je ne peux jouer que des cas menant au nul, on peut choisir de définir le meilleur comme le chemin le plus court comme je l'ai proposé dans mon premier post, ou le plus court comme ci-dessus, ou même on peut ne pas tenir compte de la longueur.

[Deedee81]

Salut,

2) entre deux coups qui vont me placer dans une position perdante (sans qu'il y ait de cas me plaçant dans une position gagnante ou de nul), c'est celui qui donne le chemin le plus long qui me paraît le meilleur (ne serait-ce que pour donner plus de circonstances pour une erreur de l'adversaire)

Ce n'est sans doute pas aussi simple. La possibilité d'erreur de l'adversaire ne tient pas qu'à la longueur. Peut-être en partie (et encore) si l'adversaire est une machine, mais si c'est un humain, la "complexité" (évaluée comment ???) des positions importe plus.

Maintenant, la longueur reste un première critère.

Pour le nul, je choisirais aussi le plus long, pour la même raison : une erreur adverse me permettant de gagner. Inutile de se serrer la main si on estime que l'adversaire a encore de grande chance de se tromper (sinon si les jeux parfaits conduisaient à une nulle, plus personne ne jouerait..... ce qui est presque le cas au tic tac toe, on ne joue pas longtemps avant d'avoir une stratégie parfaite et les jeux deviennent tous nul).

[Médiat]

La discussion est, bien sur, purement théorique, pour ne pas dire rhétorique, puisque ces calculs sont impossibles (ce jour).

On pourrait envisager d'autres mesures, et pour le nul, choisir le coup qui laisse à l'adversaire aucune stratégie gagnante, bien sur, mais qui laisse le maximum de positions perdantes, ou le plus grand rapport [Parties perdantes]/[Parties nulles] à l'adversaire (une tentative de mesure de la complexité).

[Deedee81]

La discussion est, bien sur, purement théorique, pour ne pas dire rhétorique, puisque ces calculs sont impossibles (ce jour).

On pourrait envisager d'autres mesures, et pour le nul, choisir le coup qui laisse à l'adversaire aucune stratégie gagnante, bien sur, mais qui laisse le maximum de positions perdantes, ou le plus grand rapport [Parties perdantes]/[Parties nulles] à l'adversaire (une tentative de mesure de la complexité).

A défaut, ça me semble un critère plutôt bon. C'est le genre de critère sympa à programmer (avec un arbre tronqué c'est réalisable bien que là, les heuristiques d'évaluation donnent déjà d'excellents résultats. Mais en cas de valeurs proches, ça me semble un bon critère.... d'ailleurs ça ne me surprendrait pas qu'il soit déjà appliqué. Les concepteurs de programme de ce genre sont malins ).

[Tryss]

La discussion est, bien sur, purement théorique, pour ne pas dire rhétorique, puisque ces calculs sont impossibles (ce jour).

Disons que c'est une discussion interessante que de se demander, une fois qu'un jeu est résolu, quels sont les critères pour juger une partie.

Par exemple aux echecs, on pourrait aussi considérer l'avantage aux points : il y a peut être des chemins ou l'un des joueurs capture plus de pièces que d'autre.

Après ce ne sont que des critères arbitraires, et sont probablement fortement dépendant du jeu, et il est clair que pour le jeu d'echec c'est un peu comme parler du sexe des anges , par contre pour les jeux résolu, ça a un "sens". On pourrait même définir plusieurs familles de critères, qui serraient ou non compatibles les uns avec les autres, et qui donneraient plusieurs strategies, toutes valable d'un point de vue "résultat du jeu"

[invite1e0a97f7]

c'est complétement impossible a calculer sachant qu'il n’existe pas de définition d'un joueur parfait et une erreur pour un joueur peut être une réussite pour un autre

Et cela dépend aussi du juge de la partie car un juge peut juger une stratégie "bonne" et un autre "mauvaise"

Le point de vue d'un humain est impossible a calculer

[Etorre]

c'est complétement impossible a calculer sachant qu'il n’existe pas de définition d'un joueur parfait et une erreur pour un joueur peut être une réussite pour un autre

Et cela dépend aussi du juge de la partie car un juge peut juger une stratégie "bonne" et un autre "mauvaise"

Le point de vue d'un humain est impossible a calculer

bonjour,

Le but c'est de gagner point barre. La bonne stratégie, c'est celle qui gagne, la mauvaise celle qui perd. Je comprend pas ta remarque, elle n'a aucun sens a mon avis

[invite1e0a97f7]

imaginons que la stratégie A joue contre la stratégie B A gagne 2 ieme match A joue contre C et C gagne 3iem match B contre C et B gagne maintenant éxplique moi quelle est la meilleur stratégie

[Tryss]

imaginons que la stratégie A joue contre la stratégie B A gagne 2 ieme match A joue contre C et C gagne 3iem match B contre C et B gagne maintenant éxplique moi quelle est la meilleur stratégie

Ça n'est pas possible dans un jeu comme les échecs, ou il n'y pas à proprement parler de stratégie.

En théorie jouer aux échec revient à choisir la branche de l'arbre qui donne le meilleur résultat, et l'évaluation de ce résultat ne dépend pas de l'adversaire dans l'absolu.

Le jeu d'échec n'a donc d’intérêt que parce que l'on est incapable en pratique d'évaluer ce résultat (sinon le jeu n'aurait plus d’intérêt).
Un jeu comme le dilemme du prisonnier (ou le pierre feuille ciseau) a par contre plusieurs stratégies possible, dont le résultat dépend du joueur adverse

[invite1e0a97f7]

oui tu as raison

[leon1789]

Ça n'est pas possible dans un jeu comme les échecs, ou il n'y pas à proprement parler de stratégie.

En théorie jouer aux échec revient à choisir la branche de l'arbre qui donne le meilleur résultat, et l'évaluation de ce résultat ne dépend pas de l'adversaire dans l'absolu.

A moitié vrai, à moitié faux. Exemples :
Si l'adversaire est une machine, il vaut mieux éviter les parties tactiques où l'ordi excelle par rapport aux hommes (sauf exception très particulière).
Si l'adversaire est nettement plus fort que moi en ouverture, alors je vais essayer de sortir quelques coups étranges pour le sortir de sa théorie.
Si un match nul me permet de gagner un tournoi, alors je vais choisir des variantes simplificatrices. Etc.

Le jeu d'échecs n'est pas seulement la recherche du coup objectivement le plus fort (s'il en existe un) : il y a aussi un petit coté psychologique (moindre qu'au poker, ok).

Le jeu d'échec n'a donc d’intérêt que parce que l'on est incapable en pratique d'évaluer ce résultat (sinon le jeu n'aurait plus d’intérêt).

Je ne suis pas trop d'accord. Certes, connaitre la "valeur" du jeu est très intéressant (probablement match nul, mais cela reste à prouver, ok).
Mais même si on démontrait que le résultat normal est partie nulle, le jeu continuerait à passionner les foules car aucun être humain ne sera un jour capable (sans aide informatique, ni littérature sur-abondante) de jouer parfaitement (et qui plus est rapidement).

C'est comme les maths : même si on trouvait une incohérence, les maths continueraient à exister, vu tout ce qu'elles ont pu apporter de concret...

[Etorre]

A moitié vrai, à moitié faux. Exemples :
Si l'adversaire est une machine, il vaut mieux éviter les parties tactiques où l'ordi excelle par rapport aux hommes (sauf exception très particulière).
Si l'adversaire est nettement plus fort que moi en ouverture, alors je vais essayer de sortir quelques coups étranges pour le sortir de sa théorie.
Si un match nul me permet de gagner un tournoi, alors je vais choisir des variantes simplificatrices. Etc.

Le jeu d'échecs n'est pas seulement la recherche du coup objectivement le plus fort (s'il en existe un) : il y a aussi un petit coté psychologique (moindre qu'au poker, ok).


Je ne suis pas trop d'accord. Certes, connaitre la "valeur" du jeu est très intéressant (probablement match nul, mais cela reste à prouver, ok).
Mais même si on démontrait que le résultat normal est partie nulle, le jeu continuerait à passionner les foules car aucun être humain ne sera un jour capable (sans aide informatique, ni littérature sur-abondante) de jouer parfaitement (et qui plus est rapidement).

C'est comme les maths : même si on trouvait une incohérence, les maths continueraient à exister, vu tout ce qu'elles ont pu apporter de concret...

tout a fais d'accord. même avec toutes les cartes en mains, il reste une composante psychologique. Et Il est plus que certain que Kasparov ne joue de la même manière contre un humain que contre l'ordinateur.

[Tryss]

A moitié vrai, à moitié faux.

Je parlais d'un point de vue théorique. Il est évident que pour des joueurs humains il existe tout un tas de stratégies, mais du point de vue théorique, les échecs (ou le go) ne sont pas différents du morpion.

Mais même si on démontrait que le résultat normal est partie nulle, le jeu continuerait à passionner les foules car aucun être humain ne sera un jour capable (sans aide informatique, ni littérature sur-abondante) de jouer parfaitement (et qui plus est rapidement).

Oui, c'est ce que je disais : on est incapable d'évaluer en pratique la valeur de chaque coup, et c'est ça qui rend le jeu intéressant. Sinon c'est comme un morpion (la seule différence étant le nombre de branches et la longueur de la partie).

[Pio2001]

Moi je pense le contraire, je pense même que des parties parfaites ont déjà été jouées.
[...]
Marrant comme idée, mais plus que très improbable.
La pratique ayant plutôt montré que les blancs ont l'avantage.

Il est très improbable que des parties algorithmiquement parfaites aient été jouées. L'Othello est un exemple de jeu où l'ordinateur est très supérieur à l'humain, bien qu'il ne soit pas totalement résolu.
Or on observe, lorsqu'on augmente progressivement la profondeur de recherche du logiciel jusqu'à ce qu'il atteigne sa force maximale, que des coups dits "inhumains" apparaissent. Ce sont des coups en apparence parfaitement stupides, qui semblent perdre gros, et qui pourtant, marchent. lorsque la profondeur d'analyse n'est pas trop grande, on peut encore analyser ces coups. Cela donne ce genre de chose :

L'ordinateur joue. Le coup paraît très mauvais.
Réponses possibles de l'humain :
1 Bonne réponse, sanctionne l'erreur de l'ordi.
2 Autre bonne réponse
3 Moyen, rétablit l'équilibre
4 Mauvais coup
5 Mauvais coup
etc

On regarde ensuite les réponses de l'ordi aux réponses de l'humain :
Humain réponse 1. Ordi réponse 1 : Waow ! Il reprend l'avantage contre toute attente (mais seul un grand maître peut le voir à ce stade)
Humain réponse 2. Ordi réponse 1 : l'humain semble toujours avoir l'avantage, mais bizarrement, il ne se concrétise pas tout de suite

Puis la suite de la réponse 2 :
Humain 2 ordi 1 Humain 1 : pareil, ça traîne en longueur
Humain 2 ordi 1 Humain 2 : on perd l'avantage ...

Puis Humain 2 ordi 1 humain 1 ordi 1 : ah ben finalement, cela ne marche pas, on commence à voir que l'ordi gardera l'avantage...

De même, aux échecs, il se peut très bien que le jeu soit gagnant pour noir et que le bon coup consiste à sacrifier la dame dès le début. On ne le saura probablement jamais. Cela donnera simplement une position "Noir gagne en 47 coups", et pour le démontrer, il faudra donner la liste des 10^100 variantes et montrer qu'elles sont toutes perdantes pour blanc.

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.

Pas nécessairement. Photon57, tu dis que l'ordinateur quantique donne une réponse avec une probabilité de réussite > 2/3. Si je comprends bien, cette réponse est certaine à 100 %, et dans 1/3 des cas, on n'a pas de réponse avant un temps beaucoup plus long, c'est bien ça ?

Dans ce cas, la résolution n'est pas certaine, mais si elle se produit, elle est exacte et définitive, au sens de démonstration mathématique.

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 ?

Il n'est pas nécessaire d'explorer toutes les parties si on dispose d'algorithmes permettant d'élaguer de façon définitive certaines branches de l'arbre. Par exemple, on peut démontrer que roi + tour contre roi est gagnant en donnant une méthode qui permet de faire mat.
On commence par démontrer que cette méthode marche dans la totalité des cas de figure tour + roi contre roi, et on se passe alors d'explorer des milliards de milliards de branches correspondant à toutes les variantes tour + roi contre roi. On les déclare gagnantes d'office pour le côté qui a la tour.
Et même après avoir épuisé tous les algorithmes de ce genre, on n'est pas obligé de stocker en mémoire toutes les parties qui restent à étudier. On peut les supprimer de la mémoire au fur et à mesure en ne notant le résultat que pour le noeud du graphe qui y mène.

Le jeu parfait au Rubik's Cube a ainsi été résolu, alors qu'on est très loin d'avoir exploré les 10^43 configurations possibles. L'approche a consisté à faire des études théoriques générales. Les théorèmes succédant aux théorèmes, le problème a été progressivement circoncis à une petite classe de séquences à explorer. Celle-ci était malgré tout encore bien trop grande pour être calculée en totalité.
Le problème a alors été divisé en 2 millions de problèmes plus simples qui ont été résolus un par un à l'aide du calcul brut.

[invite4492c379]

Hello,

(...)


Pas nécessairement. Photon57, tu dis que l'ordinateur quantique donne une réponse avec une probabilité de réussite > 2/3. Si je comprends bien, cette réponse est certaine à 100 %, et dans 1/3 des cas, on n'a pas de réponse avant un temps beaucoup plus long, c'est bien ça ?

Dans ce cas, la résolution n'est pas certaine, mais si elle se produit, elle est exacte et définitive, au sens de démonstration mathématique.

Non, tous les algorithmes quantiques connus possèdent la propriété de ne pas forcément donner la bonne réponse : la probabilité de donner une mauvaise réponse est non nulle (mais une réponse est toujours donnée). Évidemment la manière de les implémenter est faite de manière que la probabilité de donner un résultat incorrect est extrêmement faible.

Pour étudier la complexité des algorithmes on regroupe ces algorithme en plusieurs classes. Il y a les deux très connues P et NP par exemple dans le domaine «classique». Dans le domaine «quantique» on a créé aussi de telle classe. Il y a par exemple BQP, une classe qui regroupe les algorithmes quantiques qui en temps polynomial donnent une réponse qui est correcte avec au moins une probabilité de 2/3 (il y a la classe équivalente BPP dans le domaine classique). Cette classe est souvent considérée comme la classe des problèmes qui peuvent être résolus de manière efficiente sur un ordinateur quantique (cf machine de turing quantique).

(...)
Le jeu parfait au Rubik's Cube a ainsi été résolu, alors qu'on est très loin d'avoir exploré les 10^43 configurations possibles. L'approche a consisté à faire des études théoriques générales. Les théorèmes succédant aux théorèmes, le problème a été progressivement circoncis à une petite classe de séquences à explorer. Celle-ci était malgré tout encore bien trop grande pour être calculée en totalité.
Le problème a alors été divisé en 2 millions de problèmes plus simples qui ont été résolus un par un à l'aide du calcul brut.

Quelques précisions, il n'y a pas 10^43 configurations mais 43.10^18. Le jeu parfait (la séquence de mouvement de cardinalité minimale pour arriver à la position gagnante) ne concerne qu'une configuration. Ce qui a été prouvé est qu'un jeu parfait requiert au maximum 20 mouvements. Le problème n'était pas de résoudre tous les configurations pour en trouver un jeu parfait.
Tout est dispo (y compris le code source) sur http://www.cube20.org/

[JPL]

le problème a été progressivement circoncis

Par un argument tranchant ?

[Pio2001]

Quelques précisions, il n'y a pas 10^43 configurations mais 43.10^18.

Merci de la rectification, je savais bien qu'il y avait un 43 quelque part Maintenant que j'ai l'article de Jean-Paul Delahaie sous la main, je peux poursuivre sans trop de risques de me tromper.
Notez que même avec ce nombre réduit de configuration, le temps de calcul pour les analyser toutes était estimé à 1300 ans si on faisait tourner en parallèle le millard d'ardinateurs qui existent sur Terre. Cela illustre bien le temps de calcul que l'on peut gagner en optimisant l'algorithme. En réalité, cela a pris l'équivalent de 35 ans de calcul d'un ordinateur moyen (réalisés en quelques semaines sur des gros ordinateurs), soit un gain d'un facteur 40 milliards.

Le problème n'était pas de résoudre tous les configurations pour en trouver un jeu parfait.

A la base, si, justement. L'approche brute aurait été, pour chacune d'entre elles, de déterminer la séquence la plus courte, puis de prendre la plus courte parmi les 43 10^18 séquences optimales obtenues. Mais de nombreuses astuces ont permis de s'en passer.
Ainsi, pour les échecs, il est exact qu'analyser toutes les parties possibles est hors de portée, mais il n'est pas nécessaire d'analyser toutes les parties possibles.

Par un argument tranchant ?

Je voulais dire "circonscrit", évidemment, mais impossible d'éditer, maintenant !

[invite4492c379]

(...)
A la base, si, justement. L'approche brute aurait été, pour chacune d'entre elles, de déterminer la séquence la plus courte, puis de prendre la plus courte parmi les 43 10^18 séquences optimales obtenues. Mais de nombreuses astuces ont permis de s'en passer.
Ainsi, pour les échecs, il est exact qu'analyser toutes les parties possibles est hors de portée, mais il n'est pas nécessaire d'analyser toutes les parties possibles.
(...)

Re-,

En fait ils n'ont pas cherché la solution optimale pour chaque configuration, ils ont «juste» montré que la solution optimale prend au plus 20 mouvements. Pour une configuration s'ils trouvent disons 20 mouvements alors c'est bon même si la solution trouvée n'est pas optimale cette dernière ne peut en prendre que moins. Il existe un algorithme qui trouve la solution optimale pour n'importe quelle configuration donnée mais il est très gourmand en ressources (on paye en mémoire ce que l'on peut gagner en temps).
D'autres jeux ont été résolu comme le puissance 4 (en version originale sans règles ajoutées) pour lequel il a été montré que le premier joueur en jouant parfaitement gagne.

[JPL]

Je voulais dire "circonscrit", évidemment, mais impossible d'éditer, maintenant !

Oui mais comme ont est dans Science ludique je ne pouvais pas laisser passer ça

[invite03481543]

Salut,

je découvre tout juste cette discussion fort intéressante, avec néanmoins des affirmations plutôt curieuses.
Je ne suis pas convaincu que d'ailleurs certains comme ils le prétendent jouent vraiment au noble jeu.

Une anecdote cependant, Capablanca grand joueur, énorme joueur de son temps, "l'invincible" l'appelait-on, avait estimé qu'il fallait modifier les règles du jeu pensant que celui-ci était devenu ennuyeux, vu qu'il ne trouvait pas de joueur capable de remettre en cause sa suprématie.
C'était sans compter sur l'"artiste" Alekhine qui allait lui montrer combien il se trompait lourdement.

Les échecs c'est avant tout pour vaincre imposer sa stratégie, son rythme, sa vision, sa progression à l'autre.
L'ordinateur saura répondre par un calcul méthodique, mais le choix critique, le moment où tout bascule, où l'infime différence quasi invisible sur le moment qui va se révéler une catastrophe dans les coups suivants ne sera que le fruit d'une vision, d'une intuition géniale.
Dans ces deux mots l'ordinateur n'est pas dans son élément, car parmi les 10^100 coups ou plus possible, l'homme est capable (très peu en tout cas) de "sentir" ce moment de basculement.
Plus que de puissance de calcul, l'ordinateur manque de discernement, de "sensations", d'inconscience.
Il est capable de battre tout ceux qui pratiqueront comme lui un jeu plat et académique mais il aura toutes les peines du monde à s'imposer face à un adversaire inspiré et habité par quelque chose qui ressemble plus à du génie qu'à du calcul pur.

Un Kasparov du temps de ses débuts n'aurait jamais perdu contre un ordinateur, ce n'est que ma conviction bien sur, mais pour avoir étudié de près ses parties, je ne pense pas qu'un jour prochain un ordinateur me donne autant d'émotions que de découvrir une telle acuité, un tel talent génial.

@+

[invite03481543]

Dans le jeu d'échecs il y a quelque chose d'impalpable, d'insondable, une pure démonstration qu'il n'y a pas de vérité dans la notion de choix infaillible, le déplacement particulier du cavalier, le sacrifice possible qui déstabilise la notion de valeur, le pion et ses associations diaboliques, la promotion, tant de facteurs qui démultiplient l'arbre des possibilités et compliquent la finesse du moment du choix ultime et si fragile.
Ce jeu d'équilibristes n'est pas qu'une affaire de calculs froids et rigides, c'est la forme la plus élaborée du jeu, aussi la plus envoutante.

Je vous fait partager quelques citations de grands Maîtres que j'apprécie:

«La tactique, c'est ce que vous faites quand il y a quelque chose à faire ; la stratégie, c'est ce que vous faites quand il n'y a plus rien à faire. » »
Xavier Tartacover

« Il y a deux types de sacrifice : ceux qui sont corrects et les miens. » »
Mikhaïl Tal

«Je gagne avec les blancs car j'ai l'avantage de commencer, et je gagne avec les noirs car je m'appelle Bogolioubov. » »
Efim Bogolioubov

Bonne nuit les amis.