Difference between revisions of "Soc2012 Talbot Pierre Refactor Recruitment Algorithm"

From The Battle for Wesnoth Wiki
(WML recruiting parameterisation)
m (Hide historical instance of "SVN" from mediawiki search to avoid false positives.)
 
(42 intermediate revisions by 2 users not shown)
Line 2: Line 2:
 
[[Category:SoC_Ideas_AI_Recruitment_2012]]
 
[[Category:SoC_Ideas_AI_Recruitment_2012]]
  
/!\ In construction.
+
=Latest Edit=
 +
 
 +
Edit 07/04:
 +
* WML recruiting parameterisation update. Add examples and explanations.
 +
* Update of the "multiple leaders" section.
 +
 
 +
Edit 09/04:
 +
* Add a paragraph in "Recruiting better units" following a [http://forum.wesnoth.org/viewtopic.php?f=8&t=36571&p=525919#p525846 discussion on the forum].
 +
* Change few specifications in the "WML recruiting parameterisation" section.
 +
 
 +
Edit 11/04:
 +
* Add a section "further improvements".
 +
* Modify the introduction of the question 4.5.
 +
 
 +
Edit 13/04:
 +
* Add leader classes (example).
 +
 
 +
Edit 14/04:
 +
* Add a section in "Recruiting better units": Group analysis.
 +
 
 +
Edit 15/04:
 +
* Add a section in "Recruiting better units": Village analysis.
  
 
=Description=
 
=Description=
Line 19: Line 40:
 
=IRC=
 
=IRC=
 
trademark
 
trademark
 +
=SoC Application=
 +
Submitted to google
  
 
=Questionnaire=
 
=Questionnaire=
Line 119: Line 142:
 
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).
 
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.====
+
====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 S­­V­­N (during the evaluation period or earlier) please state so.====
  
 
A bug: [https://gna.org/bugs/?19538 Bug #19538].
 
A bug: [https://gna.org/bugs/?19538 Bug #19538].
Line 161: Line 184:
 
====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?====
 
====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".
+
I'll answer to be general and than specific. Firstly, I choose this organisation because I'd like 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.====
 
====4.2) If you have invented your own project, please describe the project and the scope.====
Line 204: Line 227:
 
====4.5) Include as much technical detail about your implementation as you can====
 
====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.
+
There are few points to refactor. I'll use piece of codes from the current recruitment algorithms:
  
The class <tt>recruitment_phase</tt> and <tt>aspect_recruitment_phase</tt> 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.
+
* <tt>ai_default_recruitment_stage</tt> (ai/default/ai.*) ;
 +
* <tt>recruitment_phase</tt> (ai/testing/ca.*) ;
 +
* <tt>testing_recruitment_phase</tt> (ai/testing/ca_testing_recruitment.*).
 +
 
 +
As suggested by Crab_ on IRC, I'll work with the class <tt>testing_recruitment_phase</tt>, the entry in register.cpp is already done.
  
 
During this summer, I'll concentrate my coding around three axes:
 
During this summer, I'll concentrate my coding around three axes:
Line 214: Line 241:
 
* Allow WML parameterisation for the recruitment, mainly for scenario editors.
 
* 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.
+
A distinction between the internal algorithm and the WML parameterisation must be made. The default choices made by the AI is specified with the two first points. The WML is elaborated with the scenario editors, and will interfere with the internal algorithm. An objective will be to distinct both, and document what the WML user can change. The birth of the new interactions with the current algorithm will be made in collaboration with the WML users on forum or IRC.
  
  
 
=====Recruiting with multiple leaders=====
 
=====Recruiting with multiple leaders=====
 
* Current implementation
 
  
 
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 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.
Line 226: Line 251:
 
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.
 
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.
  
* Goal
+
See the current code:
 +
 
 +
<tt>
 +
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();
 +
}
 +
</tt>
 +
 
 +
Could be easily transform to something like:
 +
 
 +
<tt>
 +
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;
 +
}
 +
</tt>
  
AI should consider multiple leaders and use a list of leaders which are on a keep.
+
Furthermore, we create a class dedicate to the management of multiple leaders.
  
If the leaders are not on keep, we must choose a castle not too far and not too close from the battle for each leaders. Anyway, if it's not possible we choose the furthest keep from the battle and we don't move a leader to the closest.
+
<tt>
 +
class leaders
 +
{
 +
  // Units to recruit sorted by importance.
 +
  std::priority_queue<recruit_unit> recruit_list;
 +
 +
  // The leaders who are on the keep.
 +
  std::vector<leader> leaders_on_keep;
 +
 +
  // The different recruit lists of all leaders are merged into a single one.
 +
  // Each recruit_unit have an unique map_location (on the keep) and are sorted by importance.
 +
  void merge_recruit_list();
 +
 +
  void find_leaders_on_keep();
 +
 +
  public:
 +
 
 +
    leaders();
 +
 +
    // Functions to access the recruits.
 +
    // ...
 +
};
 +
</tt>
  
* Implementation
+
Each leader are treated separately and have their own recruit list. The class <tt>leaders</tt> is used to merge
 +
the different lists.
  
The function <tt>find_leader'''s'''</tt> will help us to achieve this goal. We'll need to modify <tt>recruitment_phase::evaluate()</tt> and when counting neutral village (for the scout), consider all the keeps. The scouts will distributed on all the keeps which have neutral villages around. For example we could need a function as <tt>get_neutral_village</tt>:
+
<tt>
 +
class leader
 +
{
 +
  // The recruit list sorted by importance.
 +
  std:priority_queue<recruit_unit> recruit_list;
 +
 
 +
  // The location of the leader.
 +
  map_location where;
 +
 +
  // Build the recruit list.
 +
  build_recruit_list();
 +
 +
  public:
 +
    // pre: loc must be a keep.
 +
    leader(map_location &loc);
 +
 +
    // Functions to access the recruits.
 +
    // ...
 +
};
 +
</tt>
  
<tt>std::vector<std::pair<unit_iterator, map_location> > get_neutral_village(std::vector<unit_iterator> &leaders);</tt><br>
+
We use a POD struct to describe a unit to recruit.
Returns: The different location of neutral village per leaders. Every map_location is unique.
 
  
<tt>analyze_potential_recruit_combat</tt> should be leader specific and lead us on a recruiting-list per leader.
+
<tt>
 +
struct recruit_unit
 +
{
 +
  // Where the unit will be recruited. (Must be on a castle).
 +
  map_location where;
 +
 +
  // The name of the unit to recruit.
 +
  std::string unit;
 +
 +
  // The importance of this recruitment.
 +
  int importance;
 +
 +
  // The objective of this unit. It should be interesting for the other AI (why did we recruit this unit ?).
 +
  std::string objective;
 +
};
 +
</tt>
 +
 
 +
The objective and importance lead us to the second point of this proposal: "Recruiting better units".
  
 
=====Recruiting better units=====
 
=====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).
+
The recruitment is the basic of every strategies and so we must first analyse the unit, the terrain, the villages on the map to take the best decisions.
  
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.
+
======Groups analysis======
 +
 
 +
If we are able to see the groups of enemy and ally, we are able to recruit a suitable unit to fight well against the group, or at least, the most number of units in this group. The detection of the different group on the map is not easy because we must defined a "group". I propose a definition which could change over the time and the results:
 +
 
 +
"A group contains a designate father, the father is the unit who has the most units around him within his own range. If a unit cannot protect the father because it's too far, it is excluded from the group, and even if the father can protect this unit. A group could contain only one unit, who is its own father. A unit cannot belong to more than one group."
 +
 
 +
Concretely, the groups are represented as a disjoint set and the union-find algorithm naturally represent the situation. The class below represents the groups, it's only a prototype and so will probably be modified later.
 +
 
 +
<tt>
 +
class groups
 +
{
 +
  int side;
 +
 +
  // Each unit have a unique id.
 +
  std::map<int, map_location> units_id;
 +
 +
  // disjoint_set[i] = j where i the unit_id and j the father.
 +
  std::vector<int> disjoint_set;
 +
 +
  // The id of the fathers. (Useful for iterate over the groups).
 +
  std::set<int> fathers;
 +
 +
  // For each unit in the side "side", a id is affected and registered in units_id.
 +
  void assign_unique_id();
 +
 +
  // Initialize the fathers, all units are their own father.
 +
  void init_fathers();
 +
 +
  // returns: The number of unit around loc. (With the father rules).
 +
  int count_unit(map_location &loc);
 +
 +
  // Assign the real father of each units.
 +
  // It uses a priority queue with all the units inside and sorted with the count_unit function.
 +
  // While it's not empty: if the unit extracted is not a member of a group (use find operation),
 +
  // it's a father and all units considered like it are now member of the group (union operation).
 +
  void process_fathers();
 +
 
 +
  void union(int i, int j);
 +
  void find(int i);
 +
 
 +
  public:
 +
 +
    // The group structure is built for the side "side".
 +
    groups(int side);
 +
 +
    // Iterators: We can iterate over the groups and over the unit of a group.
 +
    class group_iterator
 +
    {
 +
      // Examples:
 +
      groups::unit_iterator operator*(group_iterator& iter);
 +
      void operator++();
 +
      // ...
 +
    };
 +
   
 +
    class unit_iterator
 +
    {
 +
        map_location operator*(unit_iterator& iter);
 +
        // ...
 +
    };
 +
 +
    group_iterator begin();
 +
    group_iterator end();
 +
 +
    // We can provide operator [] to access a group.
 +
    unit_iterator operator[] (size_t index);
 +
};
 +
</tt>
 +
 
 +
The goals of the groups are:
 +
 
 +
* Recruit units to reinforce a ally group who is weaker than the enemy group it's facing.
 +
* Recruit units to form a group fighting against a specific enemy group.
 +
* With the groups, the AI should be able to elaborate elegant strategies.
 +
 
 +
We must analyse the group and which group is fighting against another. We'll use a class <tt>group_analysis</tt> which contains all the groups of all sides and link the group fighting against the other to build a ''graph'' of all the groups. The edges contains the distance so we'll have a better overview of the battleground.
 +
 
 +
======Villages analysis======
 +
 
 +
Without villages, none of any strategies can't be set up. I propose an analyse of the village which try to recruit the best units to capture villages. I try that this analyse is not only effective in the beginning of the game.
 +
 
 +
In a first time, we divide the map into three zones:
 +
 
 +
with i the village, j our castle and k the enemy castles.
 +
 
 +
* Ally: The distance between i and j is shortest than between i and k.
 +
* Neutral: The distance between i and j is equals than between i and k.
 +
* Enemy: The distance between i and j is longer than between i and k.
 +
 
 +
We calculate paths which maximize the number of villages that scouts can reach in the minimum turns. The paths don't contain a same village.
 +
 
 +
From each vacant tiles on the castle, a path is calculated and goes by all the villages on the map. It's an optimisation problem: the travelling salesman. We don't want a village in more than one path and we apply the following algorithm:
 +
 
 +
# We initialise a graph G containing only the castle's tiles node.
 +
# In a priority queue V, we sort all the villages by the distance (the distance sum from each available castle's tiles).
 +
# While V is not empty: we connect the village extracted to the closest node in G.
 +
# G contains all the paths from each castle's tiles.
 +
 
 +
Furthermore, the villages which are already ours are removed from V. And the distance to go to the villages which belong to the enemy or in a enemy zone are doubled only if enemies are around those villages.
 +
 
 +
The maximum edge on a path indicate us the unit to recruit, we are not forced to recruit a unit who is a scout if it's more useful and can do the job of the scout and fighting well.
 +
 
 +
A problem could appear. It's not our responsibility to move the unit and to follow the path indicated. So even if we recruit units for a specific objective, we cannot be sure that other AI will understand it this way... We need a way to communicate, and it's bring us to the next improvement: "Unit's objectives".
 +
 
 +
======Unit's objectives======
 +
 
 +
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). It will be implemented such a "hint" member filled during the recruitment process and modify if needed during the next phases and by the other AI. 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.
 +
 
 +
For example, we can recruit a unit for:
 +
 
 +
* Help a specific group at the location x.
 +
* Capture villages following the path y.
 +
* Protect a unit.
 +
* ...
  
 
=====WML recruiting parameterisation=====
 
=====WML recruiting parameterisation=====
Line 251: Line 488:
 
The scenario editors would like to control more easily the recruitment phase. WML markup can be implement and the recruitment pattern modify.
 
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 the following ideas: http://forum.wesnoth.org/viewtopic.php?f=8&t=36571.
+
I opened [http://forum.wesnoth.org/viewtopic.php?f=8&t=36571 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.
 
I'll start with some examples before diving into the specification details.
Line 315: Line 552:
 
         number=1
 
         number=1
 
         increment=1
 
         increment=1
         turns=2 to END
+
         turns=2-END
 
       [/recruit]
 
       [/recruit]
 
     [/facet]
 
     [/facet]
Line 338: Line 575:
  
 
* id: Important if you need to access it later to modify it.
 
* id: Important if you need to access it later to modify it.
* type="": (string) This key takes a comma separated list containing the usage of the units that can be recruited. Common usages are: 'scout', 'fighter', 'archer', 'healer' and 'mixed fighter'. An empty string tells the AI to recruit units according to the internal recruitment algorithm. A <tt>random</tt> value means to recruit randomly all type of units.
+
* 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 <tt>random</tt> value means to recruit randomly all type of units.
* number=1: (integer) A number greater than 0 will tell the AI to recruit <tt>n</tt> units of usage <tt>type</tt> for each turns specified below.
+
* number=1: (integer) A number greater than 0 will tell the AI to recruit <tt>numbers</tt> units of type <tt>type</tt> for each of the turns specified in <tt>turns</tt>. The <tt>INF</tt> token can be specify to recruit as much units as we can. If there are other <tt>recruit</tt> tags with lower importance, there will never be executed.
 
* increment=0: (integer) <tt>number</tt> is incremented by <tt>increment</tt> for each turns specified in <tt>turns</tt>. 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.
 
* increment=0: (integer) <tt>number</tt> is incremented by <tt>increment</tt> for each turns specified in <tt>turns</tt>. 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 turn. If a 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. The keyword 'to' can be used between two values and is provided for convenience, for example: 1 to 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.
+
* 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 <tt>START</tt>, <tt>MIDDLE</tt> and <tt>END</tt> can be used, <tt>START</tt> tell the AI to recruit during the first "1/10" of the total turns, and <tt>END</tt> during the last "1/10". <tt>MIDDLE</tt> recruits units after <tt>START</tt> and before <tt>END</tt>. 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 <tt>START</tt> and <tt>END</tt>, but <tt>START</tt> must be the left value and <tt>END</tt> 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 <tt>number</tt>. If two units are equally important, the AI will choose one according to his internal recruitment algorithm.
 
* 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 <tt>number</tt>. 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 <tt>recruit</tt> 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]
 +
 +
======Further improvements======
 +
 +
If the time doesn't fly away too fast during this summer, I would like to add a <tt>objective</tt> key to specify the goal of a unit. Some values could be <tt>get_village</tt>, <tt>defend</tt>, <tt>attack</tt>, etc. It could eventually takes more than one value if an objective is completed. A unit would be "tagged" with this objective during all its life time.
 +
  
  
Line 361: Line 620:
 
====5.1) Are you familiar with any of the following tools or languages?====
 
====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.
+
* Sub&shy;&shy;version: 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.
 
* 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.
 
* 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.

Latest revision as of 19:55, 20 March 2013


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


Contents

Latest Edit

Edit 07/04:

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

Edit 09/04:

  • Add a paragraph in "Recruiting better units" following a discussion on the forum.
  • Change few specifications in the "WML recruiting parameterisation" section.

Edit 11/04:

  • Add a section "further improvements".
  • Modify the introduction of the question 4.5.

Edit 13/04:

  • Add leader classes (example).

Edit 14/04:

  • Add a section in "Recruiting better units": Group analysis.

Edit 15/04:

  • Add a section in "Recruiting better units": Village analysis.

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

SoC Application

Submitted to google

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 S­­V­­N (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 like 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'll use piece of codes from the current recruitment algorithms:

  • ai_default_recruitment_stage (ai/default/ai.*) ;
  • recruitment_phase (ai/testing/ca.*) ;
  • testing_recruitment_phase (ai/testing/ca_testing_recruitment.*).

As suggested by Crab_ on IRC, I'll work with the class testing_recruitment_phase, the entry in register.cpp is already done.

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.

A distinction between the internal algorithm and the WML parameterisation must be made. The default choices made by the AI is specified with the two first points. The WML is elaborated with the scenario editors, and will interfere with the internal algorithm. An objective will be to distinct both, and document what the WML user can change. The birth of the new interactions with the current algorithm will be made in collaboration with the WML users on forum or IRC.


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;
}

Furthermore, we create a class dedicate to the management of multiple leaders.

class leaders
{
  // Units to recruit sorted by importance.
  std::priority_queue<recruit_unit> recruit_list;

  // The leaders who are on the keep.
  std::vector<leader> leaders_on_keep;

  // The different recruit lists of all leaders are merged into a single one.
  // Each recruit_unit have an unique map_location (on the keep) and are sorted by importance.
  void merge_recruit_list();

  void find_leaders_on_keep();

  public:
 
   leaders();

   // Functions to access the recruits.
   // ...
};

Each leader are treated separately and have their own recruit list. The class leaders is used to merge the different lists.

class leader
{
  // The recruit list sorted by importance.
  std:priority_queue<recruit_unit> recruit_list;
 
  // The location of the leader.
  map_location where;

  // Build the recruit list.
  build_recruit_list();

  public:
    // pre: loc must be a keep.
    leader(map_location &loc);

    // Functions to access the recruits.
    // ...
};

We use a POD struct to describe a unit to recruit.

struct recruit_unit
{
  // Where the unit will be recruited. (Must be on a castle).
  map_location where;

  // The name of the unit to recruit.
  std::string unit;

  // The importance of this recruitment.
  int importance;

  // The objective of this unit. It should be interesting for the other AI (why did we recruit this unit ?).
  std::string objective;
};

The objective and importance lead us to the second point of this proposal: "Recruiting better units".

Recruiting better units

The recruitment is the basic of every strategies and so we must first analyse the unit, the terrain, the villages on the map to take the best decisions.

Groups analysis

If we are able to see the groups of enemy and ally, we are able to recruit a suitable unit to fight well against the group, or at least, the most number of units in this group. The detection of the different group on the map is not easy because we must defined a "group". I propose a definition which could change over the time and the results:

"A group contains a designate father, the father is the unit who has the most units around him within his own range. If a unit cannot protect the father because it's too far, it is excluded from the group, and even if the father can protect this unit. A group could contain only one unit, who is its own father. A unit cannot belong to more than one group."

Concretely, the groups are represented as a disjoint set and the union-find algorithm naturally represent the situation. The class below represents the groups, it's only a prototype and so will probably be modified later.

class groups
{
  int side;

  // Each unit have a unique id.
  std::map<int, map_location> units_id;

  // disjoint_set[i] = j where i the unit_id and j the father.
  std::vector<int> disjoint_set;

  // The id of the fathers. (Useful for iterate over the groups).
  std::set<int> fathers;

  // For each unit in the side "side", a id is affected and registered in units_id.
  void assign_unique_id();

  // Initialize the fathers, all units are their own father.
  void init_fathers();

  // returns: The number of unit around loc. (With the father rules).
  int count_unit(map_location &loc);

  // Assign the real father of each units.
  // It uses a priority queue with all the units inside and sorted with the count_unit function.
  // While it's not empty: if the unit extracted is not a member of a group (use find operation),
  // it's a father and all units considered like it are now member of the group (union operation).
  void process_fathers();
 
  void union(int i, int j);
  void find(int i);
 
  public:

    // The group structure is built for the side "side".
    groups(int side);

    // Iterators: We can iterate over the groups and over the unit of a group.
    class group_iterator
    {
      // Examples:
      groups::unit_iterator operator*(group_iterator& iter);
      void operator++();
      // ...
    };
    
    class unit_iterator
    {
       map_location operator*(unit_iterator& iter);
       // ...
    };

    group_iterator begin();
    group_iterator end();

    // We can provide operator [] to access a group.
    unit_iterator operator[] (size_t index);
};

The goals of the groups are:

  • Recruit units to reinforce a ally group who is weaker than the enemy group it's facing.
  • Recruit units to form a group fighting against a specific enemy group.
  • With the groups, the AI should be able to elaborate elegant strategies.

We must analyse the group and which group is fighting against another. We'll use a class group_analysis which contains all the groups of all sides and link the group fighting against the other to build a graph of all the groups. The edges contains the distance so we'll have a better overview of the battleground.

Villages analysis

Without villages, none of any strategies can't be set up. I propose an analyse of the village which try to recruit the best units to capture villages. I try that this analyse is not only effective in the beginning of the game.

In a first time, we divide the map into three zones:

with i the village, j our castle and k the enemy castles.

  • Ally: The distance between i and j is shortest than between i and k.
  • Neutral: The distance between i and j is equals than between i and k.
  • Enemy: The distance between i and j is longer than between i and k.

We calculate paths which maximize the number of villages that scouts can reach in the minimum turns. The paths don't contain a same village.

From each vacant tiles on the castle, a path is calculated and goes by all the villages on the map. It's an optimisation problem: the travelling salesman. We don't want a village in more than one path and we apply the following algorithm:

  1. We initialise a graph G containing only the castle's tiles node.
  2. In a priority queue V, we sort all the villages by the distance (the distance sum from each available castle's tiles).
  3. While V is not empty: we connect the village extracted to the closest node in G.
  4. G contains all the paths from each castle's tiles.

Furthermore, the villages which are already ours are removed from V. And the distance to go to the villages which belong to the enemy or in a enemy zone are doubled only if enemies are around those villages.

The maximum edge on a path indicate us the unit to recruit, we are not forced to recruit a unit who is a scout if it's more useful and can do the job of the scout and fighting well.

A problem could appear. It's not our responsibility to move the unit and to follow the path indicated. So even if we recruit units for a specific objective, we cannot be sure that other AI will understand it this way... We need a way to communicate, and it's bring us to the next improvement: "Unit's objectives".

Unit's objectives

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). It will be implemented such a "hint" member filled during the recruitment process and modify if needed during the next phases and by the other AI. 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.

For example, we can recruit a unit for:

  • Help a specific group at the location x.
  • Capture villages following the path y.
  • Protect a unit.
  • ...
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]
Further improvements

If the time doesn't fly away too fast during this summer, I would like to add a objective key to specify the goal of a unit. Some values could be get_village, defend, attack, etc. It could eventually takes more than one value if an objective is completed. A unit would be "tagged" with this objective during all its life time.


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?

  • Sub­­version: 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.

This page was last edited on 20 March 2013, at 19:55.