Le jeu vidéo est un domaine logiciel hors du commun par ses forces motrices créatives, d’immersion et d’interaction. Ces aspects des projets de jeu sont apparents même dans la rhétorique utilisée par les concepteurs de jeu, comme dans l’adage « trouver le plaisir » (en anglais find the fun) qui désigne une des premières étapes créatives. Lorsque les mécaniques au cœur du jeu sont identifiées et que le développement débute, le rôle des spécialistes d’assurance qualité (AQ) est de s’assurer que ces mécaniques fonctionnent tel qu’attendu. Bien que des fonctionnalités puissent être intentionnellement altérées, ajoutées, ou retirées durant le développement, une grande partie du temps des spécialistes d’AQ est passé à vérifier que les mécaniques existantes fonctionnent sans altération accidentelle après chaque modification. Tandis que le jeu grandit en taille et en complexité, il en va de même pour le nombre de tests et le temps requis pour les effectuer. Il s’agit d’un problème qui transcende l’industrie du jeu vidéo, comme le démontre la création de l’Automated Testing Roundtable (Table ronde du test automatisé) à la GDC (Game Developer Conference) depuis 20181, ainsi qu’un nombre grandissant de publications sur des approches de plus en plus ambitieuses pour automatiser les aspects les plus pénibles de l’assurance qualité. Pour faire face à ce défi, l’équipe de Tests de jeu automatisés (en anglais Automated Game Testing ou AGT) présente une nouvelle méthodologie de tests qui découple la validation des mécaniques de jeu des étapes de reproduction des tests fonctionnels en utilisant une structure de données simple appelée le plan explicite (PE).
Les tests logiciels
Un test logiciel dans sa version la plus simple se décline conceptuellement en trois phases :
- Initialiser – Initialiser le système à une configuration connue
- Exécuter – Faire tourner la fonction que nous désirons tester
- Valider – Mesurer si la fonction exécutée a eu l’impact attendu sur l’état du système
Considérons un exemple de test fonctionnel pour un jeu vidéo. Pour le jeu classique Super Mario Bros, imaginons un test qui valide que lorsqu’un joueur est au menu principal et envoie l’entrée Start [une entrée (input en anglais) est tout signal envoyé par le joueur et reçu par le jeu] alors le monde 1-1 est chargé. Ici, la phase d’exécution est simple car elle consiste en une seule étape.
Envisageons maintenant un test qui comprend plus d’une étape, par exemple : valider que le joueur peut éliminer le premier Goomba du monde 1-1 dans le monde Start. Les trois phases de test, Initialiser, Exécuter, et Valider seraient :
- Initialiser l’état du jeu au monde 1-1
- Exécuter une liste prédéterminée d’actions (ex., Droite, Droite, Saut, …) pour déplacer Mario et sauter sur le Goomba
- Valider si Mario est parvenu à sauter sur le Goomba
Cet exemple est encore suffisamment simple pour imaginer l’implémenter avec un script. Et si on voulait plutôt tester si Mario peut vaincre Bowser? On pourrait toujours initialiser le jeu dans le monde de départ, mais la liste d’étapes dont nous aurions besoin pour atteindre la fin du jeu serait gigantesque. Ce n’est pas réaliste de scripter un tel test. De plus, si le jeu était en développement, il faudrait fréquemment éditer la liste d’entrées pour qu’elle demeure applicable et tienne compte des changements.
Il faut noter qu’une méthode où on enregistrerait automatiquement les entrées d’un joueur humain pour ensuite les rejouer automatiquement ne serait viable que si le jeu était entièrement déterministe. En effet, s’il y a un tant soit peu de hasard, qu’il soit voulu (ex. apparition d’ennemis aléatoire) ou non (ex. multiprocesseur ou communication réseau), puisque la liste d’entrées n’est pas forcément robuste à cette variabilité, alors le test peut échouer dû à une accumulation d’erreurs. Les difficultés ci-haut demeurent présentes même pour des jeux complétés. Si le jeu est plutôt en développement, alors des modifications sont régulièrement apportées par les développeurs et les artistes. Certains de ces changements requièrent d’éditer les tests, ce qui serait fastidieux et instable au mieux, et ingérable au pire.
La solution habituelle pour les tests complexes est de demander à une personne de jouer au jeu. Les êtres humains peuvent s’adapter à différentes configurations de contrôle, ils ont une intuition de comment jouer à un jeu vidéo, ils peuvent noter ce qu’ils ont fait, et possiblement offrir des solutions aux bogues qu’ils trouvent.
Le plan explicite
Nous avons relevé deux problèmes principaux qui surviennent si l’on cherche à automatiser la phase d’exécution en reproduisant naïvement une liste d’entrées : 1) même pour des parcours simples, la liste peut être très grande et nécessiter trop de maintenance; et 2) elle ne peut pas tenir compte du hasard et du non-déterminisme. Pour remédier à ces difficultés, nous avons conçu une structure alternative plus souple et puissante, que nous appelons le plan explicite.
Encodage compact de la phase d’exécution
Considérons un type de jeu où le joueur contrôle un personnage qui peut parcourir un environnement. Les tests de fonctionnalité dans un tel environnement exigent souvent de parcourir des sections de niveaux de jeu en exécutant diverses actions. Nous avons remarqué que la plupart des entrées d’un joueur effectuant ce type de test servent à la navigation entre les différents acteurs ou emplacements d’intérêt. Le reste des entrées sont en général des actions de jeu effectuées sur ces acteurs ou emplacements cible. Dans le cadre du test automatisé, nous donnons un sens spécial au mot action, qui sert à référer à de telles actions de jeu autres que la navigation. De plus, nous appelons un nœud combinaison d’une destination cible (un acteur ou un emplacement d’intérêt) et d’une action qui y est effectué. En supposant que la navigation soit gérée par un système distinct, nous pouvons grandement simplifier la liste d’informations encodant la phase d’exécution d’un test en ne stockant que les destinations d’intérêt et les actions sous forme de nœuds. La figure 5 montre comment une longue liste d’entrées brutes peut être réduite à une liste chaînée de nœuds.
Pour automatiser la navigation, nous pouvons tirer profit de solutions fournies dans les moteurs de jeu modernes, comme la simple téléportation du joueur, ou les maillages de navigation (de l’anglais navigation mesh ou navmesh). De plus, la navigation vers un acteur étant une tâche commune pour une IA de jeu, trouver et parcourir un trajet demeure faisable même si la cible se déplace, que ce soit par son comportement dynamique, ou par l’action d’un concepteur. Il s’agit là d’une source de non-déterminisme de moins à gérer.
Bien que ces stratégies de navigation aient leurs limites (que nous abordons plus bas), elles sont faciles d’accès et servent de base solide et suffisante dans de nombreux cas.
Gérer les actions imprévues
D’autres sources de variabilité peuvent faire en sorte qu’un test ne se déroule pas exactement de la même façon d’une session à l’autre. Les jeux modernes sont souvent dynamiques et le personnage joueur peut avoir besoin de dévier du plan explicite pour s’occuper d’une menace soudaine.
Pour ce faire, nous permettons aux spécialistes d’AQ de spécifier des comportements dynamiques sous la forme de triplets contenant :
- Une liste de préconditions
- Un indice de priorité
- Une action
Nous appelons un tel triplet une règle. Lorsque toutes les préconditions d’une règle sont remplies, l’action associée s’exécute. Si plusieurs règles s’appliquent à la fois, celle qui a la plus haute priorité précède. Par exemple, on peut spécifier d’effectuer l’action attaquer lorsqu’un acteur de type ennemi est détecté à proximité.
Nous appelons plan explicite (PE) la combinaison d’une liste de nœuds et d’un ensemble de règles qui implémentent la phase d’exécution d’un test fonctionnel (Figure 6). Pour suivre un plan explicite, un agent doit se rendre à chaque nœud dans l’ordre et, une fois le nœud atteint, effectuer l’action spécifiée s’il y a lieu. Si à quelque moment que ce soit un sous-ensemble de règles voit ses préconditions remplies, la séquence de nœuds est interrompue temporairement et le comportement spécifié par la règle possédant la plus haute priorité est effectuée. Lorsqu’il n’y a plus aucune règle applicable, la séquence de nœuds est reprise là où elle avait été laissée. En utilisant des stratégies de navigation disponibles telles que celles mentionnées plus haut, il est dès lors possible de créer un agent d’IA simple qui puisse suivre un tel plan explicite. Nous nommons de tels agents les agents à plan explicite (APE).
Validation des actions
Le plan explicite correspond à la phase exécuter d’un test fonctionnel. Nous devons maintenant implémenter les deux autres phases (initialiser et valider) pour pouvoir procéder au test complet.
Avec l’APE, nous savons toujours exactement quand une action est sur le point d’être effectuée. Nous pouvons donc sonder l’état interne du jeu avant qu’il ne soit modifié avec une fonction de rappel (en anglais callback function), ce qui correspond à la phase initialiser. Nous nommons cette fonction la fonction de rappel pré-action. Ensuite, en prévision de la phase validation, nous créons une autre fonction de rappel qui sera quant à elle soit exécutée après un certain délai, soit déclenchée par un événement. C’est la fonction de rappel post-action.
Voyons un exemple où le plan explicite et les fonctions de rappel sont combinées en un test complet. Considérons un plan explicite qui comporte une règle spécifiant d’attaquer tout ennemi à proximité. Un APE en train d’exécuter ce test croise un ennemi, et interrompt la séquence de nœuds pour avancer vers celui-ci. Une fois assez près, l’agent diffuse un signal signifiant qu’il est sur le point de lancer l’action attaquer. La fonction de rappel pré-action est alors exécutée pour recueillir les données pertinentes sur l’état du jeu (ex. les points de vie de l’ennemi, le compteur d’ennemis tués du joueur). Supposons que le joueur peut tuer l’ennemi d’un seul coup, et que la mort d’un ennemi diffuse toujours un événement correspondant. Nous pouvons alors attacher à cet événement la fonction de rappel post-action. Si elle est appelée, cette fonction mesurera les nouvelles valeurs des variables observées avant l’action, et validera si les changements attendus ont eu lieu. La figure 7 illustre les séquences d’appel requises.
Les valeurs des variables étant stockées et la fonction de validation prête à être appelée, l’APE peut maintenant effectuer l’action attaquer. Si la fonction de rappel post-action est appelée, elle vérifiera que le nouvel état du jeu répond à nos attentes. Dans ce cas, nous voudrions observer une augmentation de 1 sur le compteur d’ennemis tués. Si ce n’est pas le cas ou bien si la fonction n’est pas appelée après un certain délai, le test échouera.
Nous appliquons ce principe à toutes les actions utilisables par l’APE et définissons des fonctions de rappel pré-action et post-action pour toutes. De cette façon, il importe peu si certaines actions sont exécutées à un moment imprévu, par exemple si une règle s’active. La validation des mécaniques de jeu est donc découplée de l’ordre d’exécution des actions nécessaires pour mettre ces mécaniques en jeu. Un des principaux avantages de cette séparation est que l’on peut exploiter la simplicité des plans explicites pour créer rapidement des tests fonctionnels. En plus, nous pouvons utiliser le même système pour recueillir des métriques de performance alors même que l’APE suit certains plans.
Le cycle « pré-action, action, post-action » est l’unité de test la plus simple dans le système d’AGT. Un test qui se compose de plusieurs nœuds et règles échoue si une seule des actions résulte en des valeurs inattendues ou si son délai expire. La vidéo 1 démontre comment un test de complétion de niveau échoue lorsqu’une seule action fait défaut. En effet, lorsque l’action interagir effectuée sur l’acteur de type interrupteur devrait basculer son état, rien ne se produit à cause d’un mauvais positionnement.
Créer un plan explicite
Pour utiliser le système d’AGT, les spécialistes d’AQ doivent spécifier les étapes de leurs tests sous forme de plans explicites. Il s’agit d’un processus analogue à celui de documenter les instructions pour une personne qui devra ensuite effectuer le test manuellement. Notre système supporte trois méthodes pour construire les plans :
L’édition manuelle : Remplir les champs de la structure de données à la main.
Enregistrement de session de jeu : Jouer au jeu et enregistrer la séance.
Text to Plan : Construire le plan en décodant directement une description textuelle.
Ces trois approches partagent les mêmes types de données et sont interopérables. Dans cette section, nous montrons comment ces méthodes peuvent être utilisées pour compléter un simple niveau de donjon (Figure 9). Nous abordons plus en profondeur la façon dont les plans peuvent être extraits à partir de descriptions textuelles à l’aide de techniques de compréhension du langage naturel3 (en anglais Natural Language Understanding ou NLU).
La méthode manuelle
Les plans sont stockés avec un type sérialisable, et sont donc automatiquement interfaçable dans les éditeurs de jeux modernes. L’objet comporte initialement un seul nœud, et il est possible d’en ajouter autant que nécessaire. Tel que discuté à la section précédente, chaque nœud spécifie un emplacement ou un acteur vers lequel naviguer, et optionnellement une action à effectuer une fois cette cible atteinte. Une diversité de paramètres utilitaires, tel qu’un rayon de tolérance, un type de mouvement, un temps d’attente, etc., permet de peaufiner le comportement.
Dans notre niveau exemple, les actions disponibles sont interagir, attaquer et sauter. Pour compléter le donjon, trois nœuds sont nécessaires; le joueur doit d’abord activer l’interrupteur, puis sauter par-dessus le trou de lave, et finalement activer le monument.
Vidéo 2 – Création manuelle d’un plan explicite dans l’éditeur Unreal.
Cette méthode est la plus rudimentaire et assure le plus de flexibilité. Elle est surtout appropriée pour les ajustements fins. C’est la méthode privilégiée pour faire des expériences, ou encore modifier des tests existants, quelle que soit leur méthode de création.
L’enregistrement de session de jeu
Des tests plus complexes ou plus longs peuvent nécessiter la création d’une grande quantité de nœuds. C’est le cas par exemple de tests qui servent à valider des quêtes entières. Il ne serait pas pratique de créer ces tests nœud par nœud, ce qui impliquerait un processus itératif trop long et pénible. Pour y pallier, la méthode d’enregistrement de session de jeu permet aux spécialistes d’AQ de prendre le contrôle du joueur et parcourir eux-mêmes le segment de jeu à imiter. Pendant la session de jeu, des nœuds se créent périodiquement là où le personnage joueur passe, et d’autres à chaque fois qu’une action est effectuée. Le plan explicite obtenu est une bonne approximation de la session de jeu. Il peut toutefois être sensible aux changements de position ou de terrain dans le jeu lorsqu’il est suivi par un APE. Cela étant dit, cette méthode est particulièrement rapide pour placer beaucoup de nœuds et créer un squelette de plan initial. L’édition manuelle peut toujours être utilisée pour parfaire le plan.
Vidéo 3 – Création d’un plan explicite avec l’enregistrement de session de jeu dans l’éditeur Unreal.
Lorsqu’on utilise la méthode d’enregistrement, les positions des nœuds sont des coordonnées du monde. Cela rend le plan vulnérable aux changements de terrain ou à la relocalisation d’objets dans le niveau. Cette méthode n’est pas en mesure d’abstraire l’intention des spécialistes d’AQ lorsqu’ils effectuent une action. La prochaine méthode se positionne quant à elle plus près de l’objectif de haut-niveau de la personne qui crée le test.
Text to Plan
Une partie du travail des spécialistes d’AQ est de déterminer quels tests sont nécessaires et de produire une description des étapes pour les effectuer. Ces instructions peuvent être écrites sous forme de liste. Par exemple, pour tester le niveau de la Figure 9, on pourrait retrouver les étapes suivantes :
- Activer l’interrupteur.
- Sauter par-dessus la lave.
- Interagir avec le monument.
Ces phrases sont suffisantes pour qu’un être humain puisse comprendre et effectuer le test. Ce format a l’avantage d’être intuitif, compact, et expressif. Et si l’on pouvait bâtir un plan explicite directement à partir de ce texte?
En tirant profit de technologies de NLU, la méthode Text to Plan peut transformer un extrait de texte en nœuds ou en règles de plan explicite. Le procédé pour y arriver, actuellement appliqué exclusivement en anglais, comporte 5 étapes :
- En appliquant une classification au niveau de la phrase, déterminer si une phrase représente un nœud ou une règle.
2. En appliquant une la classification au niveau des mots, extraire un mot-clé pour l’action et un mot-clé pour le type d’acteur
3. Faire correspondre les mots-clés extraits avec des valeurs permises en effectuant une analyse de similarité sémantique4
4. Trouver un acteur du type correspondant au type extrait et créer un nœud avec cette instance comme cible, et y assigner l’action extraite. Si aucune instance n’est trouvable, l’action sera simplement effectuée à un emplacement par défaut.
5. Répéter pour chaque phrase d’instruction, et concaténer les nœuds obtenus en une liste.
Un ensemble de règles est construit de la même façon s’il y a des phrases qui sont classifiées comme telles à l’étape 1. La liste de nœuds et l’ensemble de règles sont assemblés pour former un plan explicite.
Cette approche qui fait intervenir des technologies d’apprentissage automatique construit un plan uniquement à partir d’une description textuelle. En effet, nous avons remarqué que le style de phrase utilisé dans ce contexte présente une structure grammaticale qui est facile à interpréter pour ce type d’algorithme.
Vidéo 4 – Création d’un plan explicite avec Text to Plan dans l’éditeur Unreal.
L‘usage de Text to Plan permet aux spécialistes d’AQ de construire des plans explicites à un niveau d’abstraction élevé, en encodant les étapes sous une forme textuelle facile à comprendre par une personne. En contraste avec l’enregistrement des sessions de jeu, le plan explicite produit avec Text to Plan contient peu ou pas de nœud ayant seulement trait à la navigation. Cela les rend robustes aux changements dans le niveau, mais en retour ils dépendent plus fortement de la qualité de la stratégie de navigation.
Intégration avec l’apprentissage par renforcement
Même si l’APE peut tirer avantage de techniques de navigation disponibles pour se déplacer entre les différents positions et acteurs cibles, il existe plusieurs cas limites où il faut faire preuve d’astuce pour obtenir des plans explicites viables. Nous souhaiterions éviter autant de peaufinage que possible, et libérer ce temps pour qu’il soit utilisé à meilleur escient, surtout si les solutions développées peuvent être réutilisées sur les productions à venir. C’est là que l’apprentissage par renforcement (RL) peut nous venir en aide.
Le RL est une branche de l’apprentissage automatique qui se concentre sur l’entrainement d’agents à choisir des actions dans un environnement observable. Pour ce faire, on doit extraire deux types d’information de l’environnement : l’état courant du système, et un score (appelé récompense dans le contexte du RL) indiquant la performance de l’agent. L’état courant et la récompense sont fournis à l’agent, qui s’en sert alors pour déterminer quelle action prendre par la suite. Via des techniques d’apprentissage automatique, l’agent est entraîné à choisir les actions qui maximisent la future somme espérée des récompenses. Il s’avère que la plupart de la recherche en RL est concentrée sur des domaines où l’environnement est un jeu vidéo.
Les agents de RL ont également leurs failles et leur comportement n’est pas toujours celui espéré, en particulier lorsqu’il s’agit de généraliser un comportement dans un nouveau scénario. Souvent, la cause en est la définition de la récompense, qui ne sert pas à renforcer correctement le comportement attendu par le concepteur. Par exemple, voici un lien vers une vidéo d’un agent entraîné par OpenAI au jeu CoastRunners à qui il a été demandé de maximiser son pointage. Au lieu de terminer la course, l’agent a découvert qu’il pouvait augmenter son score indéfiniment en tournant en rond et en ramassant des items bonus. De telles situations rendent difficile le débogage des agents de RL. Ces problèmes deviennent de plus en plus obscurs quand le nombre d’actions possibles augmente et que l’environnement devient plus complexe.
En gardant simples les modèles des agents, ils peuvent être entrainés plus rapidement, et débogués plus facilement. Ils sont aussi plus robustes au changement s’ils ont moins de dépendances, comme l’information visuelle du jeu qui peut varier grandement et rapidement d’une version de développement à l’autre. La vidéo 5 montre comment un agent de RL qui a été entrainé à naviguer vers une destination cible peut être utilisé pour suivre un plan explicite. Le plan comporte également deux règles; 1) Ramasser tous les objets collectionnables; 2) Attaquer tout ennemi à proximité. Cet agent observe son environnement en utilisant un senseur à grille ainsi que la direction vers la cible. La cible est déterminée soit par le prochain nœud ou par la règle appliquée du plan explicite.
Cet agent de RL n’a pas été entraîné à ouvrir des portes, ni attaquer les ennemis, ni interagir avec les monuments. Cependant, en le combinant avec un plan explicite et avec un comportement similaire à l’APE qui effectue les actions une fois la cible atteinte, l’agent peut compléter le plan.
Vidéo 5 – Un agent de RL entrainé à atteindre une destination cible en suivant un plan explicite.
En allant au-delà de ce régime d’entrainement pour la navigation, nous pouvons tirer avantage du plan explicite lui-même comme base pour définir une tâche de RL. Comme les spécialistes d’AQ créeront une banque de plans explicites pour leurs tests fonctionnels, ces plans peuvent ensuite être réutilisés pour définir un ensemble de tâches sur lesquelles entraîner les agents. En entrainant des modèles d’apprentissage automatique en utilisant du RL ou de l’apprentissage par imitation pour suivre ces suites de plans explicites, on peut dès lors imaginer utiliser ces agents comme remplacement des techniques de navigation mentionnées plus tôt.
Comme les modèles d’apprentissage automatique simples pourraient ne pas être en mesure de suivre des plans explicites complexes, ceux-ci doivent être effectués manuellement par des humains. Toutefois, en incorporant l’évaluation de modèles d’apprentissage automatique directement dans une infrastructure de test de jeu, nous pouvons directement évaluer la performance de nouveaux modèles et utiliser ceux qui couvrent le plus de cas.
Conclusion
Vidéo 6 – Agent suivant des plans explicites sautant sur des maisons dans un village et courant sur une montagne pour activer un monument.
Même si des agents scriptés sont déjà utilisés pour valider des mécaniques des jeux AAA, la conception de ces scripts et des étapes de validations peuvent être fastidieuses et intimidantes alors que le développement avance et la cadence accélère. Pour porter assistance aux professionnels d’AQ face à ce problème grandissant, l’équipe d’AGT a exploré la validation basée sur les événements en combinaison avec le plan explicite pour représenter les étapes de reproduction des tests. Utiliser le NLU, l’enregistrement des sessions de jeu, et l’édition manuelle pour créer rapidement des plans explicites permet d’aisément construire et faire la maintenance de suites de tests. En regardant au-delà des méthodes d’IA classiques pour la navigation, les plans explicites peuvent être utilisés comme tâches de RL, permettant l’intégration des méthodes de RL pour les tests de jeu tout en demeurant robustes au grand nombre de changements qui ont lieu tout au long du processus de développement d’un jeu vidéo, sans requérir une architecture d’entrainement de taille.
Remerciements
Eidos-Sherbrooke souhaite remercier Matsuko pour la collaboration continue au sein de l’équipe d’AGT. Des remerciements spéciaux vont à Martin Čertický and Charles Bernardoff-Pearson.
Auteurs
Jaden Travnik
Jaden Travnik a rejoint Eidos Montréal en 2019 comme Spécialiste en apprentissage automatique. Il a obtenu sa maîtrise en Informatique en 2018 sous a supervision du Dr. Patrick Pilarski où ses activités de recherche se concentraient sur le RL appliqué aux prothèses. Jaden voit comment des applications astucieuses de l’apprentissage automatique peuvent éliminer des obstacles pour les gens tout en leur donnant plus de contrôle sur les tâches qui leur importent réellement. Le développement de jeu vidéo comprend de tels obstacles, et il est stimulant de voir comment l’apprentissage automatique peut servir à les surmonter.
Vincent Goulet
Vincent Goulet a rejoint Eidos-Montréal comme Spécialiste en apprentissage automatique en 2018. D’abord formé en physique et ingénierie, il a obtenu sa maîtrise en Informatique en 2017 pour sa recherche qui portait sur l’optimisation par contrainte appliqué à la génération automatique de mécanismes. Durant ses études supérieures, son intérêt a été capté par le domaine du traitement du langage naturel, aligné avec son intérêt de longue date pour l’apprentissage des langues et de la linguistique. Il dédie désormais son travail à faire profiter les procédés de l’industrie des avancées fulgurantes de ce domaine.
Notes légales
Super Mario Bros™ 1999 Nintendo of America Inc.
