Soc2012 Talbot Pierre Refactor Recruitment Algorithm

This page is related to Summer of Code 2012

See the list of Summer of Code 2012 Ideas

This is a Summer of Code 2012 student page

Edit 07/04:

• WML recruiting parameterisation update. Add examples and explanations.
• Update of the "multiple leaders" section.

Description

Talbot Pierre - Refactor Recruitment Algorithm

The current recruitment algorithm is based on a WML recruitment pattern which specify the recruitable units. Apart for scout, no real strategy is established because most of the units are chosen randomly from this pattern list.

I'll dedicate my summer around three axes:

• Multiple leaders: We must manage a list of leaders and free keeps, to affect each leader to a keep and change it if needed (because it's too far from the battle...). AI should choose where an unit (on which castle) will be recruited to be more efficient, taking into account the number of enemy units and their weaknesses.

• Recruiting better units: The units must be chosen for a specific purpose such as getting a village, fighting a specific unit, protecting another... AI should be able to keep in mind the original purpose of an unit to take further decisions. By the way, this design should be discuss with the community and the other GSoC participants because it has a large impact on the entire AI.

• WML parameterisation: The recruitment pattern will be improved to allow scenario editors to be more specific on which units should be recruited.

IRC

trademark

Questionnaire

1) Basics

1.1) Write a small introduction to yourself.

My name is Pierre Talbot, I'm 20 year old. I didn't discovered the programming when I was young, such we often see. Before I dive into this beautiful world I played a lot. I made the most important step in my life 3 years ago when I began my studies.

1.2) State your preferred email address.

ptalbot [at] mopong (dot) net

1.3) If you have chosen a nick for IRC and Wesnoth forums, what is it?

trademark

1.4) Why do you want to participate in summer of code?

It's for two main reasons, the first is the money. The second is to move forward my dream to become a game programmer specialised in artificial intelligence. It's also to meet new people and to discuss around a common passion. It would be the first time I code for a project of this size, I think it's a necessary step to go beyond the programmer amateur and be ready for the real world.

1.5) What are you studying, subject, level and school?

I'm finishing this year my B.Sc. in Computer Science at the University of Claude Bernard Lyon 1.

1.6) What country are you from, at what time are you most likely to be able to join IRC?

I'm from France, so I'll be able to join IRC between 3 am UTC and 6 pm UTC. I'll be the most responsive during in the morning.

1.7) Do you have other commitments for the summer period ? Do you plan to take any vacations ? If yes, when.

I have an internship during the summer, from may to august. I discussed about it with Crab_ on IRC, I asked him if it was feasible and he helps me to do a long term planning.

I'll get up early, around 4-5 am UTC+2 and I will work for Wesnoth until 9 am UTC+2. Without any distraction and with my fresh and rested head. My internship will begin at 10 am UTC+2 and finish at 6 pm UTC+2. I'll go to sleep around 8 pm UTC+2.

The week will be dedicated to code functionalities and the week-end will be reserved to rest myself up and to think about the code design of the next week.

I'm used to work a lot and all the day, my motivation can defeat the rules of time.

2) Experience

2.1) What programs/software have you worked on before?

I mainly developed short programs for school purpose such as a chess-game in C++, a pong and a naval battle in C, an adaptation of the well-known board game "Jungle Speed" in Java. I also code few data structures module such as Hash map, Tree, List,... but also the skip-list, Red-black tree in C. I'm used to work with graph and graph algorithm in C++.

I often code short and efficient programs because I like participate in programming contest. I'm participating for the second year in Prologin, which is an algorithmic French contest. The final is a 36 hours contest where the finalists must code an artificial intelligence of a given subject. I also prepare myself for the regional ACM-ICPC contest in 2012.

2.2) Have you developed software in a team environment before? (As opposed to hacking on something on your own)

Most of the projects I spoke before were in team of 2 or 3 peoples and we used version control software.

2.3) 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?

Yes, I participated as a student in 2011. It was my first real experience. I was accepted in the Boost C++ Library organisation to design and code a check digit verification and computation library oriented "human-error". For example, your credit card number or the ISBN in the back of a book have a check digit. It's not for transmission error control purpose, these checksums are designed to control the human encoding errors.

I successfully finished the summer and continued to develop and work on it during the year studying permitting. My contribution to this organisation is not done yet and I will continue to prepare my library for a Boost review.

I gain a lot of experience in C++ and mostly with some Boost library such as MPL, Test, Iterator, Phoenix, Preprocessor, Range, and all the others I've forgotten that made the programmer life easier. I studied these libraries to be sure to do the most generic library as I can. I also learned to use the Boost chain-tools to document and test.

My mentor was Paul Bristow and we regularly keep in touch since the beginning of GSoC, feel free to contact him here : pbristow [at] hetp.u-net (dot) com.

2.4) Are you already involved with any open source development projects? If yes, please describe the project and the scope of your involvement.

No.

2.5) Gaming experience - Are you a gamer?

I was what we called a "real" gamer few years ago. I play a lot less now as my interests has slipped into the programming. Anyway I love games and this passion will never pass away.

2.5.1) What type of gamer are you?

I'm a gamer who hasn't played a lot of different games. I prefer plays online because I love the competition and progress with my rank.

2.5.2) What type of games?

• Strategy : 400 hours in Warcraft III, rank 647 in Free For All and rank 630 in Arranged team 3vs3.
• CCORPG : 3600 hours in Guild Wars over 4 years. Best rank 497 in 1vs1 (PvP, mode Hero vs Hero).
• FPS : Call of duty 4.
• Race : 100 hours in Trackmania.

There are my prefered games. Currently, when I really need a break, I like to play COD4. I also played few others games I didn't mention because I didn't play these much.

2.5.3) What type of opponents do you prefer?

In my good days, I like the opponent who defeats me, so I can learn from my losses and improved my technical skills.

In my bad days, I don't like to lose and I just want to win. Contradictorily, I don't win a lot these days.

2.5.4) Are you more interested in story or gameplay?

When I don't play online, I think the story is important and I like to enjoy the mainline story. A contrario, when I play online, I prefer a balance gameplay which allow you to create new strategy.

2.5.5) Have you played Wesnoth? If so, tell us roughly for how long and whether you lean towards single player or multiplayer.

I started the campaign and I finished few scenarios. I played about 5 hours. I also played online in a custom game. I'm not good enough to play online as I don't know the units and the strategy used (I've started to watch game replay of experienced gamers).

2.6) 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 GSoC. If you have gained commit access to our SVN (during the evaluation period or earlier) please state so.

A bug: Bug #19538.

While I read the code I improved a function and did a patch: Patch #3236.

3) Communication skills

3.1) 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 only write my program in English (even if there are unimportant) and I document them in English as well. I haven't problem to discuss in English.

3.2) What spoken languages are you fluent in?

French.

3.3) Are you good at interacting with other players? Our developer community is friendly, but the player community can be a bit rough.

I know how the gamers can be, and mostly when they are experimented. I'll try to do my best to be, as soon as possible, an experienced gamer. I treated guys of noob and be treated as well, I've been on the both side so I know what is good to say or not.

3.4) Do you give constructive advice?

I'm member of a French forum "Developpez.com" where I give advices and help people. I'm not always good but I try to respond with precision and completeness, I want to show them all the possible tracks I know.

3.5) Do you receive advice well?

I have difficulties to receive advices from guys of the same level as me, I'm reluctant to follow their ideas if I don't see what's the aimed or the improvement.

From my mentor or an experienced coder, I follow the ideas more easily because I trust them. Anyway, whatever the advices is it, I try to keep my critical. For example, I change my coding style the last year for Boost, I indent with 2-spaces instead of a tab now.

3.6) Are you good at sorting useful criticisms from useless ones?

I think so, because, as explain above, I only fully consider criticisms I understand well.

3.7) How autonomous are you when developing ? Would you rather discuss intensively changes and not start coding until you know what you want to do or would you rather code a proof of concept to "see how it turn out", taking the risk of having it thrown away if it doesn't match what the project want

I like to lay down on paper my ideas to be clear. If I'm really not sure about something, I'll ask for help on IRC, forum,... Otherwise, I code it. I have difficulties to thrown away my code, but I have the feeling that is a better way to take a decision. It's a debate in my head and I'll try to code sooner to "see how it turn out".

4) Project

4.1) Did you select a project from our list? If that is the case, what project did you select? What do you want to especially concentrate on?

I'll answer to be general and than specific. Firstly, I choose this organisation because I'd to be a game programmer and I love strategy game. I choose to do my proposal on the AI part. I'm interested by a project in your list: "AI: Refactor Recruitment Algorithm".

4.2) If you have invented your own project, please describe the project and the scope.

I just create an amateur-project with a friend. It started as a school project, the idea was a Pong with N players where the game board is a geometric form with N sides. We haven't finished it yet, we started it in C with SDL (school limit). We want to code it in C++ with oriented-object paradigm, we need to rethink the application and draw the class diagram, we're currently analysing it with the knowledge of our previous implementation.

4.3) Why did you choose this project?

I choose it because the recruitment is the basis of every strategies and everything remains to be in the current implementation. I think it's such a playground where I can implement all the theory I learn, for example, to practice the data structure and graph theory.

4.4) Include an estimated timeline for your work on the project. Don't forget to mention special things like "I booked holidays between A and B" and "I got an exam at ABC and won't be doing much then".

As I would like to work on this project even if it's not in a GSoC context, the timeline is not exclusively limited to the GSoC period. Anyway the deadlines of GSoC are taking into account.

Date	Description
April	Discover the code, design on paper the current implementation and understand most of the relation between classes... Play a lot and get confident to speak with experienced players.
01/05 to 20/05	Implement the first improvement: "Multiple leaders management", test it with the AI arena and understand the code more in depth.
21/05 to 11/06	Start the coding period. Code the recruitment of units more useful and adapted to the environment. Adapt the code to avoid counter-recruiting, and manage the gold to not necessarily spend it all.
12/06 to 09/07	Support new WML markup, getting closer the scenario editors and the community to understand what should be configurable. What are they thinking it's the most useful ?
10/07 to 01/08	Code and design new members for units to allow them to have a specific goal. A unit should be recruited with a hint of his goal for the other AI part. This should be done in collaboration with the other GSoC student and the community.
02/08 to 24/08	Fully test and document what is not done yet. Discuss with experienced gamers and community about the future improvement and taking into account their advices for the current (and new) recruiting algorithm.
24/08 to ...	Continue to improve and implement new functionalities. I'll continue to work on it studying permitting.

4.5) Include as much technical detail about your implementation as you can

There are few points to refactor. I try to explain these with an incremental approach, the second point shouldn't and often couldn't be realise before the first. This is useful to code & test and directly spot the potential bugs.

The class recruitment_phase and aspect_recruitment_phase are the main classes related to this proposal. But the entire file ai/testing/ca.* and the directory ai/testing/* will be usefull as well. Of course, we are not limited to these files.

During this summer, I'll concentrate my coding around three axes:

• Recruiting with multiple leaders;
• Recruiting better units according to the environment (enemy units, terrain, gold, villages, counter-recruiting,...);
• Allow WML parameterisation for the recruitment, mainly for scenario editors.

Currently, a good part of the AI recruiting algorithm is to choose random units in the recruitment pattern. It only consider scout and count neutral village, so it can calculated how much scouts are needed.

Recruiting with multiple leaders

During the evaluation phase, BAD_SCORE is returned if the first leader is not on keep, if the castle is full or if there is no leader available. During the execution phase, only one leader location is considered.

This is rudimentary, it should at least consider multiple leader. For the moment, if a leader is on the keep BUT is not the first in the internal list, the AI can't recruit this turn.

See the current code:

double recruitment_phase::evaluate()
{
  const unit_map::const_iterator leader = resources::units->find_leader(get_side());
  if(leader == resources::units->end()) {
    return BAD_SCORE;
  }
  if (!resources::game_map->is_keep(leader->get_location())) {
    return BAD_SCORE;
  }
  std::set<map_location> checked_hexes;
  checked_hexes.insert(leader->get_location());
  if (count_free_hexes_in_castle(leader->get_location(), checked_hexes)==0) {
    return BAD_SCORE;
  }
  return get_score();
}

Could be easily transform to something like:

double recruitment_phase::evaluate()
{
  std::vector<unit_iterator> leaders = resources::units->find_leaders(get_side());

  foreach(const unit_iterator& unit_it, leaders) 
  {
    // If the current leader is on the keep.
    if(resources::game_map->is_keep(unit_it->get_location()))
    {
      std::set<map_location> checked_hexes;
      checked_hexes.insert(unit_it->get_location());
      // If there is enough space on the castle.
      if (count_free_hexes_in_castle(unit_it->get_location(), checked_hexes) != 0)
        return get_score();
    }
  }
  return BAD_SCORE;
}

It should also be done in:

• double aspect_recruitment_phase::evaluate()
• void recruitment_phase::execute()

Recruiting better units

As I said before, most of the units are chosen randomly. An analyse of which enemy units are on the map and which units can be recruited should help us to choose better units. AI could recruit the best units against the closest and the most numerous enemies. Another criteria should be considering the units that threaten the leaders. A nice improvement is to consider how much a specific enemy unit cost and to kill them first (if we can't choose from the previous analyses).

However, the AI should not use all the gold, and should maintain reserves for later. In this case, the problem becomes, "when is it later ?". In fact, the AI will recruit to have a balanced army, if a balance army doesn't cost all the gold, it's great. If it uses all the gold, then it's maybe the smartest decision, otherwise we could lose. The expression "balance army" should be defined as well: it means the AI have an army that could beat the current enemy units on the map without recruiting others. The AI army is just a little more powerful that the enemy army.

Each units should have a goal, for example, getting a village, kill a specific category of units, block others (these ideas join other proposals so we'll need to work and discuss together about these parts). This would be implemented such a "hint" member filled during the recruitment process and modify if needed during the next phase. With this hint, an unit is never without goals and further decisions are easier to take. It's a good way to have more than one turn ahead.

WML recruiting parameterisation

The scenario editors would like to control more easily the recruitment phase. WML markup can be implement and the recruitment pattern modify.

I opened a post on the forum to discuss with the scenario editors my ideas.

I'll start with some examples before diving into the specification details.

Firstly, if you want to recruit two scouts in the first turn and two in the second turn, you currently must "play" with the tag modify_ai in an event tag and add a "delete action" when the second turn is over. If you want to recruit again during the fifth and sixth turns, you must open a modify_ai tag and write an "add action". Let's now watch the first simple example:

[ai]
  [aspect]
    id=recruitment
    [facet]
      [recruit]
        id=scout_first
        type=scout
        number=2
        turns=1,2
      [/recruit]
    [/facet]
  [/aspect]
[/ai]

It's naturally simple and we can read it: "Recruit 2 scouts during the turn 1 and 2".

Now, we would like to recruit scouts such as above with 3 fighters during the start of the battle with the constraint that we want to recruit the scouts first and if possible the fighters next.

[ai]
  [aspect]
    id=recruitment
    [facet]
      [recruit]
        id=scout_start
        type=scout
        number=2
        importance=2
        turns=START
      [/recruit]
      [recruit]
        id=fighter_start
        type=fighter
        number=3
        importance=1
        turns=START
      [/recruit]
    [/facet]
  [/aspect]
[/ai]

During the first turn, the AI will firstly recruit the two scouts because the key importance is set on 2 whereas the importance of the fighters is set on 1. So if AI have enough gold and there is enough free space on the castle, it will recruit the fighters until one of these two conditions failed or that we have three fighters. Note that these conditions are also valid for the scouts. You could have noticed the new keyword START saying the we want to recruit only in the start of the battle.

I can introduce an interesting application of all we said. Assuming that we want to develop a survival mode and the AI generates the wave of enemies. We'll say that the AI have unlimited gold:

[ai]  
  [aspect]
    id=recruitment
    [facet]
      [recruit]
        id=scouts_recruit
        type=scout
        number=2
      [/recruit]
      [recruit]
        id=fighters_recruit
        type=fighter
        number=1
        increment=1
        turns=2-END
      [/recruit]
    [/facet]
  [/aspect]
[/ai]

In the first wave, there are only two scouts recruited. In the second wave, two scouts plus one fighter are recruited. In the n wave, two scouts plus (n-1) fighters are recruited.

The importance is not specified as we already know that the AI have unlimited gold (so the AI won't have to choose between potential recruits). We didn't specify the turn either, so it takes the default value "" which means "for all turns". The tag "increment" is equal to 1, for each turn, an additional unit will be recruited. In the example above, a fighter will be recruiting at the turn 2, but at the turn 3, 2 fighters will be recruited and etcetera.

After this first possibilities draft, I'll describe the functionalities.

Inside a recruitment facet

Each recruiting options are specified into a [recruit] tag. Inside this tag the following key can be used:

• id: Important if you need to access it later to modify it.
• type="": (string) This key takes a comma separated list containing the usage or the type of the units that can be recruited. Common usages are: 'scout', 'fighter', 'archer', 'healer' and 'mixed fighter'. If both type and usage are specified, the usage will be considered first, if the type is a subset of an usage, it will be ignored. Otherwise, both are considered. An empty string tells the AI to recruit units according to the internal recruitment algorithm. A random value means to recruit randomly all type of units.
• number=1: (integer) A number greater than 0 will tell the AI to recruit numbers units of type type for each of the turns specified in turns. The INF token can be specify to recruit as much units as we can. If there are other recruit tags with lower importance, there will never be executed.
• increment=0: (integer) number is incremented by increment for each turns specified in turns. If increments=3, number=1 and turns=1, 2 than one unit will be recruited during the first turn and four (1 + 3) during the second turn.
• turns="": (string) This key takes a comma separated list containing number specifying the turns. If an unit should be recruited during the turn 1, 2 and 3, the string should be "1, 2, 3". The macro START, MIDDLE and END can be used, START tell the AI to recruit during the first "1/10" of the total turns, and END during the last "1/10". MIDDLE recruits units after START and before END. A range is specify with the token '-' between two values, for example: 1-3 means "recruit during the turns 1, 2 and 3". It can be used with START and END, but START must be the left value and END the right value.
• importance=0: (integer) The importance of a recruitment tells the AI to firstly recruit units with the highest importance. If gold is lacking or the castle is full, only the most important units will be recruited, the other will be dropped. The increment key will not be applied if the AI cannot recruit all the units specified by number. If two units are equally important, the AI will choose one according to his internal recruitment algorithm.

Tips

• Fill castle if it's not full: The default behaviour is recruiting only the units pattern specify in the recruit tag. You should want to fill the vacant tiles of the castle with random units and with the gold remaining. You can easily do this with:

[ai]
  [aspect]
    id=recruitment
    [facet]
      [recruit]
        id=fill_random
        type=random
        number=INF
      [/recruit]
    [/facet]
  [/aspect]
[/ai]

I've no experience in editing campaign or using the WML markup language, so I'll actively work with the community to do something nice and easy to use. For my part, I'll continue to read the WML documentation and I hope, develop my own AI with these new tags.

4.6) What do you expect to gain from this project?

Some new skills to work on a large project with dozens of developers. To move forward my dream to develop AI in game programming and to improve my C++ code and design.

4.7) What would make you stay in the Wesnoth community after the conclusion of SOC?

If you permit it, I'd like to say what would make me leave after GSoC. If the developer community is not friendly or dead, I won't be able to continue to work on this project, but as I've seen this week, it's not happening. Secondly, if I a personal event occurs so I can't maintain my part of code.

I'm ready to continue and develop again for Wesnoth after the Summer period. As I mention before, I'd like to develop even if it's not in a GSoC context.

5) Practical considerations

5.1) Are you familiar with any of the following tools or languages?

• Subversion: Yes, I used it during my previous GSoC. For my personal projects, I'm using git.
• C++: My level is correct, I can easily debug and understand the concept and features of this language.
• STL, Boost, Sdl: I know a large part of the STL and some libraries from Boost (MPL, Phoenix, Range,...). I used very few the SDL during a C project.
• Python (optional, mainly used for tools): I wrote one project with it: a SAT solver.
• build environments (eg cmake/scons): I recently used these to compile Wesnoth, but I need to learn deeply how they work (add file,...).
• WML (the wesnoth specific scenario language): I read the manual and some files' campaign.
• Lua (used in combination with WML to create scenarios): No.

5.2) Which tools do you normally use for development? Why do you use them?

I'm using VIM and g++, because they are open-source, light and everything is in the terminal, so I rarely quit my keyboard to use the mouse. I'm using git because there are local commit and branches.

However I also programmed under Visual Studio the last year.

5.3) What programming languages are you fluent in?

C++ mostly but also C and Java.

5.4) Would you mind talking with your mentor on telephone / internet phone?

I'll let you my number in the official form but I'm not very confident in my comprehension and speaking. However, if you speak clearly, it should be alright.