Adaptive AI Engine for RTS Games

Discussing the theory and practice

Posts Tagged ‘learning’

Paper read: Call for AI Research in RTS Games

Posted by MHesham on November 2, 2010

Michael Buro. 2004. Call for AI Research in RTS Games. In Proceedings of the AAAI Workshop on AI in Games.

The paper discuss AI challenges in the real-time strategy games and presents a research agenda aimed at improving AI performance in this computer games.

RTS Games and AI Research

The current AI performance in commercial RTS games is poor. The main reasons that the AI research in RTS games is lagging behind development related fields such as classic board games:

  • RTS games feature hundreds or thousands of interacting objects, incomplete information, and fast-paced micro actions. On the other hand World-class game AI systems exist for turn-base perfect information games (e.g chess).
  • Video games companies create games under server time constraints, and don’t have the resources to engage in AI research.
  • Multi-player games do not require world-class AI performance in order to be commercially successful as long as players are more interested in on-line games.
  • RTS games are complex, which means that it is not easy to set-up an RTS game infrastructure to conduct AI experiments.

The domains where  human ability to abstract, generalize, learn, adapt and reason shine, the current RTS games fail.

Motivations for AI research in RTS games

  • RTS games constitute well-defined environments to conduct experiments in and offer a straight-forward objective ways of performance measuring.
  • RTS games can be customized to focus on specific aspects, such as local fights, scouting, resource management.
  • Strong game AI will make a different in future commercial RTS games, because graphics improvements are begging to saturate.
  • The current state of AI in RTS games is so back that there are a lot of low-hanging fruits waiting to be picked. Examples include game interface that alleviate the tedious tasks such as concentrating fire in combat.
  • Progress in AI research in RTS games is of interest for the military which uses battle simulations in training programs and purse research in autonomous weapon systems.

Research Agenda

The main goal behind the proposed research agenda is not to increase the entertainment of RTS games but to develop the strongest RTS game AI possible.

In order to repeat the success of AI in class games, the following keys are required:

  • Adversarial planning under uncertainty
    • Because the huge number of actions that had to be taken at any time and the implied complexity of RTS games, the agent can’t think at this level but in more abstracted level.
    • Agent has to search in the abstract world space and translate found solutions back into the original state.
    • All high-level decision such as what to build, when to attack are based on abstract search space augmented by beliefs about the abstract world.
    • Because the environment is hostile and dynamic, adversarial real-time planning approaches needed to be investigated, or there is no hope for RTS game AI to defeat human at commander level.
  • Learning and opponent modeling
    • One of the biggest shortcomings of current (RTS) games AI systems is their inability to learn quickly. Human players need to play a couple of games against the AI agent to exploit its style and weakness in its strategy, New efficient machine learning techniques have to be developed to tackle this problem.
    • AI would be able to discover the human player bias toward a certain unit types and strategy, and use this information to adapt its plan.
  • Spatial and temporal reasoning
    • Understanding the importance of static terrain like choke points and dynamic spatial properties such as visibility and enemy influence will influence in generating a successful plan.
    • The temporal relationship among various actions is to be understood well by the playing agent.
    • Combining terrain knowledge and simple heuristics about actions is sufficient to pick the best course of action.

Because AI is not as good as humans in planning, learning and reasoning, at least it can help humans play RTS games. However, there are numerous other ways of improving game performance which can be easily integrated in RTS game interfaces. As an example, in RTS games when attacking a group of units player has to concentrate fire or to intercept fleeing-units. This can be done by developing AI systems that handle this low-level unit management (micromanagement) and let human concentrate on the high-level decisions.

The need for an open source test-bed

Before this vision can become reality, the necessary infrastructure has to be developed. RTS game companies are reluctant to add interfaces to their products which would allow researchers to play RTS games remotely and to gauge the playing strength of RTS AI systems by means of tournaments. Therefore a free-software RTS game was developed, this game is called ORTS (Open-source RTS)

Posted in Papers Summaries | Tagged: , , , , , , , | 2 Comments »

Just an Intro : Heuristically Accelerated Hierarchical Reinforcement Learning in RTS Games

Posted by merothehero on December 3, 2009

Introduction

In this document I will analyze the game play and strategies of RTS Games, and then I will give a brief about how the Heuristically Accelerated Hierarchical Reinforcement Learning System (HAHRL-RTS System) will work.

The Strategy Game: An Analysis

There’s no doubt that strategy games are complex domains: Gigantic set of allowed Actions (almost infinite), Gigantic set of Game States (almost infinite), imperfect information, nondeterministic behavior, and with all this: Real-time Planning and Reactions are required.

Many of the Approaches to applying learning or planning to RTS Games considered the AI as one solid learning part; this leads to the great complexity at applying the techniques used.

I thought about: How can I simplify everything?

Firstly, I listed all the primitive actions which could be done by a human player:

1-      Move a unit

2-      Train/Upgrade a unit

3-      Gather a resource

4-      Make a unit attack

5-      Make a unit defend

6-      Build a building

7-      Repair a building

NB: Upgrading units or buildings is not available in BosWars but found in most RTS Games.

Any player wins by doing 2 types of actions simultaneously, either an action that strengthens him or an action that weakens his enemy (Fig 1).
NB: We neglect useless actions here and suppose the player is perfect.

When a human plays a strategy game, he doesn’t learn everything at the same time. He learns each of the following 6 sub-strategies separately:

1-      Train/Build/Upgrade attacking Units: What unit does he need to train??

  1. Will he depend on fast cheep units to perform successive fast attacks or powerful expensive slow units to perform one or two brutal attacks to finish his enemy? Or will it be a combination of the two which is often a better choice?
  2. Does his enemy have some weak points concerning a certain unit? Or his enemy has units which can infiltrate his defenses so he must train their anti-units?
  3. Does he prefer to spend his money on expensive upgrades or spend it on more amounts of non-upgraded units?

NB: I deal with attacking Buildings as static attacking units

2- Defend: How will he use his current units to defend?

  1. Will he concentrate all his units in one force stuck to each other or will he stretch his units upon his borders? Or a mix of the two approaches?
  2. Will he keep the defending units (which maybe an attacking building) around his buildings or will he make them guard far from the base to stop the enemy early. Or a mix of the two approaches?
  3. If he detects an attack on his radar, will he order the units to attack them at once, or will he wait for the opponent to come to his base and be crushed? Or a mix of the two approaches?
  4. How will he defend un-armed units? Will he place armed units near them to for protection or will he prefer to use the armed units in another useful thing? If an un-armed unit is under attack how will he react?
  5. What are his reactions to different events while defending?

3- Attack: How will he use his current units to attack?

  1. Will he attack the important buildings first? Or will he prefer to crush all the defensive buildings and units first? Or a mix of the two approaches?
  2. Will he divide his attacking force to separate small forces to attack from different places, or will he attack with one big solid force? Or a mix of the two approaches?
  3. What are his reactions to different events while attacking?

4- Gather Resources: How will he gather the resources?

  1. Will he train a lot of gatherers to have a large rate of gathering resources? Or will he train a limited amount because it would be a waste of money and he wants to rush (attack early) in the beginning of the game so he needs that money? Or a mix of the two approaches?
  2. Will he start gathering the far resources first because the near resources are more guaranteed? Or will he be greedy and acquire the resources the nearer the first? Or a mix of the two approaches?

5-      Construct Buildings: How does he place his buildings? Will he stick them to each other in order to defend them easily? Or will he leave large spaces between them to make it harder for the opponent to destroy them? Or a mix of the two approaches?

6-      Repair: How will he do the repairing? Although it’s a minor thing, but different approaches are used. Will he place a repairing unit near every building in case of having an attack, or will he just order the nearest one to repair the building being attacked? Or a mix of the two approaches?

The HAHRL-RTS System

Since the 6 sub-strategies do not depend on each other (think of it and you’ll find them nearly independent),  So, I will divide the AI system to a hierarchy as shown in figure 1, each child node is by itself a Semi-Marcov decision process (SMDP) where Heuristically Accelerated Reinforcement Learning Techniques will be applied. Each child node will be later divided into other sub-nodes of SMDPs.

So now you’ve understood why it is hierarchical, but you may be wondering why “heuristically accelerated”?

Well, because heuristic algorithms will be applied to guide and accelerate the learning process. I hear you asking what the heuristic algorithms are. But that’s another story will be said later!

Posted in HAHRL-RTS Platform | Tagged: , , , , | Leave a Comment »