Designing Emergent AI, Part 3: Limitations

The first part of this article series was basically an introduction to our AI design, and the second part of this article series took a look at some of the LINQ code used in the game, as well as discussing danger levels and clarifying a few points from the first article. The second article was basically just for programmers and AI enthusiasts, as is this third one. The topic, this time, is the manner in which this approach is limited.

This Approach Is Limited?
Well, of course. I don't think that there is any one AI approach that can be used to the exclusion of all others. And our AI designs are already heavily hybridized (as the first article in the series mentions), so it's not like I'm using any single approach with AI War, anyway. I used the techniques and approaches that were relevant for the game I was making, and in some respects (such as pathfinding), I blended in highly traditional approaches.

The purpose of this article is to discuss the limits of the new approaches I've proposed (the emergent aspects, and the LINQ aspects), and thereby expose the ways in which these techniques can be blended with other techniques in games beyond just AI War. Let's get started:

Where Emergence Quickly Breaks Down
To get emergent behavior, you need to have a sufficient number of agents. And to keep them from doing truly crazy stuff, you need to have a relatively simple set of bounds for their emergence (in the case of AI War, those bounds are choosing what to attack or where to run away to. Basically: tactics). Here are some examples of places that I think it would be massively ineffective to try for emergent behavior:

1. A competitive puzzle game like tetris. There's only one agent (the cursor).

2. Economic simulations in RTS games. That's all too interrelated, since any one decision has potentially massive effects on the rest of the economy (i.e., build one building and the opportunity cost is pretty high, so some sort of ongoing coordination would be very much needed).

3. Any sort of game that requires historical knowledge in order to predict player actions. For example, card games that involve bluffing would not fare well without a lot of historical knowledge being analyzed.

4. Any game that is turn-based, and which has a limited number of moves per turn, would probably not do well with this because of the huge opportunity cost. Civilization IV could probably use emergent techniques despite the fact that it is turn-based, but Chess or Go are right out.

Why Emergence Works For AI War
1. There are a lot of units, so that gives opportunities for compound thinking based on intelligence in each unit.

2. Though the decision space is very bounded as noted above (what to attack, or where to retreat to), that same decision space is also very complex. Just look at all of the decision points in the LINQ logic in the prior article. There are often fifty ways any given attack could succeed to some degree, and there are a thousand ways they could fail. This sort of subtlety lets the AI fuzzify its choices between the nearly-best choices, and the result is effective unpredictableness to the tactics that feels relatively human.

3. There is a very low opportunity cost per decision made. The AI can make a hundred decisions in a second for a group of ships, and then as soon as those orders are carried out it can make a whole new set of decisions if the situation has changed unfavorably.

4. Unpredictableness is valuable above most all else in the tactics, which works well with emergence. As long as the AI doesn't do something really stupid, just having it choose effectively randomly between the available pretty-good choices results in surprise tactics and apparent strategies that are really just happenstance. If there were fewer paths to success (as in a racing game, for example), the boundedness of decisions to make would be too tight to make any real opportunities for desirable emergent behavior.

Learning Over Time
One intentional design choice that I made with AI War was to keep it focused on the present. I remember seeing Grandmaster Chess players at Chess tournaments, where they would play against 50 regular ranked players at once, walking around the room and analyzing each position in turn. On most boards they could glance at the setup and make their move almost instantly. On a few they would pause a bit more. They would still typically win every game, just choosing whoever put up the best fight to cede a victory to (that person typically got a prize).

I figured it would be nice to have an AI with basically those capabilities. It would look at the board at present, disregarding anything it learned in the past (in fact, it would be just a subject matter expert, not a learning AI in any capacity), and then it would make one of the better choices based on what it saw. This is particularly interesting when players do something unexpected, because then the AI does something equally unexpected in response (responding instantly to the new, unusual "board state").

I feel like this works quite well for AI War, but it's not something that will evolve over time without the players learning and changing (thus forcing the AI to react to the different situations), or without my making extensions and tweaks to the AI. This was the sort of system I had consciously designed, but in a game with fully symmetrical rules for the AI and the humans, this approach would probably be somewhat limited.

The better solution, in those cases, would be to combine emergent decision making with data that is collected and aggregated/evaluated over time. That collected data becomes just more decision points in the central LINQ queries for each agent. Of course, this requires a lot more storage space, and more processing power, but the benefits would probably be immense if someone is able to pull it off with properly bounded evaluations (so that the AI does not "learn" something really stupid and counterproductive).

Isn't That LINQ Query Just A Decision Tree?
One complaint that a few AI programmers have had is that the LINQ queries that I've shared in the second article aren't really that different from a traditional decision tree. And to that, I reply: you're absolutely right, that aspect is not really too different. The main advantage is an increase in readability (assuming you know LINQ, complex statements are much more efficiently expressed).

The other advantage, however, is that soft "preferences" can easily be expressed. Rather than having a huge and branching set of IF/ELSE statements, you have the ORDER BY clause in LINQ which makes the tree evaluation a lot more flexible. In other words, if you have just this:

ORDER BY comparison 1,
     comparison 2,
     comparison 3

You would be able to have a case where you have 1 as true, 2 as false, and 3 as true just as easily as all three being true, or having false, true, false, or any other combination. I can't think of a way to get that sort of flexibility in traditional code without a lot of duplication (the same checks in multiple branches of the tree), or the use of the dreaded and hard-to-read gotos.

So, while the idea of the LINQ query is basically the same as the decision tree in concept, in practice it is not only more readable, but it can be vastly more effective depending on how complex your tree would otherwise be. You don't even have to use LINQ -- any sorting algorithm of sufficient complexity could do the same sort of thing. The novelty of the approach is not LINQ itself, but rather using a tiered sorting algorithm in place of a decision tree. You could also express the above LINQ code in C# as:

someCollection.Sort( delegate( SomeType o1, SomeType o2 )
{
int val = o1.property1.CompareTo( o2.property1 );
if ( val == 0 )
  val = o1.property2.CompareTo( o2.property2 );
if ( val == 0 )
  val = o1.property3.CompareTo( o2.property3 );
return val;
} );

In fact, throughout the code of AI War, statements of that very sort are quite common. These are more efficient to execute than the equivalent LINQ statement, so on the main thread where performance is key, this is the sort of approach I use. In alpha versions I had it directly in LINQ, which was excellent for prototyping the approaches, but then I converted everything except the AI thread into these sorts instead of LINQ, purely for performance reasons. If you're working in another language or don't know SQL-style code, you could easily start and end with this kind of sorting.

Combining Approaches
In AI War, I use basically the following approaches:

1. Traditional pathfinding
2. Simple decision-engine-style logic for central strategic decisions.
3. Per-unit decision-engine-style logic for tactics.
4. Fuzzy logic (in the form of minor randomization for decisions) throughout to reduce predictability and encourage emergence given #3.
5. Soft-preferences-style code (in the form of LINQ and sorts) instead of hard-rules-style IF/ELSE decision tree logic.

If I were to write an AI for a traditional symmetrical RTS AI, I'd also want to combine in the following (which are not needed, and thus not present, in AI War):

6. A decision tree for economic management (using the sorting/LINQ approach).
7. A learning-over-time component to support AI at a level for really great human players in a symmetrical system.

If I were to write an AI for a FPS or racing game, I'd probably take an approach very similar to what those genres already do. I can't think of a better way to do AI in those genres than they already are in the better games in each genre. You could potentially combine in emergence with larger groups of enemies in war-style games, and that could have some very interesting results, but for an individual AI player I can't think of much different to do.

For a puzzle game, or a turn-based affair like Chess, there again I would use basically the current approaches from other games, which are deep analysis of future moves and their consequences and results, and thus selection of the best one (with some heuristics thrown in to speed processing, perhaps.).

Performers or adventure games could also use mild bits of swarm behavior to interesting effect, but I think a lot of players (myself included) really do like the convention of heavily rules-based enemies in those genres. These games don't really tend to feature AI that is meant to mimic humans, rather AI that is meant to just follow simple rules that the human players can learn and remember.

The sort-style decision tree might be easier to code and might bring results slightly more efficiently in all of the above cases, but the end result for the player wouldn't be much different. Still, making AI code easier to program and read is a good thing for everyone (lower costs/time to develop, fewer bugs based on poor readability, etc).

Next Time
Part 4 of this series talks about the asymmetry in this AI design.

AI Article Index
Part 1 gives an overview of the AI approach being used, and its benefits.
Part 2 shows some LINQ code and discusses things such as danger levels.
Part 3 talks about the limitations of this approach.
Part 4 talks about the asymmetry of this AI design.
Part 5 is a transcript of a discussion about the desirability of slightly-nonideal emergent decisions versus too-predictable "perfect" decisions.
Part 6 talks about player agency versus AI agency, and why the gameplay of AI War is based around keeping the AI deviously reactive rather than ever fully giving it the "tempo."