URL: https://linuxfr.org/users/pitilapinou/journaux/resolution-du-jeu-d-echecs-patience-ca-arrive Title: Résolution du jeu d'échecs : patience, ça arrive... Authors: Lapinot Date: 2015年07月22日T15:30:51+02:00 License: CC By-SA Tags: échec, échecs et sif Score: 26 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 ordinateurs[^2]. 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é à 10^120 le nombre de parties différentes, et à 10^43 le nombre de positions différentes[^3], 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 10^20 , 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 10^14 . 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](http://www.societe-informatique-de-france.fr/wp-content/uploads/2015/07/1024-no6-lemoine-viennot.pdf) sous [licence CC BY-ND](http://creativecommons.org/licenses/by-nd/4.0/deed.fr). 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. [^1]: de faire troller ? [^2]: https://en.wikipedia.org/wiki/Solving_chess [^3]: https://fr.wikipedia.org/wiki/Nombre_de_Shannon