Challenges of AI in the RTS Genre

Real-time strategy games have a lot of depth. That means many decisions of varying consequence have to be made, whose effects can arrive immediately or only after many minutes of play. As a result, developing artificial intelligence for this genre doesn't end with designing a single model. AI for an RTS is more like an orchestration of many models working together. In this post, I want to give an overview of the sub-aspects that exist within the genre and how potential AI solutions need to differ from one another.

Levels of Decision-Making

These in-game decisions can be divided into the categories of strategy, tactics, and reactive control. The terms micro-management and macro-management are also often used in the context of RTS games. Both terms describe in-game decisions, but split them into two categories instead of three.

Strategy: Describes the highest level of abstraction for in-game decisions. Strategy can also be described as the ability to plan. Assumptions are made, for example about how the layout of the map will affect the course of the game. The player then has to decide which approach best suits the situation, and also what strategy the opponent is likely to pursue. Whether an aggressive or defensive playstyle is the better choice is a strategic question. So is which economic strategy for resource management is most efficient relative to the opponent's presumed strategy. Strategic decisions are typically made roughly every three minutes. This aspect of RTS games won't be part of this piece. In-game decisions around taking a fortification happen at the following two levels.
Tactics: Describes the execution of strategy. This includes decisions such as recognizing the best moment to attack, timing the right moment to secure new resources, or anticipating the opponent's attacks and acting preemptively against them. Like strategic decisions, tactical decisions are often made under uncertainty, since depending on the game, not all information about enemy activity is visible. On average, tactical decisions are made every thirty seconds to every minute.
Reactive Control: Describes the execution of tactics. This category primarily covers situations where the armies of multiple players clash and fight. Precisely controlling individual units in these fights, dodging danger, maintaining formations, and recognizing and exploiting enemy weaknesses are all part of these decisions. Decisions of this kind are made every second during combat and, in professional esports, are often measured using the unit actions-per-minute (APM).

Age of Empires II: Definitive Edition (Forgotten Empires, 2019)

Artificial Intelligence

Whenever artificial intelligence in real-time strategy games comes up, the conversation often turns to the problems and difficulties that come with it. Many of these problems can be traced back to the genre's high complexity and its real-time nature.

Chess is a comparison that gets brought up a lot. With a limited number of possible moves and an 8 ∗ 8 board, chess has an estimated complexity of a deterministic state tree of 1050 different ways the game can play out. Rough estimates suggest that the complexity of a real-time strategy game, even on a comparatively modest map of 128 ∗ 128 cells, starts at 101685 possibilities. Both the size of the map and the decision and movement options of units, as well as the choice and placement of buildings, play a role here.

At least 30 times per second, an AI has to evaluate the current situation and make in-game decisions across all three decision levels. Given the high complexity and required computing power, the entire state space can't be iteratively updated in real time. A certain degree of abstraction is necessary to preserve the real-time nature of the game while still maintaining the appearance of intelligence. This abstraction has been achieved in past and present genre entries through various implementations of deterministic and non-deterministic AI algorithms.

The simplest and most widely used technique for implementing artificial intelligence is cheating. The AI is granted access to information that players, if they were in the same situation, wouldn't have. This could be the position of enemy units, for example, or their economic situation in terms of how many resources they have available and where they're gathering them. This reduces the problem of uncertainty and, with it, the complexity of the algorithms required. However, cheating has the property that experienced players tend to notice it over time, which often causes them to lose interest in competing against the AI.

On one hand, the behavior of the artificial intelligence can be hard-coded. This means, for example, defining a fixed order in which the AI constructs buildings and/or trains units. Simple state trees and finite state machines can add further depth by switching between multiple approaches depending on whether certain external conditions are met.

However, this approach means players can quickly recognize and exploit the AI's patterns and weaknesses, which significantly reduces the challenge. Machine learning and neural networks can address the problem of an inflexible AI by training it during or after a match using recorded data. Potential fields can help make smarter decisions related to geographic pathfinding. Binary search trees or A* algorithms can help an AI make tactical and strategic decisions in order to achieve certain goals over the course of the game. It's worth noting that this is really just a way of getting closer to abstract goals. The phrase getting closer is used deliberately here, since, as mentioned before, it always involves a certain degree of abstraction.

The high complexity and the different levels of in-game decision-making mean that no single algorithm or technology can handle every aspect of an artificial intelligence. It's really a composition of deterministic (decisions under certainty) and non-deterministic (decisions under uncertainty) AI technologies.