[This is the next post in a series on building an AI to play Exospecies. Here’s the previous post.]

I got all wrapped up in trying to write the blog post for my survey of AI algorithms, how I classified them, etc. and even I got bored. So, I’m switching to the topic I actually wanted to write about: Hierarchical Task Networks (HTNs, sometimes called HTN Planners).

I used them in the first Exospecies AI prototype. I started there for a few reasons: It is a proven algorithm that had already been used in published games, it builds an AI that behaves like a human, and it appeared to be one of the fastest algorithms due to its hierarchical, depth-first, human-scripted approach.

Turns out there’s lots of information out there on HTNs but I couldn’t find enough to understand them to the level where I could build one from scratch. I also didn’t find any good examples of using one for strategy game AI. The next few posts will try to correct that. I may come back to writing up the survey once I get some distance from it.

What I did find was two buckets of stuff on the Internet:

• Bucket 1 was a bunch of PhD theses and college-level AI coursework about HTNs that was quite theoretical. The best I found were:
  https://drum.lib.umd.edu/handle/1903/5810
  https://arxiv.org/abs/1403.7426
  http://www.ai.sri.com/~sipe/
  http://www.cs.umd.edu/projects/shop/description.html
  http://www.cs.umd.edu/~nau/papers/nau2000shop.pdf
  http://pages.mtu.edu/~nilufer/classes/cs5811/2014-fall/lecture-slides/cs5811-ch11b-htn.pdf
• Bucket 2 was some very practical how-to information. It was tough to find a concrete example here. The best I found was:
  http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter12_Exploring_HTN_Planners_through_Example.pdf

The confusing part was that, if you digest the Bucket 2 stuff, HTNs seem like a relatively simple tool (along the lines of state machines) for helping you to organize a giant script that just tells the system what to do. I guess I was expecting something more magical here. So, I figured something must have gotten lost in translation from the really theoretical proofs, logic and scientific sounding stuff in the “literature”. I dug deep into that and I think I understand it now. Let me take you on the journey…

HTN Overview

In broad strokes, an HTN solves a problem using a very human planning approach that centers on abstraction and alternatives.

Alternatives: Let’s use a travel example from the famous SHOP HTN Planner. Imagine you asked me how to get from downtown to the park. I might say, “Well, it is 2Km away but, if it is nice out, I would just walk it. However, if it is raining and you’ve got taxi fare, I’d take the taxi. Otherwise, if you have bus fare, just take a bus.” A abstract thing you accomplish like “travelling from one place to another” is known in HTNs as a “Task”. The 3 alternatives I gave for accomplishing it are known as “Methods” in HTNs. Note that each Method had a “Condition” that went with it: walk if it is nice out, take a taxi if you have the fare, etc.

Abstraction: Note that these 3 Methods are at a pretty high level of abstraction. You might further ask me how to accomplish the “TakeABus” Method. I’d say something like, “Well, wait for the #1 bus at the ‘Downtown’ bus stop, pay the driver $1, and ride it to the ‘Park’ stop.”. These three tasks are known in HTNs as “Subtasks” of the “TakeABus” Method. In HTNs, Methods do what they do by decomposing into Subtasks. Now, this is a pretty complete answer for a human but maybe not if we were talking to a robot. In that case we might need to further decompose the task of “PayTheDriver$1” into something like “Reach into your pocket, grab a $1 bill, hand to driver”. Each of those could further be decomposed until we finally have something a robot could do. The final step of an HTN, the part that actually gets done, is called an “Operator”. How detailed you need to get before you are done (and have an Operator) depends on the kind of system you are building. A big part of designing an HTN model is getting your head around what the right abstractions are.

So, HTNs have these parts:

• State of the world: You are downtown. Taxi fare is $2. Bus fare is $1. Distance from downtown to park is 2Km.
• Tasks: What can be done abstractly in the world (there may be several ways to do it!): Travel from A to B. Walk from A to B. Pay a Driver X$. Wait for bus A at stop B.
• Operators: How to accomplish abstract Tasks when they can “just be done” without further explanation. They actually modify the State of the world. If you are human these might be Operators: Pay the driver $1, Ride #1 bus to the 'Park' stop. If you are a robot, these might be: Move stepper motor forward by 100 steps, turn on spotlight
• Methods: How to accomplish abstract Tasks when they involve several steps or more detailed plans. They have a Condition for when they can be used and a set of Subtasks for how to accomplish them: METHOD: "Travel from A to B" CONDITION: the weather is bad and you have bus fare, SUBTASKS: Wait for the bus at the bus stop, pay the driver, and ride it to the stop

The algorithm itself is pretty simple. You start with a Task or Goal list like Go from downtown to the park and an empty Plan list:

1. Remove and start with the first goal in the Goal List
2. See if there is an Operator that knows how to do it. If so, add the Operator to the end of the Plan List (since Operators can “just be done”) and continue at #1
3. See if there are Methods that know how to do it. If so, add their Subtasks to the front of our Goal List and continue at #1
   If there are multiple Methods, duplicate the current state of the world and run the algorithm with each, independently. Each that completes successfully will be a different solution
4. Repeat until the Goal List is empty
5. When done, what you have in the Plan List is the solution

An Example

Let’s see how the above travel example would work more formally. I’ve made up a little pseudo-computer-language just to help with the example. It is described as it is used:

State: State can be looked up using syntax like State[ThingYouWantToLookup] and is modified using State.Add() and State.Remove()

Location: downtown. 
Weather: good.
Cash: $12.
TaxiFare: $2. 
DistanceFrom(Downtown,Park): 2Km. 
TaxiLocation(Taxi1) : TaxiBase.

Operators: Anything that has a ? in front of it is a variable that works just like you’d expect

Walk(?From, ?To) : 
   State.Remove(Location, ?From), 
   State.Add(Location, ?To)
Ride(?From, ?To) : 
   State.Remove(Location, ?From), 
   State.Add(Location, ?To)
HailTaxi(?Location) : 
   State.Remove(TaxiLocation(Taxi1), TaxiBase), 
   State.Add(TaxiLocation, ?Location)
SetCash(?Old, ?New) : 
   State.Remove(Cash, ?Old), 
   State.Add(Cash, ?New)

Methods: Conditions are just English expressions that should be self explanatory

TravelTo(?X) :  
   CONDITION: 
      State[Weather] is good and 
      DistanceFrom(State[Location], ?X) < 3
   SUBTASKS: 
      Walk(State[Location], ?X)
TravelTo(?X) :  
   CONDITION: 
      State[YourCash] >= State[TaxiFare] and 
      State[TaxiLocation(Taxi1)] = Taxi Base
   SUBTASKS:  
      HailTaxi(State[Location]), 
         Ride(State[Location], ?X), 
      PayDriver(State[TaxiFare])
PayDriver(?Amount) :    
   CONDITION: 
      if ?Amount <= State[Cash]
   SUBTASKS: 
      SetCash(State[Cash], State[Cash] - ?Amount)

Note a few things about this HTN model:

• There are no “Abstract Tasks” listed anywhere. This might be confusing since they are supposedly part of the HTN model. Task names are just the union of all the Operator and Method names: Walk, Ride, HailTaxi, SetCash, TravelTo, PayDriver, etc.
• There are two Methods (i.e. ways) to travel to a place, but they have different times (i.e. Conditions) when they are appropriate. This is a key feature of an HTN model.
• Even though it seems like a “toy example”, HTN models tend to be very concise. The entire AI for my strategy game is almost finished at 350 lines and over half of those are comments.
• You may think it is totally bogus to make “Walk from A to B” as simple as changing some string called “Location” in the state. Think about it like this: HTNs allow you to build a simplified model of what you are working on and operate on it in an abstract way. The State is there to make sure your Tasks are doing things that are legal in your “real world”. You will probably ignore the State when it is done and only pay attention to the Operators, which you will map to functions in your “real” code, which have real effects on your real game.

Now let’s do the algorithm:

Start with the State, Operators and Methods above, a Goal List: TravelTo(Park), and an empty Plan List

1. Remove and Start with the first (and only) goal TravelTo(Park) in the Goal List TravelTo(Park)
2. There are no Operators called TravelTo
3. There are two Methods called TravelTo, thus we might have more than one solution. Let’s go through the first one first:
   The Condition State[Weather] is good and DistanceFrom(State[Location], ?X) < 3 is true in the current state
   Therefore: Add its Subtasks to the Goal List after substituting variables: Walk(downtown, park)
4. Remove and Start with the first goal Walk(downtown, park) from the new goal list: Walk(downtown, park)
5. There is a Walk(?From, ?To) Operator
   Fill in variables and add it to the Plan List, which is now: Walk(downtown, park)
   Allow it to modify the State in case we keep going. Changes Location: downtown to Location: park
6. There are no more goals so the Plan is Walk(downtown, park)

We found two TravelTo methods that might be applicable above. So, we need to run the algorithm on the other option too if it is valid:

The Condition State[YourCash] >= State[TaxiFare] and State[TaxiLocation(Taxi1)] = Taxi Base is also true
Therefore: Add its Subtasks to the Goal List after substituting variables: HailTaxi(downtown), Ride(downtown, park), PayDriver(2$)

1. Remove and Start with the first goal HailTaxi(downtown) in the new Goal List HailTaxi(downtown), Ride(downtown, park), PayDriver(2$)
2. There is a HailTaxi(?Location) Operator
   Fill in variables and add it to the Plan List which is now: HailTaxi(downtown)
   Allow it to modify the state in case we keep going: changes TaxiLocation(Taxi1) : Taxi Base. to TaxiLocation(Taxi1) : downtown
3. Grab the next goal: Ride(downtown, park) in the Goal List Ride(downtown, park), PayDriver(2$)
4. There is a Ride(?From, ?To) Operator
   Fill in variables and add it to the Plan List which is now: HailTaxi(downtown), Ride(downtown, park)
   Allow it to modify the state in case we keep going: changes Location: downtown to Location: park
5. Grab the next goal: PayDriver(2$) in the Goal List PayDriver(2$)
6. There is not an Operator for PayDriver
7. There is a single Method for PayDriver(?Amount)
   The condition ?Amount <= State[Cash] is true in the current state
   Therefore: Add its Subtasks to the Goal List after substituting variables: SetCash(12$, 12$ - $2)
8. Grab the next goal: SetCash(12$, 10$)
9. There is a SetCash(?Old, ?New) Operator
   Fill in variables and add it to the Plan List which is now: HailTaxi(downtown), Ride(downtown, park), SetCash(12$, 10$)
   Allow it to modify the State in case we keep going: changes Cash: $12 to Cash: $10
10. No more goals: We are done.

So, we found two solutions. Depending on what you are doing, you could stop with the first solution and just use it, or generate all of them and somehow evaluate which is the best:

1. Walk(downtown, park)
2. HailTaxi(downtown), Ride(downtown, park), SetCash(12$, 10$)

You can see how the HTN algorithm starts with a high-level goal and breaks it down into more detailed plans until you have a set of Operators that your system can “just do”, ordered in the proper order. This all works because a human has carefully crafted the Methods and Operators to make sense for your problem. In practice, you don’t end up “thinking about the algorithm” so much. Really, you just end up thinking about the base operations your system can do and about how you’d teach someone to do the things you need done.

Final Thoughts

HTNs are a natural way to describe how to solve a planning problem where you start at a high level and refine your way down to a solution. They have some great features:

• Simple to understand and debug
• Methods and Operators are relatively simple to write and understand
• Plans like a human since Tasks are written by humans and not “learned”. This is a great for game AI since users want their opponent to act “naturally”
• Final plan contains an ordered set of Operators that are guaranteed to work (if a solution can be found)

And they have some downsides:

• They won’t produce surprising behavior, which can be good or bad. The system isn’t going to do something it wasn’t told to do.
• You have to know the solutions and encode them. I.e. the AI for Exospecies will only be as good a strategist as I am. Other approaches that explore the whole game tree or learn don’t have this issue (but they have other ones…)

Coming Next

In the future posts I’ll talk about how I actually implemented an HTN and different approaches you could take, as well as how I actually implemented the Exospecies AI as an HTN.

[This is the next post in a series on building an AI to play Exospecies. previous post — next post

Like any design problem, the “best” approach for an AI algorithm depends on what you’re trying to optimize for and the constraints of the problem. So, let’s get some guardrails up by defining the game more formally and listing goals and natural computer advantages. We are going to need all the advantages we can get.

Game Definition

This is meant to be a boring distillation of the game mechanics, not a “pitch” for the game! Implementation of algorithms will be very dependent on the rules of the game, so this is here as a reference you can come back to.

The goal of Exospecies is to find and destroy all of your opponent’s supply units. How is described below.

Mechanics

• Exospecies is a two-player, turn-based (meaning not real-time) game. Players can take as long as they want to take their turn and both players take their turns at the same time.
• It takes place on a map of square “tiles” like chess. Unlike chess, the tiles do not have to be arranged in a square and some tiles can’t be moved over.
• What is on a tile may change over the course of the game. For example, poison or other items can be placed on tiles by units.
• The only objects to manipulate in the game are “units” (i.e. aliens), each of which resides on exactly one tile.
• To manipulate units, players choose from a list of actions such as: move, attack, go underground, etc.
• Different unit types can perform different sets of actions. The actions can get very advanced (e.g. lay down poison, power up other units).
• Each action has an energy cost to activate. There is a total energy budget each turn.
• The energy budget is set by special units called “Supply Units”. Each supply unit on the map adds more energy to a player’s budget.
• A player can only see enemy units when they are “within range”. This is called the “fog of war”.

Gameplay

• A map is chosen for the game which determines the space available for the battle
• Each player chooses the set of units that will be available in the course of the battle (called a “formation”). Each map has a limit for the number of supply units that can be chosen in the formation.
• The game starts with 3 randomly chosen units from each player’s formation placed on the map, far away from each other. Their supply units will always be in this starting set.
• A turn consists of the user choosing what actions they want to perform on the units they currently have, limited by their energy budget.
• When both players have chosen, the game calculates the results of the turn, shows it, and then players take the next turn.
• A player can get additional units on the map by using the “Transport” action on their supply units. This will bring in a randomly selected unit from their formation.
• When a player finds and destroys their opponent’s supply units, they win!

A Word About Exospecies Turns

Exospecies turns are complicated because each represents a period of time that actions occur in. Lots can change in this period of time: units can move into or out of range, go underground, explode and splatter poison, etc. Thinking about how things may play out over the time represented by a turn is key to winning.

Here’s how it works: Once the players have chosen their actions, the Exospecies engine calculates what happened. It does this by breaking down the turn into twenty points in time (“timeslices”) called “ticks”. It then plays out actions over this time period: units move, run into each other, attack, etc. What team gets to go first in any given timeslice alternates for fairness. This matters, for example, when two units are trying to move to the same square in one timeslice.

Formal(ish) Properties

Some types of games have been extensively studied and formalized in the field of Game Theory. Classifying Exospecies using formal terms, when I could find one, will make it easier to evaluate algorithm applicability.

It is tempting to think of Exospecies as just a variant of chess when looking at AI algorithms since chess is a well understood domain for AI with a huge amount of research and solutions available. Unfortunately, there are some big differences:

Non-deterministic

In chess, the results of a move are deterministic: if you move a piece, it moves. There are several places in Exospecies where the result of an action is not:

• Attacks can randomly do between 0 and N damage
• who goes “first” when the results are calculated is effectively random
• Units are randomly teleported in to random locations in a certain region

Hidden information (aka imperfect information)

In chess, each player can see all the state of the game. In Exospecies, there are several places where a player won’t know the entire state of the game:

• A player can’t see opponent’s pieces unless they are in range (“fog of war”)
• Actions a player chose for their turn are hidden from their opponent until they both finish
• The composition of the opponent’s formation is never shown until the units actually teleport in

High complexity (aka huge “game tree”)

If you make a tree with the starting state of a game at the root and each branch representing a possible move, once you’ve finished with all possibilities you’ll have a tree. The bigger the tree, the harder it is to analyze. Chess has a notoriously large game tree. But, in chess, a game piece has only one thing it can do: move. In Exospecies, “move” is one of 4-5 actions any piece can perform. In addition, these actions can be quite involved: modifying the game board, causing explosions, combining with other actions from other units, etc. This makes the tree of potential moves much larger than chess since:

1. The board can be bigger
2. Players can have more units than chess
3. Each unit has many more options than “move”

The number of actions available in a turn is limited by energy, so that prunes off large chunks of the tree. However, considering that you can still do about 4 different actions, selected from a number of alternatives, to chess’ 1 piece/1 action means the potential tree is still substantially larger.

Expensive turn calculation

In chess, a single turn consists of one move and results in a new position for that piece and potentially removing an opponent’s piece. In Exospecies, the turn can involve many units moving for a period of time, interacting during that time, tiles on the map changing, units getting poisoned, etc. The cost of calculating the next state of the game is expensive and often noticeable by humans in the game (you’ve seen the roiling fireball when you end a turn, right?).

Chains of dependency for actions

In chess, a unit move is only constrained by whether tiles are open. In Exospecies, this is also true, but it is also constrained by amount of global energy, which is constrained by what supply units you have and what other units are doing. Actions besides Move can have other dependency chains as well. This makes reasoning about the game more difficult, sometimes a player has to follow dependencies backward to set themselves up to do something in a few turns.

Simultaneous play

In chess, players take turns moving their pieces. In Exospecies, both players take a turn and the result of the turn is then calculated.

Similarities to Chess

There are a few characteristics shared between chess and Exospecies:

• 2 Player
• Zero-Sum: If you lose, I win, and vice versa
• Unlimited turn time: Unlike real-time strategy games, players can take as long as they want to take their turn. This makes part of our AI challenge easier since we have theoretically unlimited time.

Not surprisingly, many of the properties of Exospecies make it very hard for building an AI that plays well. I designed the game to be a rich and deep strategy game for humans, which unfortunately means it will be hard for computers to reason about.

Goals for Exospecies AI

At the outset, not knowing a lot about the solutions that are out there, I wanted to make sure I was clear about the characteristics I wanted in the AI. It’s unclear how many I’ll get, but if you don’t have goals…

• 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

The last point needs some explanation: many (most?) strategy games end up cheating in their AI algorithm because building a winning AI is so hard. It could be anything from knowing things that are supposed to be secret (e.g. the opponent’s base) or getting an advantage in odds (e.g. random damage is always high). Players naturally don’t like AIs that cheat because it feels like, well, cheating.

Computer Natural Advantages

Knowing where the computer has natural advantages will help me build an AI that enhances them when possible. Here’s what I’ve got so far:

• Math: Precisely calculating odds, etc.
• Leveraging combinations: Lots of Exospecies strategy is lighting up combination moves (e.g. when X is Y tiles from a Z it is 2x as powerful). In theory, a computer should be better at finding paths through the game that light these up systematically.
• Cheating: Obviously the computer could cheat, but I’d really like to avoid it

Places to Cheat

OK, I keep talking about cheating, but I really do want to avoid it. However, given how often it is employed by necessity, I feel compelled to think a bit about where the computer could cheat if I absolutely had to?

• Knowing where opponent units are
• Getting what it wants via teleport
• Changing its formation dynamically (since nobody knows each other’s formation)
• Getting better odds on anything that is random (e.g. attack damage)
• Always getting the first move for timeslices

OK, now that I’ve got the problem framed up a bit, my next post will be starting a shallow survey of different approaches. I’ll map them to the points above and filter out a couple of experiments to try.

This is a post in a series on building a computer player for Exospecies. Next Post.

Plan A

Exospecies was always meant to have a computer player (aspirationally called A.I.s in the game business)…eventually. I figured I’d launch with only multiplayer (i.e. human vs. human play) since writing a good computer player for a strategy game is notoriously hard. Really, beyond notoriously hard (witness Google’s Go AI). I don’t have PhD’s on my team and I don’t have one. I was going to need time to write a decent A.I. Plus: people are more interesting to play against, right? So my plan was, launch multiplayer, then build an A.I., then launch that. It gets the game in the market quicker, I get feedback from real humans playing (which will surely be more challenging than people playing computers), and then do the A.I. player when it is clear what strategies are being developed by humans. This plan also gave me the runway I’d need.

Plan B

What I discovered (and was told by basically everyone in the industry, like “Wow, multiplayer only, huh? Gutsy.”) is multiplayer-only games are hard to succeed with. Some reasons:

• There’s not always someone to play with
• In a turn-based game, the other human may not want to play a full game right now, even if you do
• New players may be hesitant to launch right into playing another human
• Some people just want to play on their own

Having a computer player gets rid of a bunch of roadblocks and fills lots of gaps.

What finally pushed me over the edge to slip Exospecies until it had an A.I. was my beta feedback coupled with early reviews. The feedback was essentially: “I want to play the computer to learn, and I want to play the computer when nobody else is around, and you really need a computer player. Really.” It was loud and clear, and it only took me running up to the final launch week and getting some blistering reviews to get it through my skull (more on that later in a postmortem).

The Quest

While there is an enormous amount of information on the Internet and in books about A.I. techniques across the spectrum from pure research to practical use in games, there were plenty of places where I’ve been going down dark holes and having a real challenge figuring out either how algorithms work, how to implement them practically, or even how to understand the academic literature. I thought that writing up a blog might save someone else the anguish later and help me collect my thoughts. I thought it might also be entertaining to see how a naive developer gets slapped around by a really hard problem and then rises above it all in glory! (that’s how I’m hoping this ends).

Follow along as I learn and attempt to explain the amazing world of A.I. as applied to game development!