FormulaAI

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.

Location

The Wesnoth Formula AI Branch is currently in SVN under branches/formula-ai. It 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 Access

To attempt to make it convenient to debug formulas, one can run formulas from within Wesnoth, and see the results. To run a formula from the Formula AI branch, just type 'f'. A command textbox will appear, where you can type a formula, and the results will be printed. For instance, try pressing 'f' and then type "8 + 4" and the result, "12" will appear. You can now use Wesnoth like a calculator. :-)

Formula Basics

The Formula language supports basic arithmetic operations, such as +, -, *, /, etc. It also supports equality, = and !=, and comparison operators, <, >, <=, and >=. 'false' values are 0 (integer) and null. Other values are true. It supports integers but does NOT support decimal or floating point numbers.

It also supports common operators such as and, or, and not. These are examples of valid formulas

4 + 8*7 (evaluates to 60) (4 + 8)*7 (evaluates to 84) 5 and 0 (evaluates to 0)

AI Formula Language

Of course, 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 textbox 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.

Functions

The formula language contains a large number of built-in functions which allow you to carry out all kinds of complex tasks. A simple example of a function is the 'if' function. The 'if' function takes three parameters; if the first parameter is true, the function will evaluate to being equal to its second input, otherwise it will evaluate to being equal to its third input.

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'))"

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

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).

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.