Adaptive AI Engine for RTS Games

Discussing the theory and practice


Posted by Ogail on August 19, 2009


  • What is AI?
  • Many of trivial problems ( playing Connect 4) were solved by computers but there are many things that computers aren’t good at which we find trivial: recognizing familiar faces, speaking our own language, deciding what to do next, and being creative. These are the domain of AI: trying to work out what kinds of algorithms are needed to display these properties
  • In academia, some AI researchers are motivated by philosophy: understanding the nature of thought and the nature of intelligence and building software to model how thinking might work. Some are motivated by psychology: understanding the mechanics of the human brain and mental processes. Others are motivated by engineering: building algorithms to perform human-like task. Where game developers concerns with the last motivation
  • History of Academic AI:
    • The Early Days:
      • In the early days (before computers) some questions appeared (in philosophy of mind) as:
        • What produces thought?
        • Could you give life to an inanimate object?
        • What’s the difference between cadavers (جثة) and human it previously was?
      • Pioneers of the field these days were: Alan Turing (father of AI), von-Neumann, Shannon
    • The Symbolic Era:
      • From 1950s till 1980s main thrust in AI research was in “symbolic” systems
      • A symbolic system: is one in which the algorithm is divided into two components (as Expert Systems):
        • Set of knowledge: represented as symbols such as words, numbers, sentences, or pictures
        • Reasoning algorithm: that manipulates those symbols to create new combinations of symbols that hopefully represent problem solutions or new knowledge
      • Other symbolic approaches in games: blackboard architecture, pathfinding, decision trees, state machines, steering algorithms
      • Common disadvantage of symbolic systems: when solving a problem the more knowledge you have, the less work you need to do in reasoning
      • The more knowledge you have, the less searching for an answer you need; the more search you can do (i.e., the faster you can search), the less knowledge you need
    • The Natural Era:
      • From 1980s to 1990s frustration symbolic approaches come into two categories:
        • From engineering point:
          • early success on simple problems didn’t seem to scale to more difficult problems
        • From philosophical point:
          • Symbolic approaches are not biologically plausible (i.e. You can’t understand how a human being plans a route by using a symbolic route planning algorithm)
          • The effect was a move toward natural computing: techniques inspired by biology or other natural systems (like ANN, GA and simulated annealing)
  • The no-free-lunch theorem and subsequent work has shown that, over all problems, no single approach is better than any other
  • The narrower the problem domain you focus on, the easier it will be for the algorithm to shine. Which, in a roundabout way, brings us back to the golden rule of AI: search (trying possible solutions) is the other side of the coin to knowledge (knowledge about the problem is equivalent to narrowing the number of problems your approach is applicable to)
  • Game AI:
  • Till 1990 all computer-controlled characters used FSM
  • In 1997 the new technique included was ability to see colleagues and notify them when killed
  • In mid-1990s RTS games (Warcraft II) was the first time popular game having robust pathfinding implementation
  • The AI in most modern games addresses three basic needs:
    • The ability to move characters,
    • The ability to make decisions about where to move
    • The ability to think tactically or strategically
  • Model of Game AI:

  • Movement:
    • Movement refers to algorithms that turn decisions into some kind of motion
    • Examples (49):
      • Super Mario example when attacking enemies with bullets
      • Guard that want to reach alarm example
  • Decision Making:
    • Involves character working out what to do next
    • Examples: take the decision to attack, defend, patrol…
  • Strategy:
    • To coordinate whole team you need a strategic AI
    • In the context of this book, strategy refers to an overall approach used by a group of characters
    • In this category are AI algorithms that don’t control just one character, but influence the behavior of a whole set of characters
    • Example: surrounding a player in FPS Game
  • Infrastructure:
    • These are Information Gatherer (perception) and execution management issues
  • Agent-Based-AI:
    • agent-based AI is about producing autonomous characters that take in information from the game data, determine what actions to take based on the information, and carry out those actions
  • Techniques in this book are implemented into 3 categories: Algorithms, Data Structures, Game Infrastructure
  • Key elements to know when implementing algorithms:
    • Know the problem the algorithm want to solve
    • A general description of the working mechanism of the algorithm including diagrams
    • A pseudo-code presentation of the algorithm
    • Indication to the data structure used in the algorithm
    • Particular implementation node
    • Analysis of the algorithm performance: execution speed, memory footprint and scalability

Weaknesses in the approach


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: