En dehors de ces simplifications, l'arbre complet est exploré.
Ici, tu te fourvoies. Considère par exemple la position qui consiste en une croix dans le coin supérieur gauche, et un rond dans une des deux cases adjacentes à ce coin. Tu ne la trouveras pas dans la figure 15. C'est un exemple parmi de multiples positions qui ne sont pas explorées.
Je refais mon schéma.
Voici deux arbres solutions. Le premier montre que Blanc peut s'assurer au moins «Nul». Le second montre que Noir peut s'assurer au moins «Nul». Et beaucoup de positions de l'arbre de départ ne sont jamais explorées. Convaincu ?
On tourne en rond, tu donnes la même explication, j'en déduis la même conclusion :-)
En effet, mais c'est pour deux raisons : parce que la répétition est la base de la pédagogie, mais aussi, parce que la répétition est la base de la pédagogie :-)
Ce que je comprends, c'est que tu explores la branche b1-1 (qui donne nul).
Si je comprends bien la notation (sur chaque feuille, on indique la valeur théorique de cette feuille), ce n'est pas un bon exemple, car la valeur théorique de cette position est «blancs». En effet, en jouant b1-3, blanc est certain de gagner. Il faudrait un exemple dont la valeur théorique est «nul».
En voici un. Si tu reprends l'article que j'ai cité ci-dessus, regarde la figure 15 : elle démontre, à l'aide de deux arbres solutions, que la valeur théorique du Tic-Tac-Toe est «nul». L'arbre solution de gauche montre que le premier joueur (celui à la croix) peut s'assurer au minimum le nul (il peut même gagner si l'autre fait une erreur, c'est ce que montre la branche de droite de cet arbre). L'arbre solution de droite montre que le deuxième joueur (celui au rond) peut lui aussi s'assurer au minimum le nul (d'ailleurs lui aussi peut gagner si son adversaire joue mal, c'est ce que montrent les deux positions marquées de fourchettes). Conclusion, le Tic-Tac-Toe est «nul», et ceci a été démontré en n'étudiant qu'une petite partie de toutes les positions possibles du jeu.
Je ne passe pas de ta première phrase à la deuxième, car la première phrase n'implique pas la deuxième. Si tel premier déplacement conduit à un nul en jouant parfaitement, alors on peut seulement en déduire que la valeur théorique du jeu d'échecs est "victoire des blancs ou nul".
Pour montrer que le jeu est résolu à "nul", il faut deux choses :
* démontrer qu'un certain premier déplacement, unique, est "gagnant ou nul" pour les blancs (ce dont est chargé un premier calcul).
* démontrer que tous les 20 premiers déplacements sont "gagnant ou nul" pour les noirs (ce dont est chargé un deuxième calcul, indépendant du premier).
Dit autrement, la valeur théorique de la position de départ est 1 (victoire du premier joueur s'il joue parfaitement), ou 0 (nul), ou -1 (victoire du second joueur). Tu fais tourner ton ordinateur pendant x jours pour démontrer que la valeur théorique est >=0, puis tu recommences un calcul totalement différent pour démontrer qu'elle est <=0. Si tu arrives à faire ça, alors tu sais que la valeur est 0 (nul).
L'idée, c'est qu'à l'aide d'un premier calcul, tu identifies qu'un des 20 coups de départ est "gagnant ou nul" pour le premier joueur. Il suffit de trouver un des 20 coups, on peut ignorer les 19 autres ; et ensuite, pour chacune des réponses du 2e joueur, il faut à nouveau trouver une bonne réponse pour le premier joueur. Ainsi, un étage sur deux, il faut étudier toutes les réponses, mais un étage sur deux, il suffit de n'étudier qu'un seul coup : c'est pourquoi les arbres solutions sont bien plus petits que les arbres de jeu (de l'ordre de la racine carrée en général, parfois encore mieux quand les arbres de jeu sont déséquilibrés).
Il faut ensuite faire un deuxième calcul, mais visant à montrer que la position de départ est "gagnante ou nulle" pour le deuxième joueur, cette fois-ci. Donc les rôles sont inversés : au premier étage, il faut étudier chacun des 20 coups du premier joueur, mais au deuxième étage, il suffit de trouver une unique bonne réponse du deuxième joueur. Et ainsi de suite. On obtient un deuxième arbre solution, lui aussi bien plus petit que l'arbre de jeu.
Si tu obtiens ces deux arbres solutions, alors tu as prouvé que la position de départ est "gagnante ou nulle" pour le premier joueur, et aussi "gagnante ou nulle" pour le deuxième joueur : elle est donc nulle.
pour résoudre le jeu d'échec (et bien d'autres) il « suffit » de trouver un seul chemin qui fait gagner un camp à coup sûr
Ce n'est pas vraiment «un chemin». On peut représenter l'ensemble des parties d'échecs possibles par un «arbre de jeu» : à la racine, on met la position initiale, à l'étage 1, les coups jouables à partir de la position initiale, etc. Il n'est pas possible de développer tout l'arbre qui contient bien trop de positions (voir https://fr.wikipedia.org/wiki/Nombre_de_Shannon) ; mais pour résoudre le jeu d'échecs, seule la connaissance d'une partie de cet arbre de jeu est nécessaire (ce qu'on appelle un «arbre solution»). La question est : existe-t-il des arbres solutions du jeu d'échecs assez petits pour être calculables ? (et si oui, arrivera-t-on à les trouver…)
Par contre ça ne fonctionne pas si la résolution donne nul ?
Si, pas besoin de parcours exhaustif dans ce cas. Un moyen simple de s'en tirer : tu changes légèrement les règles du jeu d'échecs en «Blanc est déclaré vainqueur s'il gagne ou si ça finit en nul, Noir est le vainqueur sinon». Tu fais le calcul. Puis tu changes à nouveau les règles : «Blanc est déclaré vainqueur s'il gagne, Noir est déclaré vainqueur s'il gagne ou si ça finit en nul». Tu refais le calcul. Si Blanc est en position de force dans le premier calcul, et Noir dans le deuxième calcul, c'est que deux joueurs jouant parfaitement feront nul. Et tu as obtenu ce résultat en deux «petits» calculs, ce qui est bien meilleur que le développement de tout l'arbre de jeu.
Notez que les dames sont "résolues" dans le sens où on connait le résultats quand les deux joueurs jouent parfaitement, mais je ne pense pas qu'il existe un programme parfait (qui joue parfaitement dans toutes les positions)
Pas sûr qu'on puisse utiliser cette stratégie pour les échecs, parce qu'aux échecs une partie peut se terminer avant la finale (et il existe donc de nombreuses fins de partie qui ne sont pas dans les tables)
Schaeffer a utilisé une base de fin de parties en précalculant le résultat de toutes les positions avec <= 10 pièces encore en jeu. Ça lui a probablement permis un petit gain de temps, mais c'est l'élément le moins important de son calcul. Le fait de ne pas disposer d'une base complète de positions finales aux échecs n'empêche pas d'appliquer la même stratégie : quand on rencontre une position, au lieu de la chercher dans la grande base de données de positions finales, il suffit de tester si c'est un mat. On perd certes un peu de temps de calcul, mais les mêmes algorithmes peuvent être utilisés.
Un article qui explique diverses stratégies pouvant être mises en œuvre pour se rapprocher de la résolution du jeu d'échecs, et que non, il n'est pas nécessaire d'explorer la totalité des parties pour y arriver :
En particulier, il ne faut pas imaginer que la bonne stratégie serait de remplir des tables de fin de partie jusqu'à retomber sur la position de départ. On peut faire bien plus efficace.
J'aurais été ravi d'argumenter avec toi si ton propos n'était pas inutilement agressif. Il y a bien des choses à dire, mais je doute que la discussion soit mutuellement enrichissante dans ces conditions.
Justement, tu critiques ceux qui ont des difficultés en orthographe, mais qui n’en pas ?
Il me semble n'avoir critiqué personne ; ce n'est pas le sens de mon propos, qui est, en substance : la langue évolue naturellement, et les réformes sont soit inutiles (les petites), soit néfastes (les grosses).
Donc, non, ça pas l’air de poser problème :)
Ce n'est pas contradictoire ce que j'ai dit, dans la mesure où, à mon sens, la réforme actuelle n'est que cosmétique. Cependant, une réforme en profondeur, susceptible de simplifier suffisamment l'orthographe pour avoir de l'intérêt, risquerait, elle, de poser problème.
Si le français avait évolué naturellement, il s’écrirait en phonétique comme l’espagnol ou l’italien.
Là, j'ai vraiment du mal à te suivre. Tu sembles défendre la réforme, pourtant, si l'on t'écoute, la complexité actuelle de la langue a été causée par des… réformes. Une évolution naturelle aurait donc été préférable : en celà, je suis d'accord.
Je ne suis pas opposé à cette réforme, elle m'indiffère plutôt : c'est une perte de temps, combien de siècles de réformes a-t-il fallu pour que l'orthographe évolue si peu ? Ce qui rend les textes anciens si difficiles à déchiffrer, ce n'est pas les sçavoir ou les toujoûrs, mais les innombrables expressions dont le sens a changé, et sur lesquelles l'académie n'a nulle prise. Quant à l'orthographe, qu'y a-t-il de plus difficile à écrire : nénuphar ou hashtag, oignon ou toaster ? Le temps de s'occuper d'une graphie exotique et 10 autres ont déjà apparu, le combat est perdu d'avance.
J'ai l'impression que les gens qui ont des difficultés en orthographe défendent bec et ongles cette réforme. On peut les comprendre, l'orthographe est un marqueur social puissant, et un défaut de maîtrise est fortement préjudiciable. Mais est-il bien réaliste de vouloir réformer la langue par l'intermédiaire du journal officiel ? Cela complique à mon sens le travail de l'instituteur, qui devra désormais apprendre et connaître plusieurs écritures pour de multiples mots, à un âge où ses connaissances sont fossilisées, au risque d'induire en erreur ses élèves. Élèves qui n'aiment guère le flottement : à l'école primaire, une vérité unique est plus que suffisante. Si on veut réformer la langue en profondeur par ce biais, les instituteurs seront noyés. Si on ne veut changer que quelques mots, on ne simplifiera pas grand chose au final. Quel intérêt ?
Bien avant le législateur, l'évolution des langues obéit a un simple commandement : "l'usage fait la règle". C'est ainsi que des fautes de français (après que + subjonctif, par exemple), de guère lasse, finissent par entrer dans le dictionnaire et reléguer les usages précédents aux oubliettes, sous les cris d'orfraie des puristes, parfois même au détriment de la logique ; et c'est ainsi que la langue évolue. N'est-ce pas là une revanche suffisante pour les cancres de la dictée ?
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.
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".
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 ).
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.
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
Oui, et cela prouve quoi ?
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 :
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.
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.
# Pas convaincu
Posté par Lapinot (site web personnel) . En réponse au journal Une personne malade qui ne veut pas explicitement choisir aura.... Évalué à 10.
Je ne voterai Macron que s'il s'engage à interdire les phrases de plus de 200 mots.
[^] # Re: Contexte
Posté par Lapinot (site web personnel) . En réponse au journal Une histoire d'encodage de caractères. Évalué à 10.
C'est ça le mur, je suppose ?
[^] # Re: Fascinant
Posté par Lapinot (site web personnel) . En réponse à la dépêche Stockfish 12 est sorti. Évalué à 0.
Ici, tu te fourvoies. Considère par exemple la position qui consiste en une croix dans le coin supérieur gauche, et un rond dans une des deux cases adjacentes à ce coin. Tu ne la trouveras pas dans la figure 15. C'est un exemple parmi de multiples positions qui ne sont pas explorées.
Voici deux arbres solutions. Le premier montre que Blanc peut s'assurer au moins «Nul». Le second montre que Noir peut s'assurer au moins «Nul». Et beaucoup de positions de l'arbre de départ ne sont jamais explorées. Convaincu ?
[^] # Re: Fascinant
Posté par Lapinot (site web personnel) . En réponse à la dépêche Stockfish 12 est sorti. Évalué à 2.
En effet, mais c'est pour deux raisons : parce que la répétition est la base de la pédagogie, mais aussi, parce que la répétition est la base de la pédagogie :-)
Si je comprends bien la notation (sur chaque feuille, on indique la valeur théorique de cette feuille), ce n'est pas un bon exemple, car la valeur théorique de cette position est «blancs». En effet, en jouant b1-3, blanc est certain de gagner. Il faudrait un exemple dont la valeur théorique est «nul».
En voici un. Si tu reprends l'article que j'ai cité ci-dessus, regarde la figure 15 : elle démontre, à l'aide de deux arbres solutions, que la valeur théorique du Tic-Tac-Toe est «nul». L'arbre solution de gauche montre que le premier joueur (celui à la croix) peut s'assurer au minimum le nul (il peut même gagner si l'autre fait une erreur, c'est ce que montre la branche de droite de cet arbre). L'arbre solution de droite montre que le deuxième joueur (celui au rond) peut lui aussi s'assurer au minimum le nul (d'ailleurs lui aussi peut gagner si son adversaire joue mal, c'est ce que montrent les deux positions marquées de fourchettes). Conclusion, le Tic-Tac-Toe est «nul», et ceci a été démontré en n'étudiant qu'une petite partie de toutes les positions possibles du jeu.
Est-ce que cela te convainc ?
[^] # Re: Fascinant
Posté par Lapinot (site web personnel) . En réponse à la dépêche Stockfish 12 est sorti. Évalué à 2.
Je ne passe pas de ta première phrase à la deuxième, car la première phrase n'implique pas la deuxième. Si tel premier déplacement conduit à un nul en jouant parfaitement, alors on peut seulement en déduire que la valeur théorique du jeu d'échecs est "victoire des blancs ou nul".
Pour montrer que le jeu est résolu à "nul", il faut deux choses :
* démontrer qu'un certain premier déplacement, unique, est "gagnant ou nul" pour les blancs (ce dont est chargé un premier calcul).
* démontrer que tous les 20 premiers déplacements sont "gagnant ou nul" pour les noirs (ce dont est chargé un deuxième calcul, indépendant du premier).
Dit autrement, la valeur théorique de la position de départ est 1 (victoire du premier joueur s'il joue parfaitement), ou 0 (nul), ou -1 (victoire du second joueur). Tu fais tourner ton ordinateur pendant x jours pour démontrer que la valeur théorique est >=0, puis tu recommences un calcul totalement différent pour démontrer qu'elle est <=0. Si tu arrives à faire ça, alors tu sais que la valeur est 0 (nul).
[^] # Re: Fascinant
Posté par Lapinot (site web personnel) . En réponse à la dépêche Stockfish 12 est sorti. Évalué à 1.
L'idée, c'est qu'à l'aide d'un premier calcul, tu identifies qu'un des 20 coups de départ est "gagnant ou nul" pour le premier joueur. Il suffit de trouver un des 20 coups, on peut ignorer les 19 autres ; et ensuite, pour chacune des réponses du 2e joueur, il faut à nouveau trouver une bonne réponse pour le premier joueur. Ainsi, un étage sur deux, il faut étudier toutes les réponses, mais un étage sur deux, il suffit de n'étudier qu'un seul coup : c'est pourquoi les arbres solutions sont bien plus petits que les arbres de jeu (de l'ordre de la racine carrée en général, parfois encore mieux quand les arbres de jeu sont déséquilibrés).
Il faut ensuite faire un deuxième calcul, mais visant à montrer que la position de départ est "gagnante ou nulle" pour le deuxième joueur, cette fois-ci. Donc les rôles sont inversés : au premier étage, il faut étudier chacun des 20 coups du premier joueur, mais au deuxième étage, il suffit de trouver une unique bonne réponse du deuxième joueur. Et ainsi de suite. On obtient un deuxième arbre solution, lui aussi bien plus petit que l'arbre de jeu.
Si tu obtiens ces deux arbres solutions, alors tu as prouvé que la position de départ est "gagnante ou nulle" pour le premier joueur, et aussi "gagnante ou nulle" pour le deuxième joueur : elle est donc nulle.
[^] # Re: Fascinant
Posté par Lapinot (site web personnel) . En réponse à la dépêche Stockfish 12 est sorti. Évalué à 1.
Ce n'est pas vraiment «un chemin». On peut représenter l'ensemble des parties d'échecs possibles par un «arbre de jeu» : à la racine, on met la position initiale, à l'étage 1, les coups jouables à partir de la position initiale, etc. Il n'est pas possible de développer tout l'arbre qui contient bien trop de positions (voir https://fr.wikipedia.org/wiki/Nombre_de_Shannon) ; mais pour résoudre le jeu d'échecs, seule la connaissance d'une partie de cet arbre de jeu est nécessaire (ce qu'on appelle un «arbre solution»). La question est : existe-t-il des arbres solutions du jeu d'échecs assez petits pour être calculables ? (et si oui, arrivera-t-on à les trouver…)
Si, pas besoin de parcours exhaustif dans ce cas. Un moyen simple de s'en tirer : tu changes légèrement les règles du jeu d'échecs en «Blanc est déclaré vainqueur s'il gagne ou si ça finit en nul, Noir est le vainqueur sinon». Tu fais le calcul. Puis tu changes à nouveau les règles : «Blanc est déclaré vainqueur s'il gagne, Noir est déclaré vainqueur s'il gagne ou si ça finit en nul». Tu refais le calcul. Si Blanc est en position de force dans le premier calcul, et Noir dans le deuxième calcul, c'est que deux joueurs jouant parfaitement feront nul. Et tu as obtenu ce résultat en deux «petits» calculs, ce qui est bien meilleur que le développement de tout l'arbre de jeu.
Effectivement, Schaeffer a produit ce qu'on appelle une «résolution faible», mais pas une «résolution forte» : https://fr.wikipedia.org/wiki/Jeu_r%C3%A9solu
Schaeffer a utilisé une base de fin de parties en précalculant le résultat de toutes les positions avec <= 10 pièces encore en jeu. Ça lui a probablement permis un petit gain de temps, mais c'est l'élément le moins important de son calcul. Le fait de ne pas disposer d'une base complète de positions finales aux échecs n'empêche pas d'appliquer la même stratégie : quand on rencontre une position, au lieu de la chercher dans la grande base de données de positions finales, il suffit de tester si c'est un mat. On perd certes un peu de temps de calcul, mais les mêmes algorithmes peuvent être utilisés.
[^] # Re: Fascinant
Posté par Lapinot (site web personnel) . En réponse à la dépêche Stockfish 12 est sorti. Évalué à 5.
Un article qui explique diverses stratégies pouvant être mises en œuvre pour se rapprocher de la résolution du jeu d'échecs, et que non, il n'est pas nécessaire d'explorer la totalité des parties pour y arriver :
https://www.societe-informatique-de-france.fr/wp-content/uploads/2015/07/1024-no6-lemoine-viennot.pdf
En particulier, il ne faut pas imaginer que la bonne stratégie serait de remplir des tables de fin de partie jusqu'à retomber sur la position de départ. On peut faire bien plus efficace.
[^] # Re: La parade
Posté par Lapinot (site web personnel) . En réponse au journal Affaires Milka : on finit toujours pas trouver plus fort que soi. Évalué à 6.
La tablette de Banach-Tarski : deux pour le prix d'une !
[^] # Re: Tous les coups ne sont pas permis
Posté par Lapinot (site web personnel) . En réponse au journal Publicité télévisée pour les vélos interdite. Évalué à 0.
Mais non :
https://fr.wikipedia.org/wiki/Chips_(série_télévisée)
# PC silencieux
Posté par Lapinot (site web personnel) . En réponse au journal Silence ! Contrôler le bruit des ventilos du portable. Évalué à 2.
Le meilleur moyen que les ventilos ne fassent pas de bruit, c'est qu'il n'y en ait pas.
J'ai acheté ça l'an dernier, et effectivement, c'est totalement silencieux pour l'oreille humaine.
https://www.pcvert.fr/108-mini-pc-0-decibel
Ça m'a forcé à changer d'écran car du coup j'entendais l'écran… J'habite à la campagne et maintenant, je peux profiter du silence.
# C, O, maintenant L ! Qu'est-ce que ça peut bien vouloir dire ?
Posté par Lapinot (site web personnel) . En réponse au journal Une question complexe : pourquoi on déboulonne des statues. Évalué à 4.
Et le Colonel Sanders, Coluche, Colin Kaepernick…
[^] # Re: Bonjour
Posté par Lapinot (site web personnel) . En réponse au journal Confinement : risque de release de nombreux projets inutiles. Évalué à 7.
Et tu veux coder ça en quel langage ?
[^] # Re: Solution 433 MHz
Posté par Lapinot (site web personnel) . En réponse au journal Capteurs météo et graphiques Munin. Évalué à 2.
C'est où Courroux ? En Guyane ?
[^] # Re: Est-ce bien réaliste ?
Posté par Lapinot (site web personnel) . En réponse au journal Non aux réformes de l’orthographe !. Évalué à 7.
J'aurais été ravi d'argumenter avec toi si ton propos n'était pas inutilement agressif. Il y a bien des choses à dire, mais je doute que la discussion soit mutuellement enrichissante dans ces conditions.
[^] # Re: Est-ce bien réaliste ?
Posté par Lapinot (site web personnel) . En réponse au journal Non aux réformes de l’orthographe !. Évalué à 2.
Il me semble n'avoir critiqué personne ; ce n'est pas le sens de mon propos, qui est, en substance : la langue évolue naturellement, et les réformes sont soit inutiles (les petites), soit néfastes (les grosses).
Ce n'est pas contradictoire ce que j'ai dit, dans la mesure où, à mon sens, la réforme actuelle n'est que cosmétique. Cependant, une réforme en profondeur, susceptible de simplifier suffisamment l'orthographe pour avoir de l'intérêt, risquerait, elle, de poser problème.
Là, j'ai vraiment du mal à te suivre. Tu sembles défendre la réforme, pourtant, si l'on t'écoute, la complexité actuelle de la langue a été causée par des… réformes. Une évolution naturelle aurait donc été préférable : en celà, je suis d'accord.
Je ne suis pas opposé à cette réforme, elle m'indiffère plutôt : c'est une perte de temps, combien de siècles de réformes a-t-il fallu pour que l'orthographe évolue si peu ? Ce qui rend les textes anciens si difficiles à déchiffrer, ce n'est pas les sçavoir ou les toujoûrs, mais les innombrables expressions dont le sens a changé, et sur lesquelles l'académie n'a nulle prise. Quant à l'orthographe, qu'y a-t-il de plus difficile à écrire : nénuphar ou hashtag, oignon ou toaster ? Le temps de s'occuper d'une graphie exotique et 10 autres ont déjà apparu, le combat est perdu d'avance.
# Est-ce bien réaliste ?
Posté par Lapinot (site web personnel) . En réponse au journal Non aux réformes de l’orthographe !. Évalué à 2.
J'ai l'impression que les gens qui ont des difficultés en orthographe défendent bec et ongles cette réforme. On peut les comprendre, l'orthographe est un marqueur social puissant, et un défaut de maîtrise est fortement préjudiciable. Mais est-il bien réaliste de vouloir réformer la langue par l'intermédiaire du journal officiel ? Cela complique à mon sens le travail de l'instituteur, qui devra désormais apprendre et connaître plusieurs écritures pour de multiples mots, à un âge où ses connaissances sont fossilisées, au risque d'induire en erreur ses élèves. Élèves qui n'aiment guère le flottement : à l'école primaire, une vérité unique est plus que suffisante. Si on veut réformer la langue en profondeur par ce biais, les instituteurs seront noyés. Si on ne veut changer que quelques mots, on ne simplifiera pas grand chose au final. Quel intérêt ?
Bien avant le législateur, l'évolution des langues obéit a un simple commandement : "l'usage fait la règle". C'est ainsi que des fautes de français (après que + subjonctif, par exemple), de guère lasse, finissent par entrer dans le dictionnaire et reléguer les usages précédents aux oubliettes, sous les cris d'orfraie des puristes, parfois même au détriment de la logique ; et c'est ainsi que la langue évolue. N'est-ce pas là une revanche suffisante pour les cancres de la dictée ?
[^] # Re: alpha = 2 pas prudent à mon avis
Posté par Lapinot (site web personnel) . En réponse au journal Résolution du jeu d'échecs : patience, ça arrive.... É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 Lapinot (site web personnel) . En réponse au journal Résolution du jeu d'échecs : patience, ça arrive.... É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 Lapinot (site web personnel) . En réponse au journal Résolution du jeu d'échecs : patience, ça arrive.... É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 Lapinot (site web personnel) . En réponse au journal Résolution du jeu d'échecs : patience, ça arrive.... É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 Lapinot (site web personnel) . En réponse au journal Résolution du jeu d'échecs : patience, ça arrive.... É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: Je n'y connais rien mais
Posté par Lapinot (site web personnel) . En réponse au journal Résolution du jeu d'échecs : patience, ça arrive.... É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 Lapinot (site web personnel) . En réponse au journal Résolution du jeu d'échecs : patience, ça arrive.... É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 Lapinot (site web personnel) . En réponse au journal Résolution du jeu d'échecs : patience, ça arrive.... É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.