Génération procédurale de puzzles : pourquoi vérifier compte

En 2011, Julian Togelius, Georgios Yannakakis, Kenneth Stanley et Cameron Browne ont cartographié un domaine en pleine croissance et lui ont donné un nom : la génération procédurale de contenu fondée sur la recherche (search-based). Leur revue classe les générateurs selon ce qu’ils produisent, la manière dont ce contenu est représenté dans le programme et, surtout, la façon dont sa qualité est évaluée. L’approche par recherche traite la conception de niveaux comme un problème d’optimisation. On génère des candidats, on attribue à chacun un score grâce à une fonction d’évaluation, on garde les meilleurs, on les fait varier, et on recommence, souvent avec des algorithmes évolutionnaires empruntés à la biologie.

C’est dans la fonction d’évaluation que se loge la conception. Elle peut mesurer un niveau directement (combien de pièces, combien d’espace vide), par simulation (laisser un joueur artificiel essayer et voir ce qui se passe) ou de manière interactive (demander à de vrais joueurs). Chaque méthode a un coût. Les mesures directes sont bon marché mais superficielles. La simulation est plus fidèle mais exige un programme capable de jouer réellement au jeu. Interroger des gens est le plus fidèle, et de loin le plus lent.

Pour un puzzle de blocs coulissants, c’est facile à imaginer. Un candidat est une grille sur laquelle sont posées des briques. Une variation déplace, ajoute ou retire une brique. Une mesure directe peut compter à quel point le plateau est encombré ; une mesure par simulation confie le plateau à un solveur et note s’il peut être vidé et la longueur du chemin trouvé. On garde les plateaux qui obtiennent un bon score, on les fait varier à nouveau, et après des milliers de tours le générateur a dérivé vers ce que récompense la fonction d’évaluation. C’est sa force et son danger : il trouvera exactement ce que vous avez demandé, y compris des plateaux qui satisfont les chiffres et ennuient le joueur.

Sources1Source 1Togelius, J., Yannakakis, G. N., Stanley, K. O., & Browne, C. (2011). Search-based procedural content generation: A taxonomy and survey. IEEE Transactions on Computational Intelligence and AI in Games, 3(3), 172–186.

Une autre école part de l’autre bout. Plutôt que de faire évoluer des plateaux en espérant que de bons émergent, Adam Smith et Michael Mateas ont proposé de décrire explicitement l’espace des conceptions acceptables, sous forme de contraintes logiques, et de laisser un solveur généraliste trouver les plateaux qui les satisfont. Grâce à une technique appelée programmation par ensembles réponses (answer set programming), un concepteur peut écrire des règles comme « la sortie doit être accessible » ou « cette pièce doit bouger au moins deux fois », et ne recevoir que des plateaux qui les respectent.

L’intérêt pour la conception de puzzles saute aux yeux. Beaucoup de ce qui rend un plateau intéressant tient en contraintes : telle brique doit être bloquée par telle autre, telle clé doit être nécessaire. Les écrire oblige le concepteur à dire ce qu’il veut vraiment, une discipline aussi utile aux humains qu’aux machines.

Sources2Source 2Smith, A. M., & Mateas, M. (2011). Answer set programming for procedural content generation: A design space approach. IEEE Transactions on Computational Intelligence and AI in Games, 3(3), 187–200.

Quel que soit le générateur, un puzzle doit d’abord être soluble, et le prouver est souvent l’étape la plus difficile. Noor Shaker, Mohammad Shaker et Julian Togelius s’y sont heurtés avec Cut the Rope, un puzzle physique au temps et à l’espace continus, où une recherche exhaustive est sans espoir. Leur réponse : un agent de raisonnement qui ne proposait que des coups sensés à chaque état, ce qui réduisait assez la recherche pour qu’un simple parcours en profondeur trouve des solutions et confirme que les niveaux générés étaient jouables.

Bilal Kartal, Nick Sohre et Stephen Guy ont pris une autre voie pour Sokoban, le classique puzzle où l’on pousse des caisses. Leur générateur construit les puzzles par des parties simulées, à l’aide d’une recherche arborescente Monte-Carlo, si bien que chaque puzzle produit est soluble par construction. Les puzzles de blocs coulissants sont eux aussi un cas difficile : le problème général est PSPACE-complet, comme l’explique notre histoire des puzzles de blocs coulissants, et aucun raccourci connu ne résout rapidement tous les plateaux.

Sources3Source 3Shaker, N., Shaker, M., & Togelius, J. (2013). Evolving playable content for Cut the Rope through a simulation-based approach. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 9(1), 72–78.4Source 4Kartal, B., Sohre, N., & Guy, S. (2016). Data driven Sokoban puzzle generation with Monte Carlo tree search. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 12(1), 58–64.

Un plateau peut avoir une solution et rester terne, ou n’être soluble que par un chemin qu’aucun humain ne trouverait. Kartal et ses collègues ont attaqué ce problème de front. Ils ont mené une étude auprès d’utilisateurs pour trouver des caractéristiques de plateaux peu coûteuses à calculer et corrélées à la difficulté ressentie, les ont combinées en une fonction de score, puis ont confirmé dans une seconde étude que les puzzles au score plus élevé étaient perçus comme plus difficiles. Autrement dit, la difficulté a dû être apprise auprès des gens, pas supposée.

Yannakakis et Togelius généralisent ce point dans leur cadre de génération procédurale guidée par l’expérience : modéliser l’expérience du joueur, à partir de son comportement, de ses déclarations ou de sa physiologie, et générer du contenu pour la façonner. C’est un objectif ambitieux, et en toute honnêteté, les modèles du plaisir et de la frustration restent grossiers. Pour un puzzle, des qualités comme l’élégance, le « déclic » satisfaisant et la justesse sont encore plus faciles à reconnaître qu’à calculer. Nous examinons ce que la justesse signifie pour les joueurs dans qu’est-ce qui rend un puzzle juste.

Sources4Source 4Kartal, B., Sohre, N., & Guy, S. (2016). Data driven Sokoban puzzle generation with Monte Carlo tree search. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 12(1), 58–64.5Source 5Yannakakis, G. N., & Togelius, J. (2011). Experience-driven procedural content generation. IEEE Transactions on Affective Computing, 2(3), 147–161.

Pour les joueurs, une règle empirique utile en découle. « Niveaux infinis » vous apprend qu’un générateur existe ; cela ne vous dit pas comment ses niveaux sont testés. Cherchez des jeux qui expliquent comment ils vérifient leurs plateaux, et méfiez-vous quand la difficulté fait des bonds au hasard : c’est souvent le signe que rien ne la modélise.

Quelques autres signes d’une série de puzzles bien faite, générée ou non : les idées nouvelles arrivent une par une, comme le recommande la recherche sur le rythme des puzzles ; les plateaux paraissent distincts plutôt que des quasi-copies avec une pièce déplacée ; et quand vous êtes bloqué, vous croyez qu’une solution existe. Ce dernier point est le plus difficile à simuler, et celui que les générateurs ont mis le plus longtemps à mériter.

Les 2 000 plateaux d’OutBrick forment un ensemble fixe et conçu, et non un flux généré sur votre appareil, et chacun a vu son chemin de résolution rejoué selon les règles mêmes du jeu avant la sortie. Nous décrivons ce processus, y compris pourquoi un solveur à court de budget signifie « inconnu » et non « impossible », dans comment nous avons vérifié 2 000 plateaux de blocs coulissants. Un solveur prouve qu’un chemin existe ; il ne prouve pas que le plateau est amusant, c’est pourquoi le rythme est jugé à part. Vous pouvez constater le résultat par vous-même sur le plateau du jour.