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 talking on the IRC I can see 2 proposed ideas: first is Formula AI library, with functions that user could inclue and use. Second, is AI written in FormulaAI language, that improves current C++ and can beat it. After some thinking, I consider first idea to be too general one. I find it hard to define milestones, 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 simmilar 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 nee 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

I believe, that to spot bugs and be able to think about new features and functions, usage of formula AI is needed. Besides that ,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 formula AI.

Recruitment formula and leader move

Based on my last year proposal: FormulaAIBaseAI#AI_recruitment

Recent testing of this formula, showed that it is quite useful and generally recruits better than defaul AI. Generally, this time I'd like to extend this formula to make it more loke a "leader control formula". There is still number of things to take into account while recruting for example:

size of the map, units max movement To calculate how many scouts we need, we have to remember that on small maps often we don't need any scouts.

And besides that, some more testing is needed, to tweak bonuses that units get for weapon specials and abilities.

A leader part would be responsible for keeping leader in keep/getting some nearby villages at the beggining. Further improvements may include using some special abilities like healing/poison/leadership - and these need to have higher priority than any used candidate moves.

Candidate moves formulas

I'd like to add some candidate moves for poisoners (I know velory wrote one already, but I have my own idea for that) and scouting evaluation (we already have one now, but also I'd do it a bit in a different way). But this task can wait for now.

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]