Effect of constraints on evolving behavior trees for game AI

Behavior trees are a popular method for creating AI characters in games. They allow modular and hierarchical behaviors, making it easy to maintain, extend and modify behaviors for differ situations. Nevertheless, a considerable amount of skill, experience and time is required to produce believable behaviors.

Previous attempts to automate the development of behavior trees using genetic programming have met with limited success. One of the reasons for this is that random crossover and mutation of a behavior tree can result in large trees with many nonsensical branches. We investigate different methods for constraining crossover and mutation of the behavior tree in order to reduce the size of the search space and improve the resultant AI.

Preliminary experiments have focused on the game Pacman and we present results showing that constraining crossover and mutation so that the resultant behavior trees always maintain a sensible structure produces significantly better results than an unconstrained algorithm.