Difference between revisions of "FormulaAIandDynamicScripting"

From The Battle for Wesnoth Wiki
(Candidate for deletion)
 
(24 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
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.
+
{{Delete}}
 +
==Project Progess==
  
−
==Formula AI==
+
[[GsocAIProjectProgress]]
  
−
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.
+
==About Me==
  
−
==Rulebases==
+
I am currently a full-time graduate student living in Colorado, US.  I've been coding since I was about 12, initially writing text based adventures for myself and my friends to play, moving on to RPGs using some primitive sprite based graphics and completed a mini RPG in high school, complete with graphics and music I wrote on my keyboard.
  
−
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.  
+
Since then, I have graduated from Pennsylvania State University with a bachelors degree in computer science and entered a PhD graduate program focusing on AI research.  I use C++ primarily for research and have been a teaching assistant for our undergraduate C++ course.  I have approximately 4/5 years of C++ experience and some Python experience.
  
−
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.
+
===Contact Information===
  
−
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.
+
* IRC: barbarianhero
  
−
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.
+
* Forum id: rende
  
−
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.
+
* Gna! username: dhains
  
−
===Rulebase Categories===
+
* preferred email: dhains__A!T__ gmail.com
−
====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====
+
I'll be adding more to this page as I have the time.  Please feel free to contact me if you have any questions.
−
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====
+
=== My Contribs ===
−
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.
 
  
 +
Since I have been active with Wesnoth development for the past few weeks, I have submitted several patches and gained SVN access.  Since then, I have been focusing on getting Formula AI to a point where I can begin development of the ideas set forth in this proposal by implementing necessary features:
  
−
==Evaluation Functions==
+
==== Terrain Knowledge ====
−
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.
+
These checkins exposed map and terrain features to Formula AI, a much needed feature.  Terrain information is now available to Formula AI using 'map.terrain' from within Formula AI.  This allowed implementation of the 'woodchopper' feature requested on the forums.
  
−
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).
+
* Exposed terrain, nearest_loc function, woodchopper example - [http://svn.gna.org/viewcvs/wesnoth?view=rev&rev=25365], [http://svn.gna.org/viewcvs/wesnoth?rev=25455&view=rev]
  
−
==Dynamic Scripting==
+
Documentation can be found on the [[FormulaAI|FormulaAI]] wiki page and also on the [http://www.wesnoth.org/forum/viewtopic.php?f=10&t=20471&st=0&sk=t&sd=a&start=15 Woodchopper forum thread]
  
−
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.
+
==== Formula AI Scripts ====
  
−
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.
+
The overall goal of the following checkins was to create and support a new way of writing Formula AI, i.e. formula AI script files to allow reuse and support building of pluggable Formula libraries:
  
 +
* Created def keyword for custom functions: [http://svn.gna.org/viewcvs/wesnoth?view=rev&rev=24993]
 +
* Formula Script support: [http://svn.gna.org/viewcvs/wesnoth?view=rev&rev=25052]
 +
* Cleaned up Formula AI script read method : [http://svn.gna.org/viewcvs/wesnoth?view=rev&rev=25094]
 +
* Fixed Parsing Bug in Formula AI : [http://svn.gna.org/viewcvs/wesnoth?view=rev&rev=25099]
 +
* Added Comment Support to Formula AI : [http://svn.gna.org/viewcvs/wesnoth?view=rev&rev=25136]
 +
* Checked in Vim Syntax Highlighting: [http://svn.gna.org/viewcvs/wesnoth?rev=25178&view=rev]
 +
 +
Formula AI scripts are now supported.  Documentation can be found on the [[FormulaAI|FormulaAI]] page.
 +
 +
==== Candidate moves and Eval functions ====
 +
 +
The following checkins are to support the building of candidate move lists and evaluation functions (work in progress):
 +
 +
* Initial support for candidate move lists [http://svn.gna.org/viewcvs/wesnoth?view=rev&rev=25365],[http://svn.gna.org/viewcvs/wesnoth?rev=25217&view=rev]
 +
 +
Initial Patches: [https://gna.org/patch/?1014], [https://gna.org/patch/?1016].
 +
 +
Various bug fixes: [http://svn.gna.org/viewcvs/wesnoth?rev=25452&view=rev]
 +
 +
==Overview==
 +
 +
Designing an AI for playing games is a challenge.  Techniques such as minimax and alpha-beta pruning are useful in games such as chess or backgammon, but the complexity of Wesnoth's gamestate space precludes many of these approaches.
 +
 +
A common method to overcome this problem is to use scripting.  Manually designed rules are created to determine the course of action, for instance if the AI should attack or defend.  While these methods are effective it is generally not enough to provide challenging play, especially to experienced players.  Players can 'outsmart' a scripted AI simply by exploiting the predictability inherent to scripting.
 +
 +
An ideal AI is one which exhibits human-like behavoir. One which can adapt its strategy to cover holes exploited by players. One which has the ability of surprise, to make the player feel as if he is playing a thinking, cunning opponent instead of just 'trying to beat the computer'. Such an AI is not a pipe dream and even more to the point, is quite feasible from a technical standpoint.
 +
 +
This is a proposal to implement such an AI. I propose to use dynamic scripting to combine manually designed rulebases and online learning to create a customizable, extensible and adaptive AI. his type of dynamic planning has already proven successful in creating adaptive, formidable A.I. in games such as F.E.A.R. and Neverwinter Nights [1,2].
 +
 +
The rulebases will be implemented in FormulaAI while the reinforcement learning portion will be handled by C++. This accomplishes two goals: 1, the AI can easily be customized and extended without touching the C++ code and with no knowledge of the reinforcement learning process and 2, the learning process can easily be 'switched off', perhaps as a difficulty setting or to force strict adherence to a script.
 +
 +
==Rulebases - Formula AI==
 +
 +
Rulebases contain the FormulaAI rules the AI can use to form scripts. The rulebases developed for this project will form a repository of strategies and behaviors that designers can simply plug into a WML file to create a highly effective AI without ever touching FormulaAI or the underlying learning processes. Of course, if a designer desires a new strategy they can write custom FormulaAI rules.
 +
 +
I plan to involve the community in this portion of the project to identify the common strategies used by players and desired by scenario and MP bot designers. The how to play series will also serve as a useful guide. I foresee three categories of rulebases the designer can choose from to customize the AI for a particular scenario or deathmatch.
 +
 +
=== Recruitment Rulebases ===
 +
 +
These rulebases will cover strategies to recruit units. A default recruitment strategy will be provided that selects the best units for the desired scenario goal.
 +
 +
=== Team Rulebases ===
 +
 +
Team rulebases will govern team strategies and will supply the majority of rules the AI can use when creating a script. Developed rulebases cover the majority of scenario and MP objectives, such as 'Escort unit x to hex y', 'Assassinate enemy leader', etc.
 +
 +
=== Unit Rulebases ===
 +
 +
Unit rulebases provide rules for unit specific behavior. Some of these rulebases will be associated to units by default, for instance a 'healing' rule for healing units, 'backstab' to thieves, etc.
 +
 +
A variety of rulebases to customize unit behavior to a scenario storyline will also be available, such as 'Hatred towards faction x' and can be applied to single units or groups.
 +
 +
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.
 +
 +
== Adaptation and Learning - C++ ==
 +
 +
The C++ portion of the project allows the AI to learn and adapt. Once the candidate moves are determined, the AI will rank the moves based on evaluation functions. The actual evaluation functions will be written in Formula AI, the C++ code should never have to be touch for customization or extension purposes.
 +
 +
There will be two evaluation functions: A team evaluation function, in which the impact of each move on the overall team strategy is evaluated and a unit evaluation function, in which the impact of a move on unit involved is evaluated. The results these functions determine the final evaluation of a move. Once all moves are evaluated, the script is formed based on these evaluations (i.e. best moves first).
 +
 +
At the end of turn, the success of each move is used to adjust a weight associated with that move. The weights are incorporated into the evaluation of moves during the next turn (e.g. weight * (unit_eval(formula) + team_eval(formula))). In this way, the AI can learn from it's mistakes and exploit holes in an opponent's strategy found by successful moves.
  
 
==Related Papers==
 
==Related Papers==
Line 44: Line 127:
 
Online Adaptation of Game Opponent AI in Simulation and in Practice, Spronk et al. [http://www.fdaw.unimaas.nl/education/3.1cs/postma/GAMEON2003-Paper8-Spronck.pdf]
 
Online Adaptation of Game Opponent AI in Simulation and in Practice, Spronk et al. [http://www.fdaw.unimaas.nl/education/3.1cs/postma/GAMEON2003-Paper8-Spronck.pdf]
  
 +
[[Category:AI]]
 
[[Category:Summer of Code]]
 
[[Category:Summer of Code]]

Latest revision as of 03:20, 16 November 2022

bomb.png

This page is a candidate for deletion. Someone has decided that this article does not (or no longer) serve a purpose. It may be deleted once suitable time has elapsed for others to contest the deletion on its discussion page.

Project Progess

GsocAIProjectProgress

About Me

I am currently a full-time graduate student living in Colorado, US. I've been coding since I was about 12, initially writing text based adventures for myself and my friends to play, moving on to RPGs using some primitive sprite based graphics and completed a mini RPG in high school, complete with graphics and music I wrote on my keyboard.

Since then, I have graduated from Pennsylvania State University with a bachelors degree in computer science and entered a PhD graduate program focusing on AI research. I use C++ primarily for research and have been a teaching assistant for our undergraduate C++ course. I have approximately 4/5 years of C++ experience and some Python experience.

Contact Information

  • IRC: barbarianhero
  • Forum id: rende
  • Gna! username: dhains
  • preferred email: dhains__A!T__ gmail.com

I'll be adding more to this page as I have the time. Please feel free to contact me if you have any questions.

My Contribs

Since I have been active with Wesnoth development for the past few weeks, I have submitted several patches and gained SVN access. Since then, I have been focusing on getting Formula AI to a point where I can begin development of the ideas set forth in this proposal by implementing necessary features:

Terrain Knowledge

These checkins exposed map and terrain features to Formula AI, a much needed feature. Terrain information is now available to Formula AI using 'map.terrain' from within Formula AI. This allowed implementation of the 'woodchopper' feature requested on the forums.

  • Exposed terrain, nearest_loc function, woodchopper example - [1], [2]

Documentation can be found on the FormulaAI wiki page and also on the Woodchopper forum thread

Formula AI Scripts

The overall goal of the following checkins was to create and support a new way of writing Formula AI, i.e. formula AI script files to allow reuse and support building of pluggable Formula libraries:

  • Created def keyword for custom functions: [3]
  • Formula Script support: [4]
  • Cleaned up Formula AI script read method : [5]
  • Fixed Parsing Bug in Formula AI : [6]
  • Added Comment Support to Formula AI : [7]
  • Checked in Vim Syntax Highlighting: [8]

Formula AI scripts are now supported. Documentation can be found on the FormulaAI page.

Candidate moves and Eval functions

The following checkins are to support the building of candidate move lists and evaluation functions (work in progress):

  • Initial support for candidate move lists [9],[10]

Initial Patches: [11], [12].

Various bug fixes: [13]

Overview

Designing an AI for playing games is a challenge. Techniques such as minimax and alpha-beta pruning are useful in games such as chess or backgammon, but the complexity of Wesnoth's gamestate space precludes many of these approaches.

A common method to overcome this problem is to use scripting. Manually designed rules are created to determine the course of action, for instance if the AI should attack or defend. While these methods are effective it is generally not enough to provide challenging play, especially to experienced players. Players can 'outsmart' a scripted AI simply by exploiting the predictability inherent to scripting.

An ideal AI is one which exhibits human-like behavoir. One which can adapt its strategy to cover holes exploited by players. One which has the ability of surprise, to make the player feel as if he is playing a thinking, cunning opponent instead of just 'trying to beat the computer'. Such an AI is not a pipe dream and even more to the point, is quite feasible from a technical standpoint.

This is a proposal to implement such an AI. I propose to use dynamic scripting to combine manually designed rulebases and online learning to create a customizable, extensible and adaptive AI. his type of dynamic planning has already proven successful in creating adaptive, formidable A.I. in games such as F.E.A.R. and Neverwinter Nights [1,2].

The rulebases will be implemented in FormulaAI while the reinforcement learning portion will be handled by C++. This accomplishes two goals: 1, the AI can easily be customized and extended without touching the C++ code and with no knowledge of the reinforcement learning process and 2, the learning process can easily be 'switched off', perhaps as a difficulty setting or to force strict adherence to a script.

Rulebases - Formula AI

Rulebases contain the FormulaAI rules the AI can use to form scripts. The rulebases developed for this project will form a repository of strategies and behaviors that designers can simply plug into a WML file to create a highly effective AI without ever touching FormulaAI or the underlying learning processes. Of course, if a designer desires a new strategy they can write custom FormulaAI rules.

I plan to involve the community in this portion of the project to identify the common strategies used by players and desired by scenario and MP bot designers. The how to play series will also serve as a useful guide. I foresee three categories of rulebases the designer can choose from to customize the AI for a particular scenario or deathmatch.

Recruitment Rulebases

These rulebases will cover strategies to recruit units. A default recruitment strategy will be provided that selects the best units for the desired scenario goal.

Team Rulebases

Team rulebases will govern team strategies and will supply the majority of rules the AI can use when creating a script. Developed rulebases cover the majority of scenario and MP objectives, such as 'Escort unit x to hex y', 'Assassinate enemy leader', etc.

Unit Rulebases

Unit rulebases provide rules for unit specific behavior. Some of these rulebases will be associated to units by default, for instance a 'healing' rule for healing units, 'backstab' to thieves, etc.

A variety of rulebases to customize unit behavior to a scenario storyline will also be available, such as 'Hatred towards faction x' and can be applied to single units or groups.

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.

Adaptation and Learning - C++

The C++ portion of the project allows the AI to learn and adapt. Once the candidate moves are determined, the AI will rank the moves based on evaluation functions. The actual evaluation functions will be written in Formula AI, the C++ code should never have to be touch for customization or extension purposes.

There will be two evaluation functions: A team evaluation function, in which the impact of each move on the overall team strategy is evaluated and a unit evaluation function, in which the impact of a move on unit involved is evaluated. The results these functions determine the final evaluation of a move. Once all moves are evaluated, the script is formed based on these evaluations (i.e. best moves first).

At the end of turn, the success of each move is used to adjust a weight associated with that move. The weights are incorporated into the evaluation of moves during the next turn (e.g. weight * (unit_eval(formula) + team_eval(formula))). In this way, the AI can learn from it's mistakes and exploit holes in an opponent's strategy found by successful moves.

Related Papers

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

Retrieved from "https://wiki.wesnoth.org/index.php?title=FormulaAIandDynamicScripting&oldid=70152"
This page was last edited on 16 November 2022, at 03:20.