Experimenting with Permutation Wordle

Cet article examine la conjecture d'optimalité de la stratégie de « décalage cyclique » proposée par Kutin et Smithline pour le jeu de Permutation Wordle, en formalisant les stratégies, en menant une analyse expérimentale sur des stratégies construites par induction et en étudiant les coefficients de leur fonction génératrice.

L'essentiel

Voici une explication simple et imagée de ce papier de recherche, comme si nous discutions autour d'un café.

🎯 Le Jeu : "Wordle des Permutations"

Imaginez un jeu de devinettes un peu spécial.

• Le Maître du Jeu a une liste secrète de nombres (par exemple, de 1 à 5) dans un ordre précis, mais il ne vous le dit pas.
• Vous devez deviner cet ordre. Vous proposez une liste.
• La Réponse : Le Maître ne vous dit pas quels nombres sont bons, mais à quelles places ils sont bons.
  • Exemple : Si le secret est 2-4-1-3-5 et que vous devinez 1-2-3-4-5, il vous dira : "Le 2 est à la bonne place, et le 3 aussi". Les autres sont faux.
• Le But : Trouver l'ordre secret en faisant le moins de tentatives possible.

C'est comme le jeu Wordle (les mots en 5 lettres) que tout le monde connaît, mais au lieu de deviner des mots, on devine des ordres de nombres.

🔄 La Stratégie "Décalage Circulaire" (Cyclic Shift)

Les chercheurs Samuel Kutin et Lawren Smithline ont proposé une méthode très simple pour gagner : La Stratégie du Décalage.

Imaginez que vous avez une rangée de chaises.

1. Vous vous asseyez sur une chaise. Si c'est la bonne, vous restez assis (vous ne bougez plus).
2. Si vous êtes sur la mauvaise chaise, vous vous levez et vous vous déplacez d'une place vers la droite pour votre prochaine tentative.
3. Vous continuez à faire tourner les mauvais éléments comme une roue, jusqu'à ce que tout le monde soit assis au bon endroit.

Ils pensent que c'est la meilleure méthode possible pour gagner le jeu le plus vite possible, peu importe le secret.

🔍 Ce que dit ce papier de recherche

L'auteure, Aurora Hiveley, s'est demandé : "Est-ce que cette méthode de décalage est vraiment la meilleure ?"

Pour le prouver, elle a fait deux choses :

1. Des expériences sur ordinateur : Elle a programmé des milliers de parties avec différentes stratégies pour voir laquelle gagnait le plus souvent en 1, 2 ou 3 coups.
2. Des mathématiques pures : Elle a utilisé des outils appelés "fonctions génératrices" (des formules magiques qui comptent les possibilités) pour prouver que, dans les cas où le jeu se termine en 3 coups ou moins, la stratégie de décalage est effectivement la championne incontestée.

🧩 L'Analogie du Puzzle et des Pièces

Pour comprendre pourquoi c'est difficile, imaginez que vous avez un puzzle où les pièces sont mélangées.

• Si vous essayez de mélanger les pièces au hasard, vous risquez de faire des boucles infinies (vous remettez les pièces exactement là où elles étaient avant, sans avancer).
• La stratégie de décalage, c'est comme avoir une règle stricte : "Si une pièce est mal placée, je la fais glisser toujours dans le même sens". Cela garantit que vous ne faites jamais de boucle et que vous explorez toutes les options possibles de manière ordonnée.

L'auteure a prouvé mathématiquement que, pour les jeux courts (qui finissent vite), cette règle "glisse-toujours-vers-la-droite" est plus efficace que n'importe quelle autre règle de mélange que l'on pourrait inventer.

📉 Les Résultats Clés

• Pour les jeux très courts (1 ou 2 coups) : Toutes les stratégies fonctionnent aussi bien.
• Pour les jeux de 3 coups : C'est là que ça devient intéressant. La stratégie de décalage (Cyclic Shift) gagne plus souvent que n'importe quelle autre stratégie inventée par l'auteure. Elle trouve le secret plus vite.
• La limite : Le papier prouve que c'est la meilleure stratégie pour les jeux courts. Mais pour les jeux très longs (beaucoup de nombres, beaucoup de coups), on ne sait pas encore si c'est toujours la meilleure. C'est comme si on avait prouvé que le vélo est le meilleur moyen de transport pour aller à l'épicerie, mais on n'a pas encore prouvé qu'il est le meilleur pour traverser l'océan !

🚀 En Résumé

Ce papier est une victoire pour la simplicité. Il montre que parfois, la solution la plus "bête" et la plus logique (décaler tout d'un cran vers la droite) est en réalité la plus intelligente pour gagner ce jeu de devinettes mathématiques, du moins quand le jeu ne dure pas trop longtemps.

L'auteure a utilisé des ordinateurs pour tester des millions de cas et des maths avancées pour prouver que sa théorie tient la route, confirmant ainsi l'intuition de ses prédécesseurs.

Résumé technique

Voici un résumé technique détaillé de l'article « Experimenting with Permutation Wordle » d'Aurora Hiveley, rédigé en français.

1. Problématique

L'article se concentre sur le jeu du « Permutation Wordle », une variante du célèbre jeu Wordle où le but est de deviner une permutation secrète $\sigma$ d'un ensemble de $n$ objets étiquetés de 1 à $n$.

• Mécanique du jeu : À chaque tour, le joueur propose une permutation $\gamma$. Le « maître du jeu » indique quels indices de la permutation proposée correspondent exactement à la permutation secrète (les positions correctes). Le jeu se termine lorsque toutes les positions sont correctes.
• Objectif : Minimiser le nombre moyen de devinées nécessaires pour trouver la permutation secrète.
• Conjecture de Kutin-Smithline : Samuel Kutin et Lawren Smithline ont proposé une stratégie appelée « décalage cyclique » (cyclic shift). Selon cette stratégie, si une permutation contient des éléments incorrects, ceux-ci sont décalés d'un cran vers la droite (en sautant les positions déjà correctes) pour former la prochaine devinette. Ils conjecturent que cette stratégie est optimale parmi toutes les stratégies possibles.

2. Méthodologie

L'auteure adopte une approche combinant l'analyse expérimentale et la preuve mathématique rigoureuse, structurée autour de la génération de stratégies inductives.

• Formalisation de la stratégie : Une stratégie $S$ est définie comme une séquence de permutations $[s_1, s_2, \dots, s_n]$, où $s_i$ est une permutation de longueur $i$. Pour passer d'une devinette $\gamma_r$ à $\gamma_{r+1}$, les positions correctes sont verrouillées, et les positions incorrectes sont permutées selon le composant $S[|I_r|]$ (où $I_r$ est l'ensemble des indices incorrects).
• Restriction aux dérangements et cycles : Pour éviter des boucles infinies et simplifier le calcul, l'étude se concentre initialement sur les stratégies dont les composants sont des dérangements (permutations sans point fixe), puis se restreint davantage aux permutations cycliques.
• Analyse Expérimentale : L'auteure utilise le logiciel Maple pour simuler des milliers de parties pour différentes stratégies (décalage cyclique vs autres stratégies inductives) et calculer le nombre moyen de devinées. Cela a permis de vérifier la conjecture pour $n \le 7$ (stratégies cycliques) et $n \le 8$ (stratégies inductives).
• Analyse Analytique via Fonctions Génératrices : L'approche principale consiste à étudier la fonction génératrice $f_S(x)$ associée à une stratégie $S$. Le coefficient $a_r$ de $x^r$ représente le nombre de permutations secrètes qui peuvent être résolues en exactement $r$ devinées. L'optimisation de la stratégie équivaut à maximiser ces coefficients pour les petits $r$ (en particulier $r=1, 2, 3$).

3. Contributions Clés et Résultats

A. Analyse des Coefficients Linéaires et Quadratiques ($r=1, 2$)

• $r=1$ : Pour toute stratégie, le coefficient $[x^1]f_S(x)$ est égal à 1 (seule la permutation triviale est trouvée en un coup).
• $r=2$ : Le coefficient $[x^2]f_S(x)$ est égal au nombre d'Eulerien $A(n, 1)$ pour toute stratégie inductive. Cela signifie que la performance à deux coups est identique pour toutes les stratégies inductives, indépendamment du composant $S[n]$ choisi, tant que les composants inférieurs sont des décalages cycliques.

B. Analyse des Coefficients Cubiques ($r=3$) - Résultat Principal

L'étude se concentre sur le coefficient $[x^3]f_S(x)$, qui mesure le nombre de permutations résolues en exactement trois coups. L'auteure démontre que la stratégie de décalage cyclique (CS) est optimale pour ce cas.

• Théorème 4.3 : Pour toute stratégie inductive $S$ de longueur $n \ge 4$, le nombre de permutations résolues en 3 coups par la stratégie de décalage cyclique (CS) est strictement supérieur à celui de n'importe quelle autre stratégie inductive $S$.
  $$[x^3]f_{CS}(x) > [x^3]f_S(x)$$
• Preuve par décomposition : L'auteure décompose le nombre total de permutations en trois cas basés sur l'indice de la première devinette correcte ($\rho_S(\pi)$) :
  1. $\rho = 1$ : Le nombre de cas est indépendant de la stratégie $S[n]$.
  2. $\rho = 3$ : Le nombre de cas est également indépendant de $S[n]$ (égal à 1 pour les stratégies cycliques).
  3. $\rho = 2$ : C'est ici que réside la différence. L'auteure prouve que le nombre de permutations pour lesquelles la première position correcte apparaît au 2ème tour est strictement maximisé par la stratégie CS.
     • Pour CS, ce nombre est $2^n - 2n - 2$.
     • Pour toute autre stratégie inductive, ce nombre est strictement inférieur.

C. Cas du Pire Scénario (Stratégie CSL)

L'auteure identifie également la stratégie la moins performante, appelée CSL (décalage cyclique vers la gauche pour le composant $n$, puis décalage vers la droite pour les sous-problèmes).

• Le coefficient cubique pour CSL est lié aux nombres de Lucas ($L_n$).
• Théorème 4.9 : Pour tout $n \ge 4$, $[x^3]f_{CSL}(x) < [x^3]f_S(x)$ pour toute autre stratégie inductive $S$. CSL est donc la stratégie inductive la moins efficace pour résoudre le jeu en 3 coups.

4. Signification et Limites

• Validation de la Conjecture : L'article fournit une preuve mathématique rigoureuse (via les fonctions génératrices et l'analyse combinatoire) confirmant la conjecture de Kutin-Smithline pour les jeux se terminant en 1, 2 ou 3 coups.
• Approche Inductive : L'article formalise comment construire des stratégies optimales de manière inductive et montre que la structure locale (le choix du composant $S[n]$) impacte directement la probabilité de succès à l'étape suivante.
• Limites et Perspectives :
  • Les résultats sont actuellement limités aux jeux se terminant en 3 coups. L'extension aux coefficients d'ordre supérieur ($r \ge 4$) nécessite des approches plus nuancées car les motifs observés expérimentalement ne se généralisent pas simplement.
  • L'étude se restreint aux stratégies composées de permutations cycliques. L'optimisation dans l'ensemble plus large des dérangements ou des permutations générales reste une question ouverte.
  • L'hypothèse d'une stratégie fixe (non adaptative en cours de partie) est maintenue, bien que des stratégies adaptatives dynamiques puissent potentiellement offrir de meilleures performances.

En résumé, ce papier établit que la stratégie de « décalage cyclique » est la meilleure approche inductive pour minimiser le nombre de devinées dans le Permutation Wordle, du moins pour les scénarios de jeu courts, en maximisant la probabilité de résoudre le problème en exactement trois tentatives.