|
| Vers la résolution des échecs ? par ka***d*154 le
[Aller à la fin] |
| Informatique | |
Avis aux lyonnais : le 25 novembre j'animerai un séminaire "SIESTE" à l'ENS-Lyon sur la résolution des échecs.
Personnellement j'ai assez longtemps cru que ce ne serait pas possible, je suis maintenant persuadé du contraire. C'est assez contre-intuitif. On a obtenu des résultats récemment qui laisse penser que d'ici quelques années on pourra aboutir. Avec un collègue nous avons prouvé la valeur théorique des échecs sur 5x5 (pour Gardner minichess et Mallett chess qui sont respectivement nulle et mat en 25 pour les Blancs) et nous sommes en train de travailler sur le 6x6 (on enlève les fous : c'est la variante Los Alamos chess la première à avoir été implantée). Le but est de fournir un certificat mathématique vérifiable assurant la valeur théorique du jeu (résolution faible : on fournit une stratégie pour obtenir la valeur théorique, on ne résout pas fortement pour toute position légale).
|
|
|
Bonjour Kassad, qu'entends tu par résolution des échecs s'il te plait ?
|
|
|
Est-ce que ce sera consultable par la suite ?
|
|
|
Si "résoudre les échecs" c'est savoir si la position de départ est gagnante pour les Blancs, les Noirs ou si elle est nulle je mettrais ma tête au feu avec ma main à couper qu'elle est nulle, c'est à dire qu'aucun des joueurs ne peut l'emporter si son adversaire ne commet pas d'erreur.
|
|
|
Oui surement nulle, contrairement au "Puissance 4" résolu depuis un certain temps et qui permet a celui qui commence de l'emporter à tout les coups
|
|
|
Je pense aussi que c'est nulle. Le but est de donner une preuve mathématique vérifiable de ce résultat. La stratégie pour faire une telle preuve est de produire des oracles assurant la nulle pour les Blancs et pour les noirs. Partir de la position initiale est trop dur. Il faut plutôt bactracker une partie nulle en démontrant que la position finale est nulle puis on remonte d'un coup en arrière en prouvant que la nouvelle position est nulle (en s'aidant de ce qu'on a déjà démontré) etc. De bonnes parties candidates pour cela serait des parties de GM ou bien de TCEC qu'on pourrait formellement prouver comme nulles. Déjà donner une preuve formelle d'une nulle par accord mutuel (avec une position de plus de 7 pièces sinon on n'a qu'à utiliser les tablebase de Lomonosov) serait un beau résultat.
|
|
|
Et si la position n'était pas équilibrée au départ, les échecs ne seraient plus un sport.
|
|
|
Le puissance 4 standard sur la grille 7x6 j'aurais spontanément plutôt pensé que ça tend vers la nulle. Ceci dit je n'en ai pas concédé beaucoup avec le trait, mais de là à forcer les événements quoiqu'il arrive je n'aurais pas cru.
|
|
|
Deux remarques:
1. pour l'instant je n'y crois pas du tout. Passer de 5 x 5 (félicitations au passage) à 6 x 6 est sûrement déjà du boulot, mais à 8 x 8 c'est le grand écart. Le nombre de coups possibles à chaque tour grandit énormément. Même en analyse rétrograde (backtrackant ?) puisqu'à un moment où un autre il faudra bien revenir jusqu'à l'ouverture puis la position initiale;
2. en revanche construire un oracle pour des positions à nombre limité de pièce est probablement passionnant. Quelle type de position privilégier ? Nulle de grand maître ? Une position avec roi et pions uniquement (les pions ne reculent pas) où on montrerait qu'on peut empêcher l'adversaire de faire dame - ce qui est presqu'équivalent à la nulle ?
|
|
|
J'ai l'impression que certains ont oublié l'anecdote des grains de blé !
|
|
|
Pour Dan31 : c'est très étonnant en effet. Quand j'ai commencé cette recherche je ne croyais même pas que le 5x5 soit faisable.
Bien sûr revenir jusqu'au coup 1 demandera du boulot mais ça ne me paraît pas si irréaliste au vu des expérimentations qu'on a déjà menées. On a déjà produis des oracles de taille acceptable pour des finales nulles type Roi deux pions contre Roi et pion (en mettant une position nulle).
En fait notre approche est complètement différente des tablebases dont 99,99999% (je dis ça au pif mais c'est pour donner l'idée) ne sert à rien vis-à-vis du jeu idéal. En effet, savoir qu'il y a mat en 27 coup pour Roi deux Fous + Cavalier contre Roi Fou n'a juste aucun intérêt pratique car une partie parfaite sera décidée bien avant et n'arrivera jamais à cette configuration. Je ne parle même pas des positions avec 3 fous de cases noires etc.
Effectivement le but est plutot de prouver une fin de partie style TCEC où les deux machines ont évolué à 0.00 d'éval pendant 6 plies avec assez de pièces pour que ce ne soit pas dans une tablebase (avec Lomonosov on est à 7 pièces donc au moins 8 pièces pour commencer).
Pour ANaigeon : le fait qu'il y ait 10^120 parties possibles ou 10^43 positions légales n'est pas suffisant comme argument pour dire que c'est impossible. Le meilleur contre exemple est le jeu Hex dont on peut prouver en deux lignes que le joueur qui commence gagne, par vol de stratégie, et pourtant en prenant un plateau de taille 100*100 on a au moins 2^9801 positions légales au minimum en remplissant comme on veut sans toucher les bords. On est donc loin des 2^64 des grains de blé et pourtant on peut décider le jeu.
Il se trouve que l'énorme majorité des parties d'échecs ne sont pas parfaites (je veux dire théoriquement car pratiquement on le sait depuis longtemps :) ). Or ce ne sont que celles qui sont intéressantes pour décider de la valeur du jeu. Et il n'est pas du tout clair que ce soit irréalisable. De plus même en jouant parfaitement ce n'est pas la peine de considérer toutes les parties parfaites : juste un chemin suffit. Typiquement quand on a une dame de plus il y des milliards de manières de gagner la partie : d'un point de vue théorique on s'en fout, on en veut juste une. Ca fait partie de notre étude de justement montrer que les moteurs sont trop "perfectionnistes" et passent trop de temps à se prendre le cpu pour savoir s'il faut mieux jouer Cf3+ ou Fb7 quand ils sont à +6 alors qu'à peu près n'importe quel coup les laisse gagnant (on peut donc sauver du temps en jouant le premier coup "correct" qu'on trouve).
|
|
|
Juste un commentaire... on peut avoir une dame de plus et une position perdante. Et les évaluations fausses des modules, cela existe aussi...
|
|
|
Il y a un grand nombre de positions qui ne peuvent être évaluées par les simples critères matériels. D'ailleurs c'est le problème des ordinateurs les plus puissants qui, sans les tables Nalimov, tournent éternellement en rond en indiquant toujours des avantages importants alors que la positon est totalement nulle.
|
|
|
@ kassad : tu as un preprint ou une publi que l'on puisse lire?
|
|
|
pour Maelbreizh: un preprint de l'article est là (il y a quelques coquilles dans les oracles qui ont été corrigé pour l'article ICGA) http://arxiv-web3.library.cornell.edu/pdf/1307.7118v1.pdf
Pour Chemtov: justement nous cherchons à produire une preuve mathématique qui ne dépend pas de l'évaluation d'un certain logiciel sur un certain matériel. Le certificat est un oracle qu'on peut simplement voir comme une liste de positions assorties d'un coup (celui qu'il faut jouer quand on est dans cette position). Si l'oracle a une bonne topologie (il est clos et les feuilles sont des mats ou par absence de matériel suffisant ou pat) alors on a une preuve que les blancs font nulle (on peut faire pareille du côté noir et on conclue à la nulle). Tout le truc est d'aider la construction de l'oracle car justement les ordis cherchent par défaut à optimiser une valeur (et donc choisissent un +0,34 à un +0,12 alors que cette dernière peut conduire à une nulle plus facile à produire).
Pour Flytox : bien sûr :) on peut toujours trouver des contre exemples (d'ailleurs on a trouvé des bug de stockfish en faisant nos expériences ou des positions à +5 étaient clairement nulle). Mais ce n'est pas si courant d'une part et d'autre part je n'ai jamais vu de position évalué à +1 et perdante (faut quand même se faire à l'idée que Stockfish tourne à plus de 3000 élos même sur un ordi portable)... Or on cherche juste à prouver la nulle donc une évaluation positive laisse une marge.
|
|
|
"d'autre part je n'ai jamais vu de position évalué à +1 et perdante" là il me paraît dangereux de s'aventurer sur ce terrain.
En échecs 5 X 5 c'est peut-être (sûrement ?) vrai, en échecs classique, utiliser ce principe pour montrer qu'une position est nulle me semble très optimiste. N'y a-t-il pas eu des exemples récents sur TCEC ? Et puis tout dépend de la profondeur de la recherche de Stockfish !
|
|
|
C'est pour ça que la preuve ne se base pas là dessus... :) Ca reste une très bonne approximation.
|
|
|
Il me semble que Vasik Rajlich, le créateur de Rybka avait fait une blague du 1er avril sur ce thème en affirmant avoir résolu le gambit du roi...
La méthodologie avancée était à peu prés la même
|
|
|
ref Flytox
je me souviens aussi que de nombreux sites forums d'échecs avaient repris cette information pour argent comptant, et de longues dissertations ont été écrites pour savoir quelles autres ouvertures allaient suivre !
il faut dire que la blague de Raijich etait tres bien construite, car il avait su envelopper son idée par de nombreux arguments "informatiques" et "technique de programmation" , tout en precisant que le gambit roi était l'ouverture idéale pour reussir cet exploit...
il aura fallu attendre plusiuers jours avant que beaucoup commencent à comprendre qu'il s'agissait d"une blague de premier avril ...( il avait posté sa blague fin mai...)
|
|
|
--> kassad
"Pour ANaigeon : le fait qu'il y ait 10^120 parties possibles ou 10^43 positions légales n'est pas suffisant comme argument pour dire que c'est impossible. Le meilleur contre exemple est le jeu Hex dont on peut prouver en deux lignes que le joueur qui commence gagne, par vol de stratégie, et pourtant en prenant un plateau de taille 100*100 on a au moins 2^9801 positions légales au minimum en remplissant comme on veut sans toucher les bords. On est donc loin des 2^64 des grains de blé et pourtant on peut décider le jeu.
Il se trouve que l'énorme majorité des parties d'échecs ne sont pas parfaites (je veux dire théoriquement car pratiquement on le sait depuis longtemps :) ). Or ce ne sont que celles qui sont intéressantes pour décider de la valeur du jeu. Et il n'est pas du tout clair que ce soit irréalisable. De plus même en jouant parfaitement ce n'est pas la peine de considérer toutes les parties parfaites : juste un chemin suffit. Typiquement quand on a une dame de plus il y des milliards de manières de gagner la partie : d'un point de vue théorique on s'en fout, on en veut juste une. Ca fait partie de notre étude de justement montrer que les moteurs sont trop "perfectionnistes" et passent trop de temps à se prendre le cpu pour savoir s'il faut mieux jouer Cf3+ ou Fb7 quand ils sont à +6 alors qu'à peu près n'importe quel coup les laisse gagnant (on peut donc sauver du temps en jouant le premier coup "correct" qu'on trouve).
"
Je commence par réagir à ton deuxième paragraphe, celui juste au-dessus : l'ayant lu, je ne sais plus du tout ce qu'il faut entendre par "résoudre les échecs" ; cette expression avait une allure très ambitieuse et rigoureuse, que tes propos démentent.
Ton premier paragraphe contient une objection recevable. Néanmoins ce premier paragraphe contredit le second, car il place la barre vraiment très haut !! Tu sembles dire qu'un "raisonnement" permettrait de "court-circuiter" le nombre explosif de coups à examiner. Cela, si c'était possible, oui, je l'appellerais volontiers "résoudre les échecs".
Mais vois la complexité incroyable du jeu : chaque pièce a une marche différente, les pions ne prennent pas comme ils avancent, et ne reculent pas, les cavaliers changent de couleur à chaque coup, au contraire des fous, le roque, facultatif, mais sujet à des interdictions, etc.
Or certains problèmes mathématiques infiniment plus simples ont résisté aux plus brillants cerveaux depuis des décennies (cf la suite de Syracuse, par exemple)...
On peut imaginer, d'ailleurs, un autre projet qui consisterait à vouloir démontrer que le jeu n'a *pas* de solution, au sens rigoureux donné ci-dessus, autrement dit que chercher un raisonnement pour le résoudre serait aussi complexe que l'inventaire explicite de tous les coups possibles (des théorèmes de ce type existent en mathématiques).
La dernière possibilité serait que la proposition est indécidable - cela existe aussi !
édité, car j'oubliais ceci : pourquoi ne pas imaginer que le jeu soit décidable après 1 e4, mais indécidable après 1 a4, ou que sais-je encore. Non, vraiment, en parlant de quelques années, et avec des moyens mathématiques élementaires, je crois vraiment que tu rêves.
Regarde la démonstration par Wiles du apparemment tout bête théorème de Fermat ; elle comporte des dizaines de pages, et dis-moi si tu n'es pas largué, comme moi, à la deuxième ligne de la première page !!
|
|
|
indécidable ???
cela existe en maths, mais pas pour un problème fini!!? ou alors j'ai rien compris à ce qu'était l'indécidabilité...
moi je suis vraiment séduit par la démarche, et déjà impressionné par les résultats en 5*5 ... mais du coup je trouve ça un peu déprimant, j'espère que Kassad va prendre son temps et qu'on ne connaîtra pas la résolution avant longtemps (ce qui est très probable) mais je sens que nos petits enfants la connaîtront peut être!
|
|
|
je ne comprends même pas le débat, tout le monde sait depuis longtemps que 1.e4 , c'est 1-0 sur le meilleur jeu des blancs !
Plus sérieusement, a partir du moment où le nombre de parties d'échecs possible n'est pas infini, il est a priori passible d'être résolu, y compris virtuellement à la main (même si ça devait prendre des trilliards d'années...).
Pour moi, la seule question, c'est quand.
Et là, entre la complexité (et la grandeur!) de calculer le nombre de parties, et l'évolution imprévisible de la technologie...
Cette dernière a déjà en 35 ans connu une croissance productive incroyable (que ce sooit au niveau des processeurs, des capacités de mémoire, des rapidités des bus conducteurs et tout ce que vous voulez).
Non seulement, celle ci peut se poursuivre, mais en plus, j'ai lu (il y a déjà fort longtemps!)dans pour la science ou la recherche (un des 2 je sais plus), qu'on avait désormais la technologie pour développer des composants électroniques qui ne fonctionneraient plus en binaire, mais en base 4 !
La transition serait complexe, en tout cas nécessiterait un investissement pour l'instant trop vaste pour que le libéralisme permette à ce progrès de se développer, mais du jour où elle se développera, les capacités électroniques s'accroitront brutalement de manière exponentielle !
Alors les échecs résolus : peut-être demain, peut être plus tard, mais un jour c'est sûr, juste pas prévisible :)
|
|
|
Pour mémoire, le jeu de dames anglaises (checkers) qui se joue sur un plateau 8x8 a été résolu en 2007 : partie nulle.
@kassad
Quel est la facteur approximatif de complexité entre 5x5 et 6x6 ? Autrement dit combien faut-il d'augmentation de la puissance de calcul (ou de temps, ce qui revient au même) pour résoudre 6x6 ? et pour 8x8 ? et pour 10x8 (variante Capablanca) ?
|
|
|
mouis enfin aux dames anglaises, il n'y a que 12 pions chacun qui ne peuvent ni aller ni prendre en arrière, tu ne joues que sur 32 cases, les dames ne peuvent pas suivre de longues diagonales, ...
Bref, la construction d'un oracle est grandement facilitée. Aux échecs tu as le phénomène de shuffling, spécialité des logiciels dans les positions où la progression est difficile, tu peux bouger les pièces sans motif apparent pendant 100 coups et apparemment sans évolution mais en fait avec des espèces de zugwang quasi indécelable pour l'humain cachés là-dedans (on pense au fameux mat en 500 et quelques coups découvert par les tablebase).
Bref, personnellement je souhaite bon courage à kassad mais j'ai du mal à y croire. Ce qui me semblerait en revanche quasiment faisable, ce serait de tenter de programmer un très fort logiciel dans le but qu'il ne perde jamais, une espèce de preuve par l'exemple : un Stockfish avec une bibliothèque d'ouverture béton et sans aucun risque, qui cherche à simplifier à fond vers une position nulle (on pourrait donner à la partie nulle une valeur très élevée, comme on fait pour le roi).
Mais hélas les programmeurs préfèrent dire qu'ils ont le programme qui a le meilleur elo plutôt que celui qui fait beaucoup de nulles mais joue un jeu parfait et est imbattable.
|
|
|
pour ANaigeon :
Un jeu est dit résolu si à partir de toute situation on peut prédire le résultat final dans le cas où les deux joueurs jouent de façon parfaite.
Un jeu est dit résolu faiblement, si on est capable de réaliser une partie où les deux joueurs jouent de façon parfaite depuis la position de départ jusqu'à une position de nulle ou de gain.
On trouve parfois la mention de résolution ultra faible si on est capable de dire qui l'emporte ou si la partie est nulle sur un jeu parfait sans toutefois forcément produire de partie.
Par exemple le morpion 3 X 3 est résolu ainsi que le puissance 4, mais le jeu de dames anglaises est seulement résolu faiblement si je ne m'abuse
|
|
|
Donne déjà une définition rigoureuse de "jouent de façon parfaite", sachant qu'une éventuelle "imperfection" pourrait ne manifester ses effets (càd être reconnue imparfaite) qu'à la toute fin de la partie --> on tourne en rond : à chaque choix de coup, en cours d'analyse, il faut trouver le coup qui, parmi d'autres, donnera le meiller résultat en fin d'analyse (sinon il n'est pas parfait).
Le serpent se mort la queue.
--> sumotori : un programme informatique est constitué d'un nombre fini d'instructions. Or il est impossible de *prouver* qu'il ne va pas boucler indéfiniment sans aboutir à un résultat ("problème de l'arrêt", son indécidabilité fut prouvée en 1936 par Turing)
|
|
|
@dan31
Le jeu de dames anglaises (checkers) est en effet résolu faiblement. L'article de la revue "Science" exposant ladite résolution "faible" des dames anglaises est disponible sur le net : http://www.sciencemag.org/content/317/5844/1518.abstract
Il faut s'inscrire pour y accéder mais c'est gratuit.
|
|
|
re ANaigeon,
dans l'exemple que tu donnes la boucle peut etre infinie, mais pas dans le cas de la partie d'echecs, Il y a un nombre finie de partie, donc le problème est forcément "décidable"...comme dit kaktus, il suffirait de les écrire toutes pour le prouver! non?
|
|
|
Il me semble que d'un point de vue mathématique, « jouer parfaitement » est défini rigoureusement depuis longtemps : c'est jouer un coup qui ne modifie pas le statut (gain, nulle, perte) de la position.
Par contre, s'il est évident que produire un oracle ne nécessite l'exploration que d'une infime partie de l'arbre, j'ai l'impression que cette infime partie reste… énorme.
Intuitivement, j'aurais dit que la taille de l'oracle (la partie explorée) est de l'ordre de la racine carrée de la taille de l'arbre. Me trompé-je ?
|
|
|
Pour Bellamy : la réduction est bien plus importante. Déjà expérimentalement pour les oracles pour le 5x5 ça tient sur une dizaine de pages alors que le nombre de positions légales est 9x10^18 (en ce sens c'est quasi la même chose que les dames sur 8x8 qui font 10^20).
D'autre part on peut prendre le contre exemple suivant : les noirs et les blancs ont les pions imbriqués sur la 4ème et 5ème (donc a4,b5,c4,d5,e4 ... pour les blancs et a5,b6,c5,d6 etc. pour les noirs), les noirs ont juste le roi et les blancs ont roi +2 tours. La position est nulle, mais à partir de cette position on a au moins 24*23*22*16*2 positions atteignable (sans compter si les blancs et noirs jouent n'imp du style poser une tour en b4 et que les noirs prennent en b4 etc.). Or on peut prouver la nulle en explorant simplement 2*16*2 : c'est à dire les blancs font des aller retour avec le roi (le premier 2), si je construis un oracle noir je dois regarder tout ce que les noirs peuvent faire (donc parcourir leur espace avec le roi le 16) et pour chaque position le trait peut etre au noir ou au blanc (le deuxième 2). Or en faisant des aller retour avec le roi blanc je vais prouver la nulle par répétition ou 50 coups sans prise ni mouvement de pion. Donc c'est du 510048 contre 64. Et encore je suis large car je ne considère même pas les parties où les deux pêtent les plombs (à partir d'une telle position initiale on peut se retrouver, si les joueurs coopèrent avec 3 fous contre 5 cavaliers)...
Pour Dan31: il ne faut pas oublier que quand on construit un oracle pour blanc, alors si on est obligé de voir tout ce que noir peut faire on peut se limiter les options en tant que blanc (ce dont je parlais pour Bellamy typiquement). D'autre part si les noirs font n'imp... ils se font mater rapidement et les branches se coupent d'elles mêmes.
Programmer un ordi qui ne perde jamais est sûrement faisable dès à présent... Mais ce n'est pas si simple car la tendance naturelle est de maximiser une fonction et maximiser la nulle c'est pas très clair. Cependant on a bidouillé Stockfish pour nos expériences justement pour qu'il soit plus "nullifiant" (mais ce n'est pas suffisant on veut qu'il trouve des nulles rapidement et économiquement).
Concernant l'évolution de la taille c'est pas encore très clair (on cherche à automatiser ce qu'on a fait à la main pour Gardner mais suivant les heuristiques choisies les tailles d'oracles bougent encore trop). Sinon je pense que c'est nulle à 99,99% sur 6x6 (au début on pensait gain blanc ! mais en affinant on est tombé sur des nulles qui tiennent à un cheveux). En fait on a une partie parfaite assez bien explorée (mais avec un jugement "humain" aux feuilles ce n'est pas une preuve formelle tout comme une démonstration de math qui ne remonterait pas jusqu'au axiome de ZFC+choix).
|
|
|
@ANaigeon : le jeu parfait est comme le dit Bellamy très bien défini (ce qui ne signifie qu'on sache facilement dire si tel ou tel coup est parfait) pour un jeu fini comme les échecs : on peut montrer que chaque position a une valeur théorique donnée (1-0 , nulle ou 0-1). On ne peut pas forcément la calculer (sauf cas simple comme R+D contre R ou tablebase ou autres) mais on sait qu'elle existe. Le jeu parfait est constitué d'une suite de coups parfaits c'est-à-dire dont aucun ne fait varier la valeur théorique de la nouvelle position par rapport à la valeur de l'ancienne position.
Evidemment la difficulté apparente est que la valeur théorique d'une position semble déterminée à partir de la notion de jeu parfait et vice-versa. Mais si on se plonge un peu dans le problème, on voit que ça ne génère pas de contradiction. Un peu long toutefois à exposer ici. Cependant on le comprend bien intuitivement en partant des positions finales et en remontant en arrière. Partons d'un mat. Un jeu parfait en remontant d'un demi-coup est n'importe quel coup qui donne ce mat. En remontant encore d'un demi-coup, un jeu parfait pour le perdant doit aboutir forcément à une position perdante (sinon il s'est fait mater alors qu'il aurait pu faire nulle ou gagner) , ...)
|
|
|
ou alors on ajoute une autre condition, le coup qui gagne le plus vite possible, ou le coup qui résiste le plus longtemps possible dans une position perdante;
avec ta définition on pourrait se retrouver dans un paradoxe, être gagnant mais ne jamais gagner.
|
|
|
pas vraiment : puisque le jeu est fini, même en jouant les plus mauvais coup pour lesquels la position reste gagnante, on finit par gagner (on part du principe que répéter 3 fois la même position = nulle automatique sans appel à l'arbitre).
|
|
|
