Building Exospecies AI: Problem Statement
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:
- The board can be bigger
- Players can have more units than chess
- 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.