[This is the next post in a series on building an AI to play Exospecies. Here’s the previous post.]
We are going bottom’s up on the architecture for the HTN Planner in this series of posts. The previous post described the
All the code to use the Inductor Prolog Engine and run the examples is available on Github.
Prolog is part of the Inductor HTN Engine because “the literature” described HTN’s in terms of first order logic and use rules and facts in much the same way as Prolog does. Seemed like the obvious route to take. It meets the requirements for implementing an HTN very nicely.
If you are trying to build an “AI Planner” that isn’t specific to a domain, you need a way to represent the state of the world that can cover just about anything. Turns out Prolog is perfect for this. A Prolog program is just a database of facts and logical rules about the facts. You represent your domain as a Prolog database and then ask it questions called “queries”. If you know SQL, it is conceptually very similiar to how SQL databases work: facts would be SQL tables, rules would be SQL queries.
Let’s go through a Prolog crash course and show how it can be used to meet the first requirement for building an HTN from a previous blog post:
1. Represent the current State of the world
Requirement 1: Using Prolog to represent the State of the world
Prolog is all about representing state, this is where it excels. It is a very simple way to represent widely disparate domains because it doesn’t understand what you are modeling at all, it just deals with facts and relationships between them.
Recall the state from our Taxi example from the HTN Overview:
These could be represented in Prolog like this:
Everything in Prolog is a “Term”, and a Term is simply a name (e.g.
might mean “you are happy when the weather is good and you’ve got $100”. Real simple. Each term declares a fact that is true about the world you are modelling. In Prolog, you only describe things that are true in the world, you don’t have to describe all the things that are false (the list would be large).
The magic of Prolog is that it doesn’t care what the facts are - they could be made up words or random letters (they are just meaningless strings to Prolog). You choose what they are based on what is meaningful for you reading and using the program. This makes it very flexible for describing anything.
Prolog Fact Queries
Once you have declared a bunch of facts, you can ask Prolog questions about them using variables (which have capital letters) in place of arguments. For example (
Prolog looked at all the facts I have declared and tried to match them with my query
If we make it a bit more interesting by adding distances to more than one place, we can run more interesting queries:
In this example, we specified one argument (
In addition to simple matching like the above examples, Prolog can do queries like:
The last one in particular is interesting because it uses the same Variable twice and thus only matches names that have the same first and last name.
To run any kind of Query, Prolog performs two steps:
How Unification works is described below.
All of this is done using a concept called Unification. Unification takes two expressions and tries to find a way to assign something to their variables so that they are equal. The result is called a “Substitution” since it tells you what to substitute for what to make both sides equal.
The best write-up I’ve found on Unification are from University of Iowa, Stackoverflow and a summary from a hairy academic chapter on Unification. The gist of it is that you take two sides of an equation and try to figure out what to stick in the variables to make them equal.
So if we have the fact
The general algorithm is this:
This surprisingly simple algorithm is a key part of how Prolog Queries are evaluated.
The truth is that Prolog programs are really lists of “Rules” which are just declarations of things that are true. The “Facts” we’ve been working with so far are just the simplest kind of rule that declare “X is true”. When writing Prolog code, though, this can get unweildy fast.
Think about how to model something like “Walking Distance”. We said in our Taxi example that the best route is walking “if it is nice out and the distance is <= 2km”. How would you declare a bunch of facts that handle this? You could try to list a fact with all possible distances like:
But this is obviously ridiculous. Prolog “Rules” allow us to combine Facts and Variables to easily handle cases like this. Our example would be more succinctly stated as:
The part before the
Note that I’ve used a special Term
If we now ask Prolog this query:
Prolog tells us it is true. It works like this:
(A detailed walkthrough of this is in the next section)
Because of step 4, you can compose rules out of rules. This way of building rules and running queries is the fundamental thing that Prolog does and is a surprisingly powerful way to describe and then ask about things. It is called SLD Resolution (“linear resolution” with a “selection function” for “definite clauses”) (Kowalski and Kuehner 1971).
Note that you can also use Variables with Rules and Prolog will tell you all the answers that would have worked, which is kind of mind-blowing:
Evaluating a Prolog Rule
Let’s go through this step by step to really understand what is going on:
And that is the story of how this query worked. The other two answers are done the same way by continuing down the branches we didn’t explore above:
It is important to remember that Prolog doesn’t actually understand any of the strings like
OK, now we’re in a position to model our entire Taxi example using Prolog Facts and Rules and we’ve fullfilled our first requirement: “Requirement 1: Using Prolog to represent the State of the world”. Here is the state from the Taxi example in my HTN Overview, now written in Prolog:
Rewritten in Prolog:
As a richer example, here is the actual state from the current build of Exospecies. I represent the entire tile-based map simply by declaring that there is a tile at a location like
What Have We Learned?
The thing that was amazing about using Prolog for storing the state for the Exospecies AI was that the startup cost was incredibly low (after I wrote a Prolog compiler…). Prototypes could be written crazy quick since I could just declare things to be true and not have to write a bunch of code to store them, access properties about them, group them into collections, etc. Kind of like creating SQL Databases, I did more thinking and designing than writing, which was refreshing.
Next in the blog series, I’ll be describing how the other 6 requirements were met using the Prolog engine and how it got integrated with the Hierarchical Task Network engine.
Using the Inductor Prolog Engine
All the source for just the Inductor Prolog Engine is available on Github. It is a very lightweight Prolog compiler that can be used standalone, even if you are not building a Hierarchical Task Network. Note that it is not a standards compliant, fully featured Prolog compiler. It implements just what was needed for Exospecies, but is easy to extend. For more details, look through the readme on Github.
In building Exospecies I ended up having a lot of different types of files that needed to be parsed: HTML files, settings files, Prolog files, etc. I went and researched the best tools for parsing (and there are many!) but they all seemed like big black boxes that I was going to spend a lot of time debugging, understanding, learning how to use, etc. I wanted something that was really simple, lightweight, debuggable, etc. Plus, I didn’t think I’d really understand any of them if I didn’t understand how parsers worked in the first place. Thus, the Inductor Parser Engine was born! It is the bottom layer of the Exospecies HTN Architecture:
The code for the parser is available on GitHub. This blog post will describe how to use it.
Creating a Grammar
IndParser is called a PEG Parser, which is a very simple to understand and implement type of Recursive Descent Parser. I chose this approach because the way you express your parser rules is very readable and understandable and it is straightforward to implement.
It is written in C++ so it can be ported across many platforms (PC, Mac, XBox, etc), and uses C++ Templates because I found them to be a very natural way to express grammars.
To create a grammar using IndParser, you write a set of rules that describe what you expect to find in the string you want to parse. For example, if you want to parse name/value pairs like this:
You would declare what you are looking for, in the order you expect it:
Nice and easy! Here’s how you would write the grammar using the built-in IndParse C++ template classes:
You declare a class that will be your rule (we called it
Because this is using C++ Templates, there is some extra goo you have to put in. For example, all of the built in rules normally a first argument that is “the type of thing you are looking for”. Rules like
Parsing Using the Grammar
To actually run the grammar on a string, you call the static
Tuning a Grammar
After you end up walking these trees a bunch, two things become obvious:
The first issue is solved by a concept called “Flattening”. Most rules have a template argument called
To take advantage of Flattening, you have one more step after parsing:
Turns out the default is
So, after running
Much simpler! However, the string
Here’s the updated rule:
Now if we parse and flatten, we get this tree:
Full Example Code
Here’s the full code to create the rule and parse it, getting those two values out:
Creating Multiple Rules
But wait! What if you want settings to contain more than just integers? Something like
That is how you build up a more complex grammar: defining rules and using them within other rules. The parse tree for
or if we parsed
Note that the
It turns out that giving a good parse error is hard since the code can’t tell what you meant to type. However, the IndParser uses a heuristic that seems to work out pretty well: Assume that the error is in the deepest (meaning farthest down the tree) rule that was tried and failed. The idea being that we made the most progress there and so that’s probably where the error occurred.
To make it easy to return meaningful error messages, most of the built-in templates have a
Your grammar needs to consume the entire string or it will fail.
If you tried the above example with the string
I usually have a rule called “document” to lay out the whole structure of a document. In this case it is simple:
So far we’ve been talking about Parsing, which is taking a string of text and turning it into a set of well structured symbols. Compiling is that plus walking through those symbols and turning them into whatever-it-is-that-you-are-trying-to-build. Taking HTML text and turning it into rendering objects, for example. IndParse can’t do that work for you, but it can give you a handy class called…
“All” you need to do is create a grammar, and then write all the code that is custom for your Compile operation. Here’s the simplest possible example using
Turns out you don’t always declare rules properly or rules you declare might give unexpected results. If a rule fails, how do you figure out what went wrong?
While I wish using a normal debugger was more helpful, it really isn’t. The parser engine is running all kinds of rules in various different parts of the tree, backtracking, etc. Turns out it is really hard in practice to set a breakpoint that helps you.
Instead there are the obvious things: break down the rule into smaller pieces, comment things out, etc.
If that doesn’t work, the parser has (very verbose!) tracing you can turn on that will output information about each and every path the parser takes so you can see where things fail. To turn on tracing you just put this line before your
Let’s modify the rule so that it doesn’t allow whitespace and then try to parse something with whitespace with tracing on.
If we then try to parse this string
The structure of the trace output can be a little counterintuitive. You’ll notice it starts out indented, setting out traces from
Now for the “deep” analysis: Starting from the top: You can see the Lexer reading characters one by one. You can also see the
OK, this was an easy one, but you get the idea. Sometimes the only way to debug these is to run the rule and dig through the traces.
Go use the parser to do good in the world! The code for the parser is available on GitHub.
The abstract HTN algorithm can be implemented in a bunch of different ways. We need a way to:
None of these seems like much of a challenge. They could be easily implemented in any language I can think of. So, why do academic researchers mostly end up implementing them in LISP or Prolog and taking a “logic programming” approach to their implementation? Nothing I could find in the literature or online described why this was the case. Some theories:
That final reason led me down the rabbit hole. Logic programming was always something I had meant to investigate and maybe this was a perfect use for it. I decided to make my prototype implementation using this approach and see if there was any benefit.
I’m going to jump way ahead here and outline the finished product and then we’ll come back and go through each piece in turn to understand them and see how they are built.
The AI engine has a bunch of general purpose code that I will be open sourcing eventually to save others the trouble of having to figure it out. It has nothing to do with Exospecies, and for that matter nothing to do with Game AI, it can be used for lots of different applications. It is worth noting that it is all written in C++ so it can be more easily ported to different platforms. While it might sound like a lot of complicated stuff, it turns out the entire engine is not really that much code (1500 lines of C++ for the parser/compiler and 4800 for everything else, excluding blank lines and comments). A huge goal was to keep it simple, debuggable, understandable.
The HTN Planner engine does the work that was described in my previous blog entry about Heirarchical Task Networks. It creates a plan given a set of Methods, Operators and Facts. It also allows for “Axioms”, which are simply helper rules. This engine was modelled very closely on the work done by the [SHOP planner team] (http://www.cs.umd.edu/projects/shop/description.html), and is basically a SHOP planner.
The Prolog Resolver is a simple implementation of the Prolog language that is used for Method resolution, storing facts and for creating Axioms. There are open source Prolog engines out there that I could have used, but they are large code bases and implement all kinds of details required by the full Prolog language. I wanted something that was small, easy to understand, debug and customize. It doesn’t implement all of Prolog (a notable exclusion is functionality for lists), but it has everything I’ve needed for the Exospecies AI and is easy to extend. I found The Art of Prolog to be invaluable when implementing this. This writeup on Unification from the University of Iowa was also key. There is tons of information on the Internet about Prolog, the language, etc. including online Prolog compilers like SWISH that were a huge help.
The Prolog Rule Store is a pretty simple name/value pair store that stores Prolog rules and allows for making changes to them while tracking the differences to keep memory usage down. Because the HTN algorithm (and Prolog) backtracks when it fails, there can be a ton of copies of the Rule Store around with small changes.
The HTN Domain Store really is just a very simple name/value pair store, and it is just there for completeness. It is a tiny amount of code.
Finally, while it is possible to build Prolog and HTN objects like Rules, Methods, etc using code, it is much easier to write them in text, so I needed a parser/compiler that converts text into objects in the stores. I have a simple, template-based parsing engine that I’ve used for this (and lots of other Exospecies parsing tasks)
To actually use the engine for any purpose, you’ve got to do a few things:
The next many blog entries will walk through how these different pieces work and interrelate and how they are implemented. I’ll be sharing the code for the engine when I get a chance to clean it up.
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:
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…
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:
The algorithm itself is pretty simple. You start with a Task or Goal list like
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:
Note a few things about this HTN model:
Now let’s do the algorithm:
We found two
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:
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.
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:
And they have some downsides:
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.
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.
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.
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.
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:
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:
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:
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:
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.
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?).
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.
In chess, players take turns moving their pieces. In Exospecies, both players take a turn and the result of the turn is then calculated.
There are a few characteristics shared between chess and Exospecies:
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.
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…
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.
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:
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?
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.
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.
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:
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).
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!