Game AI
13 June 2022
Alexandre Peyrot, Romain Trachel
Apprentissage par renforcement . Arbre de comportement . Environment Query System . IA de jeu adaptatif

Prédictions de jeu par apprentissage automatique pour IA de jeu adaptatif

Résumé

Nous investiguons comment combiner de l’apprentissage automatique avec l’Environment Query System (EQS) de Unreal Engine pour mettre à jour des arbres de comportement pour du jeu adaptatif. L’idée principale est de conserver l’interprétabilité et la fiabilité des décisions de l’IA provenant des arbres de comportement, tout en profitant d’une approche guidée par les données afin de mettre à jour certaines valeurs de l’arbre en fonction de l’état de jeu actuel.

Introduction

L’intelligence artificielle (IA) dans les jeux vidéo utilise des programmes informatiques codés judicieusement pour tirer parti des diverses mécaniques de jeu afin de produire des jeux divertissants et engageants. Dans Pac-Man, un jeu vidéo culte de 1980, chacun des quatre fantômes ont leur unique mécanique de poursuite et le jeu alterne entre des modes de poursuite intense suivis de périodes où les fantômes s’éparpillent. Ce design humain et créatif permet que le jeu ne soit ni trop facile ni trop difficile, afin de maintenir le joueur ou la joueuse engagé·e et dans un état de flow. Dans des jeux plus récents comme Left 4 Dead, Middle-earth: Shadow of Mordor ouAlien: Isolation, le comportement de l’ennemi est adapté dynamiquement afin de maintenir de l’engagement et d’empêcher le jeu de devenir trop répétitif. De plus, l’IA de jeu adaptatif peut contribuer à rendre les jeux accessibles pour plus de joueurs et joueuses.

Nous introduisons une approche d’IA de jeu adaptative afin d’apprendre la difficulté optimale à partir de données de jeu. L’approche est basée sur de l’apprentissage automatique (ML, Machine Learning) ainsi que des outils d’IA de jeu comme des arbres de comportement (BT, Behaviour Trees) et l’Environment Query System (EQS) de Unreal Engine. Notre formalisme est inspiré par de l’apprentissage par renforcement, un formalisme de ML qui permet d’entraîner des agents pour jouer à des jeux vidéo dans le contexte de tests de jeux automatisés, où qui peuvent compétitionner et gagner contre des joueur·euse·s professionnel·le·s dans des jeux comme Starcraft II ou Dota 2. Le but de notre travail n’est cependant pas de produire des agents imbattables, mais de construire une IA pour l’ennemi qui soit intuitive de comprendre et adéquatement difficile à jouer contre. L’idée principale est de conserver l’interprétabilité et la fiabilité des décisions de l’IA provenant des BT, tout en profitant d’une approche guidée par les données afin de mettre à jour certaines valeurs de l’arbre en fonction de l’état de jeu actuel.

Afin d’atteindre cet objectif, nous avons entrainé un réseau de neurones artificiel qui apprend à prédire le comportement du joueur ou de la joueuse à partir de plusieurs relectures de jeu. Ces prédictions sont calculées en temps réel avec une inférence runtime (ONNX) et utilisées pour mettre à jour dynamiquement les BT de l’ennemi. De telles prédictions peuvent être par exemple « quelle est la probabilité de ramasser un objet prochainement? », où bien « quelle est la probabilité que l’ennemi capture le joueur ou la joueuse prochainement? ». Ainsi, la difficulté de jeu peut être adaptée de telle manière à ce qu’en mode difficile l’ennemi se déplace vers certains endroits de menace, tandis qu’en mode facile l’ennemi serait moins agressif et se déplacerait plus loin du joueur ou de la joueuse.

Dans les prochaines sections, nous décrivons d’abord la scène et la tâche que nous avons utilisée pour tester notre approche d’IA de jeu adaptative. Nous introduisons par la suite les divers outils d’IA de jeu que nous avons combinés avec du ML. Nous continuons par expliquer comment nous avons collecté nos données de jeu et comment nous avons entrainé notre réseau de neurones. Finalement, nous présentons nos résultats et discutons les limites de notre approche ainsi que les futurs travaux envisagés.

Tâche

Vue générale de notre système implémenté dans Unreal. Dans les sections qui suivent, nous détaillons le jeu et les éléments d’IA présents dans cette vidéo.

Afin de tester notre approche, nous utilisons le point de vue de dessus de Unreal Engine 4 (UE4) pour construire une démonstration simple basée sur un jeu de cachette. La scène est une surface carrée plate avec 29 piliers distribués uniformément grâce auxquels le joueur ou la joueuse peut se cacher de l’ennemi. Le but du jeu est de collecter 16 objets tout en évitant l’ennemi. Le personnage utilise le système de navigation et se déplace en fonction des instructions de la souris pour bouger et ramasser les objets. Au début de chaque partie, le joueur ou la joueuse ainsi que l’ennemi sont instanciés dans des positions aléatoires sur la carte. Chaque item doit être collecté afin de compléter le niveau, et la partie est perdue lors d’une capture par l’ennemi.

Nous imposons une distance minimale entre les positions d’instanciation des charactères pour empêcher une capture immédiate. La disposition de la scène reste constante, et les objets à ramasser sont toujours instanciés aux mêmes endroits par simplicité. Le score de jeu est égal au nombre d’objets collectés avant d’être attrapé. Le score est utilisé pour mesurer la performance de jeu et est réinitialisé lorsque le niveau est complété ou lors d’un game over. À la fin de chaque partie, nous demandons aux testeurs et testeuses de rapporter la difficulté de l’ennemi entre facile, moyen et difficile. Ces rapports subjectifs sont utilisés pour comparer le niveau de difficulté perçu par différents types de comportements de poursuite.

Arbres de comportement et EQS

Nous utilisons un système de requête de l’espace généré automatiquement tel que l’EQS de Unreal que nous combinons avec des arbres de comportement.

Arbres de comportement

La logique des arbres de comportement marche en descendant les branches avec un système de priorité de la gauche vers la droite. Dans UE4, un BT peut stocker des variables de jeu dans sa composante blackboard et peut s’en servir pour exécuter des comportements comme se déplacer vers une position donnée lorsque certaines conditions sont satisfaites. Voir la Figure 1 pour un exemple d’un BT créé dans UE4.

Environment Query System

L’idée derrière l’EQS est de générer un ensemble de points dans la scène, vérifier à chaque point si certains critères sont satisfaits, et s’en servir par exemple pour sélectionner le meilleur point pour mettre à jour une valeur dans le blackboard du BT. Ces critères de sélection sont nommés EQS tests et contiennent comme exemples typiques des mesures de distances, de la recherche de chemin, ou bien de la vérification de visibilité directe entre des entités qui devraient heuristiquement aider le charactère d’IA à atteindre ses buts. Plusieurs tests peuvent être combinés pour produire un score de sélection. Voir la Figure 2 pour un exemple d’un BT qui utilise un EQS avec deux tests.

Comportements de l’ennemi

Nous construisons plusieurs BT à difficultés variables afin de produire plusieurs comportements d’ennemis correspondants. Nous commençons à partir d’un comportement de patrouille aléatoire et de poursuite comme décrite dans la documentation de UE4, nous poursuivons par incorporer un nœud EQS, et finalement combinons ce nœud avec des prédictions de ML.

Patrouille aléatoire 

Figure 1 – BT de patrouille aléatoire avec deux branches principales: poursuite lors de visibilité directe par l’ennemi (A) et patrouille vers un ennemi aléatoire (B).

Commençons par décrire le comportement original de poursuite par patrouille aléatoire.

La branche gauche de ce BT exécute un comportement de poursuite si l’ennemi a visibilité directe sur le joueur ou la joueuse (Figure 1.A). Autrement, l’ennemi tombe en mode de patrouille (Figure 1.B) où une position est sélectionnée aléatoirement dans un rayon donné vers laquelle l’ennemi se déplace. La visibilité directe est perdue lorsque le joueur ou la joueuse se cache derrière des piliers et l’ennemi retourne alors en patrouille lorsque la visibilité directe est perdue pendant plus d’une seconde.

EQS basé sur de la visibilité directe (LoS, Line of Sight)

Il est possible de remplacer le nœud de patrouille aléatoire par des mécanismes de recherche plus élaborés, afin de rendre le comportement de patrouille plus engageant. Dans notre scène de poursuite, nous remplaçons le nœud de patrouille aléatoire dans le BT par un nœud EQS qui exécute deux tests (Figure 2.A). Le premier test vérifie la visibilité directe, tandis que le second retourne un score en fonction de la distance entre les charactères. Le point retourné par la requête EQS est alors utilisé comme nouvel emplacement de patrouille.

Figure 2 – Requête EQS basée sur de la visibilité directe (A). L’emplacement de patrouille aléatoire a été remplacé par le résultat de cette requête EQS (B).

EQS basé sur du ML

Les heuristiques pour générer de bons EQS combinent souvent plusieurs tests afin de produire le comportement désiré. Par exemple, dans le BT précédent, nous avons choisi un EQS qui combine des tests basés sur la visibilité directe ainsi que sur la distance, car celles-ci semblaient être les considérations les plus importantes à regarder afin de capturer le joueur ou la joueuse.

Nous proposons à la place d’utiliser un EQS avec un test unique basé sur un modèle de ML qui a été entrainé pour combiner plusieurs considérations automatiquement. Le modèle produit des prédictions sur des événements de jeu tels que la capture du joueur ou de la joueuse, ou la collection d’items, qui peuvent à leur tour être convertis en un score EQS. En d’autres mots, les données de jeu informent le modèle sur comment générer un test, au lieu de sélectionner et régler plusieurs tests manuellement.

En utilisant un plugin ONNX pour UE4 développé par nos équipes, nous pouvons charger notre modèle dans l’engin et se servir des prédictions pour un score de test pour notre EQS personnalisé (Figure 3).

Figure 3 – Notre test EQS personnalisé avec un modèle Onnx.

Notre blueprint EQS consiste à présent d’un test unique qui combine automatiquement plusieurs caractéristiques pour faire ses sélections. Ces prédictions sont obtenues grâce à l’inférence ONNX lorsque le nœud EQS est exécuté.

Comment interpréter le test EQS basé sur du ML

Apprendre plusieurs valeurs simultanément à un modèle d’apprentissage par renforcement tombe dans l’ombrelle des General Value Functions (GVF) et est utile pour avoir des modèles qui se généralisent mieux en gagnant plus d’informations à travers l’exploration du monde. En utilisant de l’apprentissage par différence-temporelle (TD learning), nous avons entrainé un réseau de neurones à propagation avant avec une couche cachée et deux sorties consistant en deux GVFs: le score du jeu et le score de l’ennemi. Nous rappelons que le score du jeu correspond au nombre d’items collectés, tandis que le score de l’ennemi tient compte de s’il y a eu capture ou pas. Par soucis de brièveté, nous nous concentrons ici sur un test basé sur la GVF qui prédit le score de l’ennemi.

La valeur obtenue par notre GVF doit être vue comme une indication de la probabilité d’une fin de partie ayant lieu prochainement : le plus haut la valeur, le plus rapidement une capture devrait se produire.

EQS basé sur du ML avec des valeurs de référence

Sélectionner un point avec un score élevé se traduit généralement par un ennemi qui se dirige vers un emplacement où cela sera facile de voir et capturer le joueur ou la joueuse. Au contraire, les points ayant un faible score sont les emplacements auxquels l’ennemi se dirige dans les directions opposées à celles du joueur ou de la joueuse. Finalement, les points ayant un score moyen sont un entre-deux pour des emplacements avec un peu de visibilité et proximité au joueur ou à la joueuse, sans être trop agressif.

Une manière de bénéficier de ces scores est d’utiliser des valeurs de référence : au lieu de trouver le point ayant la valeur de prédiction maximale, nous cherchons le point qui minimise la différence entre la prédiction du modèle et la valeur de référence. Nous produisons de cette manière 3 modes de poursuite basées sur du ML avec des niveaux de difficulté intermédiaires en augmentant graduellement les valeurs de références comme suit :

  • Un mode facile: valeur de référence de 0
  • Un mode moyen : valeur de référence de 0.12
  • Un mode difficile : pas de valeur de référence
Figure 4 – Résultats EQS pour chaque niveau de difficulté: facile (A), moyen (B), et difficile (C). Le sprite bleu indique le joueur ou la joueuse tandis que l’ennemi est indiqué par un sprite rouge. Les scores EQS normalisés varient de 0 en rouge à 1 en vert.

La valeur de 0 pour le mode facile est équivalent au modèle choisissant le point auquel la prédiction du modèle est la plus basse possible. La valeur de 0.12 pour le mode moyen a été choisi manuellement par tâtonnements en fonction des différentes grilles de score EQS comme présentées dans la Figure 4, et en fonction des performances des testeurs et des testeuses vis-à-vis de plusieurs valeurs de références. Finalement, ne mettre aucune valeur de référence est équivalent à mettre une valeur de référence de 1 et ainsi choisir le point auquel la prédiction du modèle est la plus élevée possible.

Expérimentation

Collecte de données et entrainement du modèle

Nous collectons des données de jeux avec un ennemi jouant avec le BT de patrouille aléatoire (voir Figure 1), et avec un agent numérique (aussi appelé bot) qui suit une heuristique simple : il cherche l’objet le plus proche à collecter, tout en se cachant derrière les piliers de la carte pour briser la visibilité directe avec l’ennemi. Nous collectons des informations de jeu (telles que la position des joueur·euse·s, leur orientation, etc.) ainsi que le score de jeu à des intervalles réguliers de 0.3 secondes afin de préserver la consistance temporelle entre chaque échantillon. Nous avons collecté de cette manière 400 parties de jeu automatisé pour entrainer notre modèle – soit un équivalent de 2.6 heures de jeu avec une moyenne de durée de jeu de 23 secondes. Le modèle utilisé dans les expériences qui suivent est entrainé sur cette base de données avec de l’apprentissage par différence-temporelle avec un facteur d’actualisation γ = 0.9. Une prédiction du modèle de 1 correspond ainsi à une espérance de capture immédiate, une prédiction de 0.12 correspond à une espérance de capture dans 6 secondes, tandis qu’avec une prédiction de 0, aucune capture n’est espérée de se produire.

Les captures se produisant infréquemment et la parcimonie de la mise à jour du score de l’ennemi pouvaient faire en sorte qu’il était difficile de faire converger le modèle. Nous avons implémenté un priority replay buffer qui nous a aidé à faire converger le modèle à des solutions ayant de moindres erreurs de prédictions. Comme il y a 16 objets à travers la carte, nous avons également observé un déséquilibre entre la fréquence de la mise à jour du score de jeu vis-à-vis de celle du score de l’ennemi. Ceci entrainait le modèle à se concentrer sur l’optimisation de ses prédictions de score de jeu tout en négligeant les scores de l’ennemi. Afin de contrebalancer la fréquence des signaux de score, nous avons également implémenté une couche PopArt qui nous a permis d’entrainer des modèles avec les deux sorties simultanément.

Expérience 1 : Comparaisons d’IA de jeu avec et sans EQS basé sur du ML

Dans cette expérience, nous comparons trois BT qui partagent la même logique exceptée pour le mode de patrouille qui dépend de leur configuration EQS. La patrouille aléatoire et l’EQS basé sur la visibilité directe sont utilisés comme des outils d’IA de jeu et comparés avec notre EQS personnalisé basé sur du ML. Les données ont été collectées par une personne jouant 201 parties du jeu. Cette expérience a été produite en interne avec trois participant·e·s. À chaque nouvelle partie, un BT aléatoire parmi les trois comportements de patrouille a été assigné à l’ennemi. Les participant·e·s n’étaient pas au courant de quel BT contrôlait l’ennemi.

Nous analysons avec des cartes de fréquentation, dans la Figure 5, le comportement des personnages en montrant comment ils se déplacent à travers le niveau (« prey location ») et les endroits de capture (« death location »).

Figure 5 – Cartes de fréquentation des mouvements des joueurs et joueuses (colonne de gauche) / Ennemis (colonne du milieu) et des endroits de capture (colonne de droite). Chacune pour la patrouille aléatoire (rangée du haut), l’EQS basé sur du ML sans valeurs de référence (rangée du milieu) et l’EQS basé sur LoS (rangée du bas).

Les trajectoires des joueurs et des joueuses favorisent les bords de la carte ainsi que les coins pour mieux se cacher de l’ennemi. Nous remarquons que les chemins suivis par notre BT avec un EQS basé sur du ML sont homogènes à travers la carte, de manière similaire à la patrouille aléatoire ainsi que le BT avec un EQS basé sur la visibilité directe. Ceci est une indication qu’il n’y a pas trop de biais dans notre modèle de ML lié à la configuration de la carte, ce que nous voulions éviter car cela entrainerait des comportements de patrouille répétitifs. Cette homogénéité dans les prédictions peut être en partie expliquée par les cartes de fréquentation de capture qui indiquent les endroits de la carte où le score de l’ennemi est mis-à-jour.

Pour tester les niveaux de difficulté des nombreux BT décrits ci-dessus, nous comparons la performance moyenne des testeurs et des testeuses mesurée en termes de temps de jeu (i.e. pendant combien de temps ils ont pu jouer avant de se faire capturer ou de compléter le niveau), ainsi que le score du jeu (i.e. combien d’objets ils ont réussi à collecter). Ces métriques apparaissent en tant que boîtes à moustaches dans la Figure 6, qui exhibe la médiane à l’intérieur de la boite qui s’étend du quartile inférieur au supérieur pour le score de jeu et le temps de jeu (en secondes), respectivement.

Les rapports de difficulté subjectifs donnés par les joueurs et joueuses à la fin de chaque partie apparaissent également en tant que graphiques circulaires ci-dessous. Chaque graphique correspond au ratio de difficulté perçu sous chaque type de mode de patrouille utilisé par le BT de l’ennemi : soit une patrouille aléatoire, soit notre EQS basé sur du ML sans valeurs de référence, ou bien l’EQS basé sur de la visibilité directe, que nous étiquetons « Random », « EQSHard » et « EQSLoS », respectivement. La variable N indique le nombre de parties jouées avec chaque configuration de patrouille.

Figure 6 – Rapports subjectifs du niveau de difficulté (graphiques circulaires en haut) et performance par comportement en terme du score (en bas à gauche) et temps de jeu en secondes (en bas à droite) pour le mode de patrouille aléatoire, l’EQS basé sur du ML (EQSHARD) et l’EQS basé sur la visibilité directe (EQSLoS).

Les scores et temps de jeu sont comparables sous les modes EQS Hard et EQS LoS, cependant ils sont beaucoup plus bas que sous le mode de patrouille aléatoire. Ceci indique que le niveau était plus difficile à jouer sous les modes EQS Hard et LoS. De plus, le modèle de ML a appris à détecter des emplacements, vers lesquels envoyer l’ennemi, de difficulté comparable à ceux sélectionnés par le mode EQS LoS. Les rapports de difficulté montrent également que les joueurs et joueuses ont remarqué une difficulté accrue sous les deux modes utilisant de l’EQS.

Expérience 2: Comparaisons des difficultés pour les valeurs de référence basées sur du ML

Dans cette deuxième expérience, nous comparons l’EQS basé sur du ML avec différentes valeurs de référence pour avoir un meilleur contrôle sur le niveau de difficulté. Nous avons collecté 280 parties jouées par nos trois testeurs et testeuses internes. À chaque début de partie, un mode de patrouille avec EQS basé sur du ML était sélectionné aléatoirement parmi une valeur de référence de 0 (EQS Easy), 0.12 (EQS Medium) ou ne pas mettre de valeur de référence (EQS Hard), comme décrit dans la section précédente. Nous utilisons des graphiques circulaires et des boites à moustaches de manière similaire à l’expérience précédente afin de montrer les rapports de difficulté subjectifs ainsi que les scores de jeu et les temps de jeu (en secondes) obtenus dans cette nouvelle expérience.

Figure 7 – Rapports subjectifs du niveau de difficulté (graphiques circulaires en haut) et performance par comportement en terme du score (en bas à gauche) et temps de jeu en secondes (en bas à droite) pour le mode de patrouille facile, moyen et difficile basé sur notre EQS personnalisé basé sur du ML.

Nous notons une nette augmentation de difficulté, avec un score de jeu moyen de 12 en facile, 10.75 en moyen et 6.71 en difficile. Nous avons également comparé la performance de notre bot automatisé, que nous avons utilisé pour la collecte de données, contre les différents BT proposés ici. Le bot a obtenu un score moyen de 3.76 en facile, 3.35 en moyen et 2.46 en difficile. Nous remarquons que ces scores sont bien plus bas que ceux des personnes qui ont participé à l’expérience, cependant la tendance est maintenue avec des scores décroissants quand la difficulté augmente.

Le mode facile dans cette expérience a une difficulté perçue, des scores et des temps de jeu semblables à ceux obtenus avec la patrouille aléatoire de l’expérience précédente. Bien que le même mode difficile ait été utilisé dans les deux expériences, nous observons une difficulté perçue différente mais avec des scores et temps de jeu semblables. Cette différence de perception est probablement due au fait que le mode EQS LoS était plus difficile que le mode EQS moyen dans cette expérience, et il a donc pu sembler moins difficile de jouer contre le mode EQS difficile dans l’expérience 1.

Conclusions et travaux futurs

Nous avons présenté une nouvelle approche mélangeant des outils d’IA de jeu avec du ML afin de créer un comportement de poursuite adaptatif. Notre test EQS basé sur du ML peut performer des analyses de situations de jeu pour contrôler la difficulté de jeu en permettant le système de requête de prioriser les points avec de basses, moyennes, et hautes valeurs de danger. La performance des testeurs et testeuses dans un simple jeu de cachette indique que notre approche permet de moduler la difficulté de jeu efficacement.

Nous sommes présentement en train d’investiguer comment inclure d’autres prédictions d’événements de jeu dans notre EQS test. Plus spécifiquement, notre modèle prédit également la collection d’objets à collectionner, ce qui pourrait être utilisé pour créer un comportement défensif : l’ennemi se déplace pour protéger les emplacements autours des prochains objets que le joueur ou la joueuse vont probablement aller collectionner.

Une exploration préliminaire de ce comportement défensif a cependant dévoilé un fort biais pour se déplacer vers certains coins de la carte afin de défendre des objets en particulier. Il devient alors simple d’aller collecter tous les autres objets et pratiquement impossible de collecter ce dernier objet, ce qui résulte en un jeu ennuyeux. Ceci est en contraste avec notre test basé sur les événements de capture, où les expériences montrent que l’ennemi explore la scène de manière homogène. Il sera nécessaire de surmonter ce biais pour utiliser les prédictions de collection d’objets pour produire de nouvelles mécaniques de jeu, tel qu’alterner entre des épisodes de poursuites intenses suivis de comportements défensifs de protection d’objets. Cette idée est inspirée de l’alternance entre modes de poursuites et d’éparpillement utilisé dans Pac-Man pour maintenir le joueur ou la joueuse dans un état de flow. Nous faisons de la recherche pour trouver des moyens de surmonter ce biais dans nos prédictions de collection d’objets et trouver comment d’autres événements de jeu peuvent s’intégrer dans notre cadre pour un expérience de jeu engageante.

À propos des auteurs

Alexandre Peyrot

Alexandre Peyrot est un spécialiste en apprentissage automatique dans l’équipe IA et Apprentissage Automatique d’Eidos-Sherbrooke. Il a obtenu son Doctorat en mathématiques à l’École Polytechnique Fédérale de Lausanne (EPFL) en 2017. Il a poursuivi ses recherches en mathématiques en travaillant en tant que chercheur-boursier postdoctoral à Stanford University avant de rejoindre Eidos-Montréal en 2018. Il voit un immense potentiel dans la combinaison de l’apprentissage automatique avec de l’IA de jeu pour créer du jeu adaptatif ainsi que pour ajuster la difficulté de jeu de manière immersive.

Romain Trachel

Romain Trachel est un spécialiste en apprentissage automatique sénior travaillant dans l’équipe IA et Apprentissage Automatique d’Eidos-Sherbrooke, depuis juillet 2018. Il a obtenu son Doctorat de l’université de Nice (sud de la France) en 2014, où il a travaillé sur des interfaces entre le cerveau et l’ordinateur à l’Institut de Neurosciences de la Timone (Marseille –  www.int.univ-amu.fr) et INRIA (Sophia-Antipolis – https://www.inria.fr/equipes/athena). Il a effectué une paire de post-docs et a commencé à travailler en tant que chercheur indépendant pour produire des films de réalité virtuelle et des installations d’art basées sur l’intelligence artificielle. Ses plus grands intérêts incluent le traitement de signaux/images, apprentissage automatique/profond, neurosciences, sciences cognitives, art digital/moderne, et les technologies récentes tels que la réalité virtuelle/augmentée.

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert