Techniques and Their Applicability

During the development of game AI, various problems may occur. Fortunately, we've examined techniques to deal with them. The techniques presented in this book are (mostly) reactive, used ubiquitously throughout the games industry. Often, these reactive techniques can be used transparently as efficient substitutes for deliberative AI which still have to prove themselves as viable solutions for game AI (with the exception of A* pathfinding).

This section recapitulates solutions that spring to the mind of experienced developers when designing AI. Other "helper" techniques, such as reinforcement learning and evolutionary algorithms, are not discussed here; they can be seen as techniques to help solve each of the following problems.

Problem Solving

Problem solving involves finding an answer to a fixed problem, usually by deducing new facts from the information provided:

• Rule-based systems are particularly suited to problem solving, because they model the approach of a human expert. In many cases, crisp logic is more than appropriate for representing a majority of problems.

• Fuzzy expert systems are effective improvements when reasoning requires degrees of truth. However, the fuzzy approach suffers from being less efficient than the crisp alternative.

Sequential Control

Some problems require sequences of actions or behaviors. The position in the sequence needs to be tracked (with a state variable, for example):

• Finite-state machines have an intrinsic concept of state, so sequences are easily represented. By designing states (potentially nested) and connecting them together, the designers can create behaviors as a chain of actions.

• Probabilistic finite-state machines add a random element to the sequences, so designers have control over the stochastic actions.

• Fuzzy-state machines allow degrees of truth in the state activity. Although they provide additional smoothness in the transitions and actions, the computational cost grows with the number of states.

Pattern Recognition

A particular kind of problem in AI is pattern recognition, which involves classifying or recognizing a sample (set of variables). This is also known as estimating a response variable based on predictor values:

• Decision trees are particularly appropriate for categorical variables (that is, with discrete intervals). The advantage is that the representation is expressive and compact easily edited by the designer.

• Neural networks, and particularly perceptrons, are better suited for continuous variables. Multilayer perceptrons are much harder to understand than the single-layer variants, so they should be reserved for the complex problems only.

Sequence Recognition

Recognizing sequences of symbols, or classifying them, is another kind of problem that warrants its own set of techniques:

• Finite-state automata process the symbols one by one, updating the internal state variable accordingly. Sequences from regular languages can be recognized or classified.

• Probabilistic finite-state automata can be used to determine the likelihood of sequences occurring.

• Fuzzy-state automata are used to find the degree of membership of sequences in categories.