Summary

There are two kinds of decisions trees: Classification trees result in categorical responses, and regression trees return continuous values. The representation of DTs is very intuitive, and almost identical in both cases:

• Each decision node has a conditional test over predictor variables.

• The branches correspond to the possible results of the test (mutually exclusive).

• Layers of the tree can be combined hierarchically.

• The leaves store the response either categorical or continuous.

The simulation algorithm uses a data sample to traverse the tree according to the results of each conditional test. The training or induction algorithm operates with recursive partitioning:

• The data set is partitioned according to the best variable, resulting in the purest subsets.

• The corresponding decision node is created in the tree, and the process continues recursively.

The best way to improve the training is to manage the data set, using additional validation and testing sets. Pruning also is a very effective option in computer games, but other techniques such as bagging and boosting are not very suited to game development.

Because DTs are capable of finding patterns in data, and learning to recognize them, the next chapter applies them to weapon selection. Based on the situation, the DT will learn to evaluate the fitness of each weapon.

Practical Demo

Detox is an animat using an architecture rooted with a DT. The decision controls all the actions specified until now (for instance, movement, aiming, selection) and the corresponding senses. Detox is taught by imitation, collecting data from human players. The performance is relatively poor, because every action being handled homogenously (that is, no decomposition based on behaviors or capabilities). Source code and demo are available online at http://AiGameDev.com/.