Article: Real-Time Strategy High-Level Planning

Real-Time Strategy High-Level Planning

[Stefan Weijers, 2010]

In this article, the author analyzes the different elements needed for implementing AI in RTS games as well as different techniques used to achieve this. Here is a small summary:

Real-Time strategy games are computer games in which the player controls an army in real-time to destroy other players' armies, with each player requiring resources and buildings to create such army. The key to winning is to balnce the army production with the gathering of resources.

Tasks in real-time strategy games can be split in three levels of abstraction:

• Unit Control (Lowest level, players control a specific unit).
• Tactical Planning (Make plans on how to attack the enemy).
• Strategic Planning (High-Level decisions involving army creation and management).

Identified Problems in real-time strategy games:

-------------------------------------------------

Resource Management

The gathering and balancing of resources can be done with a reflex agent. The AI has all the relevant information and can simply assign more units to a certain resource when it runs low.

Decision making under uncertainty

To be able to recognize important events, the game needs some sort of pattern recognition. Even with no concrete information available, the AI should be able to plan future actions.

Spatial and temporal reasoning

Applicability of a strategy needs to be reevaluated constantly. Terrain analysis is really importante for this. An important problem encountered for this aspect is the process time, because the world might have changed while the AI is still calculating its strategy.

Collaboration

This aspect is clearly lacking in RTS. Computer players never work with human players to overcome a strong opponent. The AI should be able to recognize the allied strategy and help them in the right way.

Opponent modeling, learning

Human players can spot weaknesses in a strategy and exploit them while computer players have a hard time accomplishing this. The AI needs to learn from previous experiences and formulate aplicable counter strategies.

Reasons why current commercial RTS AI fail to challenge human players:

--------------------------------------------------------------------------

Predictability and lack of spatial reasoning.

When the AI is predictable, players will inevitably exploit it. The predictability of commercial AIs comes from the fact that all AI is scripted.

Scripting

Commercial games include a set of scripts that translate into several different strategies that the AI implements to give some diversity to games but that carries several problems:

Hard to implement

Implementation of scripts needs several expertns in the game to think of viable strategies, the game has to be near completion before the AI programmers can start implementing it and even after implementation, it needs to be tested and tweaked thoroughly.

Domain Specific

After implementing a scripted AI for a game, the implementation is not applicable for other RTS games. This forces game developers to go thorugh the implementation cycle again.

Game developers use other means to entertain players. Different scripted strategies or giving the AI more information than it should have are some examples to create diversity or add challenge.

Academic Research to solve these issues:

---------------------------------------

Dynamic Scripting

A reinforcement learning technique for scripts. This allows the AI to generate a strategy on the fly by selecting a viable tactic in the tactic database. Also, this allows the AI to overcome static challenges (players that use the same tactic over and over again).

This, however, carries some of the problems. It still needs a group of experts to create viable tactics and because most research is done with static opponents to learn from, their ability to counter other adaptive players is doubted.

Monte Carlo Planning

This type of planning generates a set of simulations for all possible actions, it then chooses the plan that corresponds with the best simulation for the player. Because in an RTS game the amount of possible actions is enormous, an abstraction of actions and states has to be found.

The problem with this technique is that it requires a lot of calculating and it doesn't learn from previous mistakes.

Case Based Planning

This technique is based on case based reasoining, which is similar to the dynamic scripting method. It is based on states and looks at past experience to calculate the best sub plan in the current state. Case Based Planning doesn't model the opponent and wont do adversarial planning. It needs a database of predefined tactics. The algorithm picks a random tactic and remembers the outcome. This technique allows an expert to play the game and teach the AI what good decisions are, simplifying the process of designing an AI.

The problem with Case Based Planning is that it needs to be trained against opponents before it can become strong. The more complex and diverse the opponents are, the longer it will take the CBP to learn how to win.

The author finally concludes that the most advanced technique is the Case Based Planning because it can adapt, change and enhance strategies, but pointing out which one of the three is the best is hard because advance scripts have been made in commercial games and the performance of the Case Based or Monte Carlo planners have yet to be proved in more complex games.

Read the full article here!

Wijers, S., 2010, Real-Time strategy high-level planning. Obtained in August 11th, 2011 from PIXEL: www.inter-actief.utwente.nl/studiereis/pixel/files/indepth/StefanWeijers.pdf