Concevoir l'Intelligence Artificielle des jeux vidéo


L’industrie des jeux vidéo a accompli de grands bons en avant au cours des dernières décennies. D’abord avec des jeux simples comme Pong* et Pac-Man* qui proposaient un court moment d’évasion jusqu’à des titres aussi prenants que World of Warcraft* et Call of Duty 4*, qui représentent aujourd’hui un passe-temps à part entière pour les aficionados. Selon l’ESA (Entertainment Software Association), les joueurs actuels ont à leur actif, en moyenne, treize ans de jeux vidéo derrière eux et se sont habitués à ce que chaque nouveau titre soit plus complexe, plus intéressant et plus intelligent. Pour les développeurs, le défi consiste à aller toujours plus loin, pour créer des jeux sans cesse plus attractifs. Afin de répondre à ces attentes, l’intelligence artificielle (IA) pilotée par ordinateur a évolué de nombreuses manières. Pourtant, créer un moteur d’IA à la hauteur des joueurs et qui les encourage dans l’évolution de leurs personnages n’est pas chose aisée.

Cet article entame une série en quatre parties qui explore les concepts suivants et la manière dont les optimiser pour un fonctionnement sur les processeurs multicœurs actuels :
1ère partie : Conception et mise en œuvre
2ème partie : Recherche de chemin et perceptions
3ème partie : IA tactique et stratégique
4ème partie : Recours à la parallélisation pour appliquer l’IA

1ère partie : Conception et mise en œuvre

L’IA des jeux, qu’est-ce que c’est ?
Au niveau le plus basique, l’« intelligence artificielle » consiste à reproduire le comportement d’autres joueurs ou entités (c’est-à-dire tous les éléments du jeu qui peuvent agir ou sur lesquels on peut agir, de joueurs à des projectiles en passant par les points de régénération) qu’ils représentent. Le concept de base est que ce comportement est simulé. En d’autres termes, l’IA des jeux est plus « artificielle » qu’« intelligente ». Il peut s’agir d’un système simple, conditionnel (à base de règles), ou aussi complexe que celui destiné à s’opposer à un joueur sous la forme du commandant d’une armée adverse.

En quoi l’IA des jeux diffère de l’IA classique?
Les recherches classiques en intelligence artificielle visent à créer une vraie intelligence, même si c’est par des moyens artificiels. Des projets comme Kismet* du MIT (Massachusetts Institute of Technology) tentent de créer une IA capable d’apprentissage et d’interactions sociales ainsi que d’émotions. A la date d’écriture de cet article, le MIT travaille sur une IA qui possède les capacités d’un jeune enfant, et ce avec des résultats prometteurs.

Dans le cadre des jeux actuels, une vraie IA est très loin de ce que l’on attend d’un logiciel ludique. L’IA des jeux n’a nul besoin d’être douée ni de raison ni de conscience (en fait, il faut mieux qu’elle ne le soit pas) ; elle n’a rien d’autre à apprendre au-delà du gameplay. Le vrai objectif de l’IA dans les jeux est de simuler un comportement intelligent et de fournir au joueur un défi crédible et qu’il soit en mesure de relever.

L’objectif de l’IA dans les jeux?
L’IA peut avoir de nombreux rôles dans les jeux. Il peut s’agir d’un jeu de règles générales qui régissent les entités de l’univers vidéoludique. On peut aussi considérer que les événements pré-scénarisés que suivent les entités relèvent d’un certain type d’IA. Dans le jeu F.E.A.R*, par exemple, la petite fille qui donne la chair de poule et qui apparaît pour effrayer les joueurs et annoncer des choses à venir est un événement pré-scénarisé. Enfin, ce qui vient à l’esprit de la plupart des gens lorsqu’ils pensent à l’IA et aux jeux, ce sont les joueurs pilotés par l’ordinateur dans les jeux multijoueurs. Tous sont différents rôles que l’IA peut assumer.

F.E.A.R.

Figure 1. Le recours à des événements scénarisés dans F.E.A.R. (Vivendi Universal) est un type d’IA.

Impératifs de base pour l’IA dans les jeux
Selon la nature du rôle que l’IA est censée jouer, les besoins du système peuvent être très limités. Plus le système est complexe, en revanche, plus les impératifs imposés à l’IA seront nombreux. Les besoins de base ne sont rien d’autre que le temps de traitement requis par la gestion de l’IA. Des systèmes plus complexes nécessitent une façon pour l’IA de percevoir son environnement, un relevé des actions du joueur et une manière d’évaluer la réussite des décisions prises précédemment.

Prise de décisions
Le concept de base sous-jacent à l’IA est la prise de décisions. Pour effectuer les choix correspondant, le système intelligent doit être capable d’influer sur les entités qui l’exploitent. Or cette exécution peut s’effectuer selon une stratégie en mode « push » ou en mode « pull ».

Les systèmes d’IA en mode « push » tendent à être isolés sous forme d’élément distinct de l’architecture du jeu. Cette stratégie prend souvent la forme d’un ou plusieurs fils (threads) où l’IA passe son temps à calculer les meilleurs choix en fonction des options du jeu. Quand elle prend une décision, celle-ci est souvent diffusée aux entités concernées. Cette approche est la plus efficace pour les jeux de stratégie en temps réel, où l’IA prend en compte le jeu dans sa globalité.

Les systèmes en mode « pull » sont les plus efficaces avec des entités simples. Dans ces jeux, les entités invoquent le système d’IA quand elles « réfléchissent » ou se mettent à jour. Cette approche fonctionne très bien dans les systèmes avec un grand nombre d’entités qui n’ont pas besoin de réfléchir très souvent, par exemple des tireurs. Elle peut aussi tirer parti des techniques de parallélisation (multi-threading), mais cela nécessite de le prévoir en plus (pour plus de détails, voir l’article sur les IA parallélisées d’Orion Granatir).

Perceptions de base
Pour que l’AI puisse prendre des décisions sensées, elle doit être capable de percevoir son environnement. Dans les systèmes simples, cette perception peut se résumer à vérifier la position de l’entité qu’est le joueur. Avec des systèmes plus lourds, les entités doivent pouvoir identifier certains éléments essentiels de l’univers vidéoludique, par exemple les chemins à emprunter, le terrain à couvert et les zones de conflit.

Le défi pour les concepteurs et les développeurs est de trouver un moyen de repérer les éléments importants pour le système d’intelligence. Ainsi, les zones à couvert peuvent être prédéterminées par le concepteur du niveau ou bien précalculées lors du chargement ou de la compilation d’une map. Certains éléments sont à évaluer au fur et à mesure, par exemple les maps de conflit et les dangers imminents.

Systèmes conditionnels
La forme la plus basique que peut prendre un système intelligent est celui d’un système conditionnel, c’est-à-dire régi par des règles, qui outrepasse d’ailleurs quelque peu le sens des termes « intelligence artificielle ». Un ensemble de comportements prédéterminé sert à fixer le comportement des entités du jeu. Avec toute une série d’actions possibles, le résultat global peut être un système de comportements qui n’est pas évident, même si « l’intelligence » est en l’occurrence bien maigre.

On trouve un bon exemple d’un système conditionnel dans les jeux de Black Jack (vidéo ou réels). Le donneur obéit à une règle simple : continuer de donner tant que le total des cartes est inférieur ou égal à 17. Pour le joueur moyen, la perception est que le donneur joue pour gagner. Le joueur imaginera un adversaire plus compétent que celui qu’il a en face de lui (sauf si le casino révèle la règle qu’applique le donneur).

Le classique des jeux qui applique ce système est Pac-Man. Quatre fantômes harcèlent le joueur. Chacun d’eux suit un jeu de règles simples : l’un d’eux tourne toujours à gauche, un autre toujours à droite, le troisième dans une direction aléatoire et le dernier toujours vers le joueur. Individuellement, les fantômes seraient faciles à circonvenir et le joueur pourrait facilement les éviter. En groupe, en revanche, leurs mouvements ressemblent à une chasse complexe et coordonnée. En réalité, le seul fantôme qui consulte la position du joueur est le dernier.

PacMan

Figure 2. Représentation visuelle des règles régissant les fantômes de Pac-Man, où les flèches représentent les « décisions » à prendre.

Comme le suggère cet exemple, il est inutile que les règles soient « codées en dur » : elles peuvent s’appuyer sur des états perçus (comme c’est le cas du quatrième fantôme) ou sur des paramètres modifiables de l’entité. Des variables comme l’agressivité, le courage, la portée de vue ou la rapidité de réflexion peuvent toutes diversifier le comportement d’une entité, même dans le cadre d’un système conditionnel. Ces systèmes représentent la structure la plus simple que puisse adopter une IA. Les systèmes intelligents plus complexes sont construits à partir d’une série de règles conditionnelles et régis par elle. Dans les jeux tactiques, les règles régissent les tactiques à employer ; dans les jeux de stratégies, elles gouvernent les ordres de construction et la manière dont réagit aux conflits. Les systèmes conditionnels sont le fondement de l’IA.

Machines à états finis
Une machine à état fini constitue une manière de conceptualiser et d’implémenter une entité dont les états changent au cours de sa durée d’utilisation. Un « état » peut représenter les conditions physiques dans lesquelles l’entité se trouve ou bien les émotions qu’elle peut manifester. Dans cet exemple, les états émotionnels n’ont rien à voir avec ceux d’une vraie IA, mais sont des modèles de comportement prédéterminés qui cadrent dans le contexte du jeu.
Voici quelques exemples d’états pour un système d’IA destiné à un jeu comportant des éléments de furtivité :

Machine-Etats-Finis

Figure 3. Schéma des états d’une machine à états finis typique, où les flèches représentent les changements d’état possibles.

 Inactif (Idle). Dans cet état, l’entité est passive, ne se déplace pas ou bien se déplace selon un chemin défini. Le niveau de perception est faible. Les sons émis par le joueur ne sont pas pris en compte ou pas souvent. Ce n’est que si l’entité est attaquée ou qu’elle « voit » un joueur directement que son état passe à un niveau de plus grande conscience.

 Conscient (Aware). Cette entité cherche activement les intrus. Elle prend souvent connaissance des sons émis par le joueur et sa vue couvre une distance et un angle plus importants que celle d’une entité inactive. Elle passera à l’état « intrigué » si elle remarque que quelque chose n’est pas normal (quelque chose à vérifier) : portes ouvertes, corps inconscients, magazine d’arme vide, etc.

 Intrigué (Intrigued). Cette entité a conscience que quelque chose cloche, ce qui la conduit à abandonner son poste ou son chemin normal pour se déplacer vers la zone intéressante, par exemple ces portes ouvertes ou ces corps. Si elle aperçoit un joueur, elle passe en mode « alerte ».

 Alerte (Alert). Dans cet état, l’entité est consciente de la présence du joueur et enclenche les actions visant à le traquer : passer à portée d’attaque, alerter d’autres gardes, faire sonner l’alarme et se mettre à couvert. Lorsque l’entité est à portée de l’ennemi, elle passe en état « agressif ».

 Agressif (Agressive). C’est l’état où l’entité a engagé le combat avec le joueur. Elle l’attaque dès qu’elle peut et se met à couvert entre les passes (pour reprendre des points de vie ou recharger son arme). Elle ne quitte cet état que si le joueur est tué (retour à la normale), si l’ennemi n’est plus à portée de feu (retour à l’état « alerte ») ou si elle meurt (passage à l’état « mort »). Si son niveau de vie faiblit, elle peut passer en état « en fuite », en fonction de l’indice de courage qu’elle possède.

 En fuite (Fleeing). Dans cet état, l’entité tente de s’enfuir du combat. Selon le jeu, elle peut avoir un objectif secondaire, comme reprendre des points de vie ou quitter la zone. Si elle récupère de la vie, elle peut revenir à l’état d’alerte et reprendre le combat. Une entité qui « s’en va » est simplement supprimée.

 Mort (Dead). Dans certains jeux, l’état de mort peut ne pas correspondre à une inactivité totale : en état de mort ou moribond, l’entité peut « pousser un cri » pour alerter d’autres entités des environs. Elle peut aussi n’être qu’assommée pour ensuite être ranimée par un médecin (et renvoyée en état d’alerte).

Il existe au moins deux moyens simples de mettre en œuvre une machine à états finis dans le système des entités. La première consiste à faire en sorte que chaque état soit une variable consultable (souvent par une commutation massive). L’autre est d’utiliser des pointeurs de fonctions (en langage C) ou des fonctions virtuelles (en C++ ou autres langages orientés objet).

IA adaptative
Les parties qui précèdent envisagent des méthodes pour concevoir des systèmes d’intelligence qui s’inscrivent dans les événements prédéfinis d’un jeu. Pour la plupart des jeux, cela suffit à condition que la conception ait été complète et que l’on comprenne clairement les objectifs des entités intelligentes. Quand un jeu appelle une plus grande variabilité et un meilleur adversaire, plus dynamique, pour le joueur, l’IA devra sans doute pouvoir se développer et s’adapter d’elle-même.

L’IA adaptative s’emploie en général dans les jeux de combat et de stratégie, où les mécanismes sont complexes et les options de gameplay innombrables. Pour opposer au joueur un défi permanent sans qu’il devine au final la stratégie optimale pour battre l’ordinateur, l’IA doit pouvoir apprendre et s’adapter.

Prédiction
La capacité d’anticiper le prochain coup d’un adversaire est essentielle dans un système adaptatif. On peut utiliser différentes méthodes, dont la reconnaissance des formes antérieures (abordée dans un article suivant) ou bien deviner aléatoirement, pour déterminer la prochaine action à prendre.

L’une des méthodes de base de l’adaptation consiste à tenir compte des décisions précédentes et d’évaluer leur réussite. Le système d’IA enregistre ainsi les choix antérieurs du joueur. Les décisions passées doivent pouvoir être évaluées (par exemple, dans les jeux de combat, l’avantage gagné ou perdu - points de vie perdus ou avantage en temps - peuvent être l’aune avec laquelle cette réussite est mesurée). Des informations supplémentaires sur la situation peuvent aussi être rassemblées pour donner plus de contexte aux décisions : niveau de vie relatif, actions précédentes et position dans le niveau (on joue différemment lorsque l’on est acculé).

Il est possible d’évaluer cet historique pour déterminer le succès des actions précédentes et si un changement de tactique est nécessaire. Jusqu’à constitution d’une liste des actions passées, on peut recourir à des tactiques générales ou à des actions aléatoires pour guider les actions de l’entité. Ce système peut se relier à des systèmes conditionnels et à différents états.

Dans un jeu tactique, l’historique peut permettre de décider des meilleures tactiques à employer contre une équipe de joueurs : défensive, offensive, « berserk » ou un mode de jeu équilibré. Dans un jeu de stratégie, la composition optimale des unités d’une armée peut se décider joueur par joueur. Dans les jeux où l’IA pilote des personnages qui accompagnent le joueur, l’IA adaptative peut mieux compléter le style naturel de celui-ci en apprenant comment il agit.

Résumé
L’intelligence artificielle est un champ de recherche complexe. L’IA pour les jeux prend différentes formes selon les besoins du jeu en question, ce qui va d’ensemble de règles simples pour les entités pilotées par l’ordinateur à des systèmes adaptatifs plus évolués. Appliquer les concepts de l’IA au jeu est un biais indispensable pour renforcer la crédibilité des personnages virtuels dans les divertissements vidéoludiques, mais ce n’est pas un défi impossible à relever. Le prochain article de cette série abordera les enjeux d’une IA pour percevoir un environnement complexe et y naviguer ainsi que la réponse à ces enjeux.
Pour de plus amples informations sur les optimisations de compilation, consultez notre Avertissement concernant les optimisations.