FormulaAIBaseAI

Introduction

• Basics
  • Write a small introduction to yourself.
    • My name is Bartek Waresiak and I'm from Poland. I'm 21 years old man interested with programming, computer science and gaming.
  • State your preferred email address.
    • 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?
    • I want to gain some experience in 'real' programming for an Open Source project and increase my level of C++ and object-oriented programming knowledge while having some fun and earning some money. :)
  • What are you studying, subject, level and school?
    • I'm studying Information Technology, 2nd year at AGH University of Science and Technology in Cracow, Poland.

• 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)
    • Yes, am 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 was one of people responsible for unit balancing, multiplayer server moderation and basic administration.

• Gaming experience
  • Are you a gamer? If so...
    • Yes, I like playing various types of games.
  • What type of gamer are you?
    • Patient and rather calm. I enjoy difficult games which require some amount of 'hard thinking'.
  • What type of games?
    • I like strategy games - both real time and turn-based, role-playing games and some of the first person shooters.
  • What type of opponents do you prefer?
    • Polite, civil, mature and experienced ones, though I don't mind also tutoring new players.
  • Are you more interested in story or gameplay?
    • I value both - IMHO to focus someone's attention to the game, game 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 multiplayers games against human opponents are for me much more enjoyable.

• 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 know Wesnoth developers and players community well, and I've been trying to always be on good terms with everyone. I know who to talk about different issues and who can give me needed advice or support. I have as well quite a lot experience with interacting with multiplayer community.
  • Do you give constructive advice?
    • When giving advice, I'm trying 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 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 Formula AI.
  • If you have invented your own project, please describe the project and the scope.
    • n/a
  • Why did you choose this project?
    • AI was always weak in Wesnoth, able to be challenge only if provided with big amounts of gold and units. I would like to contribute to creating a good and challenging AI for wesnoth.
  • Include an estimated timeline for your work on the project
    • Proposed by me milestones 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 below.
  • 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 be with Wesnoth even long after SoC will finish.

• 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++, Java.
  • What spoken languages are you fluent in?
    • Polish and English.
  • At what hours are you awake (please specify in UTC)
    • 8-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.
• 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 possibilities of functional language of the Formula AI - adding needed operators, functions, implementing lazy lists etc.
• expanding possibilities 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 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, proffered way

Maybe I'll start with the latter:

Plugability

This would able scenario creators to do such 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 should the AI be
• make AI focus on 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.
• and many many more

Important to note here is to keep in touch with scenario developers and out WML experts - since this system should be useful for them, they should decide about many aspects and possibilities of the Formula system, feedback would be more than appreciated. Also starting a thread on the forum boards with questions what other Campaign Developers would expect to be able to do with new AI should be a good idea.

Base Formula AI

As of the Base Formula AI I would divide developing it into 3 stages, each of stage would be independent AI based on a extending of the previous one, and scenario designer could chose if he want to use Simple, Average or Advanced Formula AI, and eventually tweak it.

Please note that below list is a draft of this idea, and a work in progress - some things may change/move between the types of the 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 such way, to 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.
    • Somehow connected to this is recruiting. So there will be need to improve recruiting - if AI has advantage it may get mage to support attack, if it is under pressure, getting fighter could probably be the better idea ( there are dozens of examples, important is to make AI aware in what kind of situation it is and how it should react).
  • importance of experience:
    • If unit lack only few xp points it may be better to advance it by not killing enemy but by simple fighting
  • know to not "waste" any move if possible, if after whole turn some units are unmoved, calculate if there is possibility to do something 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

Each new functionality should be documented in the wiki, preferably with example of usage. 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 sucsess. Finishing some things will take more time than the others, 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...