FormulaAI

From The Battle for Wesnoth Wiki
Revision as of 22:13, 24 March 2008 by Dragonking (talk | contribs)

Overview

The Wesnoth Formula AI is an attempt to develop an AI framework for Wesnoth that allows easy and fun development and modification of AIs for Wesnoth.

Wesnoth already has support for AIs written in Python, but writing AIs in Python has a couple of problems:

  • it's still rather difficult, especially for a non-programmer, to develop an AI, even in Python
  • Python is insecure; a malicious trojan horse Python script masquerading as an AI could do untold damage

The Wesnoth Formula AI aims to create a fairly simple, pure functional language which allows one to implement an AI. It also aims to allow AIs to be tweaked and modified by people with relatively little technical skill; anyone who can use WML should also be able to use the Formula AI to tweak an AI to make the AI in a scenario behave how they want.

The Wesnoth Formula AI is currently in an experimental stage of development. One can play with it and develop a rudimentary AI. Feedback is appreciated.

To develop an AI using the Formula AI, set ai_algorithm=formula_ai in [side].

Approach

To use the Formula AI, one should put an [ai] tag inside the [side] tag. Inside this [ai] tag, one should specify the 'move' attribute to be a formula which specifies what movement the AI will make. Each time it's the AI's move, this formula will be run, and the move it results in will be executed. Then the formula will be run again; it'll continue to be run until it stops producing a valid move, at which point the AI will end its turn. Alternatively there is a command that the formula may return which will make it end its turn immediately.

A sample AI which does nothing but recruit Wolf Riders is as follows:

[side]
...
ai_algorithm=formula_ai
  [ai]
  move="recruit('Wolf Rider')"
  [/ai]
[/side]

Formula Command Line

To attempt to make it convenient to debug formulas, one can run formulas from within Wesnoth, and see the results. To run a formula, just start game and type 'f'. A command textbox will appear, where you can type a formula, and the results will be printed. For instance, typing

8 + 4 

will result in "12" appearing on the screen. You can now use Wesnoth like a calculator. :-)

Formula Basics

  • The Formula language supports basic arithmetic operations, such as: +, -, *, /, % and ^. It supports integers but does NOT support decimal or floating point numbers. For example:
4 + 8*7     #evaluates to 60
(4 + 8)*7   #evaluates to 84
8 % 6       #evaluates to 2
5 / 2       #evaluates to 2
3 ^ 2       #evaluates to 9
  • It also supports equality, = and !=, and comparison operators, <, >, <=, and >=. 'false' values are 0 (integer) and null. Other values are true. It also supports common operators such as and, or, and not:
2 = 4     #evaluates to 0
2 <= 3    #evaluates to 1
0 != 1    #evaluates to 1
not 4     #evaluates to 0
not 0     #evaluates to 1
(2 < 4) and (3 > 6)    #evaluates to 1 and 0 which evaluates to 0
(2 < 4) or (3 > 6)     #evaluates to 1 or 0 which evaluates to 1
  • Formula language supports also 'dice' operator 'd'. Example usage is:
3d5

Which will give you one of results of rolling three five-sided dice (so random number between 3 and 15).

Data Types

AI Formula Language

Overview

The formula language must be able to access information about the scenario being played to make intelligent decisions. Thus there are various 'inputs' that one may access. A simple example of an input is the turn number one is on, given by the input, 'turn'. Try bringing up the formula command line using 'f' and then type in

turn

The AI will print out the current turn number the game is on.

The 'turn' input is a simple integer. However, some inputs are complex types which contain other inputs, or which may be lists of inputs. For instance, the input 'my_units' contains a list of all the AI's units.

A complex input such as a unit will contain a variety of inputs inside it. If one has a unit input, called 'u' for instance, one can access the 'x' co-ordinate of that unit by using u.loc.x -- u.loc accesses the 'location' object inside the 'unit' object, and the 'location' object contains 'x' and 'y' inputs inside it, which are the x and y co-ordinate of the unit.

Built-in functions

The formula language contains a large number of built-in functions which allow you to carry out all kinds of complex tasks. Syntax used to explain functions usage in this document is:

<result> = <function name>( <comma-separated list of parameters> [, <comma-separated list of optional parameters] )

Function may return <result> as:

  • <variable> - any of the supported variable types
  • <boolean> - false ( 0 or null ) or true ( 1 )
  • <unit> - unit
  • <location> - place on a gamemap
  • <action> - object, which, if later passed to 'move= ' as the result of formula evaluation, make the AI perform a desired action.
  • <result> - any of the above

Also function may return only single argument, or be able to return a whole list.

There are a wide variety of functions which can be used to accomplish many different tasks. You can also define your own functions.

'attack' function

<action> = attack( <attacker's position>, <destination>, <attack location> [,  <weapon> ] )

The first three parameters are locations. At the begining, unit which is standing at <attacker's position> is moved to <destination> place. Then, from that place unit is attacking unit which stands in place marked by <attack location>. Fourth optional parameter is number, and indicates which weapon attacker should use - if not specified, best possible weapon is chosed automatically.

'abs' function

<number> = abs( <input number> )

Function returns absolute value of an <input number>, for example

abs( -5 )

will return 5.

'chance to hit' function

<number> = chance_to_hit( <unit> , <location> )

This function returns how possible ( in % ) it is to hit given <unit> in a specific <location>. For example:

chance_to_hit( my_leader , my_leader.loc )

shows how easy it is to hit your leader has in a place he is currently standing on.

'choose' function

<result> = choose( <input list> , <formula> )

This function evaluates <formula> for each item in the <input list>. Will evaluate to the one item which <formula> gave the highest value. For example:

choose(my_units, level)

gives back the unit with the highest level.

'dir' function

'distance_between' function

'distance_to_nearest_unowned_village' function

'defense_on' function

<number> = defense_on( <unit> , <location> )

This function returns defense rate of given <unit> in a specific <location>. For example:

defense_on( my_leader , my_leader.loc )

shows how good defense your leader has in a place he is currently standing on.

'evaluate_for_position' function

'fallback' function

'filter' function

<reult list> = filter( <input list>, <formula> )

This function will run <formula> on each item in the <input list>. Will evaluate to a <result list> which only contains items the <formula> was true for. For example:

filter(my_units, hitpoints < max_hitpoints)

will return all of your units which have less than maximum hitpoints. For instance this could be used if looking for candidates for healing.

'find' function

'head' function

<variable> = head( <list of variables> )

Head returns first item from the <list of variables>, for example

head( [ 5, 7, 9] )            #returns 5
head( [ 'Orc', 'Human' ] )    #returns 'Orc'

'is_village' function

<boolean> = is_village( <map or ai.map> , <location> )   #1
<boolean> = is_village( <map or ai.map> , <coordinate x> , <coordinate y> )   #2

The first argument is always a 'map' - member of the ai which provides information about the gamemap.

In #1 usage, we put in as a second argument location. In #2, second and third arguments are numbers: coordniates of the certain hex on a map. Function checks if that place is a village, and returns either 1 (yes, it is village) or 0 (no, it isn't village). Example of usage:

is_village( map , loc( 2, 3) )
is_village( map , 2, 3)

Both check, if hex with coordinates 2,3 is a village.

Remember, when using is_village in custom function, you either have to access map by writing 'ai.map', or specify ai as a 'default input'.

'if' function

<result> = if( <condition> , <if true> , <otherwise> )


If the <condition> parameter is true, the function will evaluate to being equal to its second input ( <if true> ), otherwise it will evaluate to being equal to its third input ( <otherwise> ). For instance, an AI that recruits Wolf Riders on the first turn, and Orcish Grunts thereafter might look like this:

move="if(turn = 1, recruit('Wolf Rider'), recruit('Orcish Grunt'))"

'loc' function

<location> = loc( <X number>, <Y number> )

Function will return a location (pair of numbers) from two given input arguments.

'map' function

<result list> = map( <input list> , <formula> )

This function will run <formula> on each item in the <input list>, and evaluate to a new <result list> which contains the same number of items as in <input list>, with the formulas run on each item. For example:

map(my_units, unit.hitpoints) 

will give a list back with the number of hitpoints each unit has. This is more useful in conjunction with other functions.

'max' function

<number> = max( <list of numbers> )

Function will return maximal number from a list,

max( [ 2, 8, -10, 3] )

will return 8.

'max_possible_damage' function

'min' function

<number> = min( <list of numbers> )

Function will return minimal number from a list,

min( [ 3, 7, -2, 6] )

will return -2.

'move' function

<action> = move( <source> , <destination> )

For example unit formula like:

move(me.loc, loc(me.loc.x, me.loc.y - 1) )

will make unit move one hex north.

'recruit' function

<action> = recruit( <unit name> [, <location> ] )

This function results in recruting a unit specifed by <unit name> at first free castle hex, or at given <location>. Function:

recruit('Footpad', loc(3,3) ) 

will result in recruting Footpad at castle hex with coordinates 3,3.

'set_var' function

'size' function

<number> = size( <list of variables> )

This function returns how many variables are stored in a list:

size( [ 5, 7, 9] )                #return 3
size( [ 'Archer', 'Fighter' ] )   #return 2

'sort' function

<result list> = sort( <input list> , <formula> )

This function evaluates to a <result list> sorted according to the comparison <formula> for each item 'a' and its successor 'b'. For instance, sorting units according to hitpoints would be done by:

sort( my_units, a.hitpoints > b.hitpoints )

'sum' function

<number> = sum( <list of numbers> )

This function evaluates to the sum of the items in the <list of numbers>. For example

sum( [ 2, 5, 8] )

returns 15, and:

sum( map( my_units,  max_hitpoints - hitpoints ) )

finds the total damage your units have taken.

'switch' function

'unit_at' function

<unit> = unit_at( <location> ) 

This function takes only one argument - location, and returns unit if there is one standing in that location, or null otherwise. Example of usage:

unit_at( loc( 4, 4) )

'unit_moves' function

<locations list> = unit_moves( <unit location> )

Function returns list of all possible locations which unit standing at <unit location> can reach. If unit can't move, or there is no unit standing at given location, empty list is returned.

'units_can_reach' function

<units list> = units_can_reach( <possible moves list>, <location> )

Function takes as an input list of possible moves ( ai.my_moves for units that belong to AI, or ai.enemy_moves for units that belong to the opponent ) and checks which units from that list can reach <location>.

Custom Functions

  • You can define your own functions. A function is a formula which takes some inputs as parameters. Suppose we wanted to define a function that puts some value on a unit, we might add the following to the [ai] tag:
[function]
name=value_unit
inputs="unit"
formula="unit.hitpoints + unit.level*4"
[/function]

This has defined a new function which takes a 'unit' as an input, and runs the given calculation over it.

  • We can have multiple inputs in our functions, to define them, just create comma-separated inputs list:
inputs="attacker,defender"

This has defined a new function which takes both 'attacker' and 'defender' as an inputs.

  • Sometimes, we use one of our inputs really often in our function - to make our life easier we can make its members (inputs) directly accessible from within the formula. This is improved version of function from above:
[function]
name=value_unit
inputs="unit*"
formula="hitpoints + level*4"
[/function]

As you can see, if we define input with a * char at the end, we make it a 'default input' for a formula. Note, that you can define only one default input per function.

  • It is important to know difference between formulas defined in custom functions, and formula defined by a 'move=' in a [ai] tag. For example, if we want to get info about leader, we write in formula 'my_leader' - which acces member of the AI. To be able to use 'my_leader' in custom functions we have to add 'ai' as an input for our function:
inputs="ai"

allows us to access leader info by writing 'ai.my_leader', or:

inputs="ai*"

allows us to access leader info by simply writing 'my_leader'

Keywords

The formula language has some reserved keywords to provide primitive functionality. Currently the following keywords are defined:

  • where: This keyword is used to defining statements in formulas. You can define multiple comma-separated statements. Syntax:
 <formula> where <comma-separated list of statements>

For example formula:

 a + b where a = 2, b = 4

will give as result 6.

  • functions: Returns a list of all built-in and custom functions available to the AI
  • def: This keyword creates functions using the syntax:
 def function_name(arg1, arg2, ....) function_body

For example,

 def sum(x,y) x + y

creates a function sum taking two arguments and returns their sum.

Lists

The formula language has support for lists. A list is a sequence of values. For instance, 'my_units' is a list of unit objects. A list is represented as square brackets, [], surrounding a comma-seperated list. For instance, [4, 8, 7] is a list of three numbers.

There are various functions which operate on lists:

size(list): number of items in the list EXAMPLE: size(my_units) -- number of units the AI controls

head(list): the first item in the list EXAMPLE: head(my_units) -- the first unit in the list of units.

map(list, formula): will run 'formula' on each item in the list, and evaluate to a new list which contains the same number of items as in 'list', with the formulas run on each item. EXAMPLE: map(my_units, unit.hitpoints) -- will give a list back with the number of hitpoints each unit has. This is more useful in conjunction with other functions.

filter(list, formula): will run 'formula' on each item in the list. Will evaluate to a list which only contains items the formula was true for. EXAMPLE: filter(my_units, hitpoints < max_hitpoints) -- will return all of your units which have less than maximum hitpoints. For instance this could be used if looking for candidates for healing.

sum(list): evaluates to the sum of the items in the list (which all must be numbers) EXAMPLE: sum(map(my_units, max_hitpoints - hitpoints)) -- finds the total damage your units have taken.

max(list) and min(list): evaluates to the maximum or minimum item in the list (which all must be numbers) EXAMPLE: max(my_units, level) -- finds the maximum level of the units you have.

choose(list, formula): evaluates 'formula' for each item in the list. Will evaluate to the item which 'formula' gave the highest value. EXAMPLE: to give back the unit with the highest level, choose(my_units, level).

sort(list, formula): evaluates to a list sorted according to the comparison 'formula' for each item 'a' and its successor 'b'. For instance, sorting units according to hitpoints would be done by sort(my_units, a.hitpoints > b.hitpoints).


Unit Formulas

You san specify a formula for any kind of unit. This is a simple way of doing it:

[unit]
  ...
  formula="move(me.loc, loc(me.loc.x, me.loc.y - 1))"
[/unit]

Custom unit formulas are executed first at the begining of side's turn. Above formula will simply move unit one hex to the north every turn. Note how "me" keyword allows access to unit itself.

You can also define AI unit-specific variables and use them in you formulas:

[unit]
 ...
 formula="if(attack, attack, move(me.loc, choose(unit_moves(me.loc), -distance_between(self, me.vars.guard_loc))))
 where attack = choose(filter(attacks, units = [me.loc] and distance_between(me.vars.guard_loc, target) <= me.vars.guard_radius), avg_damage_inflicted)"
 [ai_vars]
   guard_radius=3
   guard_loc="loc(8,5)"
 [/ai_vars]
[/unit]

This formula will get location position from variable guard_loc and make sure that unit attacks opponent which is 3 hexes (value specified by guard_radius variable) or less from guard_loc.

Types of variables that are supported:

  • number:
variable=3
  • text (important: note the ' ' within " "):
name="'I am variable'"
  • list:
number_list=[ 1, 2, 3]
  • location:
place="loc(X,Y)"