# ROG-O-MATIC: A BELLIGERENT EXPERT SYSTEMMichael Mauldin, Guy Jacobson, Andrew Appel, Leonard Hamey

## 1. Introduction

### Rog-O-Matic plays the computer game Rogue, wherein the object is to explore and survive a complex and hostile environment. Rogue is an example of an exploration task.(Given an undirected planar graph, a starting node, and a visibility function which maps each node into a subset of nodes, exploration entails traversing edges so as to see all of the nodes. Minimizing the number of nodes visited is a subgoal.) Studying exploration requires two things: terrain to be explored, and an explorer to search it. There are four major advantages for choosing Rogue as a terrain generator:

• Success in Rogue depends heavily on successful exploration.
• It is a standard game, designed for human play.
• It has an objective, scalar measure of performance (i.e. the score).
• There is an abundance of human volunteers to calibrate the performance measure.

### The Rogue exploration task is complicated by adversaries whose goal is to prevent the explorer from reaching the lower levels. Carbonell has studied the problem of planning in an adversary relationship [2], but planning in Rogue is hampered by the randomness of the adversary. Where the probabilities are known, search trees can be built with each possible next state labelled with its transition probability. The action with the highest expected value can then be selected [1]. In Rogue, however, these probabilities are unknown to the player, and can change from game to game. Scenarios have also been used to analyze combat situations [8], but when unseen opponents can appear at any time, and when many of the combat parameters are unknown, choosing the right scenarios can be very difficult. Rog-O-Matic is designed as an knowledge based or "expert" system because a search based system was completely infeasible. There are as many as 500 possible actions at any one time; for each action there are several thousand possible next states. Rog-O-Matic differs from other expert systems in the following respects:

• It solves a dynamic problem rather than a static one.
• It plays a game in which some events are determined randomly.
• It plays despite limited information.

## 3.1. Knowledge Sources

### The world model is operated on by a variety of knowledge sources, which take low level data from the world model and process it into higher level information. Eventually, the information is encoded at a sufficiently high level for the rules to operate directly on it. The action primitives also change the world model. This feedback permits the production rules to encode inference mechanisms and short term memory. A partial list of knowledge sources is given here:

• Sensory system (sense) Builds low level data structures from Rogue output.
• Object map (objmap) A data structure which tracks the location and history of objects in the environment (such as weapons or monsters).
• Inventory handler (invent) A database of items in Rog-O-Matic's pack.
• Terrain map (termap) A data structure recording the terrain features of the current level.
• Connectivity analyzer (connect) Finds cycles of rooms (loops).
• Path calculation (pathc) Performs weighted shortest path calculations.
• Internal state recognizer (intern) Tracks the health and combat status of Rog-O-Matic.

## 3.2. Production Rules

### The rules are grouped hierarchically into experts; each expert performs a related set of tasks. These experts are prioritized in order of estimated contribution to survivability. For example, if the melee expert decides that a monster must be dispatched, that decision overrides the advice of the object acquisition expert calling for an object to be picked up. If the melee expert suggests no action, then the object acquisition expert's directive is acted upon. The basic structure resembles a directed acyclic graph (DAG) of IF-THEN-ELSE rules. Figure shows the information flow between these experts. Here is a list of the most important experts:

• Weapon handler (weapon) Chooses weapon to wield.
• Melee expert (melee) Controls fighting during combat.
• Target acquisition expert (target) Controls pursuit of targets.
• Missile fire expert (missile) Fires missiles (arrows, spears, rocks, etc.) at distant targets.
• Battlestations expert (battle) Performs special attacks, initiates retreat.
• Retreat expert (retreat) Uses the termap and connect to choose a path for retreat.
• Object acquisition expert (object) Picks up objects.
• Armor handler (armor) Chooses armor to wear.
• Magic item handlers (magic) Manipulates magic items.
• Health maintenance (health) Decides to eat when hungry and to heal damage by resting.
• Exploration expert (explore) Chooses next place to explore, and controls movement.

## 8. Acknowledgments

### We would like to thank the Rog-O-Matic user communities at both CMU and across the ARPANet for their thousands of hours of testing, and also the many adventuresome Rogue players who provided many, many data points on human Rogue performance. Kudos to Damon Permezel, of the University of Waterloo, for running the first Rog-O-Matic to be a total winner against Rogue 5.2. And of course, special thanks go to Ken Arnold and Michael Toy for creating a very interesting (and very, very hostile) environment. References

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.