Designing AI Algorithms For Turn-Based Strategy Games

By Ed Welch

In action games the AI opponent always has the natural advantage: perfect accuracy and lightning fast reflexes, so the challenge in designing the AI for those games is making it act more human and to be beatable.

In turn-based strategy games the tables are turned. Speed and accuracy are no longer important factors and the cunning and intuition of the human player will easily out match any AI opponent. In fact, it's nearly impossible to design a AI that can beat an experienced player, but that is not really the point anyway.

The challenge is to make the AI's attack and defense strategy to appear intelligent and thought out, providing a challenge but letting the player win in the end. Once the player has familiarized himself/herself with the tactics of the AI the game rapidly gets boring, so a certain amount of unpredictability is desirable.

Challenges Involved: Looking At A Typical Strategy Game

The AI design problem is easiest understood by taking a real life example, in this case we take a space based war game.

Our example is what's called a 4X game, where you must expand and dominate the galaxy. Each player has war ships and colony ships and starts with a home planet and can colonize habitable planets.

A first attempt at writing the AI would be a simple algorithm to assign orders to each resource (i.e. a planet, or ship), starting with the most important first. Defending planets with production queues has the highest priority, because they are the most valuable.

The next highest, is defending colonies without production queues, then attacking enemy home planets, then colonizing habitable planets, then attacking enemy ships, then repairing damaged ships and lastly exploring uncharted territory. So, we take the highest priority task first, and check for any enemy ships that are close to our colonies.

As you can see in the image above enemy frigates X & Y threaten both the AI's home world and colony. So, we find the closest warships and assign them to attack. You might see here the flaw here in our algorithm. If by chance, frigate Y is handled first, destroyer A will be assigned because it's the closest. Then, when Frigate X is processed, the only ship left to attack is destroyer B, which is too far away to reach it and Frigate X succeeds in bombing our home planet. It's obvious that Destroyer B should be assigned to Frigate Y and Destroyer A to Frigate X.

Also, other problems can occur with this simple algorithm. Have a look at a more complex scenario:

In this new scenario we have Destroyer A badly damaged from a previous attack. It would be a futile sacrifice sending it into battle again. It's wiser to send it back to the home planet for repair. So, that leaves Destroyers C and B to defend our colonies. But destroyer C is too far away to reach frigate Y in time and would be better served to bomb the enemy colony, seeing as it's so close (not to mention, that fuel conversation is important too). Meanwhile, the AI colonizer is armed, and could be diverted from its primary colonization mission.


The Solution: The Resource Assignment Algorithm

Assignment Scoring

In order to solve the problems detailed above, firstly we design a scoring system. Each task is assigned a general priority as follows:

Defending our colonies: 1
Attacking enemy colonies: 2
colonizing planets: 3
Attacking enemy ships: 4
Repairing damaged ships: 5
Exploring uncharted territory: 6

Each task also has a priority modifier, for instance the defense task gets a modifier for the value of the colony (colonies with production queues get very high modifier). Likewise, the repair task gets a modifier depending on the amount of damage and the colonize task gets a modifier depending on the "habitability" of the planet.

Finally the distance of the assigned ship is taken into account, as follows:

assignment score = (6 - general priority + modifier) / distance to ship that is assigned

Therefore, in the previous scenario destroyer C would get a higher score for attacking the enemy colony, even though the defense task has a higher priority, just because it was so close to the enemy planet.

Also, the priority modifier of the repair task for Destroyer A is quite high because it's so badly damaged. Coupled with that it is close to a repair queue, and that means that it scores higher than the defense task.

Algorithm Outline

The overall algorithm is broken into 4 parts:


Gathering Tasks

The AI has a list of enemy ships and planets within sensor range, as well as a list of its own assets. Tasks that need to be done are generated as follows:

Object present Task generated
Enemy ship near colony Defend colony task
Enemy ship Attack ship task
Enemy colony Attack planet task
habitable planet Colonize planet task
Damaged ship Repair ship task
Uncharted territory Explore task

Possible Assignments

The other part of the problem is that if we assign tasks in the wrong order the resource utilization will not be optimal. This can be resolved by assigning the tasks in phases. We use two special classes to help us: PossibleAssignment and Task. PossibleAssignment links a potential "task doer" (e.g. a ship) with a task and stores the "assignment score". Task stores the priority, priority modifier and objective.


Let's just take a quick look at our class hierarchy to make things clearer:

We generate a PossibleAssignment object for each combination of "task doer" to task. However, we eliminate impossible combinations. For instance, an unarmed ship cannot carry out an attack task, nor can it do a task if it doesn't have enough fuel to reach it. This is how the code looks:

listAsset contains a list of all assets (for instance ships)
for (n = 0; n < listTask.size(); n++)
{
for(f = 0; f < listAsset.size(); f++){
if (listAsset[f].isTaskSuitable(listTask[n])){
listPossAssignment.add(new PossibleAssignment(listTaskn]));
}
}
}

Next, we calculate assignment scoring for each PossibleAssignment and sort the list in order, highest scores first. And finally, in the last stage, we physically make the assignments. Because the list has been sorted, the most effective assignments occur first. Once an assignment is made the task doer is marked as busy and also the task is marked as assigned, preventing double assignments.

Here is part of the code:

for (n = 0; n < listPossAssignment.size();n++)
{

listPossAssignment[n].assign();

}

public void PossibleAssignment::assign()
{

if (task.isAssigned()) return;
possibleTaskDoer.assign(this);
}

public void Ship::assign(PossibleAssignment possAssign) {
if (task != null) return;
task = possAssign.getTask();
possAssign.getTask().assign(
this);
}

Reusing The Algorithm For Planet Production Assignment

The AI should manufacture new star ships if there are any leftover tasks that couldn't be taken care of by the existing fleet. For example, if we have spotted an enemy ship and there are no available warships to attack, then we need to build a new warship. Similarly, if there is a habitable planet and no available colonizers, then we need to build a new colonizer.

In fact, the build priorities for production queues are exactly the same as the task priorities for star ships. As you can see in the class diagram, both the classes Ship and Planet are derived from SpaceObject, so they both can be used in the same algorithm with little modification. This is a good example of code reuse in object oriented design.

The below diagram shows this in action:

Keeping Things Simple: Discarding Old Tasks

As this is a turn based game, at the start of each new turn all the tasks from the last turn become out-of-date. For instance, that enemy frigate that your destroyer was about to attack could suddenly retreat, or you could discover - to your horror - that the planet you were about to colonize has already been occupied by the enemy.

The easiest thing to do is just discard all tasks and call the resource assignment routine at the start of each turn. This may seem inefficient, because not all tasks need to be updated, however it does makes the AI code considerably less complicated, as you don't need to maintain tasks from previous turns.

Keeping the code uncomplicated is especially important in the case of AI algorithms, because these have a tendency grow overly complex very quickly, making debugging and maintenance very difficult. As well as that, all optimization tasks should be done at the final stage, after the algorithm has been completely finished, and then only if there is real evidence that the algorithm is to slow in the first place.

Mid-turn Surprises

During the course of our turn one of our ships may discover a new enemy colony, or ship. We could just assign a new attack task to the ship, but that would cause problems if it already had an existing task that was important. Again, the simplest and most fool-proof thing to do is just run the resource allocation routine again, as this guarantees the most optimal resource assignment.

Conclusion: How Does The Algorithm Work In Real Life?

This AI algorithm was designed during the development of a 4x strategy game (as you may have guessed from the example). In practice one got the impression that there was some sort of real intelligence behind the control of the enemy fleet.

Ships would change tactics unexpectedly. If an enemy ship ran out of ammo, it would suddenly break off battle and go back to base to re-arm. If it didn't have enough fuel to make it to base, then it would try to explore uncharted territory (the only useful task left). As new ships came out of the shipyards, the orders could change for the whole fleet. Some ships would return for repair and leave the fresh warships take up the attack.

Basically the algorithm provides good "bang for buck" ratio, a fairly uncomplicated algorithm that's easy to implement and debug, but yet provides a challenging AI opponent.

Even though, the algorithm was designed for one specific type of game it should be easily adaptable to other types of strategy game.

Return to the full version of this article
Copyright © UBM Tech, All rights reserved