|
AI Game Development. Synthetic Creatures with Learning and Reactive Behaviors Authors: Champandard A. J. Published year: 2003 Pages: 198-199/399 |
DiscussionDecision trees are extremely efficient at computing estimates for unknown samples. The data structure is simple and small, and requires little effort to traverse. DTs are particularly suited to data-mining problems, so mass processing of information in real time is not a problem. In addition, due to the small amounts of information needed, the footprint for storing DTs in memory is very small. After the knowledge has been encoded in the tree, there is often little need to keep the data samples. Finally, DTs are relatively flexible. They can be used on continuous and symbolic predictor variables. The response variables can also be used for regression or classification, which makes them easy to apply to a wide variety of problems. However, some disadvantages are worth noting. Decision trees are well suited to batch processing data sets. When it comes to learning them online, however, existing algorithms can be somewhat clumsy (both memory intensive and tricky to implement). Everything considered , gathering the samples incrementally and then applying batch learning seems the easiest approach -which usually results in the same behavior. The recursive partitioning algorithm is greedy in nature. This performs relatively well, but it is usually suboptimal in both the quality of the results and the size of the tree. This is the case for surprisingly many trees, although the quality is good enough for game development. Last but not least, there can be problems dealing with overfitting. Secondary pruning phases can be used to remedy the problem, but this requires additional computation and additional data to validate the result. Integrated algorithms, sadly, loose the benefit of simplicity. |
SummaryThere 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:
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 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.
|
|
AI Game Development. Synthetic Creatures with Learning and Reactive Behaviors Authors: Champandard A. J. Published year: 2003 Pages: 198-199/399 |
![]() Artificial Intelligence for Games, Second Edition | ![]() Programming Game AI by Example | ![]() Behavioral Mathematics for Game AI |