Bonjour,
un petit journal pour faire la pub d'un article dont je suis co-auteur concernant la résolution éventuelle du jeu d'échecs, et susceptible d'intéresser 1 quelques lecteurs. Par "résolution", on veut dire déterminer, en supposant que les deux joueurs jouent parfaitement, si la partie se termine par une victoire de Blanc, de Noir, ou un match nul.
Il ne s'agit évidemment pas de mener à bien une telle résolution par des moyens manuels, le jeu est trop complexe pour cela, mais d'évaluer la faisabilité de la chose si l'on recourt à l'assistance des ordinateurs2. L'idée peut être perturbante pour certains joueurs d'échecs : déjà que les ordinateurs ont dépassé les meilleurs joueurs humains, si en plus il existait un programme absolument imbattable, le jeu ne perdrait-il pas de sa saveur ?
Heureusement pour eux, Claude Shannon avait écrit, en 1950, un fameux article à même de les rassurer : la complexité du jeu d'échecs est telle que même l'utilisation des ordinateurs ne permettra jamais de résoudre le jeu, c'est tout du moins l'idée la plus répandue chez les spécialistes depuis lors. Shannon avait en effet évalué à 10120 le nombre de parties différentes, et à 1043 le nombre de positions différentes3, deux nombres effrayants et hors de portée de nos machines (que ce soit en temps ou en espace) pour un bon bout de temps.
Or, dans cet article, on explique que le bon nombre à considérer pour évaluer si la résolution d'un jeu est à notre portée n'est pas le nombre de positions différentes, mais plutôt la racine carrée de ce nombre. Dans le cas des échecs, ça donne un nombre de l'ordre de 1020 , dont nous ne sommes plus si loin : en 2007, le jeu des dames anglaises a été résolu avec une quantité de calculs de l'ordre de 1014 . Aussi, plutôt que "si on pourra un jour résoudre le jeu d'échecs", on peut se demander "quand le jeu d'échecs sera résolu". Dans l'article, on donne l'estimation d'une vingtaine d'années encore nécessaires… mais il est possible que ce soit moins.
L'article est téléchargeable à cette adresse sous licence CC BY-ND. Il explique les rudiments des techniques utilisées pour résoudre informatiquement les jeux combinatoires, et ne contient pas de calculs trop compliqués, aussi il est accessible au plus grand nombre, n'hésitez pas à le lire si le sujet vous intéresse.
# c'est le goût
Posté par matthieu bollot (site web personnel, Mastodon) . Évalué à -9.
Je croyais que c'était la circonférence de ce nombre le plus important…
--> []
# Blanc ou nul
Posté par 🚲 Tanguy Ortolo (site web personnel) . Évalué à 4.
Si les deux jouent parfaitement, et si on entend pas là que les deux sont capables d'analyser toutes les possibilités, je dirais que c'est forcément Blanc qui gagne, puisque c'est lui qui commence : il jouera forcément un coup qui lui permet de gagner. Ou alors, c'est peut-être nul, mais dans tous les cas, toutes les parties devraient être identiques !
[^] # Re: Blanc ou nul
Posté par sn00py . Évalué à 10.
Je te propose un jeu: chacun à son tour donne un chiffre positif (donc entre 1 et 9). On additionne chaque chiffre donné. Le premier qui annonce un chiffre qui mènera la somme à exactement 10 a gagné.
Il n'y a aucune raison de croire que, dans un jeu résolu, ce soit toujours le 1er qui gagne. C'est peut-être toujours le second !
[^] # Re: Blanc ou nul
Posté par 🚲 Tanguy Ortolo (site web personnel) . Évalué à 10.
Excellent contre-exemple, merci !
[^] # Re: Blanc ou nul
Posté par reynum (site web personnel) . Évalué à 2.
Désolé mais je n'arrive pas à voir le rapport entre le jeu d'échecs et ton jeu dans lequel le second gagne forcément.
kentoc'h mervel eget bezan saotred
[^] # Re: Blanc ou nul
Posté par Guillaume Rossignol . Évalué à 5.
L'exemple illustre qu'il y a des jeux où le premier coup ne permet pas forcement de gagner et où si le deuxieme joueur choisit bien, il gagne forcement. Et les jeux d'échecs font peut être parti de ces jeux là.
[^] # Re: Blanc ou nul
Posté par 2PetitsVerres . Évalué à 2.
Le second ne gagne pas forcément. Il gagne forcément s'il applique une stratégie optimale, mais si ce n'est pas le cas, il peut perdre. Par exemple:
Dans cette partie, c'est bien A qui gagne.
Mais comme tu l'as vu, il existe effectivement une stratégie optimale qui permet à B de gagner à tous les coups (jouer 10 - le premier coup de A.) Et ce que le journal appelle "résolution du jeu d'échec", c'est en fait de trouver la stratégie optimale pour blanc ou noir, celle qui lui permet de gagner (ou de faire match nul) à tous les coups.
Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.
[^] # Re: Blanc ou nul
Posté par 🚲 Tanguy Ortolo (site web personnel) . Évalué à 5.
Certes, mais on parlait justement de joueurs jouant parfaitement.
[^] # Re: Blanc ou nul
Posté par RenardBleu . Évalué à 0.
Très bon exemple :)
La plupart des forts joueurs (au delà de 2300 ELO) considèrent (admettons que leur connaissance avancée du jeu leur confère un peu plus de légitimité -très- supposée) que la (probablement les) partie parfaite amène à la nulle (ou peut-être au gain de Blanc).
[^] # Re: Blanc ou nul
Posté par 🚲 Tanguy Ortolo (site web personnel) . Évalué à 4.
Un nul aux échecs, c'est un pat, c'est bien ça ?
[^] # Re: Blanc ou nul
Posté par RenardBleu . Évalué à 3. Dernière modification le 23 juillet 2015 à 15:04.
Non c'est l'inverse ;)
pat est un cas de partie nulle. Tu peux avoir une nulle par accord (ce qui ne concerne pas notre cas présent) ou la répétition de coups (3 fois la même position dans une partie donne lieu à une nulle) ou un matériel insuffisant pour matter (exemple 2 rois + un fou)…
[^] # Re: Blanc ou nul
Posté par bobble bubble . Évalué à -1.
ce n'est pas plutôt la réciproque ?
[^] # Re: Blanc ou nul
Posté par reynum (site web personnel) . Évalué à 4.
Non c'est l'inverse, et réciproquement :-D
kentoc'h mervel eget bezan saotred
[^] # Re: Blanc ou nul
Posté par palm123 (site web personnel) . Évalué à 2.
Il faut s'entendre sur "toutes les possibilités"
Non, il faut seulement analyser les coups raisonnables, ceux qui perdent du matériel ou n'ont aucun but, ne rentrent dans aucun plan, sont exclus. On se retrouve avec beaucoup moins de coups à analyser. Exemple : quand les blancs attaquent sur l'aile roi pour mater ou au moins gagner du matériel, les coups servant à recaser du matériel vers la case a1 ne rentrent pas dans le plan.
ウィズコロナ
[^] # Re: Blanc ou nul
Posté par Lapinot (site web personnel) . Évalué à 2.
Un petit bémol : quand on s'intéresse à la résolution du jeu, il faut être sûr à 100% qu'un coup est inutile avant de le laisser tomber. On ne peut donc pas éliminer un coup, même absurde, comme "recaser du matériel vers la case a1", à moins d'avoir une démonstration irréfutable de son inutilité.
Ceci étant, voici un exemple montrant qu'il n'est, comme tu le remarques, pas utile d'analyser "toutes les possibilités" : dans un problème comme "les blancs jouent et matent en un coup", tout coup de blanc qui ne mate pas est une possibilité qu'il n'est pas nécessaire d'analyser.
[^] # Re: Blanc ou nul
Posté par palm123 (site web personnel) . Évalué à 5.
C'est le thème de nombreuses études, c'est l'exception qui confirme la règle, le coup gagnant semble idiot, improbable ou absurde, comme dans l'étude de Mitrofanov,
https://en.wikipedia.org/wiki/Leopold_Mitrofanov
http://timkr.home.xs4all.nl/chess2/mitrofanov.htm
https://www.youtube.com/watch?v=2vgIQikkoKQ
Oui, sur une attaque sur l'aile-roi, un coup comme a3 a4 permettra Fc1 a3 qui va contrôler les cases e7 et f8 de sortie du roi, et un coup comme Te1 a1; à priori sans sens, pourrait libérer cette case pour un cavalier, sur le chemin de l'aile-roi…
On se comprend
ウィズコロナ
[^] # Re: Blanc ou nul
Posté par ®om (site web personnel) . Évalué à 10.
https://fr.wikipedia.org/wiki/L%27exception_qui_confirme_la_r%C3%A8gle
blog.rom1v.com
[^] # Re: Blanc ou nul
Posté par Faya . Évalué à 7.
On a beau dire, il y a toujours quelque chose à apprendre sur DLFP … Merci !
[^] # Re: Blanc ou nul
Posté par RenardBleu . Évalué à 1.
Il se trouve déjà des parties qui sont des contre exemples. Evidemment, je ne retrouve pas là de suite celle à laquelle je pense en particulier et il s'agit de tout sauf d'une partie parfaite puisque un des joueurs étaient Mikhael Tal. Sur une de ses parties, notre cher monsieur alors en plein attaque (comprendre "encore une fois en ayant vaillament sacrifier une ou plusieurs pièces) sur l'aile roi joue un coup du style Txa1 ou b2 où (de mémoire) il reprend un cavalier qui n'avait rien à voir avec l'attaque en cours. Je n'ai jamais trop bien compris ce coup mais pour moi une chose est sûre Tal ne l'aurait jamais joué s'il n'était pas nécessaire (selon son analyse…)
(Il a été démontré à de nombreuses reprises avec l'aide de logiciels que le parties de Tal n'étaient pas "justes" ou "exactes")
De la même manière, une célèbre partie a vu un ancien champion du monde baptiser un Ch1 (ou h8 s'il avait les noirs) meilleur coup du monde (je ne suis plus certain de l'expression mais c'est l'idée). Il soulignait le fait que le redéploiement du cavalier qui lui a pris 5 ou 6 coups commençait par un coup assez inattendu (ou non raisonnable pour prendre ton vocabulaire).
Enfin si ton raisonnement est probablement valable pour pas mal de cas, cela reste fortement lié à une situation plutôt déséquilibrée (forte attaque) hors de nos jours (et malheureusement à mon sens) la plupart des parties de championnat du monde tendent plus sur des exploitations de failles positionnelles et dans ce genre de cas, bonne chance pour distinguer les coups raisonnables des coups non raisonnables.
[^] # Re: Blanc ou nul
Posté par palm123 (site web personnel) . Évalué à 2.
Ah celui-là… Il mettait plusieurs pièces en prises, en expliquant (fort justement) que l'adversaire ne peut en prendre qu'une à la fois ! Par exemple son sacrifice de cavalier du 16 ème coup contre Larsen (tournoi des candidats de 1965) a été analysé plusieurs mois avant de trouver la meilleure réponse des noirs
http://www.chessgames.com/perl/chessgame?gid=1139729
https://www.youtube.com/watch?v=aFHgrDS8m30
Je me demande comment sont évalués, dans sa victoire contre Smyslov en 1959, ses coups très modestes contre la Caro-Kahn 2 d3 (sortant de la théorie) et 5 d4 (on a donc perdu un temps, avec les blancs, dans le début de partie, vu qu'on aurait pu mettre le pion en d4 en un seul coup. Les théoriciens vont dire que c'est le drame)
http://www.chessgames.com/perl/chessgame?gid=1139475
ウィズコロナ
[^] # Re: Blanc ou nul
Posté par Spyhawk . Évalué à 2.
Tu ne ferais pas référence à Josh Waitzkin? J'ai du lire ça dans un des bouquins qu'il a publié (et qui ne concerne pas que les échecs).
L'idée est que le cavalier est plus puissant au centre de l'échiquier, et le plus inadéquat dans les coins… à un point que son adversaire n'a jamais considéré cette possibilité et lui a permit de se retourner une situation délicate.
# Alpha constant ?
Posté par NicolasP . Évalué à 2.
Dans le chapitre Estimation des ressources requises, qu'est-ce qui permet de dire que
est une constante ? Pourquoi ça ne serait pas une fonction de (n,p) ? 
dépend de n et p.
Intuitivement, plus il y a de fils (n), plus il est difficile de "deviner" le bon fils à explorer. De même, plus il y a de coups à jouer (p), moins la fonction de prédiction est fiable. Ça signifierait que
[^] # Re: Alpha constant ?
Posté par Lapinot (site web personnel) . Évalué à 6.
Question intéressante… α, comme tu l'as remarqué, traduit la qualité de la fonction de prédiction. Elle est considérée comme étant une constante, car c'est ainsi que ce problème a été modélisé. Mais on peut en effet imaginer faire dépendre α de n ou de p, ou même d'autres paramètres. L'important, si on veut établir une modélisation plus précise, est d'une part de réussir à mener à bien les calculs que donne cette modélisation (ce qui est généralement possible, au moins numériquement), et d'autre part, de faire une modélisation de α qui soit plus pertinente, ce qui là, n'est pas si évident.
Car quand tu dis "plus il y a de fils (n), plus il est difficile de "deviner" le bon fils à explorer", tu oublies que plus il y a de fils, plus il y a de fils perdants (ceux qu'il est valide d'explorer) : il n'y a pas forcément un unique "bon fils". De même, la qualité de la fonction de prédiction n'est pas forcément liée à p, certaines positions avec de nombreux coups à jouer sont plus lisibles que d'autres positions de fin de partie.
Il est quoi qu'il en soit difficile d'imaginer ce que sera la performance d'un programme qui n'a pas encore été écrit, et donc d'estimer α.
# l'infini est demain
Posté par Guillaume T . Évalué à 1.
Il y a 1 milliard de milliard de milliard de milliard fois moins d'atomes dans l'univers que de parties d’échecs possibles…
Dit autrement, le jour où quelqu'un sera capable de "résoudre" le jeu d'échec, je suppose qu'il ne restera que peu de "saveurs" pour bien peu de choses
[^] # Re: l'infini est demain
Posté par Xavier Verne (site web personnel) . Évalué à 2.
Pas de pessimisme ! Le jeu d'échecs est l'archétype de ce qu'un ordinateur sait calculer… Même s'il est résolu un jour, il restera de la saveur comme tu dis sur tout le reste. Penses au test de Turing, à la saveur d'un bon café. A une franche rigolade !??
[^] # Re: l'infini est demain
Posté par 2PetitsVerres . Évalué à 7.
Je ne vois pas bien le rapport entre une partie d'échec possible et un atome. Si on voulait comparer quelque chose du style, je pense qu'il faudrait comparer une partie d'échec possible à une façon possible de l'évolution de la configuration de tous les atomes de l'univers, du début à la fin (s'il y en a une, de fin.)
Et là je crois qu'il y a beaucoup plus de possibilités que de parties d'échec possibles.
Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.
[^] # Re: l'infini est demain
Posté par khivapia . Évalué à 3.
Je ne vois pas bien le rapport entre une partie d'échec possible et un atome.
S'il faut que tous les atomes de l'univers changent au moins d'un état d'énergie pour calculer une partie d'échec, alors il n'y a sans doute pas assez d'énergie dans l'univers entier pour les calculer toutes.
Par contre peut-être qu'en élaguant l'arbre des parties pour ne conserver que les coups "intéressants" (à prouver qu'ils le soient) on aurait besoin de moins d'énergie pour "résoudre" le problème d'une stratégie optimale.
[^] # Re: l'infini est demain
Posté par RenardBleu . Évalué à 0.
J'ai déjà lu cette évaluation que je n'ai jamais comprise…
Tu aurais un lien qui indique comment elle a été faite stp ?
[^] # Re: l'infini est demain
Posté par kna . Évalué à 1.
https://fr.wikipedia.org/wiki/Univers_observable#Masse
[^] # Re: l'infini est demain
Posté par Benoît Sibaud (site web personnel) . Évalué à 6.
Après il faudra résoudre la variante avec Tempête sur l'échiquier. Et encore ensuite, il restera le jeu de Go. Et si ça ne suffit toujours pas, il faudra résoudre le jeu de la vie pour trouver la vie la plus optimalement optimale.
[^] # Re: l'infini est demain
Posté par Le Pnume . Évalué à 2.
"Tempête sur l’échiquier" n'est qu'une possibilité des échecs féeriques (https://fr.wikipedia.org/wiki/%C3%89checs_f%C3%A9eriques). Il reste donc pas mal de boulot.
Pour les amateurs de SF et d'échecs (féerique), je ne saurait trop conseiller "l’échiquier fabuleux" de Lewis Padgett
[^] # Re: l'infini est demain
Posté par Yannick (site web personnel) . Évalué à 1.
Parce que c'est possible de résoudre un jeu qui contient de l'aléatoire ?
[^] # Re: l'infini est demain
Posté par Thomas Douillard . Évalué à 2.
Il me semble que le Poker a été résolu, plus ou moins : http://www.pourlascience.fr/ewb_pages/a/article-comment-jouer-parfaitement-au-poker-35430.php
[^] # Re: l'infini est demain
Posté par chimrod (site web personnel) . Évalué à 2.
L'article n'en dit pas beaucoup (contenu protégé), mais on en sait assez pour savoir qu'il s'agit d'une version « limit » du poker, c'est à dire que le montant des relances n'est pas libres. Conséquence, le pot devient rapidement plus important que le montant des mises à jouer (par rapport au « no limit » où l'on peut contrôler le montant des mises).
Ça retire de l'analyse tout l'aspect psychologie humaine du jeu, et ça devient juste une question de calcul d'espérance mathématique. (Un peu compliqué certes, mais pas complexe).
[^] # Re: l'infini est demain
Posté par Kerro . Évalué à 2.
Ça donne un éventail plus large.
Le fait qu'il contienne de l'aléatoire fait que, statistiquement, certains mouvements seront optimaux.
Par exemple au backgammon, les mouvements de sortie sont « résolus », c'est à dire qu'on sait comment faire sortir les pions de manière optimale, en fonction de la situation (si tu es en avances sur l'adversaire, en retard, ou kif-kif).
Si tu es en avance sur l'adversaire, les coups optimaux sont pour faire sortir les pions en comptant très peu sur les gros doubles (tu as statistiquement gagné, donc il faut limiter la casse en cas de tirages pas géniaux, sans toutefois trop lambiner car l'adversaire peut avoir de la chance).
Si tu es en retard, c'est l'inverse (tu as statistiquement perdu, donc tu optimises pour qu'un bon lancé de dé te fasse rattraper le retard).
# une vision du futur
Posté par RenardBleu . Évalué à 6.
Il est dommage que tu n'aies pas mis ce lien dans ton journal ^
https://www.youtube.com/watch?v=XtgZKwK6C3U
# Je n'y connais rien mais
Posté par kursus_hc . Évalué à 2.
Nombre de Shannon :
Si ces coups permettent d'éviter la victoire assurée de l'adversaire ne sont-ils plus absurdes ? Peut-on dire qu'un perdant à joué "parfaitement" sans avoir étudié toutes ses possibilités ?
Je ne crois pas une seconde qu'une stratégie gagnante ultime existe pour l'une ou l'autre des couleurs. En gros ce que vous cherchez c'est une sorte de bug comme dans une simulation de foot à grosse franchise ? Ça me "décevrait" de la part des échecs.
Le théorème à la base de cette quête :
Je sais que c'est la version simplifiée et donc biaisée mais c'est amusant de constater que pris au pied de la lettre, il ne s'applique pas aux échecs !
Sérieusement ça me paraît donner beaucoup, beaucoup plus de chances d'obtenir une collection d'égalités qu'une hypotétique victoire assurée (si c'était le cas il y aurait une légende chinoise à ce sujet :).
Il y a beaucoup de gens de le "milieu" qui croient à ça ? Dans tous les autres cas le résultat du calcul va être très décevant finalement non ?
Y a-t-il des projets similaires qui tentent de trouver les "meilleures" ouvertures, celles qui donnent le plus de chances de gagner, ou le moins de perdre ?
[^] # Re: Je n'y connais rien mais
Posté par Lapinot (site web personnel) . Évalué à 3.
Pour les jeux combinatoires, il est facile de démontrer que toute position est soit gagnante, soit perdante, soit nulle : par exemple, tu pars des positions terminales (quand le jeu est fini) dont tu connais l'état, puis tu remontes les valeurs dans "l'arbre de jeu" (voir par exemple les figures 4 et 5 de l'article qui sont assez explicites).
Le jeu d'échecs ne fait pas exception, et la position de départ du jeu d'échecs est soit une victoire pour Blanc (en supposant que Blanc joue parfaitement), soit une victoire pour Noir (en supposant que Noir joue parfaitement), soit un nul. Donc oui, la stratégie ultime existe, et c'est une de ces trois-là (mais on n'est pas sûr qu'on l'attendra un jour, c'est le sujet de cet article).
Attention cependant : si par exemple c'est Blanc qui est en position de gagner et qu'il ne fait pas d'erreur, alors Noir peut bien jouer ce qu'il veut, il perdra quand même (dans ce cas, cela n'a effectivement pas de sens de dire que Noir joue parfaitement).
Enfin, toujours dans ce cas, pour démontrer la victoire de Blanc, il faut certes étudier toutes les réponses de Noir ; mais à chaque fois que c'est le tour de Blanc, il suffit de trouver un unique coup qui assure sa victoire, ce qui explique qu'il n'est nullement nécessaire d'étudier toutes les parties.
[^] # Re: Je n'y connais rien mais
Posté par kursus_hc . Évalué à 2.
Je comprends ce que tu dis mais on est d'accord qu'il y a quand même largement, énormément, incroyablement beaucoup plus de chances de tomber sur une égalité que sur un cheat code ultime ? Que toutes les situations d'une couleur gagnante ont plus de chance d'être aussi due à une erreur de l'adversaire ? Combien de joueurs ont perdu une partie sans regretter le moindre coup ?
J'aurais presque envie d'énoncer "Dans un jeu ou l'égalité est possible, deux joueurs jouant parfaitement l'atteindront forcément".
J'ai l'impression qu'on sublime la monotonie autour d'un calcul très probablement certain avec l'infime probabilité d'une situation carrément extraordinaire. Une façon plus objective de poser le problème serait à mon sens "Le jeu d'échec est-il imparfait ?" (à mon humble avis, non).
Quel est l'intuition générale des gens qui participent au projet sur les chances des trois résultats ? Plutôt 33/33/33, 1/2/98, 0/0/100 ?
Autre question a-t-on estimé l'ensemble des parties jouées par l'être humain pour le comparer à l'ensemble des probabilités du jeu ? Pour savoir si la découverte spontanée de cette stratégie aurait pu raisonnablement être faite.
[^] # Re: Je n'y connais rien mais
Posté par Lapinot (site web personnel) . Évalué à 5.
Non, on n'est pas du tout d'accord :) Un exemple sur un jeu du même type : le puissance 4.
https://fr.wikipedia.org/wiki/Puissance_4
Le puissance 4 a été résolu il y a plus de 25 ans, car son étude est largement plus rapide que celle des échecs (mais nécessitant tout de même le recours à l'ordinateur, et une programmation subtile, car même avec les ordinateurs actuels, on ne peut pas le résoudre uniquement par la force brute).
C'est un jeu où le nul est possible (par épuisement de tous les pions sans alignement de 4), et même relativement fréquent dans les parties entre bons joueurs. Pourtant, c'est le premier joueur qui gagne s'il joue parfaitement.
À ma connaissance, il n'y a pas de projet qui ait démarré dont le but soit la résolution du jeu d'échecs, d'abord parce qu'il est sans doute trop tôt (on manque encore de puissance de calcul et/ou d'espace mémoire), mais aussi parce que la difficulté du problème est surestimée (c'est le but de cet article de montrer que ce n'est sans doute pas si difficile qu'on le croît).
L'intuition générale des très bons joueurs d'échecs penche vers la nulle, voire vers la victoire de blanc. Je serais bien en peine de donner un pourcentage, il faudrait faire un sondage comme sur linuxfr…
Enfin, l'idée d'utiliser un grand nombre de parties jouées pour estimer le résultat est une idée qui est déjà utilisée, par exemple pour les programmes de Go. Ça peut servir pour trouver de bons coups, mais pas pour mener à bien la résolution du jeu ; ça ne peut pas servir de preuve, il y a toujours un risque que le résultat obtenu ne soit pas le bon.
[^] # Re: Je n'y connais rien mais
Posté par palm123 (site web personnel) . Évalué à 1. Dernière modification le 24 juillet 2015 à 12:59.
Oui, et cela prouve quoi ? Si tous les coups joués dans toutes ces parties étaient très bons, peut-être…
Exemple, un type décide d'étudier un début donné, il récupère 3000 (ou 100 000) parties, trouve que les blancs gagnent à 78 %, les noirs à 10 %, et 12 % de nulles. Cela ne prouve pas forcément que cette ouverture est inférieure pour les noirs, si un fort coup noir est découvert, on va en conclure que cette ouverture est parfaitement jouable pour les noirs. Il y a aussi le cas de l'ouverture qui suit (après le 6 ème coup noir) qui a de bons résultats pour les noirs, si on oublie que la personne qui joue les noirs était souvent nettement plus forte. Kasparov et Judit Polgar ont gagné pas mal de parties avec les noirs sur ce début. Evidemment, quand les noirs ont 300 points Elo de plus que les blancs, ils gagnent souvent, quelque soit le début utilisé.
http://www.chessgames.com/perl/chessgame?gid=1069906
ウィズコロナ
[^] # Re: Je n'y connais rien mais
Posté par Lapinot (site web personnel) . Évalué à 2.
Rien du tout. Relis la fin de mon message : ce n'est pas utilisé dans la résolution de jeux, seulement dans les programmes pour le jeu en temps réel. Voir par exemple :
https://fr.wikipedia.org/wiki/Jeu_de_go_en_informatique#M.C3.A9thode_de_Monte-Carlo
[^] # Re: Je n'y connais rien mais
Posté par robin . Évalué à 1.
Sauf que dans le cas de la résolution du jeu d'échec, le perdant (ou l'adversaire en cas d'égalité) à un nombre de point Elo infini. Par conséquent le gagnant ne peux gagner (ou faire match nul) que si tu joue toujours le (ou un des s'il en a plusieurs) meilleur(s) coup possible.
bépo powered
[^] # Re: Je n'y connais rien mais
Posté par Benoît Sibaud (site web personnel) . Évalué à 5. Dernière modification le 30 juillet 2015 à 12:31.
Pour ceux qui se poseraient aussi la question « Quelle est la valeur max du classement Elo ? », les maigres résultats de ma recherche sur le sujet :
[^] # Re: Je n'y connais rien mais
Posté par palm123 (site web personnel) . Évalué à 3. Dernière modification le 30 juillet 2015 à 11:42.
Tout à fait d'accord avec tes remarques.
En passant, le classement Elo est inflationniste, en 1980, les joueurs classés à plus de 2600 étaient (en gros) les 10 premiers mondiaux, aujourd'hui un 2600 est un GM lambda.
Le classement Elo étant inflationniste, cela ne veut pas dire que c'est le plus fort joueur de l'histoire. Lors de débat sur ce sujet, les participants s'étripent en général en criant "Fisher ! non Kasparov ! non Capablanca ! non Alekhine …"
ウィズコロナ
# alpha = 2 pas prudent à mon avis
Posté par Xavier Combelle (site web personnel) . Évalué à 1.
D'après le texte de l'article, j'ai trouvé cette hypothèse. "Nous prendrons alpha = 2, soit en moyenne, un nœud inutilement évalué avant que le nœud perdant soit trouvé, hypothèse nous semblant prudente." Cela ne me semble pas prudent du tout, en l'état actuel de mes connaissances du jeu d'échecs et des programmes d'échecs.
Tout d'abord, en donnant une position équilibrée à un programme d'échecs, il donne facilement au moins une quinzaine de coup raisonnable pour la position, et partant de cet hypothèse il faudrait que le alpha soit au minimum de 7 (en supposant qu'une fois sur deux il y a plus et une fois sur deux moins de nœuds erronés.
Une autre hypothèse serait celle d'un ordinateur faisant des évaluations de positions aussi bonne que celles d'un fort joueur d'échecs (sans recherche dans l'arbre) Dans ce cas, j'ai vraiment de forts doutes qu'on puisse les réduire à un coup dans l'eau pour un coup correct. Ce n'est en tout cas pas ce que mon expérience de faible joueur de club me dit. Cette hypothèse est en plus vraiment optimiste car en l'état ce qui fait la force d'un programme de go c'est sa force de recherche brute, beaucoup plus que sa finesse d'évaluation d'une position.
[^] # Re: alpha = 2 pas prudent à mon avis
Posté par Xavier Verne (site web personnel) . Évalué à 1.
Ce dernier commentaire remet un peu tout en cause…
Avec alpha = 7, que deviendrait cette estimation ? Est-ce toujours aussi réaliste de dire qu'en ~2022, le sujet sera très proche d'être résolu ?
Des liens vers d'autres articles faisant des estimations différentes ou avec des méthodologies complémentaires ? Votre article manque un poil de sources…
Merci d'avance.
[^] # Re: alpha = 2 pas prudent à mon avis
Posté par Lapinot (site web personnel) . Évalué à 1.
L'article ne parle pas de 2022 mais de 2037 (environ…). Maintenant, si on m'annonçait en 2022 que le jeu était résolu, je ne serais pas si surpris.
J'aurais du mal à donner des sources vers des articles parlant de la résolution des échecs, dans la mesure où je n'en connais pas… y en a-t-il ? pour le moment, beaucoup pensent encore que le jeu ne sera jamais résolu. Les auteurs de cet article sur la résolution d'un variante sur un plateau 5x5 : http://arxiv.org/abs/1307.7118 pensent eux que le jeu se fera résoudre un jour (voir http://www.ens-lyon.fr/DI/?page_id=730 ).
[^] # Re: alpha = 2 pas prudent à mon avis
Posté par Xavier Combelle (site web personnel) . Évalué à 1.
Je sais pas si les auteurs de l'article pensent qu'on approche d'une résolution faible du jeu d'échecs "Nevertheless, the resolution of chess remains too difficult to be imagined: the number of legal positions is something around 1045 [All94] and decision complexity is very high (the amount of chess literature is a proof by itself)" ce qui semble exactement le contraire de ton opinion.
Des propriété spéciales de cette variantes ont permis cette résolution
"The main line of oracles were computed in a semi-automated way: we were mainly following the most
equalizing line. It turns out that most of the deviations from the main line can be quickly decided. It is
mainly due to the fact that in Gardner’s chess pawns are immediately exchanged or blocked. Moreover,
pieces cannot develop naturally since almost all free squares are controlled by pawns. Also the fact that
promotion happens quickly leads to some very rapid checkmates that allow to prune the game tree."
[^] # Re: alpha = 2 pas prudent à mon avis
Posté par Lapinot (site web personnel) . Évalué à 1.
Bon désolé argument massue : je sais qu'au moins un auteur de l'article pense cela car j'en ai déjà discuté avec lui :)
[^] # Re: alpha = 2 pas prudent à mon avis
Posté par Xavier Combelle (site web personnel) . Évalué à 1.
C'est un bon argument, dont j'ignorais l'existence jusque là.
[^] # Re: alpha = 2 pas prudent à mon avis
Posté par Lapinot (site web personnel) . Évalué à 1.
Question intéressante. Alpha=7 est bien trop pessimiste. D'ailleurs, je ne comprends pas le raisonnement de ton deuxième paragraphe qui donne cette valeur. Quand on cherche à prouver qu'une position est gagnante, alpha évalue le nombre d'essais que l'on fait avant de trouver un coup qui envoie l'adversaire vers une position perdante, un "coup parfait".
Déjà, un tel coup parfait n'est pas forcément unique. Dans les conditions de l'article, on considère un branching factor de 18 (18 coups sont jouables à partir de toute position). Si on suppose par exemple que sur les 18 coups jouables, 3 sont des coups parfaits (en pratique, les positions pour lesquelles un seul coup parfait existe sont rares), alors la méthode consistant à jouer au pif fournit déjà un alpha de 4,75 seulement (je le laisse en exercice)… soit déjà bien en-dessous de 7. Et évidemment, décider de programmer une meilleure technique que "jouer au pif" est susceptible d'améliorer grandement ce nombre.
Mais ce n'est pas tout. Dans le cadre de l'article, dans un souci de simplification du propos, je fais comme si on allait résoudre le jeu d'échecs par un algorithme alpha-beta. En réalité, il est probable que le jour où il sera résolu, il le sera à l'aide de méthodes plus élaborées (voir par exemple l'article de Schaeffer et al "Checkers is solved" où il explique les techniques qu'il a utilisées pour résoudre le jeu des dames anglaises), utilisant justement la recherche dans l'arbre. Ces méthodes contribuent elles-aussi à réduire le nombre de noeuds étudiés, ce qui équivaut à réduire alpha.
Attention également au parallèle avec le go. Ces deux jeux sont très différents, ce n'est pas étonnant si les ordis battent les humains d'un côté et pas de l'autre. La force d'un programme d'échecs dépend beaucoup moins de la puissance de calcul que pour les programmes de go.
Après, je suis bien d'accord que alpha=2, c'est choisi avec une bonne grosse louche bien épaisse (difficile de faire mieux sans programmer pour voir ce qui se passe). Mais si je devais parier sur la valeur réelle, je pencherais vraiment pour moins de 2.
[^] # Re: alpha = 2 pas prudent à mon avis
Posté par Xavier Combelle (site web personnel) . Évalué à 1.
comment j'avais fait mon calcul? j'avais supposé qu'il n'y avait qu'un coup parfait. L'ordinateur réduit les coups envisageable à quinze coup par une heuristique. En choisissant un coup au hasard parmi les 15. il met en moyenne 7,5 coups à choisir le coup parfait. J'avais effectivement négligé le fait qu'il pouvait y avoir plusieurs coups parfait.
Concernant la résolution du jeu de dame anglaise, si j'ai bien compris elle a été résolue: par une heuristique rapide et correcte, réduisant le alpha, et par le fait que la fin de partie était calculable par analyse rétrograde et ce a un point que la recherche avant et arrière se complétait.
Si tu as des indices sur comment faire pour aider les ordinateur à trouver rapidement le bon coup dans une position donnée, je serai ravi de l'entendre, car dans mon expérience des ordinateurs jouant aux échecs, leur meilleur coup à une profondeur n+1 est souvent le coup classée au moins 8ème à une profondeur n.
Désolé de mon erreur. Il fallait lire: "Cette hypothèse est en plus vraiment optimiste car en l'état ce qui fait la force d'un programme d'échecs c'est sa force de recherche brute, beaucoup plus que sa finesse d'évaluation d'une position." (échecs au lieu de go)
[^] # Re: alpha = 2 pas prudent à mon avis
Posté par Lapinot (site web personnel) . Évalué à 1.
Le fonctionnement des programmes dédiés à la résolution de jeux n'obéit pas aux mêmes contraintes de temps que les programmes fabriqués pour jouer en temps réel, ils ont beaucoup plus de temps pour s'orienter correctement dans l'arbre. En réalité, plutôt que d'utiliser un simple algorithme "alpha-beta" tel celui décrit dans l'article, ils utilisent souvent en haut de l'arbre un algorithme de recherche de type "best-first", par exemple le PN-search que Schaeffer a utilisé pour résoudre les dames anglaises.
C'est plus complexe qu'un alpha-beta avec une heuristique : l'alpha-beta, tu fais ton choix, puis tu t'y tiens - et si tu t'es trompé, tant pis pour toi. Le PN-search, une fois qu'il considère qu'il a passé trop de temps dans une branche, il la quitte et va essayer ailleurs. Il peut aussi déduire de ses calculs une probabilité que tel coup soit le meilleur coup.
C'est moins spontané qu'un alpha-beta, ça met plus de temps à tourner, mais sur le long terme c'est bien plus efficace, en particulier pour un jeu comme les échecs où il y a "mort subite".
[^] # Re: alpha = 2 pas prudent à mon avis
Posté par Xavier Combelle (site web personnel) . Évalué à 1.
Aurais tu des lectures (en accès gratuit) à me conseiller sur la résolution des jeux ?
[^] # Re: alpha = 2 pas prudent à mon avis
Posté par Lapinot (site web personnel) . Évalué à 1.
Je ne connais pas de livre qui soit précisément sur ce sujet ; plutôt une accumulation d'articles scientifiques, dont certains sont sur arxiv (donc accessibles), ou parfois des thèses (idem).
Ce que je peux te proposer de meilleur, c'est la thèse de Dennis Breuker, qui a le mérite à la fois d'être en accès gratuit, et d'aborder les thématiques dont on a pu parler dans notre discussion.
http://breukerd.home.xs4all.nl/thesis/
[^] # Re: alpha = 2 pas prudent à mon avis
Posté par Xavier Combelle (site web personnel) . Évalué à 1.
merci !
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.