Discussion

At this stage, we can identify some of the primary benefits of RBSs as well as their pitfalls. Additional experience will help us easily decide when RBSs are appropriate for game AI problems. Until then, to assist our decisions, here is a list of characteristics.

Advantages

It is not a coincidence that RBSs are one of the most successful AI techniques ever. Here are the main reasons they are a tremendous benefit in game development:

• Simplicity— Individual rules have simple syntax and express knowledge in a natural fashion. Rule-based systems are based on human reasoning, which implies it is straightforward for experts to understand their functioning. The knowledge is also defined in an implicit fashion, saving much time and effort.

• Modularity— Production rules capture knowledge in a relatively atomic fashion. Statements can be combined and edited independently from each other. This makes RBSs simple to extend.

• Flexibility— By specifying knowledge in a relatively informal fashion (not as logic), the data can be manipulated to provide the desired results. It is also easy to add more symbols in the working memory, or even improve the knowledge representation used.

• Applicability— Because most problems can be formalized in a compatible way (for instance, symbols), RBSs will often be a possible solution—and one that works! The scope of applicable domains ranges far, from simulation to problem solving.

Naturally, there are some trade-offs to be made, taking into account the possible problems.

Disadvantages

Rule-based systems are no miracle solution. The following points will help us decide whether to use them, and help identify the pitfalls if we do choose them:

• Expressiveness— As a knowledge representation language, RBSs aren't very expressive; little knowledge is in notational form and inference plays an important role to extract information. This implies it can be difficult to predict the behavior of an RBS just by looking at the rules.

• Power— Although single-production rules are quite flexible, their body is often restricted by the syntax of the representation (for instance, set symbol to value). The body can also be limited to one statement, especially in backward-chaining systems. This doesn't come close to the power of modern programming languages such as Java or C++.

• Efficiency— In simple systems, the computational power required scales linearly with the number of rules. This is the typical cost of the condition matching phase. Although it can be optimized for processing speed, memory usage cannot be decreased as easily. In addition, in systems where exhaustive search is required to solve the problem, RBSs can be fairly slow.

• Suitability— Although the technique can be applied to many domains, it is not always the best option. Symbols aren't suited to modeling some problems (for instance, smooth control or sequences of actions), and expert knowledge is just not always available.

Most of these disadvantages can be resolved in one way or another, although it often depends on the problem itself.

Game Developer's Approach

This section presents pertinent insights into RBSs for computer games and explains the game developer's attitude toward them.

Design and Development

A professional game AI developer will most likely be expected to be the programmer, the knowledge engineer, and the domain expert. It is a good idea to separate these three jobs even if only one person does the work. This can be achieved by splitting content and code. The implementation of the knowledge-based system comes first, and the declaration of the expert rules will follow later in the game development cycle. Generally, development is an iterative process of writing code and testing it. The distinction between mechanical reasoning and knowledge declaration splits this process into two, making it easier for one person to handle.

This has many additional advantages in game production, as well as those advantages associated with such second-generation expert systems:

• Reusability— Having the RBS as a separate module enables you to apply it to different problems. This would not be possible with procedurally encoded knowledge, but with declarative knowledge it can be loaded from a file at runtime.

• Debugging— If the RBS is performing a behavioral simulation (rather than solving problems), the results will be visible to the rest of the team. When a bug is encountered, a report can be filed describing the exact situation. To do this, a procedure can be written to save the working memory's current state to disk. Then, adding an extra rule to correct the behavior is trivial. A simple user interface could potentially allow almost anyone to update the rulebase!

There is a small drawback in developing a flexible system such as this: execution speed. This warrants looking into further.

Efficiency

It's the processing of rules that is going to be the most computationally expensive in knowledge-based system. Let's analyze both aspects of these rules—the conditions and the actions—in terms of both procedural (hard-coded) and declarative (data-driven) approaches:

Procedural  code:     if (a && b && c) { d = true; }
Declarative file:     IF a AND b AND c THEN d

In terms of raw execution speed, a condition that is hard-coded will beat any other approach (for instance, scripted and interpreted dynamically). However, this is no reason to discard the declarative approach; with a procedural approach, the system has no chance of acquiring high-level understanding of the conditions. On the other hand, when handling the rules separately to the code, the system will be given the opportunity to read and analyze the conditions. This allows the RBS module to reorganize declared production rules in convenient form (that is, a tree or graph). So, the system will minimize the number of tests required to match each rule with the current state. Such an approach will outperform the procedural alternative on large data sets.

As for the body of the rules, the problem is similar. Hard-coded actions provide more efficiency and power (thanks to native languages such as C++). The declarative alternatives are slightly more flexible at runtime, but incur a speed hit and more syntactic restrictions—usually limited to setting symbols in the working memory. This will be necessary if you require backward chaining. However, for forward chaining there is a compromise to be made. A set of default actions can be hard-coded and referenced inside a small database. Then, the declarative rules can refer to these, and the simple lookup can call the native actions at a runtime. This provides the best of both worlds!

Suitable Problems

Because of the knowledge acquisition bottleneck, we must make sure that any problem we tackle will have sufficient expert knowledge available, or that can be easily acquired. If this is not the case, it will be extremely tedious to develop a working RBS. We also rely on the domain to be represented with symbols—which RBSs are particularly suited to.

In some problems, we may find ourselves writing long sequences of if statements in C++ (for instance, defining a reactive behavior for movement). RBSs are extremely well-suited to handling of this type of problem in a flexible and extendable fashion. Often, this can be done much more efficiently, too!

RBSs strive on solving problems. The solution will be found efficiently as long as there are many alternatives to reach the goal state (that is, with no traps). In this case, the choice of the rules during conflict resolution will only be moderately important, and the complexity of a search process will not be required.

Rule-based systems do very well as a control technique, as long as the behavior is purely reactive. When the RBS need an additional internal symbol to support non-determinism, things can get problematic. (We'll see this with wall following in the next chapter.) In fact, the problem is worse when well-defined sequences of actions are required. A finite-state machine, as discussed in Chapter 38, "Finite-State Machines," would be better suited to these problems.