!!!! Spoiler Alert !!!!
Learning how the AI works in a game removes some of the “magic” as well as the fun of trying to figure out how to beat it. This post talks about a lot of specifics that could spoil your fun…
!!!! Spoiler Alert !!!!
In the previous post we went through building an HTN using the Inductor HTN Engine using a simple example. This post will go though real code from the Exospecies game AI to show some of the complexities that can happen.
Before we get into details, here are some high level facts about building the Exospecies AI using HTNs:
- Total time to implement the AI was roughly 7 months of calendar time for 1 person. This includes building the HTN and Prolog engines (which you don’t have to do since I open-sourced them!). Approximately 2/3 of the time was spent building the engine, so about 2.5 months was used to build the HTN tasks themselves.
- The AI consists of 112 total HTN Methods/HTN Operators/Prolog Rules, plus a bunch of facts (see ‘Step 1’ below)
- The HTN Engine is constrained to use only 1MB of memory, total, for everything: Tasks, Prolog Rules, runtime memory…everything.
- Don’t yet have good stats for how long it takes to “think” for a turn, but I’ll be able to get that from the beta.
A couple of unexpected side benefits of using HTNs:
- The AI can tell you why it chose to do a move. That makes debugging easier, but it also means I could add a future “Hint” feature for players. I’d simply ask the AI what it would do in the player situation and it would spit out the answer, including why it chose that. Try that with your deep learning AI!
- The HTNs are written in plain text, so updating the AI dynamically (for cases that don’t require new data, which is most changes) could be done and downloaded dynamically without requiring an update to the app. I could even add a feature to allow customers to build their own AI!
Using the HTN engine in Exospecies was exactly like integrating HTNs into any app (like the simple example from the previous blog post), there were three steps:
- Convert the app state you need to process into Prolog Facts
- Write the HTN Axioms, Methods, and Operators you need and use the Facts
- Convert the Operators that get generated into changes, moves, or whatever makes sense in your app
Let’s go step by step and see how this was done in Exospecies.
Step 1: Convert the app state you need to process into Prolog Facts
The engine needs to operate on Prolog facts. To do this, there is a simple class in Exospecies that walks through the structure of the game and converts the state into text, which is really straightforward code. Turns out this is a surpisingly small set of facts and most of them can be computed once, when the game first starts, and just reused. It is a very small amount of CPU work each turn.
When this class is done, in the current build, here are all the facts that serve as input into the engine:
/* Created once and cached: Facts about unit actions that never change */ player(Player2). enemyPlayer(Player1). supplyUnit(Queen). action(Queen,Move,3). moveSpeed(Queen,1). action(Queen,Attack,10). attackDistance(Queen,Attack,1,1,0). attackDamage(Queen,Attack,30). action(Queen,Transport,24). supplyUnit(Dynamo). action(Dynamo,Move,3). moveSpeed(Dynamo,1). action(Dynamo,Attack,10). attackDistance(Dynamo,1,1,0). attackDamage(Dynamo,30). action(Dynamo,Transport,24). action(Dynamo,Disrupt,7). disruptDistance(Dynamo, 2). action(Worker,Move,6). moveSpeed(Worker,2). action(Worker,Attack,13). attackDistance(Worker,Attack,1,1,0). attackDamage(Worker,Attack,61). action(Worker,Tunnel,6). action(Warrior,Move,3). moveSpeed(Warrior,1). action(Warrior,Attack,30). attackDistance(Warrior,Attack,2,3,0). attackDamage(Warrior,Attack,75). action(Warrior, StoreEnergy, 21). action(Warrior, ReleaseEnergy, 0). storeEnergyDistance(Warrior, 6). action(Drone,Fly,13). moveSpeed(Drone,4). action(Drone,Attack,14). attackDistance(Drone,Attack,1,1,0). attackDamage(Drone,45). action(Drone, Scare, 20). scareDistance(Drone, 3). action(Inducer,SlugTrail,1). action(Inducer,Move,25). moveSpeed(Inducer,5). action(Inducer,Attack,14). attackDistance(Inducer,Attack,1,1,0). attackDamage(Inducer,Attack,45). action(Inducer,Galvanize,28). perTickDamage(Inducer, SlugTrail, 5). action(Larva,Move,3). moveSpeed(Larva,1). action(Larva,Attack,10). attackDistance(Larva,Attack,1,1,0). attackDamage(Larva,Attack,30). action(Larva,HellJelly,1). action(Vamp,Move,9). moveSpeed(Vamp,2). action(Vamp,Attack,10). attackDistance(Vamp,Attack,1,1,0). attackDamage(Vamp,Attack,30). action(Vamp, TempTeleport, 26). tempTeleport(Vamp, 6, -1). action(Vamp, DrainEnergy, 27). action(Vamp, ReleaseEnergy, 0). drainEnergyDistance(Vamp, 3). action(Maxwell,Move,3). moveSpeed(Maxwell,1). action(Maxwell,Artillery,42). attackDistance(Maxwell,Artillery,1,6,1). attackOdds(Maxwell,Artillery,0.2). attackHitDamage(Maxwell,Artillery,61). action(Bender,Move,8). moveSpeed(Bender,2). action(Bender,Attack,10). attackDistance(Bender,Attack,1,1,0). attackDamage(Bender,Attack,30). action(Bender, SpaceBend, 13). spaceBendDistance(Bender, 2). initialLife(Worker, 66). initialLife(Warrior, 100). initialLife(Queen, 53). initialLife(Drone, 53). initialLife(Larva, 33). initialLife(Maxwell, 100). initialLife(Bender, 53). initialLife(Vamp, 53). initialLife(Inducer, 66). /* Created once and cached: The tiles in the current map (this one is a simple map that is a 8x8 grid) */ tile(0,0).tile(1,0).tile(2,0).tile(3,0). tile(4,0).tile(5,0).tile(6,0).tile(7,0). tile(0,1).tile(1,1).tile(2,1).tile(3,1). tile(4,1).tile(5,1).tile(6,1).tile(7,1). tile(0,2).tile(1,2).tile(2,2).tile(3,2). tile(4,2).tile(5,2).tile(6,2).tile(7,2). tile(0,3).tile(1,3).tile(2,3).tile(3,3). tile(4,3).tile(5,3).tile(6,3).tile(7,3). tile(0,4).tile(1,4).tile(2,4).tile(3,4). tile(4,4).tile(5,4).tile(6,4).tile(7,4). tile(0,5).tile(1,5).tile(2,5).tile(3,5). tile(4,5).tile(5,5).tile(6,5).tile(7,5). tile(0,6).tile(1,6).tile(2,6).tile(3,6). tile(4,6).tile(5,6).tile(6,6).tile(7,6). tile(0,7).tile(1,7).tile(2,7).tile(3,7). tile(4,7).tile(5,7).tile(6,7).tile(7,7). startingPosition(Player1,tile(0,0)). startingPosition(Player2,tile(7,7)). /* Created each turn: These are facts that can change turn to turn, things like position of units, etc */ /* There are only three units in this example game. */ energy(Player1,53). energy(Player2,53). unit(Inducer_8-8,Inducer,Player2). at(Inducer_8-8,tile(8,8),0). unitIdle(Inducer_8-8). life(Inducer_8-8,66). attackUnitDamage(Inducer_8-8,Attack,65). slugTrailTiles(Inducer_8-8,5). unit(Worker_8-9,Worker,Player2). at(Worker_8-9,tile(8,9),0). unitIdle(Worker_8-9). life(Worker_8-9,66). attackUnitDamage(Worker_8-9,Attack,81). unit(Queen_9-9,Queen,Player2). at(Queen_9-9,tile(9,9),0). unitIdle(Queen_9-9). life(Queen_9-9,53). teleportUnits(Queen_9-9,0). attackUnitDamage(Queen_9-9,Attack,30).
That’s it! The entire state of the game used by the AI. It was surpisingly small to me at least.
Note that, just like for players, the AI doesn’t get to know about the type and positions of units it can’t see. That’s why you don’t see any Player1 units as facts above – they aren’t visible yet.
Step 2: Write the HTN Axioms, Methods, and Operators you need and use the Facts
This is obviously the bulk of the work. Just like any type of coding, there are a bizillion ways to go about this, but I took the simplest approach I could think of: Teach the AI to play using my own personal best strategy. This clearly limits how good it can get – it’ll play as well as I’d play if I was playing “my perfect game”. This points out a pro and a con of using HTNs: The Pro is that it is easy to make them act “naturally” (i.e. like a human) if you make the rules based on how a human would play. The con is that they will only play as good as that human would play. In reality the HTN does a much better job of checking alternatives than a human would, so in practice it comes up with things that are surpising. But still…
So, here’s how my approach works: The most abstract task, the one at the top of the hierarchy is called
pickStrategy. Here is (some of) the real code from the current build:
pickStrategy(?Player) :- if(), do( // If someone is attacking us now, defend! try(trace(attackSupplyUnitAttackers), dealWithSupplyUnitAttackers(?Player)), // If we can knock out the enemy now or in one turn, do it! try(trace(attackSupplyUnit), attackSupplyUnit2(?Player)), try(trace(moveInOneTurnToFinalAttack), moveInOneTurnToFinalAttack(?Player)), // Otherwise, defend ourselves against near term threats try(trace(attackAlmostSupplyUnitAttackers), attackAlmostSupplyUnitAttackers2(?Player)), ... etc ... ).
pickStrategy has no criteria so that all the tasks will execute. The tasks are all surrounded by
try() which is a built-in directive that makes the engine attempt to execute that rule but ignore it and continue if it fails. This is how I dealt with the fact that you have limited energy in Exospecies: spend maximum energy on highest priority stuff first and then keep trying other things with anything that remains. The try() clauses allow you to keep trying lower priority things once you are close to running out in case there is something cheap, but lower priority, that you can still do.
I’ve also used the
trace operator inside of each
try. That operator is included in the Solution but ignored by the engine. The traces tell me why the AI did something. As an example, here’s part of a Solution given by the HTN for a game turn that I ran recently (comments added by me):
// First, defend the supply unit: don't move the Inducer, it is in the right place trace(defendSupplyUnit), lockMove(Inducer_6-5), // Next, Transport new units in: Do this with the Queen on position 6,6 trace(transportAll), transport(Queen_6-6, Player2, 52, 28), // Then, Find the enemy: move the Warrior at 5,5 from 5,5 to 0,0 using the Move command trace(findAllEnemySupplyUnit), move2(Warrior_5-5, tile(5,5), tile(0,0), Move, 0, Player2, 28, 25) ...etc...
You can see how the
trace operators let me know why the AI is doing what it is doing. It is also the basis for the hint system I alluded to above. It would be simple to translate each
trace into a description when the user asks for a turn hint.
That’s the highest level of the hierarchy. What happens next? Let’s go through a juicy example Method that is a Subtask in many places called
moveClosestAttackerToAttackTile. If our supply unit is about to be attacked, or someone is blocking us and we can’t attack them, or for any number of other reasons, we will execute this task.
The interesting Methods below will be explained in detail later. If you know SQL, think of this just like a big SQL Query:
moveClosestAttackerToAttackTile(?Player, ?TargetUnitType, ?TargetTile, ?TargetUnitHeight) :- if( // sortBy is a built-in rule that sorts all the attackers found // by a value (?DistanceToAttackRange), smallest to largest (<) // Thus, we'll try the closest ones first sortBy(?DistanceToAttackRange, <( // This is just standard Prolog: get all the units for ?Player, // their type, position, etc. unit() and at() are facts. unit(?Unit, ?UnitType, ?Player), at(?Unit, ?UnitTile, ?UnitHeight), // Only move non-supply units. supplyUnit() is a fact. not(supplyUnit(?UnitType)), // Get the name of the other player so we can use it later. This is a simple rule. otherPlayer(?Player, ?DefenderPlayer), // Only move units that *cannot* already attack this tile // with any attack they have. We don't want to move units that can // already attack. attackDamage defines who can attack whom not(attackDamage(?Player, ?UnitType, ?NotAttackName, ?UnitTile, ?UnitHeight, ?DefenderPlayer, ?TargetUnitType, ?TargetTile, ?TargetUnitHeight, ?Damage)), // Returns the closest tile (?ClosestTile) that // puts ?Unit in attack range of ?TargetTile // given the attack specified, etc closestTileThatPutsUnitInAttackRange(?Unit, ?AttackName, ?TargetUnitType, ?TargetTile, ?TargetUnitHeight, ?ClosestTile), // Finally, do pathfinding to that tile which avoids poison, etc // And return the best place to move in ?SafeMoveTo given all that findSafePathAnyAction(?Unit, ?ClosestTile, ?MoveAction, ?SafeMoveTo, ?NextTile, ?DistanceToAttackRange) )) ), // Here we execute the moveCheck Subtask for any units that meet all that criteria do( moveCheck(?Unit, ?SafeMoveTo, ?MoveAction) ).
There is a lot to describe here, but let’s start by noticing that a lot of the criteria is just looking up facts. The only Axioms called are:
- otherPlayer (trivial so we won’t go into it)
And there is only one subtask:
Let’s go through all 5 to understand how it works together.
attackDamage task is a workhorse of the AI. It is where I taught the AI about all the different attacks that are available. For each type of attack I wrote an alternative
attackDamage Method that determines if that attack can be used (i.e. can this unit do this attack? Is the attack in range? etc) and, if so, returns the damage that attack can do. If not, it fails. Using this approach
attackDamage fulfills two roles: It will tell you if unit X can attack unit Y by succeeding or failing and it will give you the damage done.
This is key: All the complexity of the different attacks (like Inducer being able to Galvanize a set of tiles that electrocute anything on them) is hidden in the implementation of these tasks, of which there are many. Callers just ask “Can X attack Y” and the right thing happens.
Here’s the real code for the simplest variant from the build, including a couple of Axioms it uses:
// Here's the simplest variant that is true for all units // that have a classic Attack action that just does damage // at some distance attackDamage(?AttackerPlayer, ?AttackerType, ?AttackName, ?AttackerTile, ?AttackerHeight, ?DefenderPlayer, ?DefenderType, ?DefenderTile, ?DefenderHeight, ?Damage) :- // Only applies when the ?AttackName is "Attack" =(?AttackName, Attack), // Make sure the attack is in range given the unit (see Axiom below) unitInRange(?AttackerPlayer, ?AttackerType, ?AttackerTile, ?AttackerHeight, ?DefenderPlayer, ?DefenderType, ?DefenderTile, ?DefenderHeight, ?AttackName), // This is just a fact that is looked up attackDamage(?AttackerType, ?AttackName, ?Damage). unitInRange(?AttackerPlayer, ?AttackerType, ?AttackerPosition, ?AttackerHeight, ?DefenderPlayer, ?DefenderType, ?DefenderPosition, ?DefenderHeight, ?AttackName) :- // Get all the tiles that put us in attack range of ?DefenderPosition // (see below) tilesInRangeOfTiles(?AttackerPlayer, ?AttackerType, ?AttackName, ?DefenderPosition, ?Tile), // Then see if any is the one we're on =(?AttackerPosition, ?Tile). tilesInRangeOfTiles(?Player, ?UnitType, ?AttackName, ?TargetTile, ?Tile) :- // This is just a fact attackDistance(?UnitType, ?AttackName, ?MinDistance, ?MaxDistance, ?AttackRadius), // This is a simple rule that returns all the tiles // in a square of radius ?MinDistance to ?MaxDistance // around ?TargetTile square(?TargetTile, ?MinDistance, ?MaxDistance, ?Tile).
There is a version of the
attackDamage Method for each attack any of the units can do.
Next up is
closestTileThatPutsUnitInAttackRange. No new axioms are required for this, it just uses the ones described above. Again, code is straight from the build:
// Returns closest unoccupied tile that puts a unit in attack range of ?TargetTile // with any attack Will only return the single best ?AttackName and the // ?ClosestTile that goes with it closestTileThatPutsUnitInAttackRange2(?Unit, ?AttackName, ?TargetUnitType, ?TargetTile, ?TargetUnitHeight, ?ClosestTile) :- // This is just standard Prolog: get all the units for ?Player // their type, position, etc. unit() and at() are just facts. unit(?Unit, ?UnitType, ?Player), at(?Unit, ?UnitPosition, ?UnitHeight), // Just return the first, closest tile first(sortBy(?SortValue, <( // Get all tiles in range for attacks (described in the previous section) tilesInRangeOfTiles(?Unit, ?AttackName, ?TargetTile, ?ClosestTile), // Axiom that estimates distance just for performance, Trivial straight line math distance(?UnitPosition, ?ClosestTile, ?DistanceToTile), // Make sure nobody is on that tile (but ourselves is OK). // Just checking facts not(at(?BlockingUnit, ?ClosestTile, ?BlockingHeight), \\==(?BlockingUnit, ?Unit)), // Trivial Axiom that just returns Player2 if ?Player is Player1 // and vice versa otherPlayer(?Player, ?DefenderPlayer), // See if this unit can attack, and if so // get the damage that will theoretically be done // Calls the attackDamage Method described above attackDamage(?Player, ?UnitType, ?AttackName, ?ClosestTile, ?UnitHeight, ?DefenderPlayer, ?TargetUnitType, ?TargetTile, ?TargetUnitHeight, ?Damage), // Put a pair of values in ?SortValue so we sort by both: // Sort by best distance, then by best attack if attacks have the same distance =(?SortValue, value(?DistanceToTile, ?Damage)) ))).
So, this Axiom:
- Starts by getting the position of
- Gets ALL the tiles that would put
?Unitin attack range of
?TargetTilefor any attack it can do (unless one is passed in, then just for that one). So now, we have a potentially large list of tiles!
- Gets rid of any of those tiles that has a unit on it because we couldn’t move there
- Gets the damage that each attack/tile pair will do using
- Sorts by how far away the tile is (
?DistanceToTile), and then by damage done (
?Damage) so that we’ll always pick the higher damage attack if there are multiple at the shortest distance
- Grabs the first, shortest attack using
- Returns the
Yes, this Method goes through a lot of alternatives, but I’ve found in practice that the engine is very efficient at it. That’s what it is good at.
The final Axiom is
findSafePathAnyAction. The magic here is that there are alternative versions since some units can move in different ways (like teleporting instantaneously). I’ll just describe the simplest one here which basically says “If this unit has a classic Move action, call the built in C++ function called
findSafePath to figure out which is the safest tile to go to”. Not all that interesting.
findSafePathAnyAction(?Unit, ?DestinationTile, ?MoveAction, ?SafeDestinationTile, ?NextTile, ?PathTileCount) :- // There are alternative Methods for different kinds of move, this just handles the // simplest Move action that most units have. Check to make sure unit(?Unit, ?UnitType, ?Player), =(?MoveAction, Move), action(?UnitType, ?MoveAction, ?Cost), // OK, this is kind of a cheat :-) findSafePath() is a built in C++ function, it was // just simpler to build that way... findSafePath(?Unit, ?DestinationTile, ?SafeDestinationTile, ?NextTile, ?PathTileCount).
If the full criteria for
moveClosestAttackerToAttackTile is met, a single Subtask is executed called
moveClosestAttackerToAttackTile(?Player, ?TargetUnitType, ?TargetTile, ?TargetUnitHeight) :- if( // sortBy is a built-in rule that sorts all the attackers found // by a value (DistanceToAttackRange), smallest to largest (<) // Thus we'll try the closest ones first sortBy(?DistanceToAttackRange, <( // This is just standard Prolog: get all the units for ?Player (an argument // to this Method), their type, position, etc. unit() and at() are facts. unit(?Unit, ?UnitType, ?Player), at(?Unit, ?UnitTile, ?UnitHeight), ...etc...full text earlier in this post... )) ), // Here we execute the moveCheck Subtask for any units that meet all that criteria do( moveCheck(?Unit, ?SafeMoveTo, ?MoveAction) ).
moveCheck is designed to be the lowest level Method for movement that gets executed as a Subtask in many different places. The goal is for it to do “whatever it takes” to move a unit from one place to another and fail if it can’t. It is another “workhorse” Method that has 7 different alternatives in the current build. The alternatives are designed to handle all the interesting cases like:
- A friendly unit is blocking the move (so, instead, execute a subtask that moves the friendly unit)
- An enemy unit is blocking the move (so, instead, attack it if we can)
- An enemy unit is blocking the move and we can’t attack it (so, instead, attack it with someone else) etc.
Here’s the alternative that executes if the unit can simply move without anything blocking:
moveCheck(?Unit, ?ToTile, ?MoveAction) :- if( // Simple axiom that ensures the unit has the energy available and isn't already // doing something else canPerformMove(?Unit, ?MoveAction, ?Player, ?Energy, ?NewEnergy), // A fact that gets the location at(?Unit, ?FromTile, ?UnitHeight), // Make sure we're not being blocked by a friendly. // If so, another version of this Method will be used not(friendlyUnitBlockingNextTile2(?Unit, ?ToTile, ?MoveAction, ?BlockingUnit)), // Make sure there isn't an enemy blocking us. If so, another Method will // be used not(enemyUnitBlockingPathNextTile2(?Unit, ?ToTile, ?MoveAction, ?BlockingUnit)), // Finally, pick a good target tile that avoids any poison, etc if possible safePathDestination(?Unit, ?ToTile, ?SafeToTile) ), // Call an operator to actually do the move do( move(?Unit, ?FromTile, ?SafeToTile, ?MoveAction, ?UnitHeight, ?Player, ?Energy, ?NewEnergy) ).
The only significant Axioms here are:
safePathDestination. All of these call out to C++ code since they involve pathfinding and it was much easier to reuse the code the game uses for pathfinding than to reimplement it in Prolog.
move is an Operator, so no further hierarchy gets run, we finally have the solution (for this part)!
Step 3: Convert the Operators that get generated into changes, moves, or whatever makes sense in your app
The Solution to an HTN is an ordered list of Operators. So, Exospecies just needs to interpret the Operators and do whatever they say to do.
Here is an actual Solution generated by the AI for a recent game:
trace(defendSupplyUnit), lockMove(Inducer_6-5), trace(transportAll), transport(Queen_6-6, Player2, 52, 28), trace(findAllEnemySupplyUnit), move2(Warrior_5-5, tile(5,5), tile(0,0), Move, 0, Player2, 28, 25)
Each of the top level terms like
transport() are Operators. Exospecies simply loops through each one and “does the right thing”:
trace()is ignored since it is just for debugging
lockMove()is also ignored since it is just a way for the AI to tell itself not to try moving that unit anywhere else
transport()is like clicking on the Transport action on a unit’s menu, which is just a C++ method call
As you can see, the output of the HTN is a set of Operators that should be very simple to translate into “real game actions”. That is basically the definition of an Operator!
Above you got to see some real-life HTN code running in production for the Exospecies AI. It was about 6 Tasks/Axioms/Operators and there are 112 in the full AI. So, yeah, there are a lot of things to write. To give you an idea of scope: Then entire Exospecies AI was about 850 “lines of code” ignoring comments, where a line of code is anything with a carriage return in it and it is all formatted like the above examples. Using this methodology, the
moveClosestAttackerToAttackTile Method above is 12 “lines of code”.
Here are the original goals I set for myself when I started out:
- Fun to play against for beginning and experienced players
- Beatable but not predictable (beatable in at least some modes)
- Easy to implement and maintain (Ha!)
- Ideally non-cheating
I believe the resulting Exospecies AI is challenging, feels natural, does very few “dumb moves” and doesn’t cheat. I call it a success from that standpoint. I do think the code will be easy to maintain, and (after I built the Prolog and HTN engines!), writing the HTN rules was…well…relatively easy to implement. Compared to writing the C++ code by hand at least. I’m going to call that part a success too.
See for yourself by installing the game and trying it out! Visit the Exospecies site for more details!