Solvable Sokoban Without a Solver via Diffusion

Dans le monde de l'informatique, il existe une classe de problèmes si complexes que vérifier une solution peut être facile, mais en trouver une nécessite de naviguer dans un labyrinthe de possibilités si vaste qu'il faudrait plus longtemps que l'âge de l'univers pour le résoudre par force brute. Il ne s'agit pas simplement de puzzles difficiles ; ce sont des problèmes où le chemin vers la réponse n'est pas seulement long, mais exponentiellement long, ce qui signifie que chaque étape que vous franchissez peut ouvrir un univers de nouvelles possibilités tout en en fermant d'autres. L'un des exemples les plus célèbres de cela est un jeu appelé Sokoban, qui se joue sur une grille où un personnage unique doit pousser des boîtes sur des cases cibles spécifiques. Le piège est que le personnage ne peut que pousser, jamais tirer, et une fois qu'une boîte est coincée dans un coin, elle est souvent bloquée pour toujours. Parce que la position d'une seule boîte peut complètement altérer l'accessibilité de l'ensemble du plateau, le jeu ne peut pas être décomposé en petites tâches indépendantes. Le résoudre nécessite un plan holistique qui tient compte de chaque interaction avant même qu'un seul mouvement ne soit effectué. Pendant des décennies, la capacité de générer de nouveaux puzzles valides de ce type a été un défi, car créer un labyrinthe solvable est aussi difficile que d'en résoudre un, et vérifier si un labyrinthe fonctionne nécessite généralement un ordinateur puissant pour simuler chaque mouvement possible.

Une étude récente a découvert une manière surprenante de générer ces puzzles complexes sans jamais apprendre à l'ordinateur comment les résoudre. Des chercheurs ont entraîné un type de modèle d'intelligence artificielle pour remplir les pièces manquantes d'une grille de Sokoban, un peu comme un humain complétant un mot croisé en devinant les mots manquants grâce aux lettres environnantes. Le modèle a été exposé à des milliers de vrais puzzles et on lui a demandé d'apprendre les motifs des murs, des sols et des boîtes, mais on ne lui a jamais dit quels puzzles étaient solubles, ni donné de récompenses pour créer un jeu fonctionnel. Il a simplement appris à prédire quel carreau devrait se trouver dans un emplacement caché en fonction des carreaux déjà visibles. Le résultat fut saisissant : lorsque le modèle générait de nouveaux puzzles à partir de zéro, 77,4 % d'entre eux étaient solubles. C'est un résultat remarquable car le modèle n'a jamais été explicitement entraîné pour garantir la solvabilité ; il a seulement été entraîné pour remplir les blancs. Les chercheurs ont découvert que la capacité de créer un puzzle soluble n'était pas une compétence distincte que le modèle avait apprise, mais un sous-produit naturel de l'apprentissage des motifs locaux du jeu.

Le succès de cette approche repose sur la façon dont le modèle perçoit la grille. Les programmes informatiques traditionnels qui génèrent des séquences, comme ceux qui écrivent du texte, travaillent selon un ordre fixe, décidant du premier mot, puis du deuxième, puis du troisième. Cette approche linéaire peine avec le Sokoban car une décision prise au tout début de la grille peut contraindre ce qui est possible à l'extrémité opposée, créant un conflit que le programme ne peut pas corriger plus tard. Le modèle utilisé dans cette étude, cependant, ne suit pas un ordre fixe. Il commence avec une grille complètement vide où chaque cellule est cachée et les révèle une par une dans une séquence aléatoire. À chaque étape, il regarde l'ensemble du plateau tel qu'il se présente actuellement — des murs ici, des boîtes là, et des espaces vides ailleurs — et décide de ce qui appartient au prochain emplacement caché. Cela permet au modèle de placer un mur dans un coin et un objectif dans le coin opposé, puis de concevoir le couloir qui les relie, en ajustant sa compréhension de l'ensemble du plateau à chaque nouvelle pièce qu'il révèle. Cette flexibilité reflète la façon dont un joueur humain doit penser au jeu, où la difficulté provient des interactions non locales entre des parties distantes du plateau.

Pour tester l'efficacité de cette méthode, les chercheurs ont généré 50 000 nouveaux puzzles et ont vérifié chacun d'eux avec un solveur standard. Ils ont constaté que près des trois quarts des puzzles étaient immédiatement solubles. Plus révélateur encore fut ce qui est arrivé aux puzzles qui ont échoué. Dans 94,5 % des cas insolubles, le puzzle pouvait être réparé simplement en retirant un seul mur intérieur. Cela suggère que le modèle ne devinait pas de manière aléatoire ; il créait des structures qui étaient presque entièrement correctes, avec seulement des erreurs mineures et superficielles empêchant une solution. Les chercheurs ont également vérifié que le modèle ne se contentait pas de mémoriser les puzzles qu'il avait vus pendant son entraînement. Ils ont comparé les nouveaux puzzles à l'ensemble de données original et ont trouvé que les puzzles générés étaient tout aussi différents des données d'entraînement que les vrais puzzles inédits le sont. Le modèle avait appris la structure sous-jacente du jeu, et non juste une liste d'exemples spécifiques.

L'étude a également exploré comment le comportement du modèle changeait lorsque les chercheurs ajustaient sa confiance. En rendant le modèle plus décisif dans ses choix, ils pouvaient augmenter le taux de solvabilité pour atteindre près de 99 %, bien que cela se fasse au prix de la création de puzzles avec un peu plus de murs que d'habitude. Le réglage par défaut, cependant, produisait des puzzles qui correspondaient parfaitement à la densité de murs trouvée dans l'ensemble de données d'entraînement original. Cet équilibre entre structure et aléatoire est la clé. Le modèle a appris que pour qu'un puzzle soit valide, les murs et les boîtes doivent s'assembler d'une manière très spécifique, et en apprenant à remplir les lacunes correctement, il a par inadvertance appris les règles de la solvabilité. Les chercheurs ont noté que la performance du modèle sur la propriété globale de la solvabilité continuait de s'améliorer longtemps après que sa capacité à prédire des carreaux individuels a cessé de progresser. Cela indique que les deux objectifs sont distincts : un modèle peut être bon pour remplir un seul carreau sans être bon pour créer un puzzle entier, mais dans ce cas, maîtriser les détails locaux a suffi pour débloquer la solution globale.

Les implications de cette découverte s'étendent au-delà de la simple création de meilleurs puzzles. Elle démontre que des propriétés globales complexes peuvent émerger d'objectifs d'entraînement locaux simples. Le modèle n'a jamais été informé qu'un puzzle devait être soluble, pourtant il a appris à en créer. Cela suggère que la structure des données elle-même contient la logique de la solution, et qu'un modèle capable de comprendre les relations entre toutes les parties d'un système peut hériter de la capacité de le résoudre. Les chercheurs ont confirmé que le modèle n'utilisait pas un solveur caché pour guider sa génération. Chaque étape du processus était pilotée par les propres prédictions du modèle basées sur les parties visibles de la grille. Le fait que le modèle puisse générer un labyrinthe soluble sans jamais avoir vu le chemin de la solution est un témoignage de la puissance de l'apprentissage des motifs d'un système assez profondément pour en reproduire les propriétés les plus difficiles.

En fin de compte, ce travail montre que la barrière entre générer un problème et le résoudre n'est pas aussi élevée qu'on le pensait auparavant. En entraînant un modèle à simplement compléter un motif, les chercheurs ont débloqué la capacité de créer des défis valides et complexes. Le modèle n'avait pas besoin d'être un grand maître du jeu pour créer un jeu digne d'intérêt ; il avait seulement besoin de comprendre les règles des carreaux. Cette approche offre une nouvelle façon de penser l'intelligence artificielle, suggérant que si nous enseignons à un système à comprendre les relations locales au sein d'un monde complexe, il peut naturellement apprendre à naviguer dans les défis globaux de ce monde sans jamais y être explicitement formé. Les puzzles générés n'étaient pas parfaits, mais ils étaient suffisamment proches pour qu'un petit ajustement puisse les rendre fonctionnels, prouvant que le modèle avait saisi l'essence même du jeu.