Designing Emergent AI, Part 2: Queries and Code

The first part of this article series has been a hit with a lot of people, yet criticized by others for being too introductory/broad. Fair enough, starting with this article I'm going to get a lot lower-level. If you're not a programmer or an AI enthusiast, you probably won't find much interest beyond this point.

What Do You Mean, It Works Like A Database?
First question that most people are asking is in what way my AI code can possibly be like a database. In a past article (Optimizing 30,000+ Ships In Realtime In C#) I already talked about how I am using frequent rollups for performance reasons. That also helps with the performance of the AI, but that's really not the meat of what I'm talking about.

I'm using LINQ for things like target selection and other goal selection with the AI in the game, and that really cuts down on the amount of code to make the first level of a decision (it also cuts down on the amount of code needed in general, I'd estimate that the entirety of the decision-making AI code for the game is less than 20,000 lines of code). Here's one of the LINQ queries for determining target selection:

var targets =
                     //30% chance to ignore damage enemy can do to them, and just go for highest-value targets
                     ( unit.UnitType.AIAlwaysStrikeStrongestAgainst ||
                     AILoop.Instance.AIRandom.Next( 0, 100 ) < 30 ?
                     from obj in rollup.EnemyUnits
                     where ( unit.GuardingObjectNumber <= 0 || //must not be guarding, or guard target must be within certain range of guard post
                      Mat.ApproxDistanceBetweenPoints( unit.GuardingObject.LocationCenter,
                      obj.LocationCenter ) < Configuration.GUARD_RADIUS )
                     orderby obj.UnitType.ShipType == ShipType.Scout ascending, //scouts are the lowest priority
                         obj.GetHasAttackPenaltyAgainstThis( unit ) ascending, //ships that we have penalties against are the last to be hit
                         (double)obj.GetAttackPowerAgainstThis( unit, usesSmartTargeting ) / (double)obj.UnitType.MaxHealth descending, //how much damage I can do against the enemy out of its total health
                         obj.IsProtectedByForceField ascending, //avoid ships that are under force fields
                         obj.NearbyMilitaryUnitPower ascending, //strength of nearby enemies
                         Mat.ApproxDistanceBetweenPoints( obj.LocationCenter, unit.LocationCenter ) ascending, //how close am I to the enemy
                         obj.UnitType.ShieldRating ascending, //how high are their shields
                         unit.UnitType.AttackPower ascending, //go for the lowest-attack target (economic, probably)
                         obj.Health ascending //how much health the enemy has left
                     select obj
                   :
                       from obj in rollup.EnemyUnits
                       where ( unit.GuardingObjectNumber <= 0 || //must not be guarding, or guard target must be within certain range of guard post
                          Mat.ApproxDistanceBetweenPoints( unit.GuardingObject.LocationCenter,
                          obj.LocationCenter ) < Configuration.GUARD_RADIUS )
                       orderby obj.UnitType.ShipType == ShipType.Scout ascending, //scouts are the lowest priority
                           ( chooseWeaklyDefendedTarget ?
                           obj.UnitType.TripleBasicFirePower >= obj.NearbyMilitaryUnitPower :
                           ( chooseStronglyDefendedTarget ?
                           obj.UnitType.TripleBasicFirePower < obj.NearbyMilitaryUnitPower : true ) ) descending, //lightly defended area
                           (double)obj.GetAttackPowerAgainstThis( unit, usesSmartTargeting ) / (double)obj.UnitType.MaxHealth descending, //how much damage I can do against the enemy out of its total health
                           obj.IsProtectedByForceField ascending, //avoid ships that are under force fields
                           obj.NearbyMilitaryUnitPower ascending, //strength of nearby enemies
                           obj.GetHitPercent( unit ) descending, //how likely I am to hit the enemy
                           unit.GetAttackPowerAgainstThis( obj, false ) descending, //how much damage the enemy can do to me
                           obj.Health ascending //how much health the enemy has left
                       select obj
                   );

Blogger eats a lot of the formatting there, but hopefully you can see what is going on based on the comments in green. In some ways you could call this a decision-tree (it does have multiple tiers of sorting), but the overall code is a lot more brief and (when properly formatted with tabs, etc) easier to read. And the best thing is that, since these are implemented as a sort, rather than distinct if/else or where clause statements, what you arrive at is a preference for the AI to do one thing versus another thing.

There are a lot of things that it takes into consideration up there, and there are a few different modes in which it can run, and that provides a lot of intelligence on its own. But that's not enough. The loop that actually evaluates the above logic also adds some more intelligence of its own:

bool foundTarget = false;
                        foreach ( AIUnit enemyUnit in targets )
                        {
                            if ( enemyUnit.Health <= 0 || enemyUnit.CloakingLevel == CloakingLevel.Full )
                                continue; //skip targets that are already dead, or are cloaked
                            if ( unit.CloakingLevel == CloakingLevel.Full && 
                                enemyUnit.UnitType.ShipType == ShipType.Scout )
                                continue; //don't give away the position of cloaked ships to scouts
                            if ( unit.CloakingLevel != CloakingLevel.None &&
                                enemyUnit.UnitType.TachyonBeamRange > 0 )
                                continue; //cloaked ships will not attack tachyon beam sources
                            if ( enemyUnit.UnitType.VeryLowPriorityTarget )
                                continue; //if it is a very low priority target, just skip it
                            if ( enemyUnit.IsProtectedByCounterMissiles && unit.UnitType.ShotIsMissile )
                                continue; //if enemy is protected by counter-missiles and we fire missiles, skip it
                            if ( enemyUnit.IsProtectedByCounterSnipers && unit.UnitType.ShotIsSniper )
                                continue; //if enemy is protected by counter-sniper flares and we fire sniper shots, skip it
                            if ( enemyUnit.GetAttackPowerAgainstThis( unit, false ) == 0 )
                                continue; //if we are unable to hurt the enemy unit, skip attacking it
                            if ( unit.EffectiveMoveSpeed == 0 && !unit.UnitType.UsesTeleportation && 
                                enemyUnit.GetHitPercent( unit ) <>
                                continue; //stop ourselves from targeting fixed ships onto long-range targets

                            gc = GameCommand.Create( GameCommandType.SetAttackTarget, true );
                            gc.FGObjectNumber1 = unit.FGObjectNumber;
                            gc.FGObjectNumber2 = enemyUnit.FGObjectNumber;
                            gc.Integer1 = 0; //Not Attack-Moving
                            unit.LastAICommand = gc.AICommand;
                            AILoop.Instance.RequestCommand( gc );
                            foundTarget = true;
                            break;
                        }

                        //if no target in range, and guarding, go back to base if out of range
                        if ( !foundTarget && unit.GuardingObjectNumber > 0 )
                        {
                            Point guardCenter = unit.GuardingObject.LocationCenter;
                            if ( Mat.ApproxDistanceBetweenPoints( guardCenter, unit.LocationCenter ) >
                                Configuration.GUARD_RADIUS )
                                Move( unit, guardCenter );
                        }

Nothing real surprising in there, but basically it has a few more decision points (most of these being hard rules, rather than preferences). Elsewhere, in the pursuit logic once targets are selected, ships have a preference for not all targeting exactly the same thing -- this aspect of them watching what each other are doing is all that is really needed, at least in the game design I am using, to make them do things like branching and splitting and hitting more targets, as well as targeting effectively.

Rather than analyzing the above code point by point, I'll mostly just let it speak for itself. The comments are pretty self-explanatory overall, but if anyone does have questions about a specific part, let me know.

Danger Levels
One important piece of logic from the above code that I will touch on is that of danger levels, or basically the lines of code above where it is evaluating whether or not to prefer a target based on how well it is defended by nearby ships. All ships have a 30% chance to disregard the danger level and just go for their best targets, and some ship types (like Bombers) do that pretty much all the time, and this makes the AI harder to predict.

The main benefit of an approach like that is that it causes the AI to most of the time try to pick off targets that are lightly defended (such as scrubbing out all the outlying harvesters or poorly defended constructors in a system), and yet there's still a risk that the ships, or part of the ships will make a run at a really-valuable-but-defended target like your command station or an Advanced Factory. This sort of uncertainty generally comes across as very human-like, and even if the AI makes the occasional suicide run with a batch of ships, quite often those suicide runs can be effective if you are not careful.

Changing The AI Based On Player Feedback
Another criticism that some readers had about the first AI article was to do with my note that I would fix any exploits that people find and tell me about. Fair enough, I didn't really explain myself there and so I can understand that criticism. However, as I noted, we haven't had any exploits against the AI since our alpha versions, so I'm not overly concerned that this will be a common issue.

But, more to the point, what I was actually trying to convey is that with a system of AI like what you see above, putting in extra tweaks and logic is actually fairly straightforward. In our alpha versions, whenever someone found a way to trick the AI I could often come up with a solution within a few days, sometimes a few hours. The reason is simple: the LINQ code is short and expressive. All I have to do is decide what sort of rule or preference to make the AI start considering, what relative priority that preference should have if it is indeed a preference, and then add in a few lines of code. That's it.

With a decision tree approach, I don't think I'd be able t to do that -- the code gets huge and spread out through many classes (I have 10 classes for the AI, including ones that are basically just data holders -- AIUnit, etc -- and others that are rollups -- AIUnitRollup, which is used per player per planet). My argument for using this sort of code approach is not only that it works well and can result in some nice emergent behavior, but also that it is comparably easy to maintain and extend. That's something to consider -- this style of AI is pretty quick to try out, if you want to experiment with it in your next project.

Next Time
Part 3 of this series talks the limitations of this approach.

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."