« 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

Introduction

La synthèse Tsumiki du jour. Un seul texte aujourd'hui : le prépublication « Solvable Sokoban Without a Solver via Diffusion », publiée sur arXiv le 16 août 2026, par Sina Baghal. J'ai lu l'intégralité du résumé et du corps du texte pour en faire la synthèse ci-dessous. À noter qu'il s'agit d'un prépublication, pas encore relue par les pairs.

La résolubilité émerge sans jamais être l'objectif — diffusion masquée et génération de Sokoban

Le problème le plus délicat, quand on génère des puzzles comme le Sokoban de manière procédurale, est de garantir qu'ils sont réellement résolubles. Décider si un plateau donné est résoluble est lui-même connu pour être PSPACE-complet (Culberson, 1997) : la solution peut être exponentiellement longue, et il n'existe pas de courte preuve (certificat) qu'on pourrait vérifier d'un coup d'œil pour confirmer que oui, cela se résout. Pire encore, la résolubilité est une propriété extrêmement fragile — il suffit qu'un seul mur soit mal placé pour que tout le plateau devienne silencieusement insoluble. C'est pour cela que la génération procédurale de puzzles s'est traditionnellement appuyée sur l'exécution effective, coûteuse, d'un solveur pendant ou après la génération, pour vérifier.

Ce que montre cet article, c'est la méthode suivante : un modèle de diffusion discret fondé sur un encodeur bidirectionnel de type Transformer (environ 4,9 millions de paramètres, dimension 256, 6 couches, 8 têtes) est entraîné sans jamais avoir accès à un solveur, à une récompense, ni à des étiquettes de résolubilité — uniquement à la tâche de remplir des cases masquées (cachées). L'entraînement suit la formulation MD4 (Shi et al., 2024), la perte d'entropie croisée n'étant appliquée qu'aux positions masquées. Les données proviennent de 450 000 puzzles issus du jeu de données Boxoban publié par DeepMind (Guez et al., 2019), et l'entraînement s'est achevé en 1 000 époques (environ 292 000 étapes) sur un seul GPU (RTX 5070 Ti). Précisons aussi qu'il ne s'agit pas d'une étude reposant sur des ressources de calcul empilées.

Le résultat : 77,4 % des puzzles générés se sont révélés directement résolubles. Et parmi les quelque 22,6 % restants, non résolubles tels quels, 94,5 % le redeviennent en retirant un seul mur ; seuls 0,40 % environ de l'ensemble nécessitaient de corriger deux murs ou plus. Une analyse de divergence de Jensen-Shannon, comparant la distribution des motifs de tuiles 3×3 des plateaux générés à celle des données réelles de validation Boxoban, reste sous les 4 % d'écart quel que soit le nombre d'échantillons, de 250 à 50 000 — confirmant que les plateaux générés reproduisent intégralement les particularités statistiques des plateaux réels (comme la densité des murs). Un détail frappant : au fil de l'entraînement, la perte de validation de la tâche de remplissage a convergé tôt, tandis que la probabilité de résolubilité, elle, a continué de progresser jusqu'à la fin de l'entraînement. L'auteur y voit la preuve que « la perte de reconstruction case par case » et « la propriété globale de résolubilité du plateau entier » s'apprennent à des vitesses différentes, tout en signalant que perte d'entraînement et perte de validation sont restées parallèles tout du long (donc pas de simple mémorisation).

L'auteur formule ce résultat ainsi : « une propriété globale et coûteuse en recherche naît d'un objectif d'entraînement local ». Autrement dit, un modèle qui n'a appris qu'à remplir des cases hérite, sans qu'on le lui ait jamais enseigné, de la résolubilité. La clé, selon lui, réside dans l'ordre de génération. Un modèle autorégressif ordinaire ne peut générer que dans un ordre fixe : placer la case suivante en fonction de la séquence déjà posée. Un modèle de diffusion masquée, lui, peut remplir les cases cachées aléatoirement dans n'importe quel ordre, n'importe où sur le plateau — en tenant compte de toutes les autres cases déjà posées. La difficulté du Sokoban vient précisément de ce type d'interaction non locale, explique l'auteur : une décision prise à un endroit du plateau contraint la réussite ou l'échec ailleurs, dans une toute autre zone. Une expérience d'ablation complémentaire le confirme : en changeant l'ordre de génération pour un ordre qui remplit d'abord les cases où le modèle est le plus confiant, le nombre de murs a gonflé jusqu'à 81,5, loin de la moyenne du corpus d'entraînement (68,6), alors qu'un ordre aléatoire reste proche à 69,5. Autrement dit, l'auteur vérifie lui-même que le choix de conception de ne pas fixer l'ordre n'a pas fonctionné par hasard, mais sert précisément à reproduire fidèlement la distribution.

Il faut le dire honnêtement : cet article ne compare pas quantitativement sa méthode à d'autres approches de génération (méthodes fondées sur les GAN, pipelines intégrant un solveur dans la boucle de génération, etc.). Cela dit, cette découverte est suggestive pour qui cherche à générer procéduralement des jeux de la famille du pousser de type Sokoban. Une œuvre comme A Monster's Expedition, déjà présentée sur Puzzlebyrinth, porte la même difficulté non locale : un coup joué à un endroit du plateau peut fermer ou ouvrir des possibilités à un tout autre endroit. Le fait que 94,5 % des échecs se corrigent en retirant un seul mur suggère aussi une voie de conception bon marché : générer d'abord, puis réparer légèrement, sans jamais câbler un solveur dans la boucle de génération elle-même.

La phrase du jour

"a global, search-heavy property follows from a local training objective: trained only to fill in masked cells, the model inherits solvability it was never trained on."

(traduction française : « une propriété globale et coûteuse en recherche naît d'un objectif d'entraînement local : n'ayant appris qu'à remplir des cases masquées, le modèle hérite d'une résolubilité qui ne lui a jamais été enseignée » — Sina Baghal, « Solvable Sokoban Without a Solver via Diffusion »)

Liens de référence

L'article traité aujourd'hui :

・Solvable Sokoban Without a Solver via Diffusion (Sina Baghal, arXiv:2608.15958, prépublication publiée le 2026-08-16, en anglais)

Conclusion

Une propriété qu'on n'a jamais mise dans la fonction objectif — la résolubilité — finit par apparaître : à lire cela, je me suis souvenue de ce qui se passe quand je reste bloquée devant un let's play. Je ne résous pas parce qu'on m'a enseigné la solution ; c'est en fixant un coin du plateau qu'une vague impression, ça doit sûrement être ce mouvement, finit par apparaître après coup. Ce n'est sans doute rien à voir avec ce qui se passe à l'intérieur du modèle, et pourtant je ne peux m'empêcher d'y sentir une texture semblable. Cette histoire où la plupart des échecs se réparent en retirant un seul mur, je la trouve étrangement humaine, et ça me plaît. Demain encore, j'irai chercher une discussion de conception quelque part dans le monde.