Une autre sorte de Gambit de la Reine
Un mathématicien de Harvard résout en grande partie un problème d’échecs vieux de 150 ans concernant la pièce la plus puissante de l’échiquier.
La reine est la pièce la plus puissante de l’échiquier. Contrairement à toutes les autres (y compris le roi), elle peut se déplacer d’un nombre quelconque de cases verticalement, horizontalement ou en diagonale.
Maintenant, considérez ce gambit de la reine : Si vous en placez huit sur un plateau standard de huit cases par huit cases, de combien de façons peuvent-elles être disposées pour qu’aucune ne puisse attaquer l’autre ? Il s’avère qu’il y en a 92. Mais que se passe-t-il si vous placez un nombre encore plus grand de reines sur un échiquier de même taille relative, disons 1 000 reines sur un échiquier de 1 000 par 1 000 carrés, ou même un million de reines sur un échiquier de taille similaire ?
La version originale du problème mathématique des n dames est apparue pour la première fois dans un magazine d’échecs allemand en 1848 sous le nom de problème des huit dames, et la réponse correcte est apparue quelques années plus tard. La réponse correcte est apparue quelques années plus tard. Puis en 1869, la version plus étendue du problème est apparue et est restée sans réponse jusqu’à la fin de l’année dernière, lorsqu’un mathématicien de Harvard a fourni une réponse presque définitive.
Michael Simkin, chercheur postdoctoral au Centre des sciences mathématiques et de leurs applications, a calculé qu’il existe environ (0,143n)n façons de placer les reines de manière à ce qu’aucune ne s’attaque à l’autre sur des échiquiers géants de n sur n.
L’équation finale de Simkin ne donne pas la réponse exacte, mais indique simplement que ce chiffre est le plus proche du nombre réel que l’on puisse obtenir actuellement. Le chiffre de 0,143, qui représente un niveau moyen d’incertitude quant au résultat possible de la variable, est multiplié par n, quel qu’il soit, puis élevé à la puissance de n pour obtenir la réponse.
Sur le très grand échiquier avec un million de reines, par exemple, 0,143 serait multiplié par un million, ce qui donnerait environ 143 000. Ce chiffre serait ensuite élevé à la puissance un million, ce qui signifie qu’il serait multiplié par lui-même un million de fois. La réponse finale est un chiffre à cinq millions de chiffres.
M. Simkin dit qu’il est personnellement un très mauvais joueur d’échecs mais qu’il cherche à améliorer son jeu. “Je suppose que les mathématiques sont plus indulgentes”.
Simkin a pu trouver l’équation en comprenant le schéma sous-jacent de la répartition d’un grand nombre de reines sur ces énormes échiquiers – qu’elles soient concentrées au centre ou sur les bords – puis en appliquant des techniques mathématiques et des algorithmes bien connus.
“Si vous me disiez que je veux que vous placiez vos reines de telle ou telle manière sur l’échiquier, alors je serais capable d’analyser l’algorithme et de vous dire combien de solutions il y a qui correspondent à cette contrainte”, a déclaré Simkin. “En termes formels, cela réduit le problème à un problème d’optimisation”.
En se concentrant sur les espaces qui ont le plus de chances d’être occupés, Simkin a calculé combien de dames se trouveraient dans chaque section du plateau et a trouvé une formule pour obtenir un nombre valide de configurations. Les calculs ont permis d’obtenir ce que l’on appelle la limite inférieure, c’est-à-dire le nombre minimum de configurations possibles.
Une fois ce nombre obtenu, Simkin a utilisé une stratégie connue sous le nom de méthode de l’entropie pour trouver la limite supérieure, qui est le nombre le plus élevé de configurations possibles.
Simkin a trouvé que la réponse de la borne inférieure correspondait presque parfaitement à la réponse de la borne supérieure. En d’autres termes, il a montré que la réponse exacte est prise en sandwich quelque part entre les deux limites dans un espace mathématique relativement petit.
Simkin a travaillé sur le n-queens depuis presque cinq ans. Il dit qu’il est personnellement un très mauvais joueur d’échecs mais qu’il cherche à améliorer son jeu. “J’aime toujours relever le défi du jeu, mais je suppose que les mathématiques sont plus indulgentes”, a déclaré M. Simkin, qui s’est intéressé à ce problème en raison de la manière dont il pouvait appliquer les percées réalisées dans le domaine des mathématiques dans lequel il travaille, la combinatoire, qui se concentre sur le comptage et les problèmes de sélection et d’arrangement.
Travailler sur ce problème a été un test de patience et de résistance. Il y a quatre ans, alors qu’il était étudiant en doctorat à l’Université hébraïque de Jérusalem, il a rendu visite au mathématicien et expert en échecs Zur Luria à l’Institut fédéral suisse de technologie de Zurich. Les deux hommes ont collaboré et développé de nouvelles techniques pour trouver une réponse. En fin de compte, après deux ans de travail, ils n’ont obtenu que les résultats suivants une meilleure limite inférieure et savaient qu’il leur manquait quelque chose.
Simkin a terminé son doctorat en 2020 et a déménagé à Boston pour commencer à travailler à Harvard. Le problème était toujours présent dans son esprit, et il y est revenu lorsqu’il a commencé à travailler à Harvard.a réalisé qu’il devait commencer à se concentrer sur les espaces où se trouveraient les reines plutôt que de donner un poids égal à chaque espace.
Même s’il est théoriquement possible de s’approcher un peu plus d’une réponse encore plus exacte, Simkin est pour l’instant heureux de laisser quelqu’un d’autre y venir.
“Je pense que j’en ai personnellement fini avec l’histoire de l’humanité. n-queens pour un moment, non pas parce qu’il n’y a plus rien à faire avec, mais simplement parce que j’ai rêvé d’échecs et que je suis prêt à avancer dans ma vie”, a-t-il déclaré.
Référence : “Le nombre de configurations n-queens” par Michael Simkin, 19 août 2021, Mathématiques > ; Combinatoire.
arXiv:2107.13460
