Digit Party, un casse-tête en ligne, a attiré des centaines de milliers d’amateurs de mathématiques depuis son lancement il y a trois ans. Mais les créateurs du jeu — deux mathématiciens — ont désormais une confession à faire. Vos scores élevés étaient probablement faux.
Dans un article publié récemment dans Math Horizons, les mathématiciens Robert Brignall et Vincent Vatter, de The Open University au Royaume‑Uni et de l’Université de Floride, respectivement, avouent qu’ils ne savaient pas comment calculer les vrais scores maximaux. Ils se confient maintenant après avoir résolu le problème, précisément en pré-calculant le vrai « score parfait » pour chaque partie possible. Techniquement, l’erreur moyenne était faible, d’environ 2 points, avec un maximum de 6 points d’écart, et le jeu « mentait » 55 fois sur les 1 096 énigmes passées. Par ailleurs, ce « mensonge » met en lumière un problème étonnamment courant en mathématiques pratiques, à savoir des obstacles à l’optimisation aussi présents dans la planification, la logistique et la fabrication.
« Nous savions qu’il y avait ce problème, mais nous ne savions pas comment le corriger », a déclaré Vatter dans un communiqué. « Nous avions un chiffre que personne ne pouvait battre. La plupart du temps, il était réellement atteignable, mais environ 5 % du temps, ce ne l’était pas, et nous n’avions aucun moyen de faire la différence. Nous le savons depuis tout ce temps, et cela nous tracassait ».
Comment jouer
La mécanique de Digit Party est simple et étrangement addictive. L’objectif consiste à disposer 25 chiffres allant de 1 à 9 sur une grille 5 par 5. Vous recevez un chiffre et un aperçu du chiffre suivant. Vous pouvez placer un chiffre où bon vous semble, mais pour marquer des points, il faut déposer le même chiffre à côté des autres (horizontalement, verticalement ou en diagonale), et vous marquez des points équivalents à la valeur de ce chiffre. Selon l’article, le score affiché est exprimé en pourcentage d’un maximum théorique — c’est‑à‑dire d’un score parfait qui suppose que le joueur voit « tous les 25 chiffres à l’avance et les place avec une prévision parfaite ».
« Du moins, c’est ce que nous avions affirmé », écrivaient-ils dans l’article. « Nous avons menti aux joueurs pendant trois ans. En notre défense, ce n’était pas intentionnel. »
En réalité, le « score maximum » était une approximation fondée sur une borne supérieure. Il ne représentait pas correctement l’agencement optimal de chaque groupe de chiffres identiques. Pour être juste, les marges d’erreur n’étaient pas énormes. Par exemple, si le maximum réel d’un jour était 186, l’approximation calculait les pourcentages des joueurs sur la base d’une borne supérieure de 192.
Trouver le véritable maximum
Dans la déclaration, Vatter comparait le problème à l’empaquetage d’une valise. Vous pourriez commencer par déterminer la meilleure façon d’assembler vos chemises, puis vos costumes. Mais parfois, vous vous retrouvez avec trop de vêtements, et « quelque chose doit être froissé », expliquait‑il. La question dite d’« optimisation » porte alors sur la « chose la plus intelligente à sacrifice », ou le « froissement », pour n’importe quelle combinaison des listes de bagages.
Résoudre ce problème pour Digit Party n’a pas été chose aisée. Le duo aurait techniquement pu « livrer un solveur de programmation en entier à chaque joueur » ou bourrer un peu de code supplémentaire qui ferait peut‑être « fondre votre téléphone ». Clairement, ce n’était pas une solution idéale. C’est pourquoi les mathématiciens ont décidé de « pré‑caluler les maxima réels pour chaque plateau possible et d’encoder les réponses dans le code ».
Cela a abouti à un nombre vertigineux de possibilités — 13,9 millions de séries de chiffres différentes — qui a été ramené à 1 291 une fois que les mathématiciens ont regroupé les résultats selon des motifs partagés de chiffres répétés. Et parmi ces 1 291, 891 issues ne nécessitaient aucun compromis. Pour les 400 restantes, le duo a calculé manuellement le score le plus élevé possible ; par exemple, si un joueur ne peut pas faire correspondre tous les 4 et les 8, il serait plus judicieux de laisser tomber le 4, car obtenir des paires de 8 donnerait un score plus élevé.
Cela dit, l’équipe a conclu sa confession par une autre admission : quelle est la meilleure stratégie ? Nous ne savons pas réellement.
« Nous n’avons toujours aucune idée de la façon de jouer », a déclaré Vatter. « Robert et moi jouons plutôt différemment, et personne ne sait qui est le meilleur. »
