FormulaAIandDynamicScripting

From The Battle for Wesnoth Wiki
Revision as of 22:59, 18 March 2008 by Dhains (talk | contribs) (made things a bit more clear)

This is a *very* rough outline of some ideas I have for the AI improvement. I'm pretty much open to any suggestions but this outlines what I have in mind, giving the AI some adaptive capability and making the AI tunable by scenario designers and for all out combat.

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 are required (i.e. aggressive, defensive, etc.) 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 two thirds 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 as it plays through a game, thus providing the AI the ability to adapt to an opponents strategy.

There will be team rulebases, which more or less correspond to scenario objectives (or deathmatch, etc.) such as 'Escort unit X to Hex Y'. These moves will be used to govern the overall behavior of the entire force to win the round. There will also be unit rulebases, which can be associated with particular units, such as a 'Hatred towards faction X' behavior. The rulebases will be as general and parameterized, to allow for as much reuse as possible.

This allow for an easily customizable AI for scenario designers, MP bots (perhaps for co-op campaign play), death matches, etc. For example, a scenario designer could simply select a team and recruitment rulebase appropriate to his scenario (probably specified in WML) and associate his Orcs with a hatred vs elves unit rulebase. This would give the designer's wolf riders a behavior biased towards aggressively attacking elves, but the overall team strategy will still be accomplished.

Of course the designer could make things a bit more complicated, perhaps by creating multiple team strategies associated to different units, i.e. Most units could be assigned candidate moves from a 'defend leader' team rulebase while camouflaged units could follow an 'assassinate leader' team rulebase, and since they are camouflaged units they might also be associated with a 'hide & attack' unit rulebase. The scenario designer could accomplish this in a few lines of WML and have some really cool results, i.e. the AI puts up a solid strong, ZoC defense but is also circling around a camo squad to ambush to opposing the leader. And of course, the whole time the AI is learning and adapting on it's own to the opposing strategies.

I think coming up with the specific rulebases and such will really start rolling after a fair amount of interaction with the community, specifically players and scenario designers.

Rulebase Categories

Recruitment Rulebases

Rulebases to govern the recruitment process, this may just be one parameterized rulebase to begin with, but most likely several rulebases for different recruiting strategies.

Team Rulebases

These will be more general rules for which all units would abide (We could create an easy way for certain units to ignore any team rulebase, or to follow another to setup a renegade faction within a computer controlled side, for instance a band of outlaws (thugs, poachers) which are helping the computer controlled side fight but simply for the sake of killing elves and have no care for the overall objective of the AI.) Mostly, the provided rulebases in this category will cover the most common scenarios and deathmatch games, i.e. kill opponents leader, defend for x turns, escort x to hex y, kill at all cost, etc.

Unit Rulebases

These are rulebases which can be associated to units. Scenario designers can apply some unit rulebases to all units in scenario and then customize specific units on a case by case basis if needed, to say setup faction behaviors between certain units. This could not be just aggressive but also perhaps a healing unit prefers to heal units of it's own faction. Healing units could be associated with a general unit rulebase which tells them to heal wounded units and could be even further customized with a heal elves over dwarves behavior.


Evaluation Functions

So once the global, recruitment and unit rulebases have been defined, the Formula AI in these rulebases forms a pool of candidate moves for the AI to follow. These moves will have a probability defined to them by the evaluation functions and these probabilities will be used in determining what action to take.

Following the concept of team and unit behaviors, I expect to have two evaluation functions, one for evaluating a move based on the overall impact on the tam goal and another on the unit level. A combination of the result of both of these eval functions will used to determine the final probability of a move being chosen (This is also the same method used in Dynamic Scripting).

Dynamic Scripting

I was hoping 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.

One method that seems quite suitable is dynamic scripting. This method relies on a manually designed rulebase from which the AI can construct moves. Each rule in the rulebase has an associated weight which influences the probability of a given rule being used in an upcoming move. As a game progresses, the weights are updated automatically according to the success or failure of the rules in the past of the current game (or campaign). This would allow the AI to adapt to a player's tactics and encourage the player to develop diverse strategies for use in campaign mode.


Related Papers

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