At any rate, today I just want to jot down some ideas I had while on the plane: a sketch of a method to use genetic techniques to evolve statechart based AI behavior.
First, some quick background: City Conquest, by Intelligence Engine Design Systems, is a tower defense game with some real time strategy elements, and Paul Tozour -- one of the company’s founders -- wrote a program called Evolver which was used extensively during development.
The main thing an AI can do in City Conquest is to build a building at a location. Evolver, therefore, generated good series of build commands for the AI. It did this by pitting millions of sets of randomly generated sequences of build commands against each other in-game. The intent was not only to create a set of challenging AI strategies for player to contend with, but also provide game balance feedback and automated testing for the team during development. The team would look at what strategies evolved, and discover unfair exploits or disadvantages in certain building types.
SearchGenetic programming is a process of search. The technique winnows pools of candidates down to find those that best match some predetermined “fitness score”. ( Evolver, for instance, searched for strategies where a capital city ended with the greatest number of health points. ) Note: This is different than Darwinian evolution because, in the real world, populations expand as well as contract and, in the real world, there is no single concept of fitness. ( Perhaps we might say, Darwinian evolution propagates *any* runnable program. Other running programs, and the context of the world at large, influence what it means to remain runnable. ) Genetic programming is an elimination of possibilities. It's a death match search.
Programs as TreesIn Steven Gustafson’s thesis, “Diversity in Genetic Programming”, he describes the common practice of “evolving” Lisp expressions.
To evolve ( ie. search for ) a program that satisfies a particular goal, you need a bunch of candidate programs to search through. Rather than starting with all possible combinations of programs ( re: Turning; this space is very large ), genetic “cross-breeding” swaps sub-trees after each generation to increase the size of the search pool. Cross-breeding is essentially a search space optimization. Successful strategies are used as starting points for new programs.
Only in special circumstances can you know when “evolution is complete.” Instead, you simply run the search X number of million times, and cross your fingers a good solution will pop out. As a side note: this can lead to finding “local minima” -- successful strategies, that could in theory be surpassed by a strategy not in the pool of generated candidates. Such is (the game of) life.
Trees of CommandsSaving functions as commands as I’ve previously outlined in my blog brings two interesting tools to the table. First, you don’t have to program in Lisp :) . A command-based language can look just like a procedural language. ( Under-the-hood, however, it's stored as a functional tree. ) Second, the inconsistency between “value leaf” and “function node” is removed. The system only knows about commands. The Add command data stores two scalar function value references, while the Make Value command replaces the stored value. The parameter of each Make Value is a single scalar value, just the parameters of an Add are two command references. This uniformity in node type opens the door for terminal nodes to do more interesting things. Commands could generate values over time, they could read input from users, and so on.
Command based nodes also open the door for storing programs that aren’t strictly function based. For instance, for each command type we could have meta-data describing the variability that’s allowed during cross-breeding. If, for instance, our program contained a command for how many shots an AI unit should fire in a burst, we could specify a range to restrict evolutionary variations. Maybe, for instance, cap the number of shots fired based on knowing how many projectiles the game can draw at one time. ( Probably a silly metric for burst firing, but you get the idea. )
Statechart TreesGoing one step further, it would be extremely interesting to store statecharts as command trees, and then evolve them.
|ye old stopwatch example. again.|
|a statechart execution over time.|
One concrete example of how this might work, think about evolving (searching) for what health level an AI should use a health potion. There could be a general category of logically good moments: when health is low; a general category of logically bad moments: when health is high; even nonsensical moments: triggered every time enemies heals themselves. But, rather than having to explicitly program this, we could see if the evolver can search out that fact for itself based on how well the AI succeeds in combat.