McConnell & Zhao : générer en temps réel des puzzles au niveau de difficulté « idéal » par algorithme génétique — Lu par Fukai

Résumé en un paragraphe

Ce que j'ai choisi aujourd'hui, c'est un article rapportant la tentative de créer des puzzles « sur le moment » avec un algorithme génétique et d'adapter la difficulté à chaque joueur. Le sujet est un puzzle de tracé de chemin très semblable à Cosmic Express, où l'on transporte des marchandises en un seul trait. Les auteurs enregistrent la façon dont les joueurs résolvent les puzzles (temps passé, nombres d'essais, nombre de fois où ils étaient presque à la solution, etc.), déterminent la prochaine difficulté à partir de ces données, puis génèrent un puzzle correspondant à cette difficulté avec un algorithme génétique (une méthode imitant l'évolution biologique pour trouver progressivement de bonnes solutions), à raison d'environ 7 secondes par puzzle.

Dans une expérience à petite échelle de 18 personnes, la version ne se fiant qu'au temps s'est clairement montrée inférieure, et la version utilisant plusieurs indicateurs a obtenu de meilleures évaluations pour « la difficulté est bien calibrée » et « j'ai le sentiment de progresser ». C'est un article orienté implémentation qui relie directement génération en temps réel et ajustement adaptatif de la difficulté. Cet article suffit pour saisir ce qui a été créé, comment, et ce qui a été découvert.

Introduction

L'article est « From Frustration to Fun: An Adaptive Problem-Solving Puzzle Game Powered by Genetic Algorithm » de Matthew McConnell et Richard Zhao (département d'informatique de l'Université de Calgary, Canada). La source de cet article est un prétirage publié sur arXiv en septembre 2025 (arXiv:2509.23796). Le manuscrit porte la mention de droits d'auteur de l'AAAI (association d'intelligence artificielle) et des remerciements aux évaluateurs anonymes ; on peut comprendre qu'il a été préparé ou accepté pour une présentation dans le cadre de l'AAAI, mais je traite la version arXiv comme source dans la mesure où je peux la vérifier.

Je l'ai choisi parce que c'est exactement au cœur des sujets traités par Puzzlebyrinth. La génération automatique de puzzles de tracé de chemin, la quantification de la difficulté, la modélisation du joueur (estimer « le niveau actuel de cette personne » à partir de l'enregistrement du jeu) et l'ajustement dynamique de la difficulté (mécanisme d'augmentation et de diminution de la difficulté en cours de jeu, DDA = Dynamic Difficulty Adjustment). Tout cela est intégré dans un système jouable, avec même un pseudo-code de l'algorithme. La granularité est telle que les créateurs de jeux peuvent s'en servir directement, ce que j'apprécie.

Un point à préciser d'emblée. C'est un nouveau prétirage encore peu cité, et l'expérience principale n'est qu'une étude pilote (préliminaire) de 18 participants. Les résultats que l'on peut « prouver » sont donc rares. Je cite les chiffres de l'article d'origine tels quels, et je distingue clairement à la fin ce qui peut être affirmé de ce qui ne peut pas l'être.

Contexte

L'idée même d'adapter la difficulté à chaque individu n'est pas nouvelle. Aussi bien dans les jeux que dans l'éducation, l'idée selon laquelle « trop facile ennuie, trop difficile décourage, entre les deux se trouve l'immersion (le flux) » est utilisée depuis longtemps. Les auteurs prennent aussi comme point de départ un savoir classique selon lequel l'enseignement individualisé est extrêmement efficace pour l'apprentissage (l'idée montrée par Bloom en 1984 selon laquelle un élève moyen bénéficiant d'un enseignement individuel se situe à 2 écarts-types au-dessus de la moyenne en cours ordinaire).

Qu'est-ce qui manquait alors ? Selon l'analyse des auteurs, la plupart des systèmes d'apprentissage adaptatifs existants fonctionnent « hors ligne ». C'est-à-dire qu'ils analysent les données après coup pour les utiliser la fois suivante, et les systèmes qui modifient le contenu sur le moment pendant le jeu sont rares. De plus, l'indicateur le plus largement utilisé pour l'adaptation a été le time-on-task (le temps passé sur la tâche), mais son efficacité seule a rarement été vérifiée.

Cette recherche s'attaque donc à deux points : (1) créer un système d'ajustement de difficulté en ligne en temps réel comparable à une référence non adaptative, et (2) isoler l'indicateur unique du temps pour questionner son efficacité même. La génération repose sur l'algorithme génétique, méthode représentative de la PCG (génération procédurale de contenu).

Approche

D'abord, le jeu lui-même. Les auteurs ont créé APSG (Adaptive Problem-Solving Game) avec Unity. Le sujet est un puzzle de tracé de chemin inspiré de Cosmic Express (Hazelden, Davis, Tyu, 2017). Sur une grille n×n, on trace un chemin (sans embranchement) du départ à l'arrivée. Un conteneur avance case par case le long du chemin, ne pouvant transporter qu'une marchandise à la fois. On ramasse la marchandise au point de chargement désigné et on la dépose au point de déchargement désigné. Le chemin ne peut pas se croiser, et il faut réfléchir à l'ordre pour résoudre le puzzle. La difficulté est principalement déterminée par la taille de la grille, le nombre de points de chargement/déchargement et la configuration des cases spéciales.

C'est l'algorithme génétique qui crée chaque puzzle sur le moment. Pour décrire son mécanisme en mots : on prépare d'abord un ensemble de candidats-puzzles, on attribue à chacun un score (aptitude = fitness) indiquant « à quel point il se rapproche de la difficulté visée ». On sélectionne ceux qui ont les meilleurs scores comme parents, on les croise (crossover), on les fait légèrement muter (mutation) au hasard pour créer des enfants. En répétant cela sur plusieurs générations, le puzzle se rapproche progressivement de la difficulté visée. Les auteurs utilisent la structure NSFI-2POP de Scirea (2020) comme base.

Le croisement comporte une ingéniosité. Le puzzle est représenté par une carte de caractères bidimensionnelle (# vide, X chemin, P chargement, D déchargement, S départ, E arrivée, etc.). Si l'on sélectionne une colonne au hasard pour couper les deux parents gauche-droite et les échanger, le chemin se rompt généralement. On le rebouche avec BFS (recherche en largeur d'abord, qui trouve le chemin le plus court en explorant d'abord les cases proches), et les points de chargement/déchargement sont repositionnés par distance dans chaque section délimitée par le chemin. On vérifie ensuite obligatoirement si le puzzle est soluble. Une réparation est intégrée pour que la génération ne produise pas de solution incorrecte.

L'aptitude varie selon « quelle difficulté viser ». Les auteurs définissent des valeurs cibles pour la longueur du chemin (8~50), les virages (0~20), les cases vides, le nombre de chargements (1~12), les chargements orthogonaux, etc., et interpolent ces cibles selon la difficulté 1~10. Le score est une somme pondérée de « à quelle distance de la cible se trouve-t-on » pour chaque élément (sans utiliser de formule, c'est en gros une forme de déduction plus on s'éloigne de la cible).

Alors, qui décide de la difficulté visée ? Le modèle de joueur. Le système observe l'état du joueur et propose « augmenter/diminuer/maintenir » pour le prochain puzzle. Les matériaux sont le temps de résolution, le nombre d'essais, le retour en arrière (nombre de fois où une partie du chemin tracé a été effacée pour recommencer), le nombre de réinitialisations, et le nombre de fois où le joueur était presque à la solution (moins de 25 % de points spéciaux manqués). Ce qui est intéressant, c'est que le nombre d'essais est traité comme une « contrainte dure » (filet de sécurité à respecter obligatoirement ; la difficulté n'est pas augmentée quand les échecs sont nombreux), tandis que les autres sont traités comme des « contraintes douces » dont la somme pondérée détermine en douceur l'ampleur de la hausse ou de la baisse.

Les paramètres utilisés dans l'expérience sont : taille de la population 300, taux de croisement 80 %, nombre de générations maximum 10, grille maximale 10×10. Avec ce réglage, les puzzles de toute difficulté pouvaient être générés en environ 7 secondes, selon les auteurs. En augmentant la population, les générations et la grille, on peut créer des puzzles plus grands et plus complexes, mais le temps de génération augmente considérablement, reconnaissent-ils franchement.

Résultats

L'expérience comptait 18 participants. Chacun a joué aux 3 versions de l'APSG. Standard (version utilisant tous les indicateurs du modèle de joueur), Increasing (version augmentant la difficulté de 1 quel que soit le résultat), Time-based (version utilisant uniquement le temps comme indicateur). L'ordre de présentation variait selon les personnes pour réduire les biais de familiarisation. Dans l'ensemble, les réactions étaient favorables : 89 % se sentaient « stimulés intellectuellement », 94,5 % avaient « utilisé leurs capacités de résolution de problèmes », 72,2 % estimaient que le jeu « nécessitait une réflexion critique » (dans tous les cas, accord/tout à fait d'accord).

Les comparaisons essentielles, avec les chiffres de l'article d'origine. « Frustration réduite » (1~10, plus élevé = mieux) : Standard 6,47, Increasing 6,94, Time-based 6,83 ; l'ANOVA (analyse de variance, test examinant les différences de moyennes entre plusieurs groupes) ne montre pas de différence significative (F(2,51)=0,072, p=0,93). En revanche, « difficulté bien calibrée » : Standard 6,06, Increasing 5,67, Time-based 4,44, avec une différence (p=0,039) ; l'écart entre Standard et Time-based était particulièrement net (p=0,004, taille d'effet Cohen's d=0,869 ; la taille d'effet est un indicateur de l'ampleur de la différence).

« Sentiment que la difficulté a changé » : Standard 8,17, Increasing 7,56, Time-based 6,89 (pas de différence significative, p=0,149). « Sentiment de progression » : Standard 8,56, Increasing 7,5, Time-based 6,0, avec une différence nette ici (p=0,005, Standard vs Time-based : p<0,001, d=1,083). Les données du journal montrent que Standard et Increasing avaient presque la même difficulté moyenne (5,53 et 5,50), tandis que Time-based était à 3,87, résolue en moyenne 25,67 secondes plus vite que le benchmark. L'interprétation est que la difficulté n'a pas pu être suffisamment augmentée.

En résumé, la version utilisant plusieurs indicateurs obtenait globalement de meilleures évaluations sur les indicateurs de ressenti, et la version ne se fiant qu'au temps a montré la faiblesse de « facilement rester à un niveau simple ». Les auteurs fondent sur cela leur orientation à affiner le type Standard comme noyau à l'avenir. Cependant, le fait que de nombreuses différences entre Standard et Increasing ne soient pas statistiquement significatives est aussi clairement mentionné par les auteurs eux-mêmes.

Applications pratiques

Je liste concrètement les utilisations pratiques pour les créateurs de jeux et de puzzles. D'abord, si vous créez des puzzles de tracé de chemin de type Cosmic Express ou Sokoban (仓库番), la fonction d'aptitude de cet article peut directement servir de curseur de difficulté. Définir des valeurs cibles pour des « quantités mesurables » telles que longueur du chemin, virages, cases vides, nombre de chargements et chargements orthogonaux, puis générer en conséquence. Saisir la difficulté en chiffres plutôt qu'en mots facilite la production en série par tranches de difficulté.

Ensuite, si vous mettez en place une PCG pour un hypercasuel, la leçon « ne pas se fier qu'au temps » sera utile. Cet article utilise conjointement le retour en arrière, la réinitialisation et le nombre de presque-solutions, et a mesuré la faiblesse de la version ne se fiant qu'au temps. Plus la couche de joueurs décrocheurs est grande, plus il est utile de détecter les blocages tôt avec plusieurs signaux comportementaux et d'affiner la difficulté du prochain puzzle.

Troisièmement, si vous êtes aux prises avec les « corruptions » des puzzles générés, la conception consistant à réparer le chemin avec BFS après le croisement, puis à vérifier systématiquement s'il est soluble, peut être empruntée telle quelle. Non limitée au GA, l'idée de réparer plutôt que rejeter les candidats corrompus après synthèse est efficace pour tous les puzzles à fortes contraintes. De plus, comme quatrième point, comme le mentionnent les auteurs parmi les applications futures, cela peut également s'étendre à l'ajustement de la difficulté des puzzles logiques, des exercices de mathématiques, des exercices pour apprenants ayant des troubles d'apprentissage. Au-delà du jeu, le contexte éducatif est dans la ligne de mire.

Limites

D'abord, les faiblesses reconnues par les auteurs eux-mêmes. Les participants ne sont que 18 personnes, et les résultats en sont au stade pilote. Ce qui est décisivement important, c'est l'absence de comparaison avec une version entièrement non adaptative (référence statique) : sans cela, il est impossible d'affirmer strictement « à quel point la frustration a été réduite », comme l'écrivent les auteurs. L'indicateur temporel n'a été isolé et évalué seul, et l'ablation study qui vérifierait l'efficacité en retirant les indicateurs un à un (expérience vérifiant quelle partie de la conception est efficace en retirant les éléments un par un) est renvoyée aux travaux futurs. Les seuils sont également décidés par groupe, ce qui élimine les différences individuelles.

Ce qui suit relève de ce que Fukai a remarqué en lisant. Premièrement, le temps de génération d'environ 7 secondes, si cela s'exécute de manière synchrone, risque d'interrompre le rythme. Cet article ne problématise pas cela, mais cela est en tension avec le sentiment de « passer vite au suivant » dans les puzzles commerciaux. Deuxièmement, de nombreuses différences entre Standard et Increasing ne sont pas significatives (puissance insuffisante avec 18 participants). Donc « Standard est le meilleur » est une suggestion, pas une preuve, c'est mon interprétation.

Troisièmement, ce qui me préoccupe le plus, c'est que l'aptitude mesure des « indicateurs de substitution de la difficulté » tels que la longueur du chemin et les virages, et non la difficulté cognitive ressentie par les gens elle-même. Les indicateurs de substitution et le ressenti peuvent diverger. En fait, dans cette expérience aussi, la résistance perçue et la difficulté objective ne s'alignent pas forcément en ligne droite. Enfin, le sujet Cosmic Express est un jeu commercial, et une reproduction « inspirée » nécessite des précautions en matière de droits — c'est une note à l'intention des implémenteurs, distincte des arguments de l'article.

La lecture de Fukai

Je précise que ce qui suit est mon interprétation. Je voudrais situer cette recherche dans le mouvement de déplacement du centre de gravité de la PCG, passant de « créer le plus de diversité possible » à « créer en s'adaptant au joueur qui est là, devant soi ». Dans le vocabulaire de la critique de conception, cela ressemble à l'automatisation de l'ajustement que les level designers faisaient implicitement — « lire l'adversaire et jouer le coup suivant ». Ce qui est intéressant, c'est que cette automatisation n'est pas réalisée par un apprentissage automatique avancé, mais par des outils lisibles et éprouvés comme l'algorithme génétique et des contraintes écrites à la main. En termes de reproductibilité, je suis enclin à apprécier justement cette sobriété.

Pour aller plus loin

Pour ceux qui souhaitent approfondir, je trace une ligne susceptible de servir de carte. L'algorithme génétique de cet article prend pour base la « génération adaptative de puzzles pour la pensée computationnelle » de Scirea (2020) ; si vous voulez creuser côté génération, commencez par là. Si vous voulez une vue d'ensemble de la PCG, « Procedural Content Generation in Games » de Shaker, Togelius et Nelson est la référence standard. Si la modélisation des joueurs et la DDA vous intéressent, en remontant les branches des recherches connexes depuis la revue DDA (Lopes & Lopes, 2022) dans les références de cet article, vous verrez à quelle position se situe celui-ci. Ensuite, je voudrais moi-même trouver et lire des recherches mesurant frontalement l'écart entre les indicateurs de substitution et le ressenti.

Je répète : il s'agit d'un prétirage basé sur une étude pilote de 18 personnes, qui n'a pas encore été largement débattue. C'est précisément pourquoi je le considère comme un article propice à rapporter avec soi, sans se précipiter vers des conclusions, en retenant « ce qui peut être affirmé et ce qui ne peut pas l'être ». Ce matin encore, j'ai lu cet article en tenant un thé vert chaud et fort, en traçant des lignes au feutre de couleur sur ce PDF imprimé.

Références

Articles et ressources cités dans cet article :

・From Frustration to Fun: An Adaptive Problem-Solving Puzzle Game Powered by Genetic Algorithm (McConnell & Zhao, 2025, arXiv preprint 2509.23796)

・Version HTML du même article (texte, figures et pseudo-code de l\'algorithme vérifiés)

・Recherche connexe : Scirea, M. (2020) "Adaptive puzzle generation for computational thinking" (base de la structure NSFI-2POP de l'algorithme génétique de cet article)

・Recherche connexe : Shaker, Togelius & Nelson (2016) "Procedural Content Generation in Games" (référence standard sur la PCG)

・Recherche connexe : Lopes & Lopes (2022) "A review of dynamic difficulty adjustment methods for serious games" (revue sur la DDA)

・Jeu source : Cosmic Express (Hazelden, Davis & Tyu, 2017)