FormulaAISoC2009Dragonking

Introduction

• Basics
  • Write a small introduction to yourself.
    • My name is Bartek Waresiak and I'm from Poland. I'm 22 years old male interested in programming, computer science and gaming. I have been Battle for Wesnoth player for more than 5 years, and developer for about 4 years (coder since Summer of Code 2008).
  • State your preferred email address.
    • Either dragonking_ATTT_o2_D0T_pl or b.waresiak_ATTT_gmail_D0T_com
  • If you have chosen a nick for IRC and Wesnoth forums, what is it?
    • Dragonking
  • Why do you want to participate in summer of code?
    • By participating in Google Summer of Code I want to significantly increase amount of time that I spend working for Battle for Wesnoth, have some fun and earn some money.
  • What are you studying, subject, level and school?
    • I'm studying Information Technology, 3nd year at AGH University of Science and Technology in Cracow, Poland.
  • If you have contributed any patches to Wesnoth, please list them below. You can also list patches that have been submitted but not committed yet and patches that have not been specifically written for Wesnoth. If you have gained commit access to our SVN (during the evaluation period or earlier) please state so.
    • I have access to SVN. My recent contributions to Wesnoth: my contributions

• Experience
  • What programs/software have you worked on before?
    • I've been one of Battle for Wesnoth developers since September 2005 and I have been working on FormulaAI language since Summer of Code 2008. Besides that, I wrote various projects for my university (algorithm-testing, training projects, optimalization tasks, etc...).
  • Have you developed software in a team environment before? (As opposed to hacking on something on your own)
    • I'm one of Developers in 'Battle for Wesnoth' project and I have experience in group decision making.
  • Have you participated to the Google Summer of Code before? As a mentor or a student? In what project? Were you successful? If not, why?
    • I had been participatin in Google Summer of Code 2008, workin on Formula AI for Battle for Wesnoth project. My project was successful.

• Open Source
  • Are you already involved with any open source development projects? If yes, please describe the project and the scope of your involvement.
    • As Developer for Battle for Wesnoth project I've been responsible for developing, improving, testing and documentation of the FormulaAI language. Besides that, I've been supporting people trying to use this language in their scenarios/campaigns. Previously, as a Multiplayer Developer I've been one of people responsible for unit balancing (unit statistics tweaking), multiplayer server moderation and basic administration.

• Gaming experience
  • Are you a gamer?
    • Yes, I like to play various types of games: strategy games - both real time and turn-based, role-playing games and some of the first person shooters. I'm rather patient and calm player and I enjoy difficult games which require some amount of 'hard thinking'.
  • What type of opponents do you prefer?
    • I prefer human opponents much more than AI, but they have to be polite, civil and mature. I really enjoy games against experienced player, though I don't mind also tutoring new ones.
  • Are you more interested in story or gameplay?
    • I value both - IMHO to bring a game to someone's attention, it must have a decent gameplay. If it has a nice storyline as well, then chances that players will keep playing and won't leave increase.
  • Have you played Wesnoth? If so, tell us roughly for how long and whether you lean towards single player or multiplayer.
    • I have been playing Wesnoth since about 0.7 version, mainly multiplayer because I enjoy Wesnoth players community and recognize it as polite and mature one. Also, like I mentioned, multiplayer games against human opponents are for me much more enjoyable than single-player campaigns.

• Communication skills
  • Though most of our developers are not native English speakers, English is the project's working language. Describe your fluency level in written English.
    • I have no problem with understanding written English, and describing my thoughts to the others in this language.
  • Are you good at interacting with other players? Our developer community is friendly, but the player community can be a bit rough.
    • I think I know Wesnoth developers and players community well, and I've always been trying to always be on good terms with everyone. I know whom to talk to about different issues and who can give me needed advice or support. I also have quite a lot experience with interacting with multiplayer community.
  • Do you give constructive advice?
    • When giving advice, I try to be as detailed as possible, and make sure that people who I direct advice to understand me well. I am aware that during the internet chat you can be misinterpreted and your advice may instead be received as a negative criticism, I'm trying to avoid it by being friendly towards others.
  • Do you receive advice well?
    • I know that I can be wrong and that around me many people are far more experienced than me, I consider advices from others as a good thing which helps me improve and develop my skills.
  • Are you good at sorting useful criticisms from useless ones?
    • I have to admit it is hard to receive bad criticism - if someone is telling you that you are plain wrong, but is not providing any arguments to back up his opinion, then usually this kind of criticism is a useless one. If someone can criticize what I am doing providing examples what is wrong and how it can be improved - it is definitely an example of useful and desired criticism.

• Project

Described below.

• Practical considerations
  • AAre you familiar with any of the following tools or languages?
    • Subversion
      • Yes, about 3-year experience.
    • C++
      • I have more than 2 years of C/C++ experience.
    • Python
      • No.
  • Which tools do you normally use for development? Why do you use them?
    • I'm working on Debian Linux.
  • What programming languages are you fluent in?
    • C/C++ and Java.
  • What spoken languages are you fluent in?
    • Polish - which is my mother tongue, and English.
  • At what hours are you awake (please specify in UTC)
    • Usually I'm awake between 8 and 23 UTC, and available on IRC betweeen 17 and 23 UTC.
  • Would you mind talking with your mentor on telephone / internet phone? We would like to have a backup way for communications for the case that somehow emails and IRC do fail.
    • I wouldn't mind.

Idea Description

Why FormulaAI?

I have been working on FormulaAI for a while now - bugfixing, new functions, new features, testing, etc. I know the existing code well. I'm also experienced wesnoth player and I know many various strategies/tactics. I have really strong understanding of different aspects of the game, what is definitely a desired thing if one wants to work on improving the AI. Besides that, formula AI language can be used by other people to write their own simple AI - and I do enjoy helping others who want learn this language.

Let's start from what is proposed...

In the wiki, and after some talks on the IRC, I can see 2 proposed ideas: first is Formula AI library, with functions that user could include and use. Second one is AI written in FormulaAI language that improves current C++ and can beat it. I consider first idea to be too general one. I find it hard to define milestones and find reasonable ideas for functions. In my opinion, such thing is not good to choose for SoC, when you have to write something useful in limited amount of time, but should grow slowly, based on what people who actually use formula AI need.

Then, why not AI ?

Second proposal is similar to the one form year ago. Because I was one of the people working on this during SoC 2008, I can see some problems with this idea. First problem I encountered year ago, was FormulaAI language itself - it was not developed enough for such a big task at that time, and because of that I was forced to focus on improving language itself rather than working on the AI. I believe that in current state of FormulaAI language designing AI could be easier, but still would be disturbed by bugfixing. Second problem I can see, is that I don't believe that general wesnoth AI can be written in FormulaAI language alone. It can work perfectly for some scenario where you need a specific-purpose AI, but not for general case, even with current approach of candidate moves/side formulas because of how complicated AI in wesnoth must be. And third thing: recently DarthFool and Sirp presented some interesting ideas of re-developing AI for wesnoth. Both of them mentioned, that formulas written in formula AI language could be used as plugins to the AI - difference between current implementation and their ideas would be that we could better design the relation between C++ AI and formulas - not make formula AI and then fallback to default "stupid" one like it is only possible now. And this leads to what I would like to do during Summer of Code:

Straight to the point

I would like to focus on improving and extending the formulaAI language during Google Summer of Code 2009. First, because it could be later used to "support" creating better default AI, second, because 1.6 is first stable release in which formula AI is available for campaign designers. I know that it may sound a bit "general" and it may be hard to consider good tasks and milestones, but I believe that with my experience from previous GSoC I can propose reasonable approach. Generally, I would work on my ideas for formula AI language, and in between, I would fix some bugs and help people around using formula AI. It is hard to define now how much time fixing bugs/helping others will take, so I don't want to base my evaluation on that. I just want to note that there may be a need to alter my milestones/timeline (like last year's SoC showed us). But to give you some detail that I do know what I want to do...

Things to implement to formula engine

'on_fail' formulas

Background

Current problem with formula language is: what if there no no room for recruitment but we still send order to recruit? Or we send recruit order, but with unknown/incorrect unit name? ATM, formula treats it as an invalid move, so all loop-type formulas are cancelled. This is not a good approach, because order itself is valid, just it contains incorrect data.

Solution

I propose "on_fail" formula, available both for side and for unit formulas. Basic example is:

move="recruit('Skeleton Archer')"
on_fail="fallback()"

If we cannot recruit Skeleton Archer, then we just fallaback to default AI. But there's more - to give proper info about what happened, the "error" and "errdsc" side variables would be set to allow trace the problem, thus we could use on_fail formulas like that:

on_fail="if(vars.error = 'recruitment', 
           if( vars.errdsc = 'no_space', find_nearest_free_keep(), var.errdsc = 'unknown_unit', something_else() ), fallback() )"

There would be different types of errors and errdscs - depending on what caused the problem. on_fail formulas would support recruit, move, move_partial and attack formula orders.

Fractions

Background

Currently formula language does not support fractions like 0.25, so formula like "1/2" is evaluated to 0.

Solution

I would implement simple fractions - by simple I mean that these fraction would have only 2 decimal places. So "1/3" would result in 0.33. Such simplified solution should be enough for formula AI, and still will make writing formulas more intuitive. This change would lead to implementing new variant TYPE_FRACTION and of course various rounding functions like round(), floor(), ceil().

New operators for list/map operations

Background

We lack good way of simply doing some math operations on values inside lists and maps.

Solution

I propose something like that:

[ 1, 2, 3 ] .+ [ 7, 6, 5 ]

Operator .+ would just sum up values of above lists, and return new one of the same size:

[ 8, 8, 8 ]

Simmilar operators would be .- .* and ./

In case of map, operator .+ would work in simmilar way, just for values:

[ 'elf' -> 10, 'dwarf' -> 20 ] .+ [ 'elf' -> 30, 'dwarf'-> 40, 'skeleton' -> 5 ]

would return

[ 'elf' -> 40, 'dwarf'-> 60, 'skeleton' -> 5 ]

So values of the same keys are added, if key is non-existent in one of the maps, it is treated like it has value of 0 in this map.

Candidate moves ideas

Generic "three part" formula ( based on what boucman proposed )

This kind of candidate move would look like that:

name=something
type=three_part
precondition="calculate_units()"
evaluation="eval()"
actions="action()"

precondition would be used to create vector or map with units. Then based on outcome, evaluation would be run, and finally, action. Thanks ot that, we could add some flexibility to candidate moves system. I already can see that probably some new functions that operate on a map will be needed. Example usage:

precondition="[ tomap( my_leader, enemy_units ) ]"

Assuming we extend "tomap" functionality it could return map like

[ my_leader -> unit1, my_leader -> unit2, ... ]

Then we would take keys and values and do pair evaluation:

my_leader <-> unit1
my_leader <-> unit2
....

'support' type candidate move

Simple idea, simmilar to "attack" candidate move, just working for 2 units of the same side.

Precondition formula

Background

Currently, when we have attack candidate move with eval like:

name=my_candidate_move
evaluation="if( me.hitpoints > 30, evaluate_me_and_target(), -1 )"

It is evaluated for each friendly unit m times - where m is number of enemies. And after one valuation, it can be evaluated again - and that happens j+1 times, where j is number of units for which different evals returned score > 0. This is quite not optimal solution.

Solution

I want to add precondition formula, which would be evaluated once for every unit, so above example coulbe be replaced with:

precondition="if(me.hitpoints > 30, 1, -1)"
evaluation="evaluate_me_and_target()"

For each my unit precondition will be run once, and only if it returns score > 0, evaluation will be executed m times (for every enemy unit). I think that assuming we can have 10+ candidate moves, and more than 50 units on a map, we should consider implementing it.

FormulaAI improved logs

This idea is about making formula AI more verbose, and allow it to take advantage of different log levels:

info level would provide information about executed orders

warning level would provide info about possible type errors

error level would provide info about moves that caused formula to run on_fail formula

More info for FormulaAI

To know where we or anamy can move, we can use now my_moves and enemy_moves. But we lack info about how far we can move if we for example kill one unit. For that I would like to add functions that return info about individual unit range, and AI members that could inform about the same, just for all units - my_range, enemy_range.

Add option to choose FormulaAI as alternative AI

That idea requires taking care of two things:

First, add option to choose formula AI, which would be at the beggining defaul AI with my recruting algorithm. Second - allow user data to overwrite default ai settings while creating multiplayer scenarios with custom formula - that is not yet possible.

Other ideas

I had few different ideas, regarding writing formulas and making that and testing easier, but currently other students (well, mainly Crab :) ) are working on some patches to do exactly that, so I'll focus on what I've written above, to not duplicate their work.

Things to write with FormulaAI language

Recruitment formula

I believe that to spot bugs and think about good new features and functions that should be added, usage of the formula AI is needed. As I wrote before, I don't think that writing whole AI in formula AI makes much sense, and that it is hard to create good general function library. That's why I would like to continue work on the recruitment formula, based on my last year proposal: FormulaAIBaseAI#AI_recruitment but modified and improved.

First questions that may come to your mind are probably "Is this formula really needed?", "Will it really bring some improvement?" or "Will it be really useful after re-designing of the whole AI?".

Recent testing of this formula showed that it is quite useful and generally recruits better than default AI. It does not exactly mean that default AI that uses this formula is always doing better - no, because even if we provide current AI with most useful set of units, it may still suicide some of them with stupid moves. But it brings at least some improvement. And what's most important - since in both Dave's and DartFool's proposal they mentioned possibility of using formula AI, then this recruitment formula will work with "new" AIs as well.

Recruting in SP

One of the problems is how to make recruting customizable for scenario designers and campaigns developers. In that matter, cooperation with campaign developers is needed, since there are people who are supposed to use it. I already did some talking about this idea and scenario developers needs with zookeeper.

My idea is to re-organize recruitment code, categorize functions and put these into fai file that one could include to their scenarios and make use of some default functions. For example if one wants to have AI recruit army, that consists of 60% elvish fighters, 30% elvish archers and 10% mages, he would just write:

{data/AI/formula/lib/recruitment.fai}
recruit_army( [ 'Elvish Fighter' -> 60, 'Elvish archer' -> 30, 'Mage' -> 10 ], self )

Function would check for current unit ratio and try to recruit most needed units first, according to the specified map. Variations of above will be possible, for example:

• recruiting one set of units between turns 1 and 10 and different one later
• making side 2 seem to recruit only units good agaisnt side 3, and side 1 recruit agaisnt side 4
• much more...

all easy to achieve with some if() conditions.

Also it would be good idea to take into account units "usage" attribute:

{data/AI/formula/lib/recruitment.fai}
recruit_army_by_usage( [ 'fighter' -> 60, 'archer' -> 30, 'scout' -> 10 ], self )

Other example is trying to get good defensive set of units:

{data/AI/formula/lib/recruitment.fai}
recruit_army( calculate_defenders(self), self )

There would be set of functions, documented in the wiki and ready to use. Of course for some specific purposes someone may need combining some custom rate_effectivness function with these provided by us. Example usage where we get units good against side 3 and good in forest:

{data/AI/formula/lib/recruitment.fai}

def rate_units_in_forest(ai*) # custom function that returns map of unit -> score #
 ...;

recruit_army( combine_ratings( calculate_defenders(self),rate_units_in_forest(self) ), self )

Of course custom function must meet some conditions, but these would be specified in the "recruitment wiki" with some examples. Some additional function to "normalize" score values could be use as well.

Recruting in MP

Recruting in multiplayer would be based on this library as well. To get desired set of functions and good set of recruting options, testing is needed. I would like to create table of units "ratings" against different factions, and of course play some games to test how recruiting works in certain situations.

Leader candidate move

Recruiting is connected with leader control, because we can recruit only if leader is in the keep. I'd like to introduce leader control candidate move, that could control the leader and take use for example of multiple available keeps, make use of it's abilities, etc. For example leader control itself could return set of orders to execute to make use of leadership ability.

Candidate moves formulas

Besides recruitment formula I'd like to add some candidate moves to improve AI with some candidate moves:

• Candidate moves that I would like to have:
  • Scouting candidate move
    • Such candidate move exists already, just in not to well tested and remains unmaintained. I believe it is good idea to try to add it to the AI.
  • Poisoners candidate move
    • Velory already wrote this candidate move. This also could be added to support default AI and when tested, maybe tweaked a bit (eval formula probably has the biggest impact on how effective this function is).
• Candidate moves that I would like to test:
  • Berserker candidate move
    • Candidate move for this unit could probably improve how AI now uses these units. I believe that candidate move would be just temporary solution, because such special units should be treated by the AI in completely different way and be considered as really precious ones that AI should try to screen well.
  • Levelup candidate move
    • Also one of candidate moves that we already have in our repository - also one that is not maintained anymore. I'd like to check whether it works properly and maybe tweak it.

So far I can think only about adding above candidate moves to support the AI, I somehow doubt that altering what healers and units with low hp do will have good influence on the AI.

Developer games

We need testing, that's why I would like to organize from time to time (starting from around midterm evaluation) regular developer games to test the formula AI, exchange ideas and of course have some fun. Games would be simmilar to these we used to play some time ago: developers against AI.

My contributions

Up to one month before releasing 1.6

More important and significant changes

• Implemented pathfinding especially for formula AI to make functions move and move_partial work properly and be intuitive [1][2][3][4]
• Fixed candidate moves crash wesnoth every time there was an error in the formula [5]
• Made unit loop formulas work even when no unit formula is specified [6]
• Candidate moves and general side formula now work besides each other, not instead [7]
• Added support for prorities for unit formulas, fixed candidate moves bug that made it execute first moves with *lowest* score, initial unit modification to prepare it for on_fail formula support.[8]
• Added [ai] tag to single unit WML, renamed [ai_vars] to [vars], renamed 'faifile' keyword to 'fai', added new keyword: end. Fixed bug that caused some unit variables be saved to file incorrectly. Removed obsolete formula test case. [9]
• Added new formula function castle_locs [10]

Various fixes and improvements

• Disable formula AI in multiplayer [11]
• Fixed candidate moves into infinite loop bug [12]
• Fix for attack function and some overall improvements [13][14]
• Made formula AI unit members correspond to these in SingleUnitWML [15]
• Fixed formula parser bug [16]
• Fixed formula operator '.' bug [17]
• Made [function] WML tag for formula work [18]
• Improved formula test scenario [19]
• Moved adjacent_locs form location object to separate function and fixed it. Fixed attack() function. [20]
• Fixed buggy 'special' attack object member [21]
• Formula AI parser bug causing where keyword crash wesnoth when 'self' was used in the formula [22]
• Fixed defense_on function [23]

Other contributions

• Wrote partol formula for 16th scenario of 'Legend of Wesmere' [24][25]

Milestones/Timeline

Like last year, I'll have limited amount of free time till I finish all of my exams (around end of June). So there will be time when I will work for wesnoth for about 3-4 dais straight in a row, but there will be also some when I won't touch the code for even one week. I plan finis about 1/3 work before midterm evaluation, and focus on the rest after it, during July and August when I'll have a lot of free time just for wesnoth. Lat year it was not a problem at all.

Things to finish before midtime evaluation

• Redesign recruitment formula and make simple library from it
• Redesign how evaluation of unit effectivness works
• Code on fail formulas for units, side, candidate moves, design error reporting standard and document it, use it
• Implement one or two proposed code functionality
• Reorganize rercuitment= formula o work more like a move= formula
• Attach some simple recruitment formula to multiplayer scenario
• Play developer game around

Goals for the final evaluation

• Play more developer games to test different recruitment approaches.
• Make good recruitment formula for MP (comments from noy and Soliton and other people will be helpful)
  • NOTE - this milestone is a HUGE one due to amount of things that we need to take into account:
    • Size of a map
    • number of villages
    • average defense/movement cost
    • enemy strength
    • AI current strength
    • abilities/weapon special bonuses
    • many more...
• Finish documentation of recruitment library
• Implement all of proposed code functionality

Above expectations

• Design "Leader formula" to control leader
• Make recruit formula smartly position recruted units