Dans le cadre de mon cours en intelligence artificielle, j’ai voulu écrire ce billet afin d’illustrer une application des techniques vu dans le cours à une situation qui pourrait se produire dans mon projet de jeu vidéo. Grosso-modo, le tiers du cours est fait. Il a été question de différentes façons de représenter des connaissances afin qu’un système puisse les traiter. Les façons abordées étaient jusqu’à maintenant, toutes sous formes de règles modus ponens : logique propositionnel, logique des prédicats, etc. Ces règles ressemblant à une série de Si A alors B, sont à la base des systèmes experts permettant d’obtenir des réponses sur un problème d’un domaine bien précis. Par le chaînage avant ou arrière, le système questionne l’usager afin de déduire des faits et de proposer une solution à un problème. Cette technique peut être utilisée dans une situation de jeu vidéo.
L’objectif du projet Kradius est d’abord de créer un shoot’em up à haute intensité d’action (bullet hell), dont les inspirations viennent de Gradius et de shooter comme Ikaruga. La technique d’IA que je veux illustrer est plus ou moins pertinente dans ce genre de jeu. La raison en est simple, ces jeux sont basés sur l’intensité de l’action, les réflexes du joueur et non la stratégie. Les ennemis ont des patterns d’attaques bien définis. Le joueur n’a qu’à entrer dans la danse et survivre. Par contre, mon projet est plus ambitieux que cela. Une fois l’étape « bullet hell » atteinte, je prévois incorporer différents gameplay afin de diversifier le jeu. Par exemple, dans les niveaux d’action, je pense intégrer des « zones d’atterrissages » ou le joueur aurait la possibilité de sortir de son vaisseau et de continuer l’exploration à pied. Admettons que ce soit le cas et que le pilote se retrouve sur une planète en guerre. Son seul refuge est un village extra-terrestre sur le point d’être assiégé par un ennemi impitoyable. Hors, la seule chance de survie du pilote, est de coopérer avec les villageois pour organiser la défense du village, repousser l’ennemi et récupérer le vaisseau du pilote qui a bien évidemment été capturé par l’ennemi. À ce point, le gameplay passe d’un shoot’em up à un RTS style Starcraft qui est tout à fait approprié pour l’intégration de techniques IA basé sur un système de règles.
Observons le graphique précédent. Il s’agit de l’arbre technologique hypothétique de Kradius. Notre héros s’est donc écrasé sur une planète hostile où il se retrouve à la tête d’un petit village. Afin de préparer les villageois au combat et finalement regagner l’espace, le héros doit entrainer les villageois (ils deviendront soit, ouvrier, charpentier ou scout), construire des bâtiments, et récolter des ressources. Le but ici, est de mettre l’adversaire informatique au courant de l’avancé technologique du joueur afin qu’il puisse planifier et déployer des ressources offensives et défensives selon la situation du joueur. Comme je l’ai mentionné plus haut, on pourrait rendre l’ordinateur omniscient mais se serait injuste et se serait plus réaliste que l’ordinateur puisse améliorer ses connaissances sur cette situation en faisant des inférences sur l’état technologique du joueur. L’ordinateur devra donc envoyer des scouts en éclaireur sur le terrain de son adversaire pour récolter l’information lui permettant de faire des déductions sur son avancement technologique. Le joueur pourrait avoir la possibilité de couper l’information en éliminant le scout avant qu’il ne transmettre ses nouvelles données, par exemple.
Le système de règle est constitué de deux éléments principaux : la base de faits et les règles. La base de faits de notre exemple pourrait ressembler à ceci :
Cette base contient tous les nœuds du graphe qui peuvent prendre 4 valeurs : YES, NO, MAYBE, UNKNOWN. Une valeur à YES implique que le joueur possède la technologie. Si le joueur possède tous les éléments nécessaires à la construction d’une technologie, mais que le fait doit être confirmé par un scout, la valeur est à MAYBE. L’ordinateur peut alors rassembler des faits en envoyant ces scouts et en faisant des observations. Si le scout rencontre un Mur d’enceinte, alors murEnceinte est mis à YES. Si le scout retourne à sa base sain et sauf, alors l’adversaire ajoute les observations du scout à sa base de fait et effectue des déductions sur les technologies possibles que le joueur est en mesure de posséder. Il le fait en inférant à travers les règles de déductions de sa base de règles. Une règle peut ressembler à celle-ci :
Cette règle nous dit qu’étant donné qu’un mur d’enceinte a été observé, il y a forcément un charpentier en jeu qui l’a construit. On peut aussi supposer que s’il y un charpentier, il y a probablement des maisons. Ce qui se traduit par la règle :
On pourrait se demander à quoi peut servir une valeur MAYBE. Et bien, admettons que l’adversaire doit déployer des forces en se basant sur ces valeurs, avant de gaspiller des ressources contre une technologie hypothétique, il pourra soit envoyer plus de scouts pour combler les informations manquantes ou envoyer 20% moins de soldats étant donnée qu’il ne peut confirmer la présence de cette technologie même s’il a un doute raisonnable. La stratégie à adopter selon les données de la base de faits dépasse le cadre de mon exemple.
Voici d’autres exemples de règles :
Ceci étant dit, il ne reste qu’à traduire chaque lien de l’arbre technologique en règles pour que le moteur d’IA fasse les déductions adéquates. Attention, cela peut représenter un nombre impressionnant de règles. Et si certains faits ne sont pas, ou sont mal représentés par les règles, le moteur d’inférence ne pourra jamais faire les bonnes déductions. De plus, il ne s’agit pas d’utiliser nécessairement un véritable moteur d’inférence pour faire ces déductions, il faut simplement recréer son fonctionnement au sein du module IA de l’engin. Il faut que l’algorithme soit simple puisque les déductions peuvent être requises à chaque itération de la boucle de jeu. Comme les déductions se produisent par l’ajout de nouvelles données, l’algorithme le plus simple reste le chaînage avant.
Le chaînage avant est constitué de 3 étapes principales. Dans notre exemple, une fois que les scouts ont transmis les informations au commandement central, et que la base de fait ai été mise à jour, les déductions commencent. La première étape consiste à faire correspondre les règles aux faits. Ceci ce fait en vérifiant la partie conditionnelle des règles. Lorsqu’il y a une correspondance, la règle peut être activée. Mais avant, il faut vérifier si d’autres règles s’appliquent pour les mêmes faits. Et choisir la règle à activer. C’est l’étape de résolution des conflits, l’étape 2. On peut choisir les règles en prenant soit la première rencontrée, soit une au hasard parmi celles applicable, ou leur donner un poids dans le but d’appliquer la plus pertinente. Une fois que la résolution des conflits est terminée, la règle choisie est activée. C’est l’étape 3. La règle peut alors enclencher des évènements ou comme dans notre exemple, déduire de nouveaux faits. Quand des nouveaux faits ont été déduits, il faut recommencer les inférences jusqu’à ce qu’il n’y ai plus rien à déduire.
En résumé, l’adversaire informatique doit récolter des informations pour pouvoir établir la stratégie à adopter face à son adversaire humain. Cette façon de faire rend le jeu plus réaliste, plus satisfaisant, plus juste. L’expérience en sera donc plus grande et le jeu sera plus apprécié.
BIBLIOGRAPHIE
1- David M. Bourg & Glenn Seemann, AI for Game Developers, 2004, O’Reilly Media, Livre sur l’intelligence artificielle pour les jeux video.
public enum MemoryValue {YES, NO, MAYBE, UNKNOWN};
// Variables globales.
public MemoryValue villageois;
public MemoryValue scout;
public MemoryValue ouvrier;
public MemoryValue charpentier;
public MemoryValue bouclier;
public MemoryValue murEnceinte;
public MemoryValue maison;
public MemoryValue ecole;
public MemoryValue technicien;
public MemoryValue usineArme;
public MemoryValue scientifique;
public MemoryValue tank;
public MemoryValue caserne;
public MemoryValue fusillier;
public MemoryValue mitrailleur;
public MemoryValue sniper;
public MemoryValue soldat;
public MemoryValue piloteTank;
public MemoryValue piloteAvion;
Cette base contient tous les nœuds du graphe qui peuvent prendre 4 valeurs : YES, NO, MAYBE, UNKNOWN. Une valeur à YES implique que le joueur possède la technologie. Si le joueur possède tous les éléments nécessaires à la construction d’une technologie, mais que le fait doit être confirmé par un scout, la valeur est à MAYBE. L’ordinateur peut alors rassembler des faits en envoyant ces scouts et en faisant des observations. Si le scout rencontre un Mur d’enceinte, alors murEnceinte est mis à YES. Si le scout retourne à sa base sain et sauf, alors l’adversaire ajoute les observations du scout à sa base de fait et effectue des déductions sur les technologies possibles que le joueur est en mesure de posséder. Il le fait en inférant à travers les règles de déductions de sa base de règles. Une règle peut ressembler à celle-ci :
If (murEnceinte == MemoryValue.YES) {
charpentier = MemoryValue.YES ;
}
Cette règle nous dit qu’étant donné qu’un mur d’enceinte a été observé, il y a forcément un charpentier en jeu qui l’a construit. On peut aussi supposer que s’il y un charpentier, il y a probablement des maisons. Ce qui se traduit par la règle :
if ((charpentier == MemoryValue.YES) &&( maison == MemoryValue.UNKNOWN)) {
maison = MemoryValue.MAYBE ;
}
On pourrait se demander à quoi peut servir une valeur MAYBE. Et bien, admettons que l’adversaire doit déployer des forces en se basant sur ces valeurs, avant de gaspiller des ressources contre une technologie hypothétique, il pourra soit envoyer plus de scouts pour combler les informations manquantes ou envoyer 20% moins de soldats étant donnée qu’il ne peut confirmer la présence de cette technologie même s’il a un doute raisonnable. La stratégie à adopter selon les données de la base de faits dépasse le cadre de mon exemple.
Voici d’autres exemples de règles :
if (bouclier == MemoryValue.YES) {
ouvrier = MemoryValue.YES ;
technicien = MemoryValue.YES ;
}
if (usineArme == MemoryValue.YES) {
ouvrier = MemoryValue.YES ;
technicien = MemoryValue.YES ;
scientifique = MemoryValue.YES ;
}
if ((fusillier == MemoryValue.YES) &&( sniper == MemoryValue.UNKNOWN)) {
sniper = MemoryValue.MAYBE ;
}
Ceci étant dit, il ne reste qu’à traduire chaque lien de l’arbre technologique en règles pour que le moteur d’IA fasse les déductions adéquates. Attention, cela peut représenter un nombre impressionnant de règles. Et si certains faits ne sont pas, ou sont mal représentés par les règles, le moteur d’inférence ne pourra jamais faire les bonnes déductions. De plus, il ne s’agit pas d’utiliser nécessairement un véritable moteur d’inférence pour faire ces déductions, il faut simplement recréer son fonctionnement au sein du module IA de l’engin. Il faut que l’algorithme soit simple puisque les déductions peuvent être requises à chaque itération de la boucle de jeu. Comme les déductions se produisent par l’ajout de nouvelles données, l’algorithme le plus simple reste le chaînage avant.
Le chaînage avant est constitué de 3 étapes principales. Dans notre exemple, une fois que les scouts ont transmis les informations au commandement central, et que la base de fait ai été mise à jour, les déductions commencent. La première étape consiste à faire correspondre les règles aux faits. Ceci ce fait en vérifiant la partie conditionnelle des règles. Lorsqu’il y a une correspondance, la règle peut être activée. Mais avant, il faut vérifier si d’autres règles s’appliquent pour les mêmes faits. Et choisir la règle à activer. C’est l’étape de résolution des conflits, l’étape 2. On peut choisir les règles en prenant soit la première rencontrée, soit une au hasard parmi celles applicable, ou leur donner un poids dans le but d’appliquer la plus pertinente. Une fois que la résolution des conflits est terminée, la règle choisie est activée. C’est l’étape 3. La règle peut alors enclencher des évènements ou comme dans notre exemple, déduire de nouveaux faits. Quand des nouveaux faits ont été déduits, il faut recommencer les inférences jusqu’à ce qu’il n’y ai plus rien à déduire.
En résumé, l’adversaire informatique doit récolter des informations pour pouvoir établir la stratégie à adopter face à son adversaire humain. Cette façon de faire rend le jeu plus réaliste, plus satisfaisant, plus juste. L’expérience en sera donc plus grande et le jeu sera plus apprécié.
BIBLIOGRAPHIE
1- David M. Bourg & Glenn Seemann, AI for Game Developers, 2004, O’Reilly Media, Livre sur l’intelligence artificielle pour les jeux video.
Commentaires
Enregistrer un commentaire