Adaptive AI Engine for RTS Games

Discussing the theory and practice

Other Techniques of Note

Posted by Ogail on August 9, 2009

Other Techniques of Note

  • Artificial Life (ALife):
    • ALife is about searching to find “governing principles” to the life
    • Rules that can’t be broken in the future and can be used without fail to understand aspects of nature and predict outcomes based on hard equations
    • Newton has proved Descartes’ clockwork universe: in which God set up everything like a clock. God’s only contribution to the universe was to set everything in motion, and from there the laws of science took hold and have governed every sequence of events since that time
    • Chances to find any governing principles are so limited so we could construct our own “life simulations” so and doing so find out more about how life in general operates
    • ALife is a field of studies that hopes to understand natural life better by attempting to recreate biological phenomena from virtual computer environments
    • One main tenet of alife is that life is simply an emergent property of nature following some very simple rules over and over again
    • An emergent property refers to a trait or behavior exhibited by a creature that reaches beyond the capabilities of its constituent parts (Question)
  • ALife Usage in Games:
    ALife was used in Black & White and Creature Games
  • Artificial Life Disciplines:
    • Cellular (خلوي) Automata (CA):
      • CAs are group of algorithms that show a stunning amount of complex behavior with the very simplest of rules
      • Cells example (page 522)
      • When to use CAs:
        • Simulating mold growth
        • City building
    • Self-Organizing Behavior and Flocking (التدفق):
      • Large group of creatures can organize their movements within groups quickly, easily with what appears to be unified mind
      • Investigations here were to produce algorithms that allow us to replicate this kind of behavior using simple rules
      • The most famous research in this area was Boid research, mainly by using few key concepts you can achieve a remarkable simulation of many types of flocking movement
        • These simple concepts are:
          • Separation to avoid crowding
          • Alignment to the average group heading
          • Positional cohesion of the group
    • Genetic Algorithms: can
      model the idea of evolution
  • Pros of ALife:
    • Emergent behavior:
      • ALife is one of the best ways we currently have of creating emergent situations
      • Emergent behavior will appears in games where the AI opponent with simple actions that can be combined in different ways leading to a wealth of different final behaviors
    • Behavior of reuse:
      • ALife forces the developers to build games out of building blocks, assembling gameplay until it can be expressed in simple rules. In fact many ALife games are simple to build
  • Cons of ALife:
    • Emergent behavior: the emergence outcome could be not entertained!
    • Tuning issues: little changes in game parameters could destroys the emergence behavior completely
  • Some games uses ALife with creatures to create actual ecologies within the world instead of random spawn points

     

  • Planning Algorithms:
  • Planning is, deciding upon a course of action before acting
  • Formulas that planning algorithms follow:
    • Break the abilities of the AI into distinct operators
    • Designing your AI character, and game environment in states manner
    • Construct either:    
      • Tree: that shows transition connections between states and lists the transition operators
      • Rules embedded in each state: that details which operators are available
    • Then, AI forms a plan within a local working memory by applying these transitions on a copy of its current state, testing for the best action to the behavior it wants
  • Here you know what your start state and end state, planning lists the best string of operations to get you to the end
  • Example: the plan to a pathfinding (page 525)
  • Because planning is costly we’ve used hardcoded plans (scripts, FSM…) which allow us usually do right behaviors
  • Usage in Games:
    • Used in pathfinding algorithms
    • Used in attacked/defense in RTS games: when AI sees that the enemy creates unit from type X so it (AI Opponent) searches in its technology tree for the path to get the anti-unit to that unit and start creating it
    • In FPS games: a human entering a room for a power up and AI should kills him (527)
      • This is a serious AI player that mimic humans
    • Make AI anticipate ambushes
  • Some Planning Techniques:
    • A*
    • Means And Analysis (MEA):
      • combines forward and backward searching of tree & tries to minimize unnecessary search
    • Patch Recalculation:
      • Get a broken plan then pass this plan to a function that patches (by come up with planning step) the hole is this plan
      • This method is used when an event happens results in broken plan & also your plan should be long
      • This planning technique provides a way of keeping plans up to date without having to start from zero
    • Minimax:
      • Considers your opponent is going to be working against you every chance he can get
      • Reinforcement Learning cold be combined with that technique resulting in more challenging behaviors
  • Pros of Planning:
    • Planning algorithms provide much intelligent looking behavior
    • Planning is generic and could be developed once and used in many contexts
    • Planning can be implemented hierarchically (See example page 528)
  • Cons of Planning:
    • Planning is computationally complex
    • Humans player are unpredictable so you should be careful in the plan depth
      • Make balance between speed and flexibility of plan Vs. having short range plans to avoid gaffs
      • For long plans you could use patching recalculation to adapt them on the situation
    • Planning can make the AI seems sluggish (بطيء) or un-reactive if plans are too monolithic (متشابهة) or take too long to adapt to new situations
  • Areas for Exploitations (الإستغلال)within Games:
    • Planning is used when creating strategic AI systems that require many steps to achieve goals
    • Most candidate for planning is RTS Games
    • Used in FPS, could be used to set ambushes and traps
    • Used in race-car to pass critical corners quickly rather than just “seed up” the car
    • Used in Frightening Games in choosing damaging combinations (box attack then kick head …)
    • Used in football games to confuse human player or waste time till much ends (to win of course!)

 

  • Production Systems:
  • Production systems are also referred as expert systems
  • Production systems are rule-based systems that strive to encompasses expert knowledge within a specific area
  • Example of this is hardcoded conditional if-then branches within your AI engine to make decisions
  • In 1969, Alan Newell and Herbert Simon released the theory of the General Problem Solver (GPS) based on how the human mind operates (means-and-analysis)
  • GPS tends to store expert knowledge about highly specific problem
  • Production system is separated into four parts:
    • Global database
    • Production rules: serve as actual if-then statements
    • Rules/Situation Matcher: decides which operator to use next upon the database get closer to your goal
    • Conflict resolution function (for use with rule collisions)
  • Production system use:
    forward chaining inference and backward chaining inference
  • Production systems could be used as planning systems or learning devices
  • John Laird and his team successfully interfaced Soar with both Decent 3 and Quack 2 and created competent, non-scripted opponents for each game. Using a system more than 700 rules, they created quack bot that can move in game levels; use all weapons and level elements (such as bonus pad, teleporters). Can anticipate human actions and also creating custom routes of travel to maximize amount of power ups it could collect and perform intelligent ambushes and human behaviors
  • Pros of production systems:
    • Generic Algorithm; production systems are data independent
    • Research; tons of researches have been on production systems fast matching algorithms like RETE and TRETE (stateless of RETE) they speed up matching
    • Goal directed
    • Highly reactive (with as good set of rules)
  • Cons of Production Systems:
    • Computationally expensive; especially with games having large rule set or non-arbitrary match collision resolution
  • Areas for Exploitation within Games:
    • Written in a data-driven way; so new rules perceptions could be added easily to the game world
    • So it’ll offer highly extendible and reusable systems

     

  • Decision Trees:
  • Here you mainly convert each if-else statement in a node within a tree
  • The root of the tree could be the question that the tree answers
  • There are 2 types of decision trees used:
    • Classification Trees: trying to determine “type” of player the human is behaving like (aggressive, defensive)
    • Regression Trees: adjusting AI behaviors (too hard, too easy) on human playing difficulty
  • The differences between using Decision Trees (DT) and NN are:
    • NNs are black box; weights couldn’t be changed or understood whereas DT are fully understandable, descriptive and easy to change
    • DT can only comprehend hard comparisons within a binary outcome whereas NN could handle noisy data or data within gaps and strange jumps in behavior
    • Output from DT always discrete values where output from a NN can be continues value
    • DT consider single variable at a time (called monothetic) whereas NN can handle multiple variables at a time (called polythetic) So when a combination of variables used to take one decision NN are more suitable here
    • NN are much accurate than DT. Relative error in traditional data set might be 10 times or more for DT over back-propagated NN

  • Pros of Decision Trees:
    • Easy to use, understand and change
    • Many algorithms exist for designing, training, debugging, tuning and optimizing decision trees
    • DT are suitable to be used in games and make more sense than NN
    • Complexity could be resolved using hierarchal decision tree
  • Cons of Decision Trees:
    • BDTs deals only with distinct states, don’t scale well and difficult to maintain or extend once they got a certain level of complexity
    • The size of your tree is direct inverse correlation between accuracy and size
      • So if you need specific and accurate outputs go to NN or other techniques
    • Non-binary trees are hard in constructing, altering and using
  • Areas of Exploitation within Games:
    • Using classification to perform simple player modeling
    • Data driving the trees and provide adding and removing nodes from trees (used in Black & White to record high level thinking that you avatar did about his environment given his experiences and training, about which actions to take at any given time)
    • Can be simply used by game level designers

 

  • Fuzzy Logic:
  • Fuzzy logic is a far more advanced system, complete with its own logical proof and methods
  • The Sony PlamTop is reported to use decision trees based on fuzzy logic to classify handwritten Kanji characters
  • Fuzzy logic could be used in “Fuzzy-Logical Production System” which follows all the rules of regular production systems, but performs all its inference using fuzzy logic instead
  • The general inference process is three (optionally four) – Page 537:
    • During Fuzzification: membership function is applied to the input to determine the degree of membership
    • Unser inference: usually MIN or PRODCUT are used in inferred rules
    • Under Composition: usually MAX or SUM are used
    • Defuzzification: converting fuzzy output to crisp number (common methods: Centroid and Maximum)
  • Fuzzy systems are used in pattern recognition, financial systems and heavy data analysis
  • They are not implemented in systems that require a heavy amount of realism
  • Fuzzy set membership discuss to what extend something already is true
  • Pros: extends Boolean logic in a new manner
  • Cons: Computationally expensive (Combs method to combat this problem)
  • Areas of Exploitation within Games:
    • Dealing with unknown or partially known information (like player modeling)
    • In online games, it could used as “helper AI” that plays a game for you temporarily (if you are afk for a while)
Advertisements

One Response to “Other Techniques of Note”

  1. […] Other Techniques of Note […]

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: