FormulaAIandDynamicScripting

Me

IRC: barbarianhero

Forum id: Rende

gna! username: dhains

Overview

Many types of AI techniques to provide intelligent strategies in games revolve around the concept of search and evaluation. The problem with search is it can simply take too long. Anyone who has played a chess AI knows of the delays between moves due to this search and eval procedure. These delays would interrupt the flow of game play in Wesnoth, so the approach used in Dynamic Scripting can be applied to heavily cut down on the search portion by coding domain knowledge of the game into sets of moves known as rulebases. Evaluation and selection of exactly what moves to make is still up to the AI, but we can cut the computational costs significantly by providing a pool of candidate moves.

By using modular rulebases instead of a single large database of moves, scenario AIs, MP bots, death match AI's, etc. can be designed easily by plugging together appropriate rulebases as described below. The designer can achieve a high level of customization and still have an intelligent, adaptive AI as a result. The dynamic scripting technique has been applied successfully in creating an aftermarket AI to control characters in Neverwinter Nights. A party consisting of a variety of character classes was able to adapt and cooperate to defeat an opposing force. It is not much of a stretch to see how this technique could be applied to Wesnoth. There are quite a few more characters to be controlled, but the choice of actions is less (e.g. they don't have a plethora of items and spells at their disposal on top of moving and attacking).

Formula AI

Formula AI will be used for designing the AI rulebases described below. A rulebase can be thought of as a set of candidate moves written in Formula AI which accomplish some particular behavior or strategy. Much of the work will be defining what behaviors/strategies are required and implementing the appropriate moves in Formula AI. I believe there will be some back and forth between implementing rulebases in FormulaAI and extending Formula AI when additional functionality needs to be added. These two things will probably be a majority of the project.

Rulebases

Think of a rulebase as a collection of moves which coordinate some type of behavior (i.e. assassinate opposing leader, defend castle with ZoC, etc.). The moves in each rulebase are not necessarily the moves which are taken at any given point in a game but rather they create a pool of candidate moves the AI can choose from. Exactly what move is chosen from this pool of candidate moves depends on an evaluation function which assigns probabilities to each move. These probabilities can be altered by the AI itself (using dynamic scripting) as it plays through a game, thus providing the AI the ability to adapt to an opponents strategy.

There will be two types of rulebases: team rulebases and unit rulebases. A team rulebase will contain formulas which more or less correspond to scenario objectives (or deathmatch, MP, etc.) such as 'Escort unit X to Hex Y'. These moves will be used to govern the overall behavior of the AI to win the round. Unit rulebases, cover unit specific behavior such as 'Hatred towards faction X', 'Hide and Ambush' or 'Healing unit'. These rulebases can be applied to specific units or classes of units to allow them to use unit specific strategies and techniques. This allows for an easily customizable AI for scenario designers, MP bots for co-op campaign play, death matches, etc.

For example, a scenario designer might want to create a scenario in which a group of orcs, goblins and ogres must escort an orcish leader across a map to hex 5,10. The storyline might dictate that the goblins and ogres are only helping the orcs for a chance to kill elves, which the player has the ability to recruit. The scenario designer could implement this quite easily in their cfg file for that scenario with something like

  [ai]
     [team_formula]
       rulebase = "escort"
       parameters = "Orcish Leader", 5, 10
     [\team_formula]
     [unit_formula]
       apply_to_units = "goblins", "ogres"
       rulebase = "faction_hatred"
       parameters = "Elves"
     [\unit_faction]
  [\ai]

Of course the designer could make things a bit more complicated, by creating multiple team strategies associated to different units, e.g. suppose in the above example the AI also had a renegade faction of elvish rangers along for the ride, hellbent on destroying the human leader and don't really care about escorting the orcish leader. The designer might create an entirely new side, but if he or she wanted all the units on a single side, he might add the following to the above ai section.

     [unit_formula]
       apply_to_units = "Elvish Ranger", "Elvish Avenger"
       rulebase = "hide_and_ambush"  # Make elves stay hidden if possible until they attack
       [team_formula]  # This will override the "escort" team formula
         rulebase = "assassinate"
         parameters = "Human Leader"
        [\team_formula]
     [\unit_formula]

The AI designer can go deeper or shallower if necessary. An adequate default AI with appropriate unit rulebases and a 'kill all' team rulebase will be the default if none are specified. If the provided rulebases do not cover some specific behavior, the designer of course may implement his own rulebase by creating a custom formula script or by altering the evaluation functions of the existing rulebases.

Evaluation Functions

Along with the rulebases defined above also comes evaluation functions appropriate to each rulebase. These will be included with the formula scripts for each rulebase and will be transparent to the designer unless he or she wishes to modify them to fine tune the behavior. These evaluation functions will be used to determine the probability of a particular move.

I expect to have two evaluation functions, one for evaluating a move based on the overall impact on the team goal (this one will come from the team formula) and another on the unit level (from the unit formulas). Both evaluation functions will be evaluated on the candidate moves and a combination of the results will be used to determine the final probability of a move being chosen (This is the method used in Dynamic Scripting).

Dynamic Scripting

Finally, I would like to apply some machine learning concepts to the AI, specifically online learning. Online learning allows the AI to adapt it's strategy to fix holes being exploited by the human player and over all to perform more intelligently, giving the player a feeling he or she is playing against a thinking, clever opponent.

This can be accomplished by Dynamic Scripting, a proven (and relatively cutting edge) technique. Actually, everything described thus far is the general dynamic scripting as I would apply it to Wesnoth. The adaptability comes into play with the following addition.

As described above, each unit will have some probability associated with it assigned by the evaluation functions. The evaluation functions themselves are defined in the formula scripts and as such cannot be modified directly by the AI (at least for now). However we can assign a weight (initially set to 1) to each probability and allow the AI to modify this weight as it determines whether moves are successful or not. In this way, we give the AI ability to adapt it's techniques and an easy way to turn the learning portion off (set the weights to 1, don't allow change) for experimentation and perhaps adjust the difficulty setting.

Related Papers

Online Adaptation of Game Opponent AI in Simulation and in Practice, Spronk et al. [1]