FormulaAIBaseAI

Introduction

• Basics
  • My name is Bartek Waresiak and I'm from Poland. I'm 21 years old male interested in programming, computer science and gaming. I'm studying Information Technology, 2nd year at AGH University of Science and Technology in Cracow, Poland. By participating in Google Summer of Code I want to become C++ Battle for Wesnoth developer, gain experience in programming for an Open Source project and increase my level of C++ and object-oriented programming knowledge, have fun and earn some money. You can contact me on IRC or forum boards where my nick is Dragonking, or via mail: either dragonking_ATTT_o2_D0T_pl or b.waresiak_ATTT_gmail_D0T_com

• Experience
  • What programs/software have you worked on before?
    • Besides projects for my university (various algorithm-testing training projects), I've been one of Battle for Wesnoth developers since September 2005.
  • Have you developed software in a team environment before? (As opposed to hacking on something on your own)
    • I'm a member of Multiplayer 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?
    • It is my first time applying to Google Summer of Code.
  • What development model would you use (e.g. keywords: V-model, XP programming, agile programming, iterative; with the help of prototyping, formal specifications, tests, etc.).
    • Iterative development model with Unit/Integration tests.

• 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 a Multiplayer Developer for 'Battle for Wesnoth' project I've been one of people responsible for unit balancing (unit statistics tweaking), multiplayer server moderation and basic administration. This work did not involve any C/C++ coding

• 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
  • Did you select a project from our list? If that is the case, what project did you select?
    • I chose to develop the Formula AI.
  • Why did you choose this project?
    • AI has always been weak in Wesnoth, challenging only if provided with big amounts of gold and units. Also sometimes you can see AI-controlled units just getting stuck and not moving. I would like to contribute to creating a good and challenging AI for wesnoth, which would fix some problems with the current one.
  • Include an estimated timeline for your work on the project
    • Milestoned proposed by me are presented below. I think I can start working on the formula system rather soon, since I'm already familiar with Wesnoth community, I have a bit of knowledge about existing Formula AI code and I know gameplay side of Wesnoth really well.
  • Include as much technical detail about your implementation as you can
    • Details can be found in the Idea Description section.
  • What do you expect to gain from this project?
    • Some C++ experience, knowledge about functional programming and AI.
  • What would make you stay in the Wesnoth community after the conclusion of SOC?
    • Since I am one of Wesnoth developers for 2 and half year already, I think that I'll stay with Wesnoth after SoC finishes.

• Practical considerations
  • Are you familiar with any of the following tools?
    • Subversion
      • Yes, about 2-year experience.
    • C++
      • I have more than 1 year of C/C++ experience.
    • Python
      • No.
  • Which tools do you normally use for development? Why do you use them?
    • I'm working on Linux Gentoo,
  • 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?
    • I wouldn't mind.

Idea Description

Required knowledge and talent

• A minimal knowledge of C++ is required, a good knowledge of C++ is desired: I believe I have quite good knowledge of the C++, during the last few weeks when I dug into Formula AI code I managed to understand most of the code and find few bugs by code inspection (see what I commited).
• Good social interaction with a large player community: As a Multiplayer Developer I have a lot gaming experience, knowledge about units statistics, usage, strong and weak sides. I know many tactics and strategies, both general and faction-specific. Proof of that can be fact that I was the winner of the first Wesnoth Tournament of Champions.

Detailed project description

As I see it, Formula AI project consists of 3 parts, which would be done step by step and rather concurrently. Each of these parts is important. some things can't be done before earlier completion of other goals.

C++ part

In my opinion C++ part of the project would be:

• expanding capabilities of functional language of the Formula AI - adding needed operators, functions, implementing lazy lists etc.
• expanding capabilities of Formula AI by adding more commands
• writing external tools for work with Formula system:
  • Unit/Integration tests which would check if formulas return expected results and ensure that system works correctly;
  • command line so simple formulas could be evaluated without need of running them within Wesnoth
• debugging and optimizing current and future Formula code

Formula part

Formula part would consist of 2 things:

• pluggable Base Formula AI itself, which should be a challenging AI opponent able to fight on any kind of map
• set of external rules/formulas - either from our 'formulas database' or user-created, which could make AI behave in a specific, preffered way

Maybe I'll start with the latter:

Plugability

First of all Formula System should be fairly easily extendable by people with no knowledge about programming. To achieve this good documentation and base with some 'official' formulas shipped with wesnoth are needed. This would allow scenario creators to do things like:

• Improve general AI efficiency on any map, by giving advices like what to recruit/what to not recruit, how to make good opening moves, which part of map should AI focus on more etc. One of possible examples could be to make AI move leader to keep which is closer to the battlefield, so needed reinforcements could reach enemy sooner.
• Set how aggressive/defensive the AI should be.
• Make AI focus on a given task like protect some unit, protect some place (bridge, mountain, ...), attack some specific unit or types of units, etc. Important is to make sure that specific task could be given to one, or any number of units, or even AI as a whole.
  • EDIT: After I commited Unit Formulas it is now possible to define formula for a single unit which completely determines what this unit is supposed to do.
• and many many more

Note that keeping in touch with scenario developers and our WML experts is important - since this system should be useful for them, they should decide about many aspects and possibilities of the Formula system, and their feedback would be more than appreciated. Also starting a thread on the forum boards with questions what other Campaign Developers would expect from the new Formula System seems to be a good idea.

Base Formula AI

As for the base Formula AI, I would divide its development into 3 stages. Each stage would be an independent AI derived from the previous one, so that scenario designers could choose whether to use a Simple, Average or Advanced Formula AI and eventually tweak it. I would start with basic implementation of below proposals, tweaking, improving and expanding them over a time.

Please not that the list below is a draft of this idea and a work in progress - some things may change/move between the types of AI and new proposals may appear any time.

• Simple Formula AI
  • recruitment patterns - which unit is generally good against opponents units/faction on a certain map. It is important to beside opponents units consider on what kind of terrain AI is supposed to fight on, and what kind of units AI already posses - if it has 3 mages only getting another one against skeletons doesn't seem to be a good idea...
  • terrain advantages and importance of villages - make it stick to good defence terrain, and protect its villages with best units - it is important to note that strong resilient unit is better guardian than fast intelligent one of the same type.
  • importance of experience:
    • make AI kill opponents experienced units
    • make AI accumulate xp and try to deal killing blows with already experienced units
  • importance of healing and ability to retreat - if AI is in bad health shape, and opponent is in good, it is better to give up and move back
  • importance of the leader - protect it at all cost and don't put him into risk
  • awareness of the objective - kill enemy leader
  • ability to attack in way which maximize opponent's damage and minimalize damage taken - so it won't attack a mage with an archer.
  • ability to divide forces between parts of the map according to enemy positions

• Average Formula AI:
  • know how to use of heal, cure, poison, magic, berserk abilities/weapon specials
  • knowledge about offence and defence part of the game and improving unit recruitment and positioning:
    • The basic thing that AI should know was described above - make sure that it will inflict as much damage as possible and take only a little if any. Next thing is to learn with which unit AI should defend - you put melee units against possible melee attackers, and ranged units against possible ranged attackers. AI has to decide if it is attacking or defending on certain part of a map during certain turn.
    • In some way, connected to this is recruiting. If AI has advantage, it may get mage to support attack, but if it is under pressure then getting a fighter could probably be preferable ( there are dozens of examples like this one, important is to make AI aware in what kind of situation it is and how it should react ).
  • importance of experience:
    • If unit lacks only few xp points to the advancement, it may be better to advance it by not killing enemy but by simply fighting.
  • AI should know to try to not "waste" any possibility move: if after a whole turn some units are still unmoved, AI should calculate if there is possibility to do something constructive with them (move to village, heal, attack to gain even 1 point of experience etc. )

• Advanced:
  • be able to use any unit with any kind of special ability
  • be aware of fog of war/shroud
  • have option to try and "push luck" - for example at the very beginning of the MP game when initial luck can result in huge advantage

Documentation part

There isn't much to write about this part: each new Formula System functionality should be documented in the wiki, using simple and understandable for non-technicians language, preferably with an example of usage. If new functionality implements some changes outside Formula System - for example in WML - it also should be documented. Again in this matter, close cooperation with Campaign Developers is desired.

Milestones

In my opinion, there should be plenty of milestones so it is easier to see actual progress of the work. Also smart planning and sheduling increase possibility of success. Finishing some things will take more time than the others, and some may be finished only with cooperation with other people (Multiplayer Developers, Campaign Developers,...)

• Geting fammiliar with Formula AI code: First thing would be to get fammiliar with the current Formula AI code, and prove some knowledge about it by expanding its functionality.

• Finish creation of Simple AI's Recruitment pattern: this step would prove understanding the Formula AI language, and would be basis for future work. The AI would use Frmula System for recruitment and DefaultAI for rest of actions. Up to this point, general idea how Formula AI and its Plugins System will look like should be ready. Note that cooperation with Multiplayer Community is needed for successful comletion of this milestone.

• Expand Simple AI - make Simple AI move and attack on its own, be aware of the enemy and being able to make decisions in relativly short time. At this point basic customization (i.e. how agressive AI is) should be possible. This milestone is one of the most difficult ones and will most likely take a lot of time (probably good as mid-term goal).

• Implementation of the Average AI formulas, and expanding set of possible tweaks to the AI. At this point it is far more important to be able to tweak AI as needed, than having Formula AI win agaisnt Default one. Need to remember to keep documentation up to date.

• Finishing all formulas for the Average AI, and making it fight (in the worst possible scenario) at the equal terms with current default AI.

Later comes tweaking the existing formulas, improving documentation, writing more complex formulas...

Timeline

According to Google SoC timeline:

April 14 - May 26: Community Bonding Period - students get to know mentors, read documentation, get up to speed to begin working on their projects.

May 26 - July 14: Students are coding for their GSoC projects. July 14 is also final date to submit mid-term evaluation.

The time between April and July will be most difficult one for me - I have classes on my university so I would be able to spend only 1-3 days per week to work on SoC project. But since I already know community well, and got into Formula AI code and its docummentation, I can start working on idea itself immidiately just after the begining of the 'Community Bonding Period', thus before July 14 mid-term goals should be achieved.

It is hard to set exact dates for each part of the Formula AI, since some ideas may evolve and change.

For sure first thing to do will be recruitment patterns for AI. It is one of top important parts of new AI and it will take much time to create good algorithm, test it and refine it. It will also bring new functionality to the Formula System itself, prividing further work much more easier (functions to evaluate game state, unit vs unit efficency, unit efficency on a certain map etc...).

• first three weeks of april: AI recruitment formula and needed functions should be ready
• last week of april, first half of may: testing and fine-tuning the recruitment formula and functions

Then work on completing another Simple AI goals will begin. Also next part of timeline will be presented then, according to progress of the development (if I'll reach previous goals earlier then expected some goals can be extened or added). Optimal thing to achieve before mid-term evaluation would be having AI which can recruit well on any given map, know importance of villages and good defense tarrain. AI also should not get stuck, like current C++ AI often does. Besides that, basic set of options allowing Campaign and Scenario Developers customize their AIs should be available.

July 14 - August 18: I have summer break then, so working _full_ time (which may mean more than 8h per day) for Wesnoth wouldn't be a problem. Note that I may want to take a break (upon earlier agreement) for about a week during that time, but I consider that it should not be a problem since outside of that I'll have whole days to work on Formula System.

Before the final evaluation goals from Simple AI and most important ones from Advanced AI should be achieved. Formula AI should be able to fight on any given map and do _at_least_ as well as the current C++ AI does. Of course it will surpass it in terms of being simply and widely customizable.

After SoC I plan to continue to mantain and improve Formula System.

AI recruitment

Idea

My proposal for building customizable recruit algorithm for an AI:

• Calculate unit effectivness on a map. If it isn't defined by a scenario designer, it is calculated by an internal function. Outcome is represented by a map: pair of unit and a number between 0 and 100 (0 - unit is bad, 100 - unit is great).

• Create list of enemy units (get_enemy_units()): if enemy has no gold (or only a little), look only for units on a map, otherwise check also units that opponent may get.

• Take list of our units, effectivness and list of enemy units (both caluclated earlier). Then put them into evaluate_attackers() and evaluate_defenders(). Result are two maps, with list of our units and information how good defenders/attackers these units are

• Execute eval() function - this function can be defined by a scenario designer. Function returns number between 0 and 100 (0 - we are losing, 100 - we are winning).

• Execute recruit_list_builder(): use result of eval(), to determine how many attackers/defenders we need and build output map with needed units, and information how important these units are.

• Unit_choser() - compare units that we already have with list of units that we need, chose unit that is best one to get now.

This is idea for now. Building a good recruitment algorithm will take much time, and require a lot of testing. Many of chosed now solutions may change.

Progress

These things are needed to be done in order to implement recruting algorithm for an AI:

• Add support for a 'map' type to the Formula System, and implement operator [] (done - please look at My commits)

• Implement needed functions (names may change, some more functions may be added): (in progress)
  • eval() and evaluate()
  • units_effectivness()
  • evaluate_attackers()
  • evaluate_defenders()
  • recruit_list_builder()
  • unit_chooser()
  • units_stats_eval()
  • villages_eval()

• Test functions and outcomes, tweak algorithm in order to get best results.

My commits

My commits to Formula System ordered by date:

• Some basic variant bug fixes [1] [2] [3]
• Improved performance of formula tokenizer [4]
• Added unit formulas (more info: FormulaAI#Unit_Formulas) [5]
• Small fixes, improvements etc. : [6] [7] [8] [9]
• New functions: [10] [11]
• More powerful formula command line (you can now move, recruit and attack using it): [12] [13]
• Added support for 'map' to the Formula System [14]
• Implemented operator [], and two functions which operate on a map [15]

Besides above, I have been working on improving the FormulaAI documentation.