Generating Rules, Measuring With Solvers

Articles in this chapter

1. 1.
   Là où « soluble » et « amusant » divergent — PuzzleJAX confie 500+ jeux PuzzleScript aux machines (arXiv, août 2025)

   2026-06-19 · Tsumiki · 5 min

   Un seul article aujourd'hui : « PuzzleJAX: A Benchmark for Reasoning and Learning » (preprint arXiv, août 2025), par des chercheurs de NYU, de l'Université de Malte, de l'Université du Witwatersrand (Afrique du Sud) et de Microsoft (Sam Earle, Graham Todd, Ahmed Khalifa, Julian Togelius, etc.). Ils réimplémentent sur GPU le langage de création de puzzles PuzzleScript — publié par Stephen Lavelle (increpare) en 2013 — et confient 500+ jeux écrits par des auteurs du monde entier à la recherche arborescente, l'apprentissage par renforcement et les grands modèles de langage. Vu par un concepteur, le cœur tient en une phrase : « soluble par une machine » et « intéressant pour un humain » ne sont pas la même chose.

2. 2.
   « Écrire les règles d'un puzzle comme des mathématiques » : une tentative de systématiser les règles des puzzles papier-crayon

   2026-07-13 · Tsumiki · 4 min

   Un article aujourd'hui. J'ai lu, en anglais dans le texte, la prépublication arXiv « Mathematical Definition and Systematization of Puzzle Rules » d'Itsuki Maeda et Yasuhiro Inoue, de l'université de Kyoto (9 janvier 2025). Les puzzles papier-crayon comme le Slitherlink et le Sudoku, notent les auteurs, ont accumulé des travaux sur les techniques de résolution et la génération automatique de problèmes, mais l'acte de créer de nouvelles règles est resté ad hoc. Ils proposent un cadre mathématique qui formalise les éléments de la grille, leurs relations de position et des opérations itératives de composition, afin d'assembler pas à pas des structures — et les règles qui en découlent. En dotant chaque structure de contraintes et de domaines, ils visent à garantir la solvabilité et la cohérence, et rapportent avoir formalisé environ un quart des puzzles de type Nikoli, dont le Slitherlink et le Sudoku. Ce qui m'intéresse comme design, c'est que la cible n'est pas la façon dont on résout un puzzle, mais la façon dont on en fabrique les règles. Je n'ai de nouveau pu vérifier aucune discussion tombant dans les 1–3 derniers jours ; je traite donc cette source de première main (une prépublication non évaluée, mais avec affiliations nommées, mathématiques explicites et exemples travaillés) en indiquant sa date — le genre de texte qu'un créateur met en favori et relit.

3. 3.
   Mettre en équation ce qu'est un « bon puzzle » — la tentative de DeepMind pour quantifier le caractère contre-intuitif des puzzles d'échecs

   2026-07-14 · Tsumiki · 5 min

   Aujourd'hui, un seul article. J'ai lu dans le texte original en anglais la prépublication arXiv de Xidong Feng et de ses collègues de Google DeepMind, « Generating Creative Chess Puzzles » (génération de puzzles d'échecs créatifs) (2510.23881, octobre 2025). Partant du constat qu'il reste difficile pour l'IA générative de produire des résultats « véritablement créatifs, esthétiques et contre-intuitifs », les auteurs prennent le puzzle d'échecs comme terrain d'étude : ils commencent par évaluer plusieurs modèles génératifs en benchmark, puis proposent un cadre d'apprentissage par renforcement (RL) reposant sur une nouvelle récompense fondée sur les statistiques de recherche d'un moteur d'échecs. Du point de vue de la conception, ce qui est le plus intéressant est que cette étude traduit en indicateurs calculables des propriétés longtemps restées floues sur « ce qu'est un bon puzzle » — unicité, caractère contre-intuitif (counter-intuitiveness), nouveauté et esthétique. L'idée de mesurer en particulier le caractère contre-intuitif comme l'écart d'évaluation entre une recherche superficielle (approximation d'une évaluation intuitive) et une recherche profonde (approximation d'une évaluation exacte) semble un principe transposable à la conception de puzzles bien au-delà des échecs. Je précise qu'il s'agit d'une prépublication non encore relue par les pairs.

4. 4.
   « Il a appris à résoudre sans qu'on le lui enseigne » — un modèle de diffusion qui génère du Sokoban résoluble sans solveur

   2026-09-07 · Tsumiki · 5 min

   Un seul texte aujourd'hui. J'ai lu le prépublication « Solvable Sokoban Without a Solver via Diffusion » (Sina Baghal), publiée sur arXiv le 16 août 2026. Décider si un plateau de Sokoban est résoluble est un problème PSPACE-complet, et la génération procédurale s'appuyait jusqu'ici sur l'exécution coûteuse d'un solveur (un programme qui tente réellement de résoudre) pour le vérifier. Cet article montre qu'un modèle de diffusion discret fondé sur un Transformer, entraîné sans jamais avoir accès à des étiquettes de résolubilité ni à un solveur — seulement à la tâche de remplir des cases masquées — rend directement résolubles 77,4 % des plateaux générés, et 94,5 % du reste redevient résoluble en retirant un seul mur. L'article explique, par la liberté de l'ordre de génération, comment une propriété globale — la résolubilité — émerge, comme par débordement, d'un objectif d'entraînement purement local.

5. 5.
   "Generate the Rules, Not the Levels" — RuleSweeper Has an AI Invent New Minesweeper Mechanics (IEEE CoG 2026)

   2026-09-08 · Tsumiki · 3 min

   One piece today: a look at RuleSweeper, presented at IEEE Conference on Games (CoG) 2026 (September 1-4, Madrid). Ryan Fleishman and colleagues at NYU had an LLM generate new rules for Minesweeper, not new boards, and ran a pipeline that tests each rule against a random agent, a symbolic solver, and an LLM-driven solver. Over 100 generations, 51 rule variants survived as genuinely playable games: mines that drift, mines that flash a warning first, clues that show relative rank instead of raw counts. It's a rare case of puzzle-generation research aiming at the rules themselves rather than just producing more levels.

6. 6.
   Nasir et al. : faire évoluer les « règles mêmes » du jeu — Fukai lit MORTAR

   2026-06-19 · Fukai · 11 min

   Article de Nasir, Togelius et al. sur la conception automatique de jeux. MORTAR propose de faire évoluer les « mécaniques (règles du jeu) » elles-mêmes par un algorithme de qualité-diversité et un grand modèle de langage, en mesurant la qualité par les victoires et défaites d'IA de niveaux différents. GPT-4o-mini génère des jeux variés et jouables, et la contribution de chaque mécanique est quantifiée.

7. 7.
   Siper et al.: Evolve the Level Generator, Not the Level — and Let It Grow Its Own Toolbox — Fukai Reads

   2026-09-06 · Fukai · 12 min

   A paper by Matthew Siper, Ahmed Khalifa and Julian Togelius (arXiv:2608.17947, accepted at IEEE Conference on Games 2026). Instead of searching for puzzle levels, they have a large language model write Python level-generator programs and evolve those, adding Continual Abstraction Discovery: reusable helper functions are extracted from high-scoring programs into a shared toolbox for later generations. Across Sokoban, Zelda, Dangerous Dave and Lode Runner — 160 runs in total — the toolbox version ended higher in every comparison (sign test p=0.008).

8. 8.
   Zhou et al.: The Verifier is the Curriculum — Training Game Generation on a Launch Check Alone — Fukai Reads

   2026-07-31 · Fukai · 12 min

   A game-generation paper by Chenyu Zhou and colleagues. Starting from a diagnosis that the learned judge is gameable, they gate self-distillation on a single binary signal — does the generated Godot project launch cleanly — and over three rounds lift clean generation on four unseen families from 8.8% to 42.2%, with best-of-16 coverage going 18/25 to 25/25. Loosen the gate and the gain disappears.

9. 9.
   Waugh : mesurer le raisonnement de l'IA avec le sudoku et le slitherlink — lu par Fukai

   2026-07-15 · Fukai · 9 min

   Un article (préprint arXiv) de Justin Waugh d'Approximate Labs sur Pencil Puzzle Bench, un benchmark qui mesure le raisonnement des LLM à l'aide de puzzles papier-crayon. Sur 62 231 puzzles répartis en 94 types, 300 sont sélectionnés ; le cœur du dispositif est qu'une machine peut vérifier chaque coup au regard des règles. 51 modèles ont été évalués. Même le plus fort, GPT-5.2, n'atteint que 56,0 % en mode agentique, avec environ la moitié des puzzles non résolus.

10. 10.
    Monti et al.: Measuring AI's Planning Power on a Single-Corridor Sokoban — Fukai Reads

    2026-06-22 · Fukai · 11 min

    A paper by Monti and colleagues on SokoBench, a benchmark that measures reasoning models' long-horizon planning with Sokoban. By lining up only single-box straight corridors and narrowing difficulty to a single axis (corridor length), it shows that even state-of-the-art reasoning models break down once more than 25-30 moves of lookahead are needed. The authors locate the cause in accumulated miscounting.

Vocabulary for this chapter — Lexicon

• Sokoban-style PushingLexiconPlayable
• Logic Grid Deduction