Programmation Bayésienne
de Personnages de Jeux
VidéosRonan Le Hy
encadré par Pierre Bessière et Olivier Lebeltel

R APPORT DE S TAGE DE DEA

Juin 2002

Institut National Polytechnique de Grenoble
46, avenue Félix-Viallet
38031 Grenoble cedex 1

Ronan Le Hy (encadré par Pierre Bessière et Olivier Lebeltel)
Programmation Bayésienne de Personnages de Jeux Vidéosc Juin 2002 par Ronan Le Hy
rapport_bots.tex – Programmation Bayésienne de Personnages de Jeux Vidéos – 21/6/ 2002 – 2:27

Programmation Bayésienne de Personnages deJeux Vidéos
Ronan Le Hy (encadré par Pierre Bessière et Olivier Lebeltel)
rlehy@free.fr

3

Remerciements
Je remercie en premier lieu mes maîtres de stage, Pierre Bessière et Olivier Lebeltel pour leur encadrement souple et éclairé, mais aussi pour m’avoir offert un sujet de stage qui fait un excellent sujet deconversation pour les dîners en ville.
Je remercie également David Raulo, thésard à l’INRIA, dont les discussions ont été extrêmement
enrichissantes quant aux mondes virtuels et à l’approche bayésienne du contrôle de personnages synthétiques.

introduction
Ce stage de DEA Sciences Cognitives a été effectué à l’INRIA Rhône-Alpes du 1 er Mars au 30 Juin
2002, au sein de l’équipe SHARP, sous la direction de Pierre Bessière et Olivier Lebeltel. Il porte sur laprogrammation bayésienne de personnages de jeux vidéos.
Nous explorons l’intérêt de l’application d’une technique de programmation des robots aux jeuxvidéos. Nous espérons montrer les bénéfices de cette approche probabiliste en termes pratiques. Pourcela, nous utilisons une plateforme basée sur un jeu commercial nommé Unreal Tournament 1 , pourlequel nous nous attachons à développer un joueur synthétique.
Nous exposons en premier lieu la problématique de l’intelligence artificielle dans les jeux vidéos, dupoint de vue de l’indutrie et de celui de la recherche ; cela nous conduit à énoncer les critères d’évaluation de notre méthode par rapport à celles existantes. Nous détaillons ensuite la construction de notre
modèle bayésien, puis son ajustement sous deux formes : par spécification manuelle exhaustive, puis par
apprentissage par l’exemple. Enfin, nous analysons les apports de notre méthode dans le domaine de laprogrammation de personnages dans les jeux vidéos. Cela nous conduit en particulier à une comparaison
avec la technique classique des automates à états finis.
Une synthèse du cadre technique de notre étude est fournie en annexe. Cela inclut une description
de la plateforme de jeu utilisée (Unreal Tournament et Gamebots), et du système de contrôle que nous
avons développé par dessus pour acueillir notre schéma de programmation bayésienne.

1

Unreal Tournament est une marque déposée de Epic Games, Inc.

5

Chapitre 1

problematique de l’IA dans les jeux vidéos
1.1 problématique industrielle
1.1.1 impératifs industriels
Nous dressons ici une liste de ce qui peut être vu comme des contraintes ou des objectifs lors dudéveloppement d’agents pour jeux vidéos. Une discussion plus détaillée sur ce sujet a été faite par L AIRD([Lai00a]).
du point de vue du joueur
L’objectif central est la performance comportementale, qui doit s’approcher au mieux de celle d’unjoueur humain. Cela implique des capacités de raisonnement spatial, de mémoire, de raisonnement debon sens, d’établissement de buts, de tactique, de planification, de communication et de coordination,d’adaptation, d’imprévisibilité, et de personnalité.
Un point important qui vient contraindre cet objectif de performance est que le personnage synthétique ne doit pas tricher. Autant que possible, ses perceptions et possibilités d’action doivent êtres
calquées sur celles du joueur humain. Dans le cas contraire, l’intérêt du jeu est fortement diminué.
du point de vue du programmeur
La première contrainte pour le programmeur est la productivité. Cela implique que pour lui la facilité
de développement et la puissance expressive du mode de description sont essentielles.
Par ailleurs, pour qu’une méthode soit exploitable, elle doit conduire à des résultats prédictibles
et contrôlables. Les comportements produits doivent être ajustables, pour éventuellement en produire
différentes variantes. A cet effet, toutes les méthodes permettant un ajustement par apprentissage sont unavantage.
contraintes industrielles
Enfin, une méthode de programmation de personnage synthétique est utilisable si elle s’intègre biendans le schéma de développement d’une application complexe, et si ses besoins de temps de calcul sontlimités. En effet, l’industrie fait généralement une séparation claire entre les développeurs et les concepteurs de niveaux et de personnages ; ces derniers doivent pouvoir manipuler une interface simple sans6

7maîtriser les aspects techniques qui la sous-tendent. De plus, le temps processeur réservé à l’intelligenceartificielle dans un jeu est typiquement de l’ordre de 10% à 20% ([Woo01b]).

1.1.2 techniques classiques employees
Nous faisons ici un survol rapide des techniques d’intelligence artificielle couramment utilisées dansl’industrie du jeu vidéo. Il faut noter l’absence de certaines méthodes bien implantées dans la recherche
académique, comme les réseaux de neurones ou les algorithmes génétiques. Ces principes ont du mal às’implanter dans les pratiques industrielles ([Woo01b]), principalement pour leur réputation – justifiée
ou non – d’être peu prédictibles et difficiles à maîtriser.
systèmes de scripts
La méthode de programmation de personnages artificiels de loin la plus commune est l’écriture descripts, dans un langage propre ou en C, sans méthodologie codifiée de haut niveau. Parmi les jeux
utilisant ce mode de programmation, on trouve Unreal Tournament ([unr]), Civilization II ([civ], ou
Baldur’s Gate ([bal]).
La puissance expressive de ce type de méthode est bonne, dans la mesure où le langage de scripts
utilisé est généralement propre au moteur de jeu. Cependant, ces langages étant souvent des langages impératifs ou objets classiques augmentés d’un système de gestion d’évènements, ils ne fournissent pas un
cadre qui faciliterait particulièrement la programmation comportementale. Un script classique se ramène
généralement à des cascades de si ... alors ... sinon .... Ce type de systèmes impose
donc aux programmes de conserver une taille limitée pour éviter de rendre les heuristiques ingérables
par le programmeur.
Avec ces systèmes de programmation, la programmation et l’ajustement des comportements est réservée à des programmeurs, et ne peut être confiée à des scénaristes. Cependant, le temps de calcul est
bien maîtrisé, dans la mesure où l’API de programmation est de suffisament haut niveau et où les scripts
restent de taille raisonnable (pour la raison de complexité de conception évoquée plus haut).
Enfin, grâce à ce type de méthode, il suffit de rendre le moteur de script accessible pour permettre lamodification du jeu par tous (ce qui est un argument commercial).
logique, moteurs d’inférence, systèmes experts
Des approches logiques sont faites de la programmation comportementale. Par exemple, John Funge
présente un langage de type Prolog dédié à la programmation de comportements ([FTT99]) ; on peutaussi citer SOAR ([Lai00b]), architecture de contrôle proche d’un système expert.
Ces systèmes, faisant souvent l’objet de recherches académiques, ne s’imposent pas dans l’industrie.
Les raisons de ce fait sont probablement leur lourdeur et leur gourmandise en temps de calcul. Malgrécela, ils autorisent une expressivité très grande, et intègrent bien certains problèmes d’apprentissage(pour SOAR : [Lai00b]).
flocking
Une technique particulièrement applicable aux jeux mettant en scène de nombreuses unités simples
est celle du flocking. Cela consiste à essayer de faire émerger des comportements de groupe à partir decomportements élémentaires « sociaux ». [Woo01a] montre ainsi comment synthétiser un comportement

8de troupeau à partir de quatre règles comportementales élémentaires qu’appliquent séparément chacun
des individus contrôlés : séparation, alignement, cohésion et évitement.
Ce type de méthode donne des résultats souvent saisissants pour peu d’efforts de programmation.
Cependant, le contrôle en est difficile, et on ne peut en envisager l’utilisation que dans le cas d’unités
simples en grand nombre. Par ailleurs, les contraintes de temps de calcul et d’ajustabilité du comportement de masse produit font que les comportements élémentaires doivent rester simples.
automates
Un automate à états finis est un ensemble d’états reliés par des transitions étiquetées par des évènements ou des combinaisons de valeurs des variables décrivant le système. Chaque état correspond à unmode de fonctionnement du système, et les transitions d’état à état sont franchies selon les valeurs desvariables internes. Un exemple d’implémentation pratique appliquée aux jeux vidéos de cette techniqueclassique peut être trouvée dans un article d’E. Dysband ([Dys00]).
Ce mode de structuration des programmes a l’intérêt de fournir un schéma simple et bien compris
de construction d’un comportement à partir du séquencement de plusieurs comportements élémentaires.
Cependant, les transitions étant exprimées sous forme logique, ce type de structure se prête mal à l’apprentissage. Enfin, un automate nécessite très peu de calcul, et peut être implanté de manière très légère
(voir par exemple [Car01]).
Les automates sont aussi utilisés dans leur version floue et non déterministe – dont un exemple
pratique est donné dans un article d’E. Dysband ([Dys01]). Ils gagnent alors en expressivité, au prix d’une
légère complication du formalisme. Cependant, ils sont sujets à l’explosion combinatoire du nombre decas à traiter au niveau des transitions quand le nombre de variables augmente (une méthode pour tenterde réduire cette explosion est exposée dans [Zar01]).
Une comparaison des techniques d’automates déterministes à états finis et de notre méthode de programmation bayésienne sera faite au 5.2.

1.2 problématique de recherche
Les jeux vidéos fournissent aujourd’hui des problèmes mettant en jeu des interactions complexes
avec le joueur humain. Les rôles qu’un personnage synthéthique peut jouer sont multiples. Il peut être([LVL00]) ennemi tactique (comme dans la présente étude), partenaire du joueur humain, personnage
secondaire de soutient du scenario, opposant stratégique, simple unité parmi d’autres, ou encore commentateur... Dans tous les cas l’objectif pratique est d’avoir un personnage qui agit comme agirait unjoueur humain.
Devant cet objectif d’une intelligence artificielle de niveau humain, l’idée d’une forme de test deTuring ([Tur50]) survient : peut-on créer un joueur synthetique qui fasse illusion aux yeux d’un humain ?
Cette approche est d’ailleurs suggérée par Laird ([LD00]), où une métode d’évaluation de personnages
synthétiques est proposée ; un des critères pris en compte est l’« humanité ». Pour l’évaluer, des juges observent des joueurs humains et synthétiques en action, et tentent de déterminer lesquels sont humains, etlesquels sont artificiels. Cette idée met en valeur le fait que l’objectif recherché est bien une performancede niveau humain, et non une performance la meilleure possible ; par exemple, un délai de réaction trop
court désignera un personnage comme artificiel, alors même qu’il représente un avantage du point de vue
de l’efficacité au jeu.
Les jeux vidéos présentent les avantages pratiques d’autoriser un mode de développement non monolothique sur des plateformes très variées et peu onéreuses, et d’avoir le soutient d’une industrie puissante.

9Celle-ci a des besoins en termes de résultats comme en termes de méthodes, et possède des moyens financiers, ainsi qu’une forte expertise technologique dans les champs connexes (animation, interfaces...).
Finalement, les jeux vidéos apparaissent comme « un environnement riche pour le développement
incrémental d’une IA de niveau humain » ([LVL00]).

1.3 cadre pratique
Nous avons fait le choix de travailler sur un jeu de combat à la première personne : Unreal Tournament, agrémenté d’une modification nommée Gamebots ([AMS 01], [KVS 02], [gam]) permettant des’y connecter facilement. Ce jeu met en scène des personnages humanoïdes se déplaçant dans un mondetridimensionnel. Le joueur contrôle un de ces joueurs de l’intérieur. Le but est de tuer un maximum defois les autres joueurs, à l’aide d’armes, de munitions, et de bonus de santé ramassés dans le niveau. Un
comportement performant dans cet environnement a donc une composante de dextérité (viser juste, sauter et courir au bon endroit...), et une autre de gestion de ressources (ramasser les armes les plus fortes,savoir fuire quand son niveau de vie est bas...).
Les modalités techniques de notre étude ainsi que l’architecture de contrôle choisie sont détaillées enannexe. Le fait que le type de jeu choisi soit bien adapté aux comportements réactifs, et l’accès simple
au moteur de jeu fourni par Gamebots sont les principaux avantages de cette plateforme.
Dans la suite de ce rapport, nous utilisons le terme bot (prononcé comme botte) pour désigner ces
robots virtuels supposés agir comme des humains. Nos bots sont des personnages d’un jeu de combat,
dont l’apparence n’est pas différente de celle des avatars commandés par des joueurs humains, et qui
tendent au même but, à savoir toucher ses ennemis un nombre maximum de fois.

1.4 méthodologie d’évaluation
Compte-tenu des objectifs exposés au 1.4 et de la plateforme technique choisie, nous avons les objectifs pratiques suivants :– mettre en place un schéma de programmation bayésienne pour le comportements de personnages,
et l’évaluer en regard des méthodes existantes ;– mettre en oeuvre et évaluer une méthode d’ajustement du comportement programmé par aprentissage.
Il faut noter que ces objectifs n’engagent pas à construire un personnage qui soit absolument efficace
au combat ; il est question d’élaborer une méthode et d’en montrer les avantages pratiques.
Le problème posé est d’évaluer les comportements programmés au regard des critères énoncés au
1.4, que l’on peut résumer de la façon suivante :1. performance du bot :(a) score(b) « humanité » : raisonnement spatial, mémoire, bon sens, buts, tactique, planification, communication et coordination, adaptation, imprévisibilité, personnalité
2. développement :(a) facilité de développement(b) puissance expressive
3. comportements :10(a) prévisibilité(b) ajustabilité
4. contraintes industrielles :(a) séparation développement / conception des personnages(b) temps de calcul nécessaire limité
Une solution pratique pour évaluer le critère 1a (score) est de laisser les personnages programmés secomparer au combat à des bots existants. Nous avons essayé cette solution, en utilisant comme référence
un bot développé sur la même plateforme (Gamebots). Cependant, les résultats de ce côté ne sont pas
aussi etoffés qu’on le voudrait à cause de l’instabilité des bots de référence disponibles. Nous avons donc
aussi comparé les différentes versions de nos bots entre elles.
Le critère 1b (« humanité ») met en jeu des aspects purement délibératifs et communicationnels,
que nous avons délibérément laissés de côté dans cette étude. Nous retiendrons donc essentiellement
les aspects d’imprévisibilité et de personnalité. Nous retiendrons aussi l’aspect stratégique plutôt que
tactique, puisque c’est à ce niveau que se place notre modèle comportemental. Enfin, Nous laissons decôté le problème de l’adaptation en ligne, pour nous focaliser sur l’apprentissage hors ligne 1 . Les notions
retenues sont qualitatives et subjectives ; nous tenterons cependant de donner des éléments d’appréciation
tangibles et termes de comportement.
Les critères 2a (facilité de développement) et 2b (puissance expressive) seront évalués au regard dutemps pris pour programmer un comportement, et de la variété des comportements possibles au sein denotre modèle.
Nous évaluerons les criteres 3a (prévisibilité) et 3b (ajustabilité) au regard de la facilité de programmer différents comportements avec certaines caractéristiques particulières (comme l’agressivité, et laprise en compte du niveau de santé).
La question 4a (séparation développement/conception) se verra abordée sur la base de l’organisation
de notre modèle ; 4b (complexité) à partir du calcul mis en jeu dans par modèle.

1

C’est-à-dire où les phases d’apprentissage et de restitution sont séparées.

Chapitre 2

modèle de programmation bayésienne depersonnages
2.1 programmation bayésienne des robots
Nous faisons ici un très bref rappel du principe de la programmation bayésienne des robots ([BDL 98a],[BDL 98b],[Leb99]). Nous ne prétendons pas à l’exhaustivité, mais à jeter les bases de son application
aux jeux vidéos.

2.1.1 organisation générale
Un programme bayésien (voir figure 2.1) est composé d’une description, et d’une question. La description est constituée du choix des variables pertinentes pour le problème, de la décomposition de ladistribution conjointe, et de l’écriture des formes paramétriques.
La question consiste à interroger la distribution en faisant un tirage sur une distribution de probabilité.


















DescriptionProgramme

















Variables Pertinentes
Décomposition
Formes Paramétriques
Identification

Question
F IG . 2.1 – structure d’un programme bayésienPlutôt que de réiterer les considérations formelles des références données plus haut, nous explicitonsla méthode sur un exmple simple (sans rapport avec notre bot).

2.1.2 exemple
Considérons un personnage très simple pouvant se trouver dans deux états : attaque et fuite. Cepersonnage dispose de son niveau de vie et (faible ou fort) de son arme (faible ou forte). A partir de ces
informations, il doit décider à chaque instant dans quel état passer.

11

12

variables pertinentes 
  !"  Les variables pertinentes sont :– l’état– le niveau de vie– l’arme
décomposition

Nous choisisson d’écrire la décomposition comme :#%$ &!')(+* #%$ ,( #%$ .- )( #/$ !,- ,(! L’hypothèse d’indépendance conditionnelle nécessaire à l’écriture de la décomposition sous cette forme
est que et sont indépendants conditionnellement à .
formes paramétriques#%$ ,(#%$ 0- ,( %# $ ! - )(Nous choisissons les formes paramétriques suivantes :est uniforme ;––etsont définies dans les tables 2.1 et 2.2.

12 34
6 7
7 689#%$T . 2.1 – 0- )(12 34 5
689 7 
7 7#%$
T . 2.2 – !- )( 5 

AB

AB

Le format de ces tables est le suivant. La première colonne fait la liste des valeurs de la variablecherchée, la première ligne celle des valeurs des la variable connue. Par exemple, pour la table 2.1 lacasecorrespond à. Les cases marquées d’un sont calculées de façon
à de ce que chaque colonne soit normalisée, c’est-à-dire.

$ 9;:1(
FUP?QSQSTV (W*X9#%$ <*=- *=3>?(7@A1CBED #%$FHGI2JK GMI L * FNGOI JK GMI L D - FNPRQSQST *identification
Toutes les formes élémentaires étant complètement spécifiées, nous n’avons pas d’identification à
faire. L’identification pourrait par exemple consister à apprendre les tables au lieu de les écrire complètement.

13question%# $ - ! )( . Elle se résout de la façon suivante :#%$ - ! )(W* #/#%$ "!$ ' ( * #/$ #%)($ #%$ #%.$ - ,( #%$ #/!,$- ,( (! )( B  ,( .- )( !,- ,(Notre question est :Une décision est ensuite prise à partir de la distribution résultante. Elle peut consister à choisir lavaleur de de plus grande probabilité, ou à effectuer un tirage.

2.2 description
2.2.1 variables pertinentes
Les variables choisies représentent les espaces moteurs et sensoriels du bot au sein du modèle. En
particulier, les variables sensorielles font la représentation du monde du bot : ce sont celles qui lui permettent de caractériser son état interne et son environnement en temps réel, et de prendre des décisions.
Pour faire le choix de ces variables, nous avons pris en compte les informations disponibles au sein denotre plateforme. Nous en avons gardé un certain nombre d’informations simples et vraisemblablement
pertinentes pour un humain qui jouerait. Enfin, nous avons cherché à conserver un nombre réduit devariables pour garder le modèle relativement simple.
Les variables choisies le sont aussi dans la perspective d’un comportement réactif. Cela exclut par
exemple des caractéristiques délibératives comme la planification.
variables d’état
Ces variables sont l’équivalent des variables motrices en robotique.

     )   : l’état du bot à l’instant  (les valeurs possibles sont détaillées plus
bas).
 
      )     : l’état du bot à l’instant  9 .
 4         : drapeau indiquant au bot de faire feu.


Les valeurs possibles des variables d’état  et 







 sont :: (attaque) le bot recherche un ennemi s’il n’en a pas à proximité, et l’attaque.
: (recherche arme) le bot part à la recherche d’une arme.
: (recherche vie) le bot part à la recherche d’un bonus de santé.
: (exploration) le bot explore les parties du niveau non encore visitées.

: (fuite) le bot cherche à s’éloigner des ennemis en présence.

: (détection danger) le bot observe autour de lui pour détecter un éventuel danger.

variables sensorielles      E! #" $   : le niveau de vie du bot.
%%  '&2(" E!1#"'"  3) : la force de l’arme du bot.

+*,

%%
-   '& ." 1E! #"'"  ) : la force de l’arme de l’adversaire s’il y en a un.

14









   - : drapeau indiquant si un bruit a été entendu récemment.

 %% - "" %,  &2."  " ,     : le nombre d’ennemis proches.
 
%%      : drapeau indiquant la proximité d’une arme.
  O "       : drapeau indiquant la proximité d’un bonus de santé.
2.2.2 décomposition
La distribution conjointe est décomposée de la manière suivante :#%$     %%  %  *,     %%  "'" #%,     %   O"O   (* #%#%$$      %   %% +*, +-*, 4  3>   %    "'" %,     %%   O"1(
4 -     %% %% 4 34 %% - "'" %,    %%   O"(%#$* #%$  (#%$ >- -  ( ( #/$  %%-  ( #%$  %  *,  -  (#%$  3>2-  ( #%$  %% - "'" #%) -  ( #%$    %% -  ( #/$   O"-  (#%$  4 -   %% - "'" #%) (
Deux hypothèses d’indépendance conditionnelleLa sont formulées *, pour écrire cette décomposition.

,
%
,
%

,
,

%
'
"
"
%
,
première
est
que
les
variables
perceptives(% ,   " ) sont indépendantes deux à deux sachant   .
""  %  ,La seconde hypothèse est que sachant %ne dépend pas des autres variables.
 ne variera que -selon
Cela revient à faire le choix que
% - "'" %  .
   ), celle
Cette décomposition met en jeu une la probabilité du passage d’un état à l’autre (du tir en fonction du nombre d’ennemis proches, ainsi que celle de chaque variable perceptive sachant  ). Nous allons donc spécifier et utiliser lal’état suivant le moment où la variable est mesurée (distribution de chaque variable perceptive en supposant connu l’état à l’instant suivant. Cette démarche,appelée programmation inverse, peu paraître peu naturelle au premier abord ; cependant nous verrons
qu’elle rend l’identification par écriture à la main ou par apprentissage aisée et efficace.

 %  O 

4

 % %  4
 % , 4
 % ,#%$ 85858 - (3>  %
#%$

,

- (

#%$ (

2.2.3 formes paramétriques– est choisi uniforme.
– Toutes les autres distributions sont spécifiées dans des tables. La partie suivante (3) est centrée surl’écriture et la génération de ceux-ci.

2.2.4 identification
L’identification consiste ici à fixer les valeurs des tables de probabilités. Elle peut être faite manuellement, ou par apprentissage,
manuelle
Une forme d’identification manuelle peut être faite. Comme sur notre exemple-jouet du 2.1.2, lestables sont écrites manuellement.

15

apprentissage
L’apprentissage que nous envisageons ici est supervisé : un humain pilote le bot à partir d’une interface lui permettant de sélectionner en temps réel l’état du bot et de suivre son évolution dans le jeu (voirfigure 2.2).

F IG . 2.2 – interface de pilotage du bot

Q DV
Q DV
%
#
$
V
9

D
@ + @; @A X*  - * (+* B D Q D V  - 0QV$Voù  et  sont des variables, D est le nombre d’occurences du cas  *  D  * ( , et - 0- est lenombre de valeurs possibles pour  .

Cet apprentissage permet de fixer les tables de probabilités sous la forme de lois de succession de
Laplace. Cette loi, paramétrée par les, s’écrit :Il est intéressant de remarquer que loi de succession de Laplace part, pour un nombre nul d’échantillons, d’un a priori uniforme sur la distribution :@ $ A>( Q D V *'6 #%$ &*  D - *  V (W* - 09 -De plus, quand le nombre de d’échantillons devient grand, la loi tend vers celle donnée par lesfréquences :Q DV
9Q  V Q DV
B D D  - 0-  B D Q D V

Enfin, il est notable que cette loi n’assigne jamais de valeur de probabilité nulle. Une discussion plus
poussée son l’intérêt peut être trouvée dans un Probability Theory : the Logic of Science, d’E. T. Jaynes([Jay]).

16

2.3 question
La première question posée au modèle pour faire agir le bot est : « quelle est la distribution de l’étatà l’instant suivant, sachant l’état à l’instant courant et les valeurs des variables sensorielles ? » ; soit, dansnotre formalisme :#%$  - )   %%  %%  *, 4  34  %% - "'" %,     %%   O"1(

Elle est résolue de la façon suivante :#%$  -    %%  %% +*, 4  34  %% - "" %,     %%    "1(
#/$


 *,





)


%
%
%
%





4

3

4



%
%


'
"
"
,
%


 

* #%$    %%  %% +*, 4  34  %% - "'" %,     %%%%   O "O("(* 9 $#%$  ( #%$   -  ( #%$ -   ( #%$  % -   ( #%$  %% +*, -  -   ( #%$   -   (#/$   %%  "'" #%, >-  ( #%$   %% -  ( #%$     " -  ( (
 #%$ +*, 

$
%
#
$
%
#
$
%
#
$
9
* #/$     -  ( - #% $ (  % -   ( #%$ %% -  -   ( #/$  34C-   ( (2.1)
 %%  "'" #%, >-   (   %% -   (     " -   ( (* B   #%#%$$  ( #%$  * , -  ( #%$ >- #% $  ( #%$  %% - #%$ (avec#%$  %  %% -  ( -#/$  (  O "34C- -  ( (  %   "'" %,  -   (
* #%$ #%$ ( On remarque que + ( n’intervient pas dans la résolution de la question.
#%$  4 -   %% - "'" %, ( . Elle est spécifiée directement dans
La seconde question porte sur le Tir :le modèle et ne requiert pas d’inférence.

#/$ * D -* D (

La résolution de la première question met en valeur l’influence de chaque distribution élémentaire 
sur la distribution de l’état à l’instant suivant. En particulier, si une probabilité
vaut zéro, cela implique que 
est nulle aussi. Nous voyons donc là le moyend’interdire de passer dans un état pour une valeur donnée d’une variable sensorielle.

#%$*' D - 85858 * D 85858 (Chapitre 3

programmation d’un comportement
Nous identifions ici nos formes paramétriques par écriture directe. Nous nous attachons à montrer,à travers les commentaires de toutes les tables utilisées, de quelle façon ces tables sont structurées etcomment elles influencent le comportement synthétisé.

3.1 tables de comportement
3.1.1 format des tables
Chaque table est donnée en deux versions, qui correspondent à deux types de comportements : odge,
bot ordinaire, et brsk (berserk), bot très agressif.

3.1.2    

La table 3.1 correspond aux probabilités de transitions entre états. Elle est construite pour stabiliserles états (auto-maintien). Les probabilités de transition entre deux états différents sont fixées à une valeurfaible.
La version brsk présente une particularité : outre les de la diagonale correspondant à la force del’auto-maintien, la probabilité est toujours grande de basculer dans l’état Attaque.

7

3.1.3

      

La table 3.2 montre comment mettre en relation une variable et l’état du bot. Par exemple, sachantque le bot bascule dans l’état Recherche de Vie, la probabilité qu’il ait un niveau de vie élevé est de, celle que son niveau de vie soit moyen de, et celle que son niveau de vie soit faible,.
Le comportement brsk est indifférent à la variable. Il consiste en effet à attaquer aveuglément,sans se préocupper de son niveau de vie.

6 66 9
6 6 96 66 9 * 6

3.1.4

6 6 9

9     

La table 3.3 est identique pour les deux comportements envisagés. Elle spécifie en particulier que lebot a peu de chances de percevoir un bruit dans les états de recherche de santé ou d’arme, d’exploration
ou de détection de danger.

17

18





7I
9 I E6
9 I E6
9 I E6
9 E6
 9  I E6
odge

 7

68 6 968 6 968 6 968 6 9
 68 6 9
brsk





7




7I
9 I E6
9 I E6
9 I E69  E6
68 6 97
68 6 968 6 968 6 968 6 9



7I
9 I E6
9 E6
7I
9 I E6
9 E6
68 6 968 6 968 6 97
68 6 968 6 9#%$  -  (T . 3.1 –7I
9 6
7I
9 I 6
9 I 6
9 6
68 6 968 6 97
68 6 968 6 968 6 97I
9 I E6
9 I E6
9 E67I
9 E6

68 6 968 6 968 6 968 6 97
68 6 9

7



S

7





7I
9 I E6
9 I E6
9 I E69 E677

 

68 6 968 6 968 6 968 6 968 6 9

AB





 
! "$  
odge ! "$  

7

brsk

7

7

7

7
68 66 9
689




7

689

7

7

7

7

7

7

68 6 968 66 9

TAB . 3.2 –

 



7
  7odge  7  7
brsk





7

689
7

689



689
7
7



7
7

689

7

7
7
7

7

689

#%$ -  (

7
7

S

68
68 :
689
7



7

689

7



7

9 I E6

7

S

9 I E6
7

7
7#%$  C-  (T . 3.3 –

AB

7



S

7

7

I 

9 E6
I 
9 E6

19

3.1.5

      

La table 3.4 détaille la probabilité du nombre d’ennemis selon l’état du bot. On cherche ici à spécifierque odge a tendance à fuire s’il est en présence de deux ennemis ou plus, alors que le bot brsk est porté
à attaquer quand les ennemis sont nombreux. Les deux bots explorent quand il n’ont pas d’ennemis.
Cette connaissance est exprimée sous forme inverse : nous écrivons donc par exemple que sachant quele bot brsk passe dans l’état Attaque, il a de grandes chances ( ) d’avoir deux ennemis ou plus, depetites chances ( ) d’avoir un ennemi, et aucune chance de pas avoir d’ennemi. Cela lui interdit donc
effectivement de passer en attaque quand il n’a pas d’ennemi et son excitation accrue quand de nombreux
ennemis sont présents. Pour le bot odge, on peut noter que sachant que l’état suivant est la recherched’armes, les chances sont infimes que des ennemis soient présents.

6 

68 :

 brsk
2& ."
 "

6



68 :
 ( 6 8 
 odge&2."6 "7,    ( 689
,

7
7







7

7



7



7

7

7

 

7I
9 I E6
9  96



7

7

7I
9 I E6
9  96

6
68 66 9 689
7
68 666 9 7#%$ %   "'" %,  -  (T . 3.4 –
68968 6 9

7

7



7

7



68 66 9
68 666 9

AB

3.1.6

         et        

Les tables 3.5 et 3.6 rendent le bot opportuniste quand il passe à côté d’une arme ou d’un bonus desanté : certains états sont exclus quand un objet est proche. En particulier, la probabilité d’être proche,ou  est faible.
d’une arme quand on bascule dans les états 

 

brsk

7



  7odge  7  7




S
7I
7I
7
7
9 E6 9 E6 7


S
7
7I
7I
7
7
9 E6 9 E6 7#/$  %% -  (T . 3.5 –  

7



AB

3.1.7

      7I
9 E6

7I
9 E6

La table 3.7 montre que l’arme courante du bot a une influence interdit ou influence le basculement
vers certains états ( ,  ,  ), mais ne joue pas sur le basculement vers d’autres ( ,,  ).

20

 





7
  7odge  7  7brsk



7I
9  E6

7I
9 E6
 brsk'&2("
E1! #"'"
 3
 odge'&2("E1! #"'"
 3

7

68 6 97

9 I E6
7

7
7
7

7

7I
9 E6

7I
9 E6



AB



7



6I8 66 9
9   6 

77



6I899 6

7
7

7



7
7

7
7

7

 

7



7

7

 

7

7

6I8 66 9
9 E 67

689
68 6 9

7

TAB . 3.7 –

3.1.8



7I
7
9 E6 7

S
7
7I
7
7
9 E6 7#/$
T . 3.6 –   O" -  (




7

S



%# $  %%>-  (

7
7



           

La table 3.8 spécifie que le comportement d’attaque est inhibé par l’arme de l’adversaire si elle est
forte, particuliérement pour le comportement odge.



'&2("
E!1#"'"
 3
 odge'&2("
E!1#"'"
 3

7



brsk

7

7
7



7

6 89
7

7





7

68 6 9     

7



7

7





7
7

7

7

TAB . 3.8 –

3.1.9

7



7

7



7

7



7

7
7

7
7
7

#%$  %% +*, - 4 -  (

7

7

 

7

7

 

7

7

7
7





La table 3.9, identique pour les deux comportements envisagés, décrit une heuristique de tir simple :le bot fait feu s’il a des ennemis autour de lui. Il faut noter que cette table simple est quasiment équivalenteà l’utilisation d’un simple$ %% - "" %,  *  '& ." (L’avantage de la gestion bayésienne de la variable 4 est l’homogénéité du modèle.
 4

21

 



'& ."

7
 6 8 66 9

brsk

7

"

68 66 9

,     odge
68 66 9
 



'& ."

"

7
68 66 9
 68 66 9 7#%$  4-  %   "'" %, ?(
T . 3.9 –7

7

,    68 66 9

AB

3.2 résultats
Dans ces résultats, nous faisons référence aux critères d’évaluation établis au 1.4.
1a score
La version brsk se montre plus efficace et prend généralement une avance au score de 20% à 30%.
On observe que dans l’état de la plateforme sur laquelle tourne notre modèle, la fuite semble un mauvais
choix, souvent plus dangeureux que l’attaque.
1b « humanité »Ce critère est relié à celui de prévisibilité. Les bots se comportent, vus de l’intérieur comme del’extérieur (c’est-à-dire en voyant ou non leur état interne) de manière plausible ; dit autrement, ils ne
donnent pas l’impression d’agir au hasard.
2a facilité de développement
L’écriture de ces tables est relativement systématique. Elle a été faite en une vingtaine de minutes.
On peut cependant arguer que celle-ci deviendrait impraticable si le nombre de variables sensorielles ou
celui des états possibles augmentait grandement. Dans le cas de l’augmentation du nombre des valeurspossibles des variables, il serait sans doute plus intéressant d’utiliser des formes paramétriques fonctionnelles. Par ailleurs, la démarche de programmation inverse est particulière et parfois peu intuitive ;cependant, l’habitude permet de maîtriser cette technique qui est centrale à notre modèle.
2b puissance expressive
Les limites de la puissance expressive de notre modèle sont dans le choix de nos variables. En effet,
nous contrôlons avec ces tables l’influence de chacune des variables sensorielles sur l’état du bot. Nousavons vu en particulier comment interdire ou inhiber à différents niveaux un état quand une variable
prend une valeur donnée.
3a prévisibilité
Les deux comportements programmés ici montrent après essais leur plausibilité. Il apparaît en effet
que les bots changent d’état de manière sinon toujours prévisible, au moins compréhensible. Les tablesde probabilités remplissent leur rôle selon les attentes.
3b ajustabilité
Il est intéressant de constater que les différences de comportement que nous avons cherché à introduire entre les versions odge et brsk apparaissent dans le jeu. Elle se montre comme prévu plus agressive,

22

et ses différentes particularités recherchées se retrouvent. Par exemple, elle ne se préoccuppe pas de son
niveau de vie, et bascule très rarement dans l’état Fuite.
4a séparation développement/conception
Pour implanter les comportements, le seul travail nécessaire a été de saisir les tables dans des fichiers.
Notre modèle est en effet adapté au chargement des comportements à la volée, sans recompilation ni
modification des routines de calcul. Il est donc clair que la séparation entre l’implantation du modèle etson ajustement peuvent être complètement séparés.
4b complexité
L’écriture des tables ne met pas en jeu de calcul. La question de la complexité est donc ici sansfondement.

Chapitre 4

apprentissage d’un comportement
Notre propos ici est d’ajuster un comportement, les connaissances préalables étant posées. On cherche
donc à déterminer les tables à partir d’un apprentissage.
Il s’agit donc d’ajuster un modèle réactif à un comportement humain complexe. Cela exclut de reproduire ce comportement dans sa totalité, en particulier dans ses aspects de planification. De plus, notre
bot ne possède pas de représentation structurée de l’espace, ce qui écarte sans discussion qu’il puisse
prendre en compte les même variables que le joueur humain. Cependant, nous avons l’espoir de pouvoir
ajuster un modèle réactif imitant certains des aspects du jeu, à savoir la gestion des ressources (arme,santé) et des objectifs (atteindre son adversaire sans être atteint).

4.1 pilotage par comportement
Le pilotage par comportement, déjà évoqué au 2.2.4, consiste à fournir au concepteur de personnage
une interface lui permettant de piloter le bot. Cette interface (figure 2.2) comporte d’une part la fenêtre
de jeu d’Unreal Tournament centrée sur le bot, d’autre part une fenêtre de contrôle de l’état interne dubot. Cette fenêtre inclut des boutons qui permettent de sélectionner en temps réel le comportement dubot.
Les résultats que nous présentons ont été collectés avec un apprentissage d’une durée de l’ordre de
10 à 15 mn. Cela correspond à environ 7000 échantillons servant à paramétrer les lois de succession de
Laplace utilisée pour l’apprentissage.

4.2 tables#%$(

Nous commentons ici les tables1 apprises, par comparaison avec celles écrites au 3.1. On note quebien qu’il soit possible d’apprendre la table concernant
 , cela n’a pas d’intérêt dans la mesure où
cette distribution se trouve simplifiée dans le calcul des questions posées au modèle (voir la formule 2.1).
 |  % - "'" %  ) n’est pas apprise, pour la difficulté que représenterait lePar ailleurs, la table P(
fait de contrôler deux valeurs simultanément, et pour celle d’évaluer en temps réel quels sont les ennemis
que le bot perçoit, compte-tenu de son angle de vision réduit.

4  %,

1Pour une lecture plus aisée, les tables sont données arrondies, avec deux chiffres significatifs. Les probabilités donnéescomme sont donc en réalité comprises entre   et .

23

24

4.2.1

    S

6;:

La table 4.1 est très proche, dans l’esprit que celle correspondante (3.1) écrite à la main (versionodge). La seule différence notable est la valeur d’auto-maintien de l’état  , qui est plus faible ()
ici. Cela s’explique par le fait que le pilotage d’un bot à la main ne conduit pas souvent à fuire ; ainsi,    s’éloigne peu de l’uniforme par manque de données. Pour cette raison, dans la suitede ce commentaire, nous ne tiendrons pas compte du comportement  .

#%$- * S(



appris> 8 II E6
>8 I E 6
>8 I E 6
>8 I E 6
>8 E
 6





S








9 68 666 68 661: 68 66 9 689
9 68 661: 68 66 9 689
68 666
68  68 66 9 689
68 666 68 661: 68  689
68 666 68 661: 68 66 9 68 :
68 666 68 661: 68 66 9 689
#%$  -  (T . 4.1 –

68 66
68 66 
68 66 
68 66 
68 66 
68 



AB

4.2.2



      

La table apprise (4.2) est ici assez différente de celles écrites à la main (3.2). Cela est dû au fait qu’il
est difficile lors du pilotage en temps réel de tenir compte en continu du niveau de vie ; il est souvent
plus naturel d’être opportuniste en ramassant les objets proches, et en attaquant de manière suicidairesinon. Chaque colonne de la table apprise reflète donc grossièrement la probabilité du niveau de vie dubot, indépendamment de l’état.













 


6899 68 6 9  6 8 661: 68 66 9 6 8 68 6
E! " 68  68 6 8  68  68 : 68  $H  6 8 6661: 68 :
6 8 : 68  68 : 6 8 66#%$ -  (T . 4.2 –appris



AB

4.2.3

     

La table 4.2 montre que pour le comportement appris, le bruit est indifférent à la plupart des comportements, sauf àet , qui sont quasi-incompatibles avec le bruit (ces comportements s’interrompent
quand un ennemi attaque, par exemple).

 













68  6 8  6 8 9 68 9 68  6 8
  68   6 8 : 68 6  689 68   6 8#%$  C-  (T . 4.3 –appris

AB



25

4.2.4

      

La table 4.4 est identique à celle spécifiée à la main (version odge) pour les comportements  ,et  . La colonne 
est similaire à  , contrairement à la spécification à la main qui la voyait
uniforme ; cela s’explique par un comportement piloté qui prone l’attaque quand un ennemi est présent.
Enfin, dans la table apprise, l’attaque exclut la présence de deux ennemis ou plus, comme la version
odge.


,

&2."

appris

 "
 











6 8 : 6 8  68   68  68 68 
68  6 89 68 6 9 68 69 68 : 689 
I ( >8 E6 68 6 9 68 661: 68 66 9 68 : 6 8 61::#%$  %   "'" %,  -  (T . 4.4 –


AB

4.2.5



         et        

Les tables 4.5 et 4.6 correspondent grossièrement à celles écrites à la main ; cependant, les proportions sont beaucoup moins marquées. Il faut ici remarquer pour expliquer ce point que le pilotage permet
difficilement d’évaluer en temps réel quels objets sont perçus comme proches par le bot.

 









S







68  68  6 8  68  68  6 8  68 9 68 : 6 899 68 : 68   6 8 #/$  %% -  (T . 4.5 –  appris



AB

 









68  6 8 : 68  68 68  6 8 9  68 61: 6 89 68 9 68 : 68   6 89
#/$
T . 4.6 –   O" -  (apprisAB

4.2.6      

La table 4.7 a peu de rapports avec celle spécifiée à la main. Elle reflète principalement le fait quele bot est la quasi-totalité du temps avec une arme de classe ! "'" . Cela conduit à penser que laclassification des armes devrait être remaniée, ou que le comportement de recherche d’armes n’est pasassez efficace.

4.2.7           

La table 4.8 donne plus d’informations que celle écrite à la *main, (3.8). Elle est caractéristique du fait
que quand aucun adversaire n’est présent, lavariablevaut%& ." . Par conséquent,on voit ici que dans les comportements  , et, la probabilité qu’un ennemi soit présent est
très faible. Par ailleurs on retrouve le fait que la probabilité de l’arme de l’ennemi sachant que le bot%  4

2

26



appris'& ."! "'" 







 
I
98 E6 68 666  68 661: 68 66 9 68 6 8 66
68 9 68 
9 68  68 : 6 8
689  68 6 68 661: 68 6 92: 68 : 6 8 :#%$  %%>- + (T . 4.7 –




AB

est en attaque exclut pratiquement que l’ennemi ait une arme très forte. En somme, la table issue del’apprentissage suggère une autre façon d’exprimer certaines notions que la spécification à la main ; cetteautre façon est adaptée aux spécificités de l’architecture de contrôle.

 appris'& ."E1! #"'" 






S

6 8 : 6 8  68   68  68 6 8 
68  68 6  68 6 9 68 6 68 : 6 8968 66: 68 6 68 661: 68 6 92: 68 : 68 6 #%$  %% +*, - 4 -  (T . 4.8 –
AB





4.3 résultats
1a score
Au combat, le bot issu de l’apprentissage se montre moins efficace que ceux programmés à la main(des confrontations à trois entre les versions apprise, odge et brsk conduisent à des scores 2 moyens del’ordre de 2, 5 et 7 respectivement).
1b « humanité »Il se pose notamment un problème d’opportunisme : la version apprise du bot profite mal de laprésence proche d’armes et de bonus de santé pour les ramasser. Des raisons pour expliquer ce problème,ainsi que celui plus général de l’efficacité seront proposées au 4.3.
2a facilité de développement
L’ajustement d’un comportement par apprentissage représente une méthode idéale de développement. Les résultats sur les tables indiquent que le pilotage par comportement conduit à des résultats
acceptables. Cependant celui-ci empêche le joueur de faire jouer son expertise, qui est associée à l’interface propre du jeu.
2b puissance expressive
La puissance expressive du modèle n’est pas affectée par l’apprentissage, en ce qu’elle dépend principalement de la description utilisée, et en particulier du choix des variables.
2

Le score correspond au nombre de joueurs tués.

27

3a prévisibilité
Dans l’ensemble, nous retrouvons dans les tables apprises les principes comportementaux injectésdans les tables écrites à la main. Il y a cependant un certain nombre de différences notables. Ces différences ne sont pas des problèmes en soi (l’objectif n’étant pas de faire apprendre un comportement
identique à celui spécifié à la main), mais sont seulement caractéristiques de différences entre les comportements appris et spécifiés a priori. Elles deviennent problématiques quand les distributions obtenues
sont indûment3 proches de l’uniforme.
En effet, une distribution proche de l’uniforme contient très peu d’information ; les variables asso   pour le comportement
ciées en partie gauche sont neutralisées (ici, par exemple
appris). Ce phénomène est caractéristique d’une inadéquation entre les variables prises en compte par lepilote humain, et celles contenues dans le modèle (comme les problèmes du bruit et de la proximité desobjets).

#/$ 342-*(

3b ajustabilité
L’apprentissage permet, dans la limite des capacités du modèle, de programmer une variété de comportements. Cependant, on peut arguer que le contrôle sur certains aspects précis est moindre que lors
de l’écriture manuelle de toutes les tables. En effet, si certaines situations importantes ne se reproduisentpas souvent lors de l’apprentissage, les probabilités qui les conditionnent seront mal estimées.
4a séparation développement/conception
L’apprentissage peut être vu comme le niveau ultime de la séparation entre développement et conception de personnages. En effet, la personne ajustant le comportement n’a plus alors besoin d’aucune
connaissance du modèle sous-jacent. Il est possible, par exemple, de profiter de l’expertise d’un joueurne prenant pas part au développement.
4b complexité
Du point de la complexité, notre méthode d’apprentissage requiert de stocker autant de fréquences
qu’il y a de valeurs de probabilité dans les tables, et de mettre à jour une valeur dans chacune des tables
à chaque pas de temps. L’opération est donc légère en temps de calcul, et les besoins en mémoire évoluent quadratiquement en fonction du nombre d’états et linéairement en fonction du nombre de variables
sensorielles :% 4- 0-   - - D $ - D - (La solution aux problèmes de performances liés à cette méthode d’apprentissage consisterait soit à
retravailler et à étoffer le modèle pour l’approcher de celui pris en compte par le joueur humain, soit àfournir à celui-ci une interface qui limite sa perception à celle que connait le bot. Cependant, d’un côténous n’avons pas accès au modèle du joueur (à supposer même qu’il puisse être exprimé dans le cadre dela programmation bayésienne) ; de l’autre, réduire l’interface de pilotage au maximum rendrait celui-ci
impraticable, puisqu’elle retirerait au pilote son expertise, qui est justement associée à l’environnement« naturel » du jeu. Nous proposerons cependant des pistes pour tenter de rapprocher l’homme et le bot
au 5.3.
3

C’est-à-dire alors qu’elles devraient clairement être marquées pour que le comportement soit efficace.

Chapitre 5

discussion
5.1 intérêts et inconvénients de la méthode
Nous reprenons ici les critères d’évaluation tels que nous les avons énoncés au 1.4, de façon à mettreen avant les avantages et les failles de la méthode de programmation bayésienne appliquée aux personnages de jeux vidéos.
1a score
Il est important de remarquer que comme celle de tout modèle de haut niveau, l’efficacité pratiquede notre modèle dépend de architecture de contrôle sur laquelle il est basé, et d’une plateforme fournissant les variables nécessaires. C’est la raison pour laquelle il est difficile de comparer nos bots à ceux
existants pour Unreal Tournament, dans la mesure où ceux-ci ont un accès plus direct à leur monde,
alors que les notres en ont une vision « humanisée », qui limite leur perception et leurs déplacements.
Si elle est faite, cette comparaison est cruelle, tant l’avantage de dextérité perceptive (par exemple dansl’identification des dangers) des bots natifs d’Unreal Tournament est grand. Par ailleurs, confrontés à desbots programmés sur la même plateforme (Gamebots), nos bots se montrent à la hauteur.
Nous ne pouvons donc conclure sur ce point particulier, puisqu’il mesure beaucoup plus que l’efficacité de notre modèle bayésien. C’est l’efficacité de toute notre plateforme (Unreal Tournament, Gamebots, système de contrôle, modèle bayésien) qui influe ce résultat. Nous pensons cependant qu’il est
possible, en couplant notre modèle à une plateforme performante d’obtenir un ensemble compétitif, grâce
aux avantages sur les autres critères, dont la description suit.
1b « humanité »Notre modèle porte spécifiquement sur la programmation d’un comportement stratégique. Nousavons montré que cette démarche était couronnée de succès : les décisions prises transcrivent bien la
stratégie telle qu’elle a été conçue. Notre modèle conduit à une évaluation des situations et à des prisesde décisions conformes aux attentes.
Pour ce qui est de l’imprévisibilite, il semble clair que l’utilisation d’un schéma de décision nondéterministe comme le nôtre est un avantage. Alors que les décisions sont conformes aux attentes, elles
ne sont pas prévisibles individuellement avec précision.
Nous avons montré que notre méthode permettait, au sein d’une description fixée, de donner une

28

29

personnalité propre à un bot en ajustant de manière sélective certaines de ses caractéristiques comportementales.
Enfin,nous avons d’emblée écarté les aspects délibératifs de notre étude, mais il semble indispensablede les prendre en compte tôt ou tard. En particulier, les travaux de David Raulo ([RAC00]) se dirigent
sur la voie de l’intégration des problèmes de navigation et de localisation au modèle bayésien.
2a facilité de développement
Le formalisme de la programmation bayésienne des robots est clairement défini et fournit une manière simple et concise de décrire un programme. Il est bien adapté au développement incrémental. D’unepart, il est simple d’ajouter une variable sensorielle à la description : cela revient à spécifier une ligne
et une colonne de plus dans la matrice de transition   , ainsi que de spécifier la forme para  . D’autre part, les schèmas de programmation
métriquecomprenant une description et unequestion sont réutilisables comme formes élémentaires au sein d’une description de plus haut niveau.
Cependant, dans l’état de la technique, l’interfaçage du système de programmation bayésienne avec
les systèmes perceptifs classiques dans les jeux vidéos reste plus problématique que celui réalisable avec
un système de script. Le problème est au niveau du traitement de variables à valeurs discrètes (arme) ou
composées (tir ou bruit : un booléen et une direction) : cela complique l’utilisation de fonctionnelles enlieu de formes paramétriques, et pousse à celle de tables dont tous les éléments doivent être écrites à lamain.

#%$ 0-

(

 #%$

- (

2b puissance expressive
La programmation avec notre méthode est du même niveau que les variables choisies dans la description. On a donc un bon contrôle sur la puissance expressive. Elle peut même s’étaler à plusieurs niveaux.
Ainsi, sur notre exemple, nous pourrions envisager d’écrire un schéma pour le comportement d’attaque,ainsi (au niveau inférieur) que pour le comportement de déplacement élémentaire.
3a prévisibilité
Il est important pour le programmeur de savoir quels seront les répercussions sur le comportement deses choix, tant dans le choix des variables et de la distribution conjointe qu’au niveau de l’identification
des formes paramétriques. Nous pensons avoir montré avec les comportements odge et brsk que lesattentes exprimés lors de l’écriture du modèle sont satisfaites dans sa réalisation.
3b ajustabilité
Les comportements construits a partir de la programmation bayésienne sont spécifiés par atomes
contrôlables et ajustables séparément (les formes paramétriques). L’influence de chaque variable sensorielle sur l’état du bot y est spécifiée. Ainsi, dans notre démarche, nous avons pu contrôler separementl’influence du bruit sur l’etat du bot (voir table 3.3). L’influence de la variation des formes paramétriques
est observable et compréhensible, comme nous l’avons montré avec les comportements odge et brsk. Enfin, les formes paramétriques sont facilement apprenables, qu’elles soient des tables comme dans cetteétude ou des fonctionnelles (comme dans [Leb99]).
L’apprentissage s’intègre naturellement à notre modèle, et offre une façon très puissante de spécifier
un comportement de manière intuitive et accessible

30

Quant à l’apprentissage, s’il s’intègre naturellement à notre modélisation bayésienne, sa forme actuelle de pilotage par comportement semble insuffisante. En effet, elle n’est pas naturelle pour le pilote.
4a séparation développement/conception
Pour de mêmes connaissances préalables, différents comportements sont décrits par des données(les formes paramétriques), et non du code. Cela implique une flexibilité dans le developpement decomportements multiples, et dans leur utilisation (sauvegarde et chargement au vol, par exemple).
Par ailleurs, une fois le modèle écrit, il peut etre ajusté séparément, à la main ou par apprentissage.
Celui-ci offre une façon très puissante de spécifier un comportement sans avoir de connaissance approfondie du modèle utilisé.
4b complexité
Du point de vue de la complexité, notre méthode se montre extrêmement économe. Si nous notons-   - le nombre de valeurs possibles pour #%$ et Q le nombre
 de variables sensorielles, la formule 2.1
montre que l’établissement de la probabilité  - )  %%185858 ( met en jeu :$4Q  9C( lectures dans des tables, – -  - Q
– -  - multiplications,– -  -  9 additions, et– -  - divisions.


La complexité du calcul est donc linéaire dans le nombre de variables sensorielles. En revanche,elle ne dépend pas du nombre de cas de ces variables, mais seulement linéairement du nombre d’états
possibles. A titre de comparaison, dans un automate déterministe à états finis, le passage d’un état à unautre nécessite au plus  comparaisons permettant d’identifier la situation sensorielle à
une transition. Il est donc clair que notre méthode est très performante en termes de temps de calcul, et lereste quand le nombre de variables sensorielles et la granularité de celles-ci augmentent au-delà de notre
exemple-jouet.

--  $4Q 9C(

5.2 comparaison avec un automate équivalent
Au tirage sur les distributions près 1 , notre modèle en action se comporte comme un automate dontles états sont les valeurs de la variable  et dont les transitions portent des conditions logiques surl’ensemble des variables perceptives ; cet automate a un nombre d’état réduit mais des transitions trèscomplexes.
Il est possible de dresser une table de transitions donnant l’état le plus probable à partir d’un état etd’une configuration de variables sensorielles donnés.
A partir d’un état donné, les transitions partitionnent l’espace sensoriel de cardinal- >-  -  %%>-  -  %%  *, 4 -  -  2-5-  %%  "'" #%, -  -    %% -  -   O" -*  
en -  -*  ensembles.
Ces transitions
des formules logiques du type+*: ,$  *  ,*sont  donc
$ $   *  



%
%
*
'&
2
("
%
%
-


4

*
'&
."



 %% - "" %,  *  '& ." ( $  *   $ $  %% - "" %, ,* "    %%,*   ( %% - "" %, M* ,    (R( ( ( (  85858    * 
1

Si nous remplaçons notre tirage par le choix de la valeur de plus grande probabilité, cette réserve est levée.

31

Il est clair que l’écriture à la main de toutes ces formules est pratiquement infaisable. Elles doivent
prendre en compte toute la logique des transitions entre états, sont longues et difficiles à lire et à modifier.
Pour que cette méthode reste utilisable, il est nécessaire de limiter le nombre de variables sensorielles
ainsi que le nombre de cas de ces variables, dans la mesure où le nombre de cas à prendre en compte
correspond à la taille de l’espace sensoriel. Par ailleurs, ces règles sont difficilement apprenables dans lecadre du formalisme logique classique.
Par comparaison, notre méthode autorise la définition de l’automate et de toutes ses transitions demanière légère, contrôlable et maintenable, à partir de briques élémentaires (les formes paramétriques,
ici sous forme de tables).

5.3 perspectives
Pour dépasser les limites de la méthode de programmation bayésienne pour les jeux vidéos telle quenous l’avons présentée ici, plusieurs pistes sont ouvertes. La première est de descendre plus bas dans lahiérarchie des comportements implémentés, pour permettre par exemple la programmation bayésienne
et l’apprentissage des comportements de base (attaque, fuite, . . .). Cela étendrait les avantages de laprogrammation bayésienne à une part plus importante de la programmation du bot, qui repose encore surune méthode de programmation classique, et autoriserait l’amélioration des performances de dextérité
perceptive.
Une seconde piste est l’utilisation de formes paramétriques fonctionnelles, qui pourraient permettredes spécifications plus aisées, et encore plus concises que celles sous forme de tables. Cela permettrait
de prende une compte une meilleure granularité des variables perceptives.
Un seconde piste est l’exploration de nouvelles formes d’apprentissage auxquelles le schéma bayésien semble approprié. Il serait souhaitable de pouvoir piloter le bot directement à travers l’interface
native du jeu ; cela permettrait un véritable « transsfert de compétences » du joueur au bot, sous réserveque le modèle de départ soit approprié. Cependant, il faut noter que ce type d’aprentissage soulève leproblème de la reconnaissance en temps réel du comportement suivi. Par ailleurs, un apprentissage nonsupervisé par renforcement est envisageable.
Enfin, il serait intéressant de se pencher sur d’autres types de jeux que ceux de combat à la première
personne. Ceux-ci ont une forte composante de dextérité, qui restreint l’avantage qu’une méthode donnée
peut proposer au niveau stratégique. Certain jeux de rôle feraient sans doute une plateforme mieux adaptée à la mise en évidence d’avantages en termes d’efficacité d’une méthodologie de haut niveau commela nôtre.

conclusion
En guise de conclusion, nous voulons soulever la question de l’incertitude. En effet, la programmation bayésienne des robots que nous mettons en application ici prétend « traiter formellement desproblèmes d’incertitude et d’incomplétude inhérents au domaine considéré » ([Leb99]). Or il peut sembler que notre domaine d’étude, les mondes virtuels, ne présente pas la même incertitude motrice etperceptive propre aux robots réels : les informations de position ou de vitesse sont connues précisément,
et les déplacements et les actions sur le monde ont des résultats prévisibles.
Mais la place de l’incertain est double dans les mondes virtuels. Premièrement, la complexité desmondes virtuels est aujourd’hui suffisante pour que les personnages y évoluant, humains ou virtuels,
ne puissent en avoir qu’une vision incomplète. Deuxièmement, l’incertitude est d’abord dans la tête duprogrammeur. Nous ne savons formaliser nos raisonnements sur le monde ordinaire (c’est-à-dire hors
des mathématiques) qu’avec difficulté. Nous avons vu au 5.2 combien il peut être difficile d’exprimer
en termes logiques la totalité des cas qui peuvent faire passer de l’attaque à la fuite un personnage dontl’état est caractérisé par seulement 6 variables à 2 ou 3 états chacune. En dehors du fait que le formalisme
que nous exposons réduise grandement la quantité d’informations à fournir par le programmeur pour
synthétiser son raisonnement, il lui permet d’exprimer celui-ci sous une forme intuitive.
Nous pensons avoir montré que la programmation bayésienne est bien adaptée au champ des mondes
virtuels. Elle possède des avantages sur les méthodes classiques, même si certains de ces avantages(comme l’apprentissage) restent à concrétiser sous une forme satisfaisante.

32Annexe A

cadre technique de l’etude
A.1

plateforme

A.1.1 Unreal Tournament et Gamebots
Notre plateforme déxpérimentation est constitué d’un jeu de combat à la première personne, Unreal
Tournament ([unr]), augmenté d’une modification intitulée Gamebots ([AMS 01], [KVS 02]). Cette
modification permet le contrôle de bots à distance par le réseau. Elle fournit un protocole de communication qui permet à un client contrôlant un joueur virtuel de recevoir des informations perceptives locales
au joueur, et d’envoyer des ordres moteurs. Par ailleurs, il offre un service de recherche de chemin
entre deux points. Un des intérêts de cette plateforme est de fournir une interface de contrôle « humanisée » : les bots contrôlés par Gamebots ne sont pas omniscients et disposent d’informations perceptives
et d’ordres moteurs limités. L’inconvénient inhérent à cette approche est qu’elle introduit d’entrée unsévère handicap des bots contrôlés via Gamebots par rapports aux bots natifs d’Unreal Tournament.

A.1.2 API de contrôle des bots
Nous donnons ici une liste simplifiée des informations perceptives et des ordres moteurs offerts par
Gamebots. Les détails de cette API peuvent être trouvés en ligne sur [gam].
informations perceptives
personnage– id, nom, équipe– position (rotation, lieu), vitesse– santé, armure, niveau de vie– arme, munitions– ramassé objet– pieds, tête ou corps changent de zone (eau, lave...)– changement d’arme (automatique ou provoqué)– collision avec un mur, un objet ou un joueur– chute– mort, blessure

33

34

autres personnages visibles– id, nom, équipe– position (rotation, lieu), vitesse, accessibilité– arme, fait feu– mort, blessure infligée par soi
environnement dans le champ de vision– nœuds de navigation : id, lieu, accessibilité– portes, ascenseurs : id, lieu, accessibilité, type– objets : id, lieu, accessibilité, type– bruit (pas, ascenseur, tirs, objet ramassé)– projectile se dirigeant vers soi– réponse à une requête de chemin ou d’accessibilité
jeu– scores, capture de drapeau– message d’un autre joueur (texte ou typé)ordres moteurs et requêtes
déplacement– marcher, courir vers un point, un joueur, un objet, un nœud de navigation...
– courir vers un point en faisant face à un point/objet (strafe)– se tourner vers un point/objet ou d’un angle– s’arrêter
– sauterarmes– armes– commencer de tirer– arrêter de tirer– changer d’armerequêtes– chemin vers un point/objet– accessibilité d’un point/objet– message aux autres joueurs

A.2

architecture de contrôle

Notre architecture de contrôle est présentée sur la figure A.1. Elle est composée de trois processus légers (threads) (mise à jour, décision, interface) agissant sur les données internes du bot, et communiquantavec la surcouche Gamebots d’Unreal Tournament via une socket. Le threadde mise à jour analyse lesmessages envoyés par Gamebots, et met à jour en conséquence les données internes du bot (les flèches
indiquent le sens de circulation des données). Il déclenche aussi des évènements qui sont passés au

35

threadde décision par un tunnel de communication. Le threadde décision agit en envoyant des ordresà Gamebots à partir de la consultation des données internes. Enfin, une interface graphique affiche unepartie des données internes à fins de pilotage et de contrôle de l’état du bot.

mise a jourdonnees internes

consultationinterfacemise a jourevenements

decisionmessages
socketordresGamebots

Unreal Tournament

F IG . A.1 – architecture de contrôle
Nous illustrons la gestion du flux de contrôle par la figure A.2. Cette figure représente un gros plan
sur le threadde décision. Au plus haut niveau, une décision est prise, et le comportement correspondant
est lancé (exploration). Celui-ci appelle un comportement élémentaire (aller_a). Ce comportement de base cherche à se synchroniser sur l’arrivée d’un évènement depuis le threadde mise à jour(attendre NOEUD_ATTEINT). Si cet évènement est reçu (flèches vertes), aller_a continue à agir,
jusqu’ à retourner le contrôle à explore_local, qui le retourne enfin à la boucle de décision. Mais lethreadde décision peut envoyer un évènement signalant le changement d’une des variables sensorielles
à partir desquelles se fait la décision. Dans ce cas, à la réception du message dans aller_a, une exception est lancée et propagée (en rouge) jusqu’a la boucle de décision. Dans les deux cas, une nouvelle
décision est prise, et le cycle recommence.
La figure A.3 montre la hiérarchie d’héritage des comportements élémentaires (pointillés). Les com-36

boucle :choisir etat
lancer action
explore_local :choisir noeud
aller_a noeud

exception Bot_bloquealler_a n :demander chemin(n)pour chaque noeud (chemin)envoyer ALLER_A(noeud)
attendre NOEUD_ATTEINTBOT_BLOQUE ...
[changement variables internes]

NOEUD_ATTEINT

mise a jour

F IG . A.2 – flux de contrôledecision

37

portements séquencés par la boucle de décision bayésienne (RechercheSante, RechercheArme,
Fuite, Exploration, DetectionDanger, Attaque) sont les feuilles de l’arbre. Tous les comportements implémentent un comportement abstrait spécifiant leur interface. Celle-ci consiste en une méthode permettant de reprendre un comportement à zéro, et une autre permettant de le continuer là où il a
été arrêté. Les lignes pleines reliant AllerA à RechercheObjet, Attaque et DetectionDanger
matérialisent le fait que ces trois comportements contiennent un comportement AllerA, qui gère au plus
bas niveau le déplacement d’un point à un autre de la carte.

Comportement+continuer()+recommencer()

Attaque
RechercheObjet

AllerA

DetectionDanger

DeplacementSansCible
RechercheSante
RechercheArme
Fuite

Exploration

F IG . A.3 – comportements

Bibliographie[AMS 01] R. Adobbati, A. N. Marshall, A. Scholer, S. Tejada, G. A. Kaminka, S. Schaffer, and C. Sollitto. Gamebots : A 3d virtual world test-bed for multi-agent research. In Second International Workshop on Infrastructure for Agents, MAS, and Scalable MAS, 2001.
[bal]

Baldur’s gate scripting. Site web. http ://www25.brinkster.com/iesdp/.

[BDL 98a] P. Bessière, E. Dedieu, O. Lebeltel, E. Mazer, and K. Mekhnacha. Interprétation vs. description i : Proposition pour une théorie probabiliste des systèmes cognitifs sensori-moteurs.
Intellectica, pages 257–311, 1998.
[BDL 98b] P. Bessière, E. Dedieu, O. Lebeltel, E. Mazer, and K. Mekhnacha. Interprétation vs. description ii : Fondements mathématiques. Intellectica, pages 313–336, 1998.
[Car01]

S. Carter. Micro-threads for game object ai. In M. Deloura, editor, Game ProgrammingGems 2, pages 265–272. Charles River Media, 2001.

[civ]

Slic : Civilization ii scripting.
ton.net/ctp2/modification/activision/slic.shtml.

[Dys00]E. Dysband. A finite-state machine class. In M. Deloura, editor, Game Programming Gems,
pages 237–248. Charles River Media, 2000.

[Dys01]

E. Dysband. A generic fuzzy state machine in c++. In M. Deloura, editor, Game Programming Gems 2, pages 337–341. Charles River Media, 2001.

[FTT99]J. Funge, X. Tu, and D. Terzopoulos. Cognitive modeling : Knowledge, reasoning andplanning for intelligent characters. In SIGGRAPH, August 1999.

[gam]

Gamebots api. Site web. www.planetunreal.com/gamebots.

[Jay]

E.T. Jaynes. Probability theory - The logic of science. à paraître. Version provisoire disponible à http ://bayes.wustl.edu.

[KVS 02]

G. A. Kaminka, M. Veloso, S. Schaffer, C. Sollitto, Andrew N. Adobbati, R.and Marshal,
S. Scholer, Andrew, and S. Tejada. Gamebots : the ever-challenging multi-agent research
test-bed. Communications of the ACM, January 2002.

[Lai00a]J. Laird. Design goals for autonomous synthetic characters. Draft., 2000.

[Lai00b]

J. E. Laird. It knows what you’re going to do : Adding anticipation to a quakebot. In AAAI
Spring Symposium Technical Report, March 2000.

[LD00]

J. E. Laird and J. C. Duchi. Creating human-like synthetic characters with multiple skilllevels : A case study using the soar quakebot. In AAAI Fall Symposium Technical Report,
August 2000.

[Leb99]

O. Lebeltel. Programmation Bayésienne des Robots. PhD thesis, Institut National Polytechnique de Grenoble, FRANCE, 1999.
i

Site

web.

http

://apoly-

ii[LVL00]J. E. Laird and M. Van Lent. Human-level ai’s killer application : Interactive computer
games. In AAAI Fall Symposium Technical Report, August 2000.

[RAC00]

D. Raulo, J.-M. Ahuactzin, and Laugier C. Controlling virtual autonomous entities in dynamic environments using an appropriate sense-plan-control paradigm. In Proc. of theIEEE-RSJ Int. Conf. on Intelligent Robots and Systems, Takamatsu (JP), November 2000.

[Tur50]A. M. Turing. Computing machinery and intelligence. Mind, 59(236) :433–460, 1950.

[unr]

Unreal tournament. Site web. http ://www.unrealtournament.com.

[Woo01a]S. Woodcock. Flocking with teeth : Predators and prey. In M. Deloura, editor, Game
Programming Gems 2, pages 330–336. Charles River Media, 2001.

[Woo01b]

S. Woodcock. Game ai : The state of the industry 2000-2001. Game Developer, August
2001.

[Zar01]

M. Zarozinski. Imploding combinatorial explosion in a fuzzy system. In M. Deloura, editor,
Game Programming Gems 2, pages 342–350. Charles River Media, 2001.

Sommaire1

problematique de l’IA dans les jeux vidéos
1.1 problématique industrielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1 impératifs industriels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.2 techniques classiques employees . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 problématique de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 cadre pratique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 méthodologie d’évaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6
6
6
7
8
9
9

2

modèle de programmation bayésienne de personnages
2.1 programmation bayésienne des robots . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 organisation générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2 exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 variables pertinentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2 décomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.3 formes paramétriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.4 identification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 question . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11
11
11
11
13
13
14
14
14
16

3

programmation d’un comportement
3.1 tables de comportement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 format des tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.2
   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.3

3.1.4
  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.5
%   "'" %    . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.6

%
  et   "   . . . . . . . . . . . . . . . . . . .
3.1.7
 %  * ,  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.8
 %  % - "'" %   .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
3.1.9
3.2 résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17
17
17
17
17
17
19
19
19
20
20
21

apprentissage d’un comportement
4.1 pilotage par comportement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1
  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23
23
23
24

#%$ - (#%$ - (#%$ C- (#%$  #%$  % - , ( - #%$ (  O O #%$ - (#%$#%$  -  %  - , ?( (

4

#%$

 -

(

iii

(

iv

#%$ - (#%$ C- (#%$  #%$  % - , ( - #%$ (  O O #%$ - (#%$
  - (4.2.2
  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
 ...................................
4.2.3

4.2.4
%   "'" %    . . . . . . . . . . . . . . . . . . . . . . . . . . . .
%  et   "   . . . . . . . . . . . . . . . . . . .
4.2.5
4.2.6
%


 *,  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
  . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.7
%

résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24
24
25
25
25
25
26

discussion
5.1 intérêts et inconvénients de la méthode . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 comparaison avec un automate équivalent . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28
28
30
31

A cadre technique de l’etude
A.1 plateforme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.1.1 Unreal Tournament et Gamebots . . . . . . . . . . . . . . . . . . . . . . . . . .
A.1.2 API de contrôle des bots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.2 architecture de contrôle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33
33
33
33
34

Annexes
Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Sommaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

i
iii

4.3
5

(

Programmation Bayésienne de
Personnages de Jeux Vidéos

Ronan Le Hy(encadré par Pierre Bessière et Olivier Lebeltel)

Résumé
Nous présentons une méthode de spécification de comportement pour personnages de jeux vidéos.

Institut National Polytechnique de Grenoble
46, avenue Félix-Viallet
38031 Grenoble cedex 1