Working Group on Rule-based Systems

Working Group on Rule-based Systems

In this report, we introduce the current work carried-out by the Artificial Intelligence Interface Standards Committee (AIISC) working group on Rule-based Systems (RBS).

Due to work-commitment of most of the members including the coordinator, the group has started very slowly. Many points of discussion have been started without having been concluded or reached any agreement. To allow a better progression of the group toward its identified goal, a more clear strategy and distribution of tasks will have to be defined, with each member of the group responsible of a specific task. This scheme will be in place and monitored in the forthcoming weeks.

For now, we present some of the background concepts and issues discussed on the aspects of specification, design and development of a Rule-based System for game AI to implement challenging game agents (i.e. NPC). We are investigating the components and possible architectures of RBS, and the different applications of game AI in general and of RBS in particular, depending on game genres.

This is a preliminary report on the current work of the RBS group.

Goal

Programming game AI is one of the most challenging enhancements that a game developer can implement. The real-time performance requirements of computer game AI and the demand for human-like interactions, appropriate animation sequences, and internal state simulations for populations of scripted agents have impressively demonstrated the potential of academic AI research and game AI technologies.

Many academic AI techniques have been used and are currently used to implement game AI. These include, without being exhaustive: finite state machines (FSM), decision trees (DT), pathfinding, steering, goal-oriented action planning and rule-based systems (RBS).

Regardless of their differences, many concepts from academic AI can be implemented in games.

To be believable, the AI in a game must simulate cognition, sense the environment realistically, and act convincingly within that context. In defining game AI, the programmer will have to code agent activity and behavior so that characters appear intelligent and respond realistically to perceived conditions and situations.

The aims of these pages are to introduce the work carried-out by the Artificial Intelligence Interface Standard Committee (AIISC) working group on Rule-Based Systems (RBS).

Rules Based Systems are comprised of a database of associated rules. Rules are conditional program statements with consequent actions that are performed if the specified conditions are satisfied.

The aims of the group are to discuss and develop a set of standard on RBS applications and architectures suitable to games. This is a preliminary report on the current work of the RBS group, and which will be followed-up by recommendation and a proposal for a game-AI RBS standard in future reports.

Games Genres and AI

Many game genres have been created, and while they might be different in the aims, the gameplay and the setting, they share some commonalities in term of game AI.

Action Games

Action games involve the player in the exploration of fantasy worlds in the form of running, jumping, climbing or leaping with the goal of discovering the doorway or exit into the next stage or level. Generally, these titles feature cute characters battling a cast of "baddies" and often involve a simple plot such as rescuing a princess. Platform games like Donkey Kong as well as maze games such as Pac-Man fall into this category. Another game genre that can be considered as action games are shooters.

In action game genre, it is in creating intelligent opponents that the most obvious possibilities for integration of sophisticated AI arise. NPCs cooperating with the player character (PC), is another area in which there is a real opportunity for further application of sophisticated AI such as RBSs.

Adventure Games

Adventure games take players on a journey in which they visit strange lands, find keys to unlock mysterious doors, and often they must gather inventory such as keys and sometimes weapons to solve puzzles. The combination of certain inventory items and clues received along the journey are the keys to moving on to hidden areas to discover more mysteries. An overall story, sometimes of epic proportion, or comedic intent is the drive of each small task.

Two interesting applications of AI and RBS to the genre are the creation of more realistic and engaging NPCs and maintaining consistency in dynamic storylines.

Role Playing Games

Role-Playing games require players to take on the role of a person or group of people. While role-playing is generally associated with sword and sorcery and fantasy, it can take place in any setting or time. These games typically send players on a journey where they can interact with other characters and attain new skills and abilities, often by fighting battles.

The differences between RPGs and adventure games arise from the scope involved. RPGs take place in far larger worlds and the player has more freedom to explore the environment at their own pace. Also, underlying RPGs is some rule set stemming from the original, and quite complex, Dungeons & Dragons rules.

The RPG format offers the same kind of challenges to the AI developer as the adventure game.

Strategy Games

Strategy games require the player to take on a leadership role (general, king, god-like figure, etc.) and oversee every detail of the provided scenario(s). Generally, strategy games require the user to move and to deploy troops or units, to manage resources and to attain set goals.

Two distinct classes of game have emerged from the strategy genre. Turn based strategy (TBS) games involve each player taking their turn to move units, order production, mount attacks and so on, one after another. The Civilization (www.civ3.com) series is the definitive example of this kind of game. Real time strategy (RTS) games, as the title suggests, take place in real-time with players moving units, ordering production etc. in parallel. The Age of Empires (www.ensemblestudios.com/) and Command & Conquer (westwood.ea.com) series, along with Total Annihilation (www.cavedog.com), stand out as good examples of this genre.

AI in strategy games needs to be applied both at the level of strategic opponents and at the level of individual units. AI at the strategic level involves the creation of computer opponents capable of mounting ordered, cohesive, well-planned and innovative campaigns against the human player. At the unit level, AI is required in order to allow a player's units to carry out the player's orders as accurately as possible. Challenges at unit level include accurate path finding and allowing units a degree of autonomy in order to be able to behave sensibly without the player's direct control.

In RPGs or RTSGs, rules can be used to program the behavior of your own PCs or units. For example, in Baldur's Gate you can specify the behavior of the characters in your group using a scripting language. This would have been easier using rules.

Rules can be used also to specify scenarios. For example, in most RTS games map editors, you can describe a scenario by specifying rules applied to a map section (if a number of units enter this section, then trigger this action).

Game-AI Behavior

The sections above show some of the possible application for AI in game in general and RBS in particular. These are the creation of interesting opponents, realistic and engaging NPCs and maintaining consistency in dynamic storylines.

To help in making the game immersive and allow suspension of disbelief, the creation of the NPCs must provide different types of behavior. Two categories of generic behavior in NPCs are commonly used: reactionary and spontaneous.

NPCs behave in a reactionary manner whenever they are responding to a change in their environment. If an enemy spots you and starts to run towards you and shoot, then they have acted as a reaction to seeing you.

NPCs behave in a spontaneous manner when they perform an action that is not based on any change in their environment. A NPC that decides to move from his standing guard post to a walking sentry around the base has made a spontaneous action.

For more details Please see: Howland G, A Practical Guide To Building A Complete Game AI, 1999.

SOAR-BOT Example

Example: SOAR-Quake, courtesy of J. Laird.

IF enemy visible and my health is < very-low-health-value (20%)
OR
his weapon is much better than mine
THEN propose retreat
RBS Definitions

Introduction

One form of AI that can be used is a rule-based system.

Rule-based systems differ from standard procedural or object-oriented programs in that there is no clear order in which code executes. Instead, the knowledge of the expert is captured in a set of rules, each of which encodes a small piece of the expert's knowledge.

Each rule has a left hand side and a ride hand side. The left hand side contains information about certain facts and objects which must be true in order for the rule to potentially fire (that is, execute).

Any rules whose left hand sides match in this manner at a given time are placed on an agenda. One of the rules on the agenda is picked (there is no way of predicting which one), and its right hand side is executed, and then it is removed from the agenda. The agenda is then updated (generally using a special algorithm called the RETE algorithm), and a new rules is picked to execute. This continues until there are no more rules on the agenda.

Rule Based Systems Components

Rule-based systems consist of a set of rules, a working memory and an inference engine. The rules encode domain knowledge as simple condition-action pairs. The working memory initially represents the input to the system, but the actions that occur when rules are fired can cause the state of working memory to change. The inference engine must have a conflict resolution strategy to handle cases where more than one rule is eligible to fire.

A rule-based system consists of:

• a set of rules,
• working memory that stores temporary data,
• inference engine.

The inference mechanisms that can be used by inference engines are:

• Backward Chaining:
  • To determine if a decision should be made, work backwards looking for justifications for the decision.
  • Eventually, a decision must be justified by facts.
• Forward Chaining
  • Given some facts, work forward through inference net.
  • Discovers what conclusions can be derived from data.

Extensions to Rule-based Systems

Rule-based systems support formalisms with different level of expressiveness. Examples of these include:

• propositional logic,
• first-order logic,
• events and temporal constraints,
• probability associated with rules,
• fuzzy logic,
• etc.

All of these can be used to provide better AIs, e.g., you can imagine a bot that hides when it is being shot at. Then it waits for five seconds before trying to shoot back if there is no other shooting and no incoming noise.

RETE Algorithm

A possible inference engine is the RETE Algorithm. The RETE Algorithm is widely recognized as by far the most efficient algorithm for the implementation of rule-based systems. It is the only algorithm whose efficiency is asymptotically independent of the number of rules. Although a number algorithms implementing production rules have been considered, based on actual, empirical evidence, the RETE Algorithm is orders of magnitude faster than all published algorithms with the exception of TREAT algorithm. RETE is usually several times faster than TREAT for small numbers of rules with RETE's performance becoming increasingly dominant as the number of rules increases.

The typical RBS has a fixed set of rules while the knowledge base changes continuously. However, it is an empirical fact that, in most RBSs, much of the knowledge base is also fairly fixed from one rule operation to the next. Although new facts arrive and old ones are removed at all times, the percentage of facts that change per unit time is generally fairly small. For this reason, the obvious implementation for an RBS architecture is very inefficient. The obvious implementation would be to keep a list of the rules and continuously cycle through the list, checking each one's left-hand-side (LHS) against the knowledge base and executing the right-hand-side (RHS) of any rules that apply. This is inefficient because most of the tests made on each cycle will have the same results as on the previous iteration. However, since the knowledge base is stable, most of the tests will be repeated. You might call this the rules finding facts approach and its computational complexity is exponential.

A very efficient method known is the RETE algorithm. It became the basis for a whole generation of fast expert system shells: OPS5, its descendant ART, RETE++, CLIPS, JESS, and ILOG-Rules.

For more information on RETE see:

• Forgy, C. L., "RETE: A fast algorithm for the many pattern/many object pattern match problem". Artificial Intelligence, 19(1) 1982, pp. 17-37.
• Giarratano and Riley, Expert Systems: Principles and Programming, Second Edition, PWS Publishing, Boston, 1993.

Specification

The aim is to propose a general game AI engine organized around the components mentioned in the RBS definitions section. This should make the implementation of NPCs easier by providing a suitable interface with the game-world, a common inference engine and different knowledge base suitable for a large variety of games.

A summary of RBS components is below with possible choices:

Knowledge Representation

• Production Rules
• Frames
• Object Oriented Representation

Inference Algorithm

• RETE
• TREAT

System Architecture

• Centralized
• Multi-Agent
• Blackboard

RBS Game AI Cycle

The diagram below shows the "thinking" process.

Interface with Game World

The following architecture shows an example how an RBS could be integrated. Note that the architecture is of course very dependent on what the final world interface will look like.

Group Members

Current members of the working group on rule-based systems:

• Group coordinator: Abdennour El Rhalibi - Liverpool John Moores University
• Jean-Louis Ardoint - ILOG
• Daniele Benegiamo - AI42
• Nathan Combs - BBN Technologies
• Hannibal Ding - Interserv Information Technique
• Clay Dreslough - Sports Mogul
• Frank Hunter - Adanac Command Studies
• Gerard Lawlor - Kapooki Games
• John Mancine - Human Head Studios
• Miranda Paugh - Magnetar Games

Appendix A: Concepts and Terminology

Blackboard architecture

A Blackboard Architecture is an AI solution where Knowledge for a domain is shared between numerous KS (Knowledge Sources). Each KS represents an expert bringing its own set of knowledge to the blackboard and uses the knowledge published through the blackboard to build assumptions, make deductions etc.

Condition-action rule

A condition-action rule, also called a production or production rule, is a rule of the form: if condition then action.

The condition may be a compound one using connectives like and, or, and not. The action, too, may be compound. The action can affect the value of working memory variables, or take some real world action, or potentially do other things, including stopping the production system. See also inference engine.

Conflict resolution

Conflict resolution in a forward-chaining inference engine decides which of several rules that could be fired (because their condition part matches the contents of working memory should actually be fired.

Conflict resolution proceeds by sorting the rules into some order, and then using the rule that is first in that particular ordering. There are quite a number of possible orderings that could be used.

Frames

Frames are a knowledge representation technique. They resemble an extended form of record (as in Pascal and Modula-2) or struct (using C terminology) or class (in Java) in that they have a number of slots which are like fields in a record or struct, or variable in a class. Unlike a record/struct/class, it is possible to add slots to a frame dynamically (i.e. while the program is executing) and the contents of the slot need not be a simple value. There may be a demon present to help compute a value for the slot.

Demons in frames differ from methods in a Java class in that a demon is associated with a particular slot, whereas a Java method is not so linked to a particular variable.

Heuristic

A heuristic is a fancy name for a "rule of thumb" - a rule or approach that doesn't always work or doesn't always produce completely optimal results, but which goes some way towards solving a particularly difficult problem for which no optimal or perfect solution is available.

Inference engine

A rule-based system requires some kind of program to manipulate the rules - for example to decide which ones are ready to fire (i.e., which ones have conditions that match the contents of working memory). The program that does this is called an inference engine, because in many rule-based systems, the task of the system is to infer something, e.g. a diagnosis, from the data using the rules. See also match-resolve-act cycle.

Knowledge base

Collection of the data and rules that suitably represent the problem domain.

Match-Resolve-Act cycle

The match-resolve-act cycle is the algorithm performed by a forward-chaining inference engine. It can be expressed as follows:

loop

1. match all condition parts of condition-action rules against working memory and collect all the rules that match;
2. if more than one match, resolve which to use;
3. perform the action for the chosen rule until action is STOP or no conditions match.

Step 2 is called "conflict resolution". There are a number of conflict resolution strategies.

RETE

Algorithm used to optimize forward chaining inference engines by optimizing time involved in recomputing a conflict set once a rule is fired.

Rule-based system

A rule-based system is one based on condition-action rules.

Search

Search is a prevalent metaphor in artificial intelligence. Many types of problems that do not immediately present themselves as requiring search can be transformed into search problems. An example is problem solving, which can be viewed in many cases as search a state space, using operators to move from one state to the next.

Particular kinds of search are breadth-first search, depth-first search, and best-first search.

Working memory

The working memory of a rule-based system is a store of information used by the system to decide which of the condition-action rules is able to be fired. The contents of the working memory when the system was started up would normally include the input data - e.g. the patient's symptoms and signs in the case of a medical diagnosis system. Subsequently, the working memory might be used to store intermediate conclusions and any other information inferred by the system from the data (using the condition-action rules).

Appendix B: Links and References

Links

• ai-depot.com/Main.html
• www.gameai.com/
• www.exa.unicen.edu.ar/~azunino/javalog.html
• www.firingsquad.gamers.com/games/war3preview/
• Pottinger, Dave C., "Implementing Coordinated Unit Movement", Game Developer magazine, february 1999. Also available online at www.gamasutra.com/features/19990129/implementing_01.htm
• Howland G, "A Practical Guide To Building A Complete Game AI", www.gamedev.net/reference/articles/article784.as, 1999.
• www.jcp.org/en/jsr/detail?id=94
• www.expertise2go.com/webesie/tutorials/ESIntro/
• www.cee.hw.ac.uk/~alison/ai3notes/subsection2_4_4_1.html
• www.aiwisdom.com/
• www.gamasutra.com/features/20000619/wright_01.htm

References

• Pinter, Marco, "Realistic Turning between Waypoints", AI Game Programming Wisdom, Charles River Media, 2002.
• Laird, J. E. and van Lent, M. 1999. "Developing an Artificial Intelligence Engine". In Proceedings of the Game Developers' Conference, San Jose, CA, pp. 577-588.
• Frank, I. 1999. "Explanations Count". In Papers from the AAAI 1999 Spring Symposium on Artificial Intelligence and Computer Games, Technical Report SS-99-02, pp. 77-80. AAAI Press.
• Forgy, C. L., "RETE: A fast algorithm for the many pattern/many object pattern match problem". Artificial Intelligence, 19(1) 1982, pp. 17-37.
• Giarratano and Riley, Expert Systems: Principles and Programming, Second Edition, PWS Publishing, Boston, 1993.
• Miranker, D., "TREAT: A new and efficient match algorithm for AI production systems". Pittman/Morgan Kaufman, 1989.
• Rollings A, Game Architecture and Design, Coriolis Technology Press, 2000.