Le graphe qui a battu la grille : pourquoi les modèles GAT surpassent les CNNs dans les tests de jeu de Candy Crush

Depuis des années, les tests de jeu automatisés des jeux de puzzle basés sur une grille s'appuient sur les réseaux de neurones convolutionnels. Leur capacité à extraire des motifs spatiaux des états du plateau en faisait un choix naturel. Mais une nouvelle étude comparative menée par des chercheurs de King Digital Entertainment, le studio derrière Candy Crush Saga, suggère que l'architecture la plus courante n'est peut-être pas la meilleure pour cette tâche.

L'article, dirigé par Kleio Fragkedaki et ses collègues, oppose les CNN à deux alternatives : un modèle transformer basé sur BERT et un réseau d'attention de graphe (GAT). L'objectif est de déterminer lequel peut prédire le plus précisément les mouvements des joueurs et estimer la difficulté des niveaux parmi les plus de 18 000 niveaux de Candy Crush Saga, dont beaucoup introduisent des mécaniques qui brisent les hypothèses des modèles basés sur une grille.

Pourquoi les grilles sont insuffisantes

Les CNN traitent le plateau de jeu comme une image de taille fixe, encodant le contenu de chaque tuile dans des couches de canaux séparées. Cela fonctionne bien pour les plateaux statiques, mais les concepteurs de Candy Crush continuent d'ajouter de nouveaux éléments : des portails qui téléportent des bonbons à travers le plateau, des tuiles spéciales qui interagissent de manière non locale, et des objectifs qui varient d'un niveau à l'autre. Chaque nouvelle fonctionnalité force une réingénierie de la représentation d'entrée du CNN, ajoutant des canaux, ajustant les tailles de noyaux, et réentraînant le modèle depuis zéro.

Le modèle GAT contourne cela en représentant le plateau comme un graphe. Les tuiles deviennent des nœuds, et les relations, l'adjacence, les connexions de portails, deviennent des arêtes. Le mécanisme d'attention apprend ensuite à pondérer ces connexions de manière dynamique, capturant des dépendances à longue portée avec lesquelles les CNN peinent.

Des chiffres qui parlent

Le résultat principal de l'étude : GAT atteint une précision de prédiction de mouvement top-1 de 54,37 %, légèrement devant le CNN avec 53,33 %, et le dépasse sur les métriques top-2, top-3 et top-6. Mais l'écart réel apparaît dans l'estimation de la difficulté, où le modèle GAT complet affiche une erreur absolue médiane de 1,61 sur tous les niveaux contre 1,98 pour le CNN. Sur les niveaux difficiles, l'erreur de GAT tombe à 10,03 contre 14,00 pour le CNN.

Peut-être plus révélateur : lorsque les connexions de portails sont incluses dans l'entrée du graphe, la performance de GAT sur les niveaux avec portails s'améliore, atteignant une erreur médiane de 10,69 sur les niveaux difficiles avec portails contre 15,24 pour le CNN. Il s'agit d'une capacité que les CNN ne peuvent tout simplement pas reproduire, car les portails connectent des tuiles non adjacentes de manière à briser l'hypothèse spatiale locale des filtres convolutionnels.

BERT peine à s'adapter au plateau

Les modèles basés sur BERT, adaptés pour encoder les états du plateau sous forme de séquences de texte ou de jetons matriciels, ont mal performé. La variante textuelle n'a atteint qu'une précision top-1 de 22,20 %, et la version basée sur le plateau a atteint 35,84 %. Les deux sont bien derrière le CNN et le GAT. Les chercheurs notent que le manque de priori spatial dans l'architecture du transformer nuit probablement à la performance sur un problème aussi structuré, malgré ses forces dans les tâches linguistiques.

Ces résultats suggèrent que GAT offre une voie médiane : il conserve la capacité des CNN à capturer les motifs locaux tout en gagnant la flexibilité de modéliser des relations arbitraires, le tout sans nécessiter d'ingénierie manuelle de caractéristiques pour chaque nouvelle mécanique de jeu.

Ce que cela signifie pour les tests de jeu automatisés

Les tests de jeu automatisés sont un outil essentiel pour les studios de jeux, leur permettant de tester des centaines de niveaux à grande échelle avant la sortie. Le flux de travail standard consiste à entraîner un modèle sur des données historiques de joueurs, puis à utiliser ce modèle pour simuler des parties et estimer des métriques de difficulté comme le nombre de tentatives par succès (Attempts Per Success, APS). Une estimation précise de la difficulté permet aux concepteurs de régler les niveaux avant qu'ils ne frustrent les vrais joueurs.

Le principal enseignement de l'étude : choisir la bonne représentation d'entrée importe plus que de sélectionner la dernière architecture. L'approche basée sur un graphe de GAT correspond naturellement à la structure relationnelle des plateaux de jeu, tandis que les CNN imposent une vue centrée sur la grille qui se brise à mesure que les jeux évoluent. Pour les studios gérant des titres avec plus de 10 000 niveaux et des mises à jour régulières de contenu, le passage des CNN au GAT pourrait signifier moins de cycles de réentraînement et une qualité de test de jeu plus constante.

Des travaux futurs pourraient explorer des architectures hybrides, combinant les forces relationnelles de GAT avec le traitement séquentiel basé sur les transformers pour une modélisation plus nuancée des joueurs, mais pour l'instant, le graphe a prouvé son avantage.