Apparue à la cinquième Conférence biennale de la société canadienne pour les études informatiques d’Intelligence, London (Ontario), 16 mai 1984.

Original: http://www.cs.princeton.edu/~appel/papers/rogomatic.html


ROG-O-MATIC : Un système Expert belliqueux
MICHAEL L. MAULDIN, GUY JACOBSON, ANDREW APPEL et LEONARD hanane
DÉPARTEMENT D’INFORMATIQUE
CARNEGIE MELLON UNIVERSITY
5000 FORBES AVENUE
PITTSBURGH, PA 15213
16 mai 1984

RÉSUMÉ

Rog-O-Matic est une nouvelle combinaison d’algorithmique et programmation de systèmes de production techniques qui coopèrent à la découverte d’un environnement hostile. Cet environnement est le jeu Rogue, qui offre plusieurs avantages pour l’étude des tâches d’exploration. Cet article présente les principales caractéristiques du système Rog-O-Matic, les types de sources de connaissances et de règles utilisées pour contrôler l’exploration et compare les performances du système avec des joueurs humains de Rogue.
1. Introduction
Rog-O-Matic joue le jeu Rogue, dans lequel l’objet est d’explorer et de survivre à un environnement complex et hostile. Rogue est un exemple d’une tâche d’exploration.(Étant donné un graphe planaire, un nœud de démarrage et une fonction de visibilité qui mappe chaque nœud dans un sous-ensemble de nœuds, exploration implique traversant les bords afin de voir tous les nœuds. Réduire le nombre de nœuds visités est un sous-objectif.) Étudier l’exploration nécessite deux choses : terrain à explorer et un Explorateur de le fouiller. Il y a quatre avantages majeurs d’avoir choisi Rogue comme un générateur de terrain :
  • Succès à Rogue dépend fortement des succès de l’exploration.
  • C’est un jeu standard, conçu pour le jeu humain.
  • Il a un objectif, la mesure scalaire de la performance (c’est-à-dire le score).
  • Il y a une abondance de volontaires humains pour calibrer la mesure de la performance.
La tâche d’exploration Rogue est compliquée par les adversaires dont le but est d’empêcher l’Explorateur d’atteindre les niveaux inférieurs. Carbonell a étudié le problème de la planification dans un rapport contradictoire [2], mais la planification à Rogue est entravée par le caractère aléatoire de l’adversaire. Lorsque les probabilités sont connues, les arbres de recherche peuvent être construits avec chaque État prochaine possible avec sa probabilité de transition. L’action avec la plus haute valeur peut ensuite être sélectionnée [1]. À Rogue, cependant, ces probabilités sont inconnues au joueur et peuvent changer de jeu en jeu. Des scénarios ont également été utilisés pour analyser les situations de combat [8], mais lorsque les adversaires invisibles peuvent apparaître à tout moment, et lorsque plusieurs paramètres combats sont inconnus, choisir les bons scénarios peut être très difficile.
Rog-O-Matic est conçu comme une connaissance de base ou système « expert » parce qu’une recherche basé système était totalement infaisable. Il y a 500 actions possibles à tout moment ; pour chaque action, il y a plusieurs milliers États suivants possibles.
Rog-O-Matic se distingue des autres systèmes experts dans les domaines suivants :
  • Il résout un problème dynamique et non statique.
  • Il projette contre des adversaires.
  • Il joue un jeu dans lequel certains évènements sont déterminés au hasard.
  • Il joue malgré le peu de renseignements.
Dans cet article, nous introduisons l’environnement Rogue et discuter de l’architecture, des sources de connaissances et des règles de production utilisés par Rog-O-Matic pour explorer cet environnement. Aussi, nous discutons l’implémentation du système et comparer ses performances avec celles d’experts humains de Rogue. Pour une description plus détaillée du programme, voir [6].
2. L‘environnement de Rogue
Le jeu Rogue est décrite plus en détail dans [7] ; un aperçu est donné ici. L’environnement est une grotte composée de niveaux ; chaque niveau contienne entre six et neuf pièces rectangulaires reliées par des tunnels. Le joueur prend le rôle de l’Explorateur de solutions, la recherche d’or et la lutte contre les monstres qui gardent la grotte. Objets magiques comme les potions ou les armes sont également dispersés, et ils peuvent servir d’avantage dans le combat. Pièges sont cachés dans les chambres pour contrecarrer les joueurs négligents. Le but du jeu est d’explorer au niveau 26 et récupérer l’amulette de Yendor. Comme l’Explorateur va plus loin dans la grotte, l’or devient plus abondant et les monstres deviennent plus difficiles à vaincre. L’Explorateur tue les monstres en combat, il devient un meilleur combattant. En moyenne, monstres augmentent plus vite que le joueur augmente son habileté, pour atteindre le niveau 26 est donc presque impossible en férocité. Score du joueur est la quantité d’or qu’il obtient, avec bonus donnés afin de récupérer l’amulette.
3. L‘Architecture de système Expert
Rog-O-Matic est une combinaison de sources de connaissances algorithmiques et de règles de production. Là où l’incertitude est faible, méthodes algorithmiques fournissent un calcul rapide de l’information pertinente. Là où l’incertitude est grande, règles de production heuristique fournissent un comportement raisonnable. Sources de connaissances et de règles de production interagissent via un modèle mondial ou le “tableau noir” [3]. Parce que le système est mis en œuvre dans un langage impératif, les règles de production sont classés en statiquement. Dynamiquement ordonnée règles auraient été beaucoup plus compliqués au code, et très peu de règles bénéficieraient de cette complexité supplémentaire.

Figure 3-1: Architecture de système Rog-O-Matic


Figure 3-1 montre l’architecture de haut niveau système Rog-O-Matic. Rog-O-Matic joue le jeu en interceptant les caractères depuis le flux terminal et en renvoyant des caractères de commande vers le processus de Rogue. L’interface d’entrée doit convertir un flux de caractères conçue pour dessiner une image significative sur un écran CRT dans une représentation de l’état du monde. Cette fonction est assurée par le module sensoriel. La tâche moins difficile de convertir des directives de mouvement et d’action en commandes de voyous se faite par le module de l’effecteur, qui est indiqué principalement pour la symétrie. Langley et coll. ont décrit les avantages des interfaces simples sensorielle/effecteur en étudiant un environnement réactif [5]. Le fichier de mémoire à long terme est une partie du modèle mondial qui est sauvegardé entre les jeux. Tout apprentissage à long terme est obtenu en modifiant ce fichier.

3.1. LA CONNAISSANCE DES SOURCES
Le modèle mondial est exploité sur une variété de sources de connaissances, prendre des données de niveau faibles du modèle du monde et le transformer en informations de niveau supérieures. Finalement, l’information est encodée à un niveau suffisamment élevé pour les règles fonctionner directement sur elle. Les primitives d’action aussi changent le modèle du monde. Cette rétroaction permet d’encoder des mécanismes d’inférence et de la mémoire à court terme, les règles de production. Une liste partielle des sources de connaissances est donnée ici :
  • Système sensoriel (sens) construit des structures de données à faible niveau de sortie de Rogue.
  • Mappage d’objets (objmap) une structure de données qui suit la situation et l’histoire des objets dans l’environnement (tels que des armes ou des monstres).
  • Gestionnaire d’inventaire (inventer) une base de données d’éléments contenus dans le pack de Rog-O-Matic.
  • Carte du terrain (termap) une structure de données enregistrant les caractéristiques du terrain du niveau actuel.
  • L’analyseur de connectivité (connecter) trouve des cycles des chambres (boucles).
  • Calcul de chemin (pathc) effectue des calculs de chemin d’accès plus court pondérée.
  • Reconnaissance de l’état interne (stagiaire) suit la situation sanitaire et combattre de Rog-O-Matic.

Figure 3-2: Experts (ovales) et Sources de connaissances (boîtes)


3.2. RÈGLES DE PRODUCTION

Les règles sont regroupées hiérarchiquement en experts ; Chaque expert effectue un jeu de tâches associé. Ces experts sont priorisés afin de la contribution estimée de survie. Par exemple, si l’expert mêlée décide qu’un monstre doit être envoyé, cette décision remplace l’avis de l’expert d’acquisition objet appelant pour un objet à être ramassé. Si l’expert mêlée n’indique aucune action, directive de l’expert objet de l’acquisition est donné suite. La structure de base ressemble à un graphe acyclique dirigΘ (DAG) des règles IF-THEN-ELSE. Figure 3-2 illustre le flux d’informations entre ces experts. Voici une liste des plus importants experts :
  • Arme gestionnaire (arme) choisit arme à manier.
  • Expert mêlée (mêlée) contrôles des combats en combat.
  • Target acquisition expertise (cible) contrôle la poursuite de cibles.
  • Expert incendie de missiles (missile) tire des missiles (flèches, lances, roches, etc.) sur des cibles éloignées.
  • Battlestations expert (bataille) effectue des attaques spéciales, retraite initiés.
  • Expert retraite (retraite) utilise le termap et se connecter pour choisir une voie pour la retraite.
  • Expert d’acquisition objet (objet) ramasse des objets.
  • Gestionnaire d’armure (armor) armor choisit de porter.
  • Les gestionnaires d’élément magique (magic) manipule des objets magiques.
  • Maintien de la santé (santé) décide de manger quand on a faim et à guérir les dommages en se reposant.
  • Expert de l’exploration (Explorer) choisit le prochain endroit à explorer et contrôle le mouvement.
3.3. SOURCES DE CONNAISSANCES ALGORITHMIQUE
Les sources de connaissances algorithmiques, la calculatrice de chemin d’accès est le plus intéressant. Il lit la carte du terrain et détermine les chemins les plus courts pondérées de Rog-O-Matic à l’endroit le plus proche, répondant à certains critères (tels que l’objet inconnu le plus proche, ou la voie d’évacuation le plus proche). Les coûts de bord sont petites, délimitée entiers qui codent des dangers connus ou possibles (tels que les pièges ou inexplorés places). Un algorithme de parcours en largeur explore l’extérieur de l’emplacement actuel et n’importe quelle case avec un coût non nul (une valeur d’évitement) a son coût décrémenté et ensuite carré est placé non examinée à la fin de la file d’attente de recherche. Il en résulte un plus court chemin pondéré obtenu en temps linéaire pour le nombre de carrés de terrain. Exploration nécessite le système pour passer la plupart de son temps de déplacement, une calculatrice de chemin d’accès rapide est essentielle.
La plupart des mesures prises par Rog-O-Matic est plus simple que le mouvement, et ces actions sont effectuées directement par les règles de production. Par exemple, lorsque l’expert mêlée a déterminé qu’une bataille est en cours, il met certains paramètres clés de la bataille, comme la force du monstre, le nombre de tours que le monstre aura besoin pour atteindre le joueur et sa direction, dans le tableau noir et appelle l’expert battlestations. Battlestations décide s’il faut attaquer avec l’arme en main, attaque avec une magie spéciale point, ou à la retraite. Figure 3-3 indique certaines règles d’échantillon extraits de battlestations.


 /*
    * If we can die in 1 turn and we are not at peak strength, we might want
    * to retreat.  Don't try to run if we are confused or being held by
    * something.  If we are on a door, wait until the monster is next to us
    * (that way we can shoot arrows at him, while he catches up). Don't run
    * away from Dragons!!!  They'll just flame you from behind.
    */
if ((die_ in (1) && Hp+Explev < Hpmax) &&
       !confused && !beingheld && (!on(DOOR) || turns < 1) &&
       !streq(monster, "dragon") &&
       runaway ())
   { display ("Run away! Run away!"); return(1); } 

/*
    * We can't run and there is a monster next to us who could kill
    * us in 1 turn.  If we have a scroll of teleportation, read it.
    */ 

   if (die_ in (1) && turns == 0 &&
       (obj = havenamed (scroll, "teleportation")) >= 0 && reads (obj))
   { return (1); } 

Figure 3-3: règles d’échantillon de l’Expert Battlestations

3.4. APPRENTISSAGE

Il existe deux types d’apprentissage en Rog-O-Matic: à court terme, pour la reconnaissance de l’objet et à long terme pour les caractéristiques de monster. Apprentissage à court terme est utilisé pour collecter des informations sur les armements offensifs et défensifs disponible au joueur. Utilisation correcte de cet armement est cruciale au succès à Rogue. Au début, le joueur ne connaît pas les caractéristiques de la plupart des objets dans le jeu. Connaître les éléments peut être obtenue par expérimentation, soit en utilisant les parchemins d’identifier différentes dans le jeu. Ce type d’apprentissage est fermé, car il y a moins de 50 différentes choses que n’importe quel objet peut être. Une base de données codées manuellement est utilisé pour faire correspondre les résultats de l’expérimentation (c’est à dire en essayant un élément pour voir ce qu’il fait) avec la nature et l’utilisation de cet élément.
Un problème plus intéressant est d’apprendre sur les caractéristiques du monstre. Lorsque vous décidez que ce soit pour l’attaque ou de retraite, une estimation précise des forces et des faiblesses de l’adversaire est nécessaire. Un tableau câblé de ces estimations a été utilisé dans les premières versions de Rog-O-Matic, mais les monstres ont été changés dans la dernière version de Rogue (version 5.3). Plutôt que de construire une autre table à la main, nous avons ajouté une trousse d’apprentissage qui assure le suivi de la force offensive et défensive de chaque monstre rencontré. Ces valeurs sont conservés de jeu à jeu et sont stockés dans le fichier de mémoire à long terme. Ce type d’apprentissage n’est pas prévu d’augmenter les performances (car les versions antérieures avaient déjà une information parfaite sur les caractéristiques du monstre), mais pour fournir la flexibilité du programme. Changements dans les adversaires ne nécessitent pas de changements dans le programme.
4. Mise en œuvre
Rog-O-Matic s’exécute sur un Vax 11/780 sous le système d’exploitation Unix de Berkeley. Elle est composée de 12 000 lignes de code C ; C a été choisi pour la commodité et de rapidité. Il offre un accès direct pour les primitives de système d’exploitation requis pour l’interface du jeu Rogue (une nécessité, car nous voulions que notre programme de jouer exactement le même jeu que les joueurs humains). Code C, aussi s’exécute beaucoup plus rapidement que la plupart des langages systèmes de production, et cette vitesse était nécessaire pour Rog-O-Matic à jouer suffisamment de parties pour ses performances à mesurer. Le programme prend environ 30 secondes de CPU (générant environ 400 actions) à la découverte d’un niveau, et Rogue prend un autre 15 secondes de CPU, calculer sa part de la simulation. À la CMU, Rog-O-Matic a joué plus de 7000 jeux dans deux ans. Rog-O-Matic se déroule aussi à plus de 36 installations aux États-Unis, Canada, et l’Angleterre.
5. Performance
Évaluation des systèmes experts peut être un problème difficile [4], mais les deux mesures d’un programme de jeu sont évidentes : sa réputation parmi ses concurrents et ses notes brutes. Rog-O-Matic a acquis une réputation très favorable comme un joueur expert de Rogue, et plusieurs joueurs humains ont parlé d’apprentissage beaucoup Rogue aussi bien le regarder jouer et en lisant le code source.
Nous avons comparé les scores Rog-O-Matic avec 15 des meilleurs joueurs de Rogue à la CMU sur une période de deux mois, et Rog-O-Matic a joué ainsi que les experts humains. Figure 5-1 montre parcelles percentile de ces jeux, classés par score médian. Rog-O-Matic a obtenu le septième meilleur score élevé et le meilleur score médian de n’importe quel joueur. Rog-O-Matic a également été un soi-disant gagnant Total contre les voyous 3.6 et Rogue 5.2.

Figure 5-1: Journal Scores contre joueur, Tri par médiane

Le graphique inclut tous les joueurs avec dix ou plusieurs matchs contre Rogue (version 5.2) sur le GP-Vax à la CMU. Les données ont été recueillies au cours d’une période de deux mois du 1er janvier 1983 au 21 février 1983. Boîtes sont tirés du quartile inférieur au quartile supérieur, avec une ligne à la médiane. Les moustaches sont dessinés sur les marques de 10e et 90e percentiles et jeux extrêmes est restituées sous forme d’astérisques. L’échelle verticale est le score (tiré de façon logarithmique) et l’échelle horizontale est le rang du joueur. L’échelle verticale est logarithmique dessiné parce que les scores de Rogue approximativement une distribution log-normale.

6. Problèmes
Le classement statique utilisé empêche certaines tactiques de Rogue étant proprement représentés. Un exemple est l’utilisation de l’armure. Dans certains cas la meilleure armure doit être portée, et dans d’autres cas, la deuxième meilleure armure devrait être porté. Vous devez désactiver la règle prévoyant la meilleure armure tandis que la deuxième meilleure armure est en place et encore être réactivé au bon moment. Chacune de ces dépendances requiert une nouvelle variable globale en mémoire à court terme. Règle dynamique vous passez votre commande peut être un moyen plus propre à résoudre ce problème.
Un autre problème est la détermination. Par exemple, lors de l’exécution d’un monstre, il est souvent possible de ramasser des objets sur la voie d’une échappatoire. Étant donné que Rog-O-Matic ne considère pas qu’une seule action peut répondre à plusieurs objectifs, que le programme ne parvient pas à tirer profit de telles situations. Dans d’autres cas, la présence d’un facteur secondaire requiert des actions plus créatives que sont actuellement possibles. Ce problème est plus grave lorsque Rog-O-Matic doit combattre des monstres multiples. Son heuristique est de combattre le monstre plus dangereux tout d’abord, mais il existe des situations dans lesquelles cette règle échoue lamentablement. À Rogue, omettant lamentablement habituellement entraîne la mort.
7. Conclusion et travaux futurs
En combinant les sources de connaissance algorithmique efficace avec un mécanisme de contrôle règle fondée, nous avons produit un programme manifestement expert lors du match de voyous. Le résultat est un système capable d’effectuer des tâches d’exploration tout en respectant également l’objectif de l’auto-conservation. Le système peut fonctionner bien face aux dangers incertains, faire bien réfléchie de lutte ou de décisions de vol et battre en retraite avec succès lorsqu’il est confronté à une opposition écrasante. À court terme et à long terme d’apprentissage ont suffisamment de latitude pour gérer un environnement en mutation et réduit le temps de programmation requis pour gérer les versions plus récentes de voyous.
Notre objectif le plus important pour l’avenir est de renforcer la composante de l’apprentissage. Beaucoup plus de fonctionnalités du jeu peuvent être apprises, exigeant moins transfert de connaissances d’un expert externe et accroître la flexibilité du programme. Nous espérons que cette capacité d’apprentissage se traduira également par des résultats beaucoup plus élevés.
8. Remerciements
Nous tenons à remercier les communautés d’utilisateurs Rog-O-Matic à deux CMU et travers ARPANet pour leurs milliers d’heures de tests, et indique également les nombreux acteurs aventureux de Rogue qui ont fourni de nombreuses données sur la performance humaine de Rogue. Bravo à Damon Permezel, de l’Université de Waterloo, pour faire fonctionner la première Rog-O-Matic pour être un gagnant total contre Rogue 5.2. Et bien sûr, nous tenons à Ken Arnold et Michael Toy pour la création d’un environnement très intéressant (et très, très hostile).
Références
  1. H. Berliner. Experiences in Evaluation with BKG–A Program that plays Backgammon. In IJCAIVproc. IJCAI, 1977.
  2. J. Carbonell. Counterplanning: A Strategy-Based Model of Adversary Planning in Real-World Situations. AI 16, 1981.
  3. L. Erman, F. Hayes-Roth, V. Lesser and R. Reddy. The Hearsay-II Speech-Understanding System: Integrating Knowledge to Resolve Uncertainty. Computing Surveys 12(2), June, 1980.
  4. J. Gaschnig, P. Klahr, H. Pople, E. Shortliffe, and A. Terry. Evaluation of Expert Systems: Issues and Case Studies. In F. Hayes-Roth, D. Waterman, and D. Lenat (editor), Building Expert Systems. Addison-Wesley, Reading, Mass., 1983.
  5. P. Langley, D. Nicholas, D. Klahr and G. Hood. A Simulated World for Modelling Learning and Development. In Proceedings of the Third Annual Conference of the Cognitive Science Society. 1981.
  6. M. Mauldin, G. Jacobson, A. Appel and L. Hamey. ROG-O-MATIC: A Belligerent Expert System. Technical Report CMU-CS-83-144, Carnegie-Mellon University, July, 1983.
  7. M. Toy and K. Arnold. A Guide to the Dungeons of Doom. Unix Documentation, Department of Electrical Engineering and Computer Science, University of California.
  8. R. Wall and E. Rissland. Scenarios as an Aid to Planning. In AAAI82. AAAI, 1982.

Mise à jour le 4 mars 94 par fuzzy@cmu.edu

Comments are closed.