Searching for the best strategy

How to use automated planning to play a Warhammer 40k game

Photo by Maarten van den Heuvel on Unsplash

Hello!

In older posts we have seen how to solve a problem of selection, using different Computer Science techniques. Today, I would like to start a new series of posts using a different Artificial Intelligence technique to play a game, in this case as you know, we focus on Warhammer 40K. Since this is a very large subject, I wanted to divide it in several posts. The idea is to first introduce a bit of theory today (but don’t worry!), and in future posts show some experiments to illustrate this approach.

So let us begin by first describing the problem we will be tackling in the next posts, and then we will introduce an Artificial Intelligence technique called Automated Planning. To see what is special about this technique, imagine a problem where you have all the information about the environment, or a game where you know all the rules. Instead of relying in experiences or past games to make the agent learn, you can use these rules to create a good agent able to play the game. These are good examples for a technique we are going to study today, called Automated Planning which is one of the most classics AI techniques.

Warhammer 40K as a problem

Warhammer 40K is a wargame, a board game where a war between two or more players is simulated. Instead of abstract thinking and resource managing like most of board games, here war is represented more realistically. Each band has an army and some objectives and the goal is to hold objectives while killing all the units of the opponent. There are a lot of strategic decisions to be made and, as we will see, that is an excellent reason to use a wargame as an example for Artificial Intelligence. Warhammer 40k is a science fiction wargame set in a distant future (circa year 40000, hence the 40k). The rules I will be considering are the 8ed. (currently there is a 9ed. released in the middle of the pandemic, but I haven’t had access yet…), and are quite easy to understand, so I will show you an overview of them. Notice that we will be focusing on how to automate these rules, and not on how to learn to play. There are excellent resources online, and the core rules are for free (see link here).

As explained above, the goal of a game of W40k is to win a battle, by scoring points. These points can be earned by holding objectives, or killing enemy units. Each player alternates in turns, and each turn has a set of ordered phases:

Phases in a turn of Warhammer 40K

1. In the movement phase, a player moves his troops up to a distance indicated by the type of the unit. Aditionally, the player may move a bit more by choosing to advance, but this may affect later phases.
2. In the psychic phase only units marked with a tag: <PSYKER> can be played. These units are able to do special actions like buffs, extra damage, and so on.
3. Shooting phase is a straightforward phase. You shoot enemy units.
4. After shooting, you can declare a charge, that consist in running forward your enemy with melee weapons. Enemy units are allowed to shoot you back.
5. When units are in contact, they can fight with melee weapons in the fight phase.
6. After the wounds are counted, units must pass a courage test in the morale phase. If they fail this test, they flee in terror.

With the rules explained above, can we design an intelligent agent that is able to command an army of models to victory?

Automated Planning

As some people know, artificial intelligence is the study of rational agents. An agent is something that acts, and in this case, it also reasons about the state of the world it is in. It seems reasonable that any intelligent agent is able to make plans to act. These plans are made by anticipating the effect of the actions that an agent can make in the environment. Roughly speaking, the agent starts in an initial configuration of the environment, the initial state, and modifies the environment until it reaches a defined state, called goal state.

Agent located in an environment

Environment is represented by states. Each state represents a configuration of the world, for example in W40K it can represent the number of units exist in an army, the number of soldiers in each unit, the type and number of weapons, and it can also represent the distance to each enemy, or the disposition of the obstacles in the terrain. Everything can be represented in variables, that can be boolean of multi-valued. As an example, consider the following state of a unit:

; Boolean representation
State=[
  5_men_unit,
  3_bolters,
  2_blight_launchers,
  enemy_in_range
]

In that (small) representation we can see that we have a 5 men unit, using 3 bolters and 2 blight launchers (special weapons), and an enemy unit in range. The same representation in multi-valued variables can be:

; Multivalued representation
State={
  unit_size=5,
  bolters=3,
  blight_launchers=2,
  enemy_distance=8
}

Each representation has its advantages and disadvantages, and usually planning work with one or the other. In this example we will use the boolean representation because it can be easier to understand. In the boolean representation, a state can be seen as a list of propositions. This is called the Closed World Assumption, that states that everything that is true, must be represented in the state, and everything else is assumed to be false.

Two special states are important for a planning problem. The initial state, and the goal state (or goal conditions). The initial state is the configuration of the world at the start of the problem. And the goal state is the desired state. Instead of describing the whole goal state, it is possible to describe the conditions that must hold in a goal state.

An action can be applied whenever its preconditions meets, and it has effects that can change the world. Using the boolean representation we can represent an action as three lists, a list of preconditions, an add list and a delete list:

1. Precondition list: a list of propositions that must be true before applying the action;
2. add list: a list of propositions that become true after executing the action, that is, must be added to the state;
3. delete list: a list of proposition that become false, i.e. must be removed from the state.

For example, consider the following example of an action of shooting (for simplicity we will not explain the rules of shooting in W40K here):

action shoot():
  preconditions: enemy_in_range
  add: enemy_wounded, 4_men_unit
  delete: 5_men_unit

This action is only an example, but let us see how it works. First, it will check first if the enemy is in range. If this condition holds, then it will add the proposition representing that the enemy is wounded and the proposition indicating that one man of the unit fell, and will delete the proposition indicating that the unit had 5 men.

Planning can be done in an offline or online way. In offline planning, it will explore all possible actions starting from the initial state, applying them while exploring all the state space, i.e. all possible states, anticipating the results for all actions until a goal is reached, and will return a plan, that is a sequence of actions that are ready to be executed by an agent and anticipates all outcomes.

Dr. Strange using offline planning to solve a universal problem.

On the other hand, the online planning will produce a plan also by searching in the state space usually considering less states and a simplified version of the problem. This plan will be executed by the agent until some action is not possible to execute, because its preconditions do not hold, so the agent must resort to online planning again, considering the state where it stopped as the initial state.

Usually offline planning is really difficult to implement because of the size of the problem. To produce a full plan, that will work in all states, the planner must consider a lot of different aspects. Online planning can be more forgiving, by producing a plan that can be followed until a certain point, and then, the agent can re-plan with new information not considered before.

Conclusions

I presented here in this post the basics for automated planning. In this series of posts we will explore how to use planners to play Warhammer. In the next post, we will see how Automated Planners work, and how they use search algorithms. We will be considering the state of the art planners, but we will look at some of the most important planners in the area, and will also start formulating Warhammer 40K as a planning problem, and will use planners to play a game either real or simulated.

Stay safe!