Difference between revisions of "GSoC Akihara Proposal"

From The Battle for Wesnoth Wiki
(Goals)
m (Hide historical references to Subversion from the wiki search function)
 
(13 intermediate revisions by one other user not shown)
Line 142: Line 142:
 
| 13 August
 
| 13 August
 
| Take a week to scrub code, write tests, improve documentation, etc.
 
| Take a week to scrub code, write tests, improve documentation, etc.
 +
|}
 +
 +
Second Period
 +
 +
{| border="1"
 +
| width ="8%" | +
 +
| width ="17%" | 16 June - 20 June
 +
| Working on the terrain analyzing. I will describe my idea later in a specified section.
 +
|-
 +
| +
 +
| 21 June - 23 June
 +
| Begin the implementation of simulation battle. They will give more specific stats in ordre to choose the right unit to recruit.
 +
|-
 +
| +
 +
| 24 June - 27 June
 +
| Working on scout/ village capture analyzing. We only evaluate battle thusfar, but capturing villages is also an important point.
 +
|-
 +
| +
 +
| 28 June - 30 June
 +
| Evaluate support unit.
 +
|-
 +
| +
 +
| 31 June - 2 July
 +
| Leader must recruit unit. Test the algorithm and modify if necessary.
 +
|-
 +
| +
 +
| 3 July - 7 July
 +
| Working on leader limitation - AI must understand herself if he can recruit certain unit according to his limits.
 +
|-
 +
| +
 +
| 8 July - 13 August
 +
| Placement of leaders. AI must know how to place his leaders according to number of keep, number of leaders and leaders' race.
 +
|-
 +
| +
 +
| 13 August
 +
| Take to test or continue to work!
 
|}
 
|}
  
Line 219: Line 255:
 
| align="center" | Recruitment
 
| align="center" | Recruitment
 
| Implement the minmax algorithm with a basic formula.
 
| Implement the minmax algorithm with a basic formula.
| align="center" | To do
+
| align="center" style="color:orange"| On going
 
|-
 
|-
 
| align="center" width ="5%" | 10
 
| align="center" width ="5%" | 10
Line 544: Line 580:
 
All the algorithm need to be done once in order to have the final list. When we decide to recruit a unit, the only thing to do is to cancel unit we cannot recruit anymore according to gold.
 
All the algorithm need to be done once in order to have the final list. When we decide to recruit a unit, the only thing to do is to cancel unit we cannot recruit anymore according to gold.
  
===== Scoots and village =====
+
==== Scoots and village ====
 
Scoots are very special unit. They are usually used to take villages around . The problem here is "How many scoot should be recruit?".
 
Scoots are very special unit. They are usually used to take villages around . The problem here is "How many scoot should be recruit?".
  
Line 555: Line 591:
 
At least, we will have two zones to explore: zone A and B. The two of them will be explored in the same way.
 
At least, we will have two zones to explore: zone A and B. The two of them will be explored in the same way.
  
We will seek to create a graph on which each vertex will be a village. To simplify the algorithm, and also make more sense, we won't consider ALL villages. In fact, nobody could take all villages before the opponent. It makes same to consider the 60% of them regarding to our castle.
+
'''For the moment, we will forget the notion of BlueZone'''. It will come later :)
To find edges, we will calculate the shortest path between each village. Finally, we will have N shortest path according to the number of final vertices in the graph.
+
 
The distance between villages can be the factor to determine edges.
+
Let's take an example !
 +
 
 +
http://ar.chroot-me.in/random/wesnoth/scout_example.png
 +
 
 +
This screen is a part of the ai_arena map. There is a lot of informations on this picture, but we will take them one by one.
 +
 
 +
* The '''crisscross'''
 +
The crisscross permit to divide the map in different areas. In this example, the map is divided into 9 areas. The aim of this is to determine ''in which direction we will research villages for the determination of the scout number''. For this, the position of the castle is the key! Let's go to the next point ;)
 +
 
 +
* The '''searching direction'''
 +
 
 +
If we look at the picture, the castle is located into area 2 which is the most particular area (with 4,6 and 8). Indeed, they are 'middle' areas, so the direction ''searching direction'' depend of the village location. Let's take the example of the village on area 2, and the nearest one in area 3. They don't have the same ''search direction'' (green area) !!
 +
 
 +
Well, the explanation is simple: the castle is in area 2, a ''middle'' area. So the ''searching direction'' depend of the village location. Let's imagine that area 2 is divided into two parts verticaly: villages which are on the right of the castle will have DOWN and RIGHT for searching direction, wheareas villages on the left will have DOWN and LEFT.
 +
 
 +
If a castle is in area 1 for example, the searching direction will be RIGHT and DOWN. In this case, the village position don't matter for the direction :) We always use the castle as our first research position.
 +
 
 +
In code format, these information will be stored in a int according to a enum type:
 +
enum searchDirection { UP = 1, DOWN = 2, LEFT = 4, RIGHT = 8}
 +
The values are chose in order to have a unique value when adding one to an other.
 +
5 = UP + LEFT
 +
6 = DOWN + LEFT
 +
9 = UP + RIGHT
 +
10 = DOWN + RIGHT
 +
14 = DOWN + RIGHT + LEFT
 +
...
 +
 
 +
* Searching villages
 +
We will search villages according to the searching direction. In the case of our example, the castle is in position 15 - 2 with a searching direction equal to 14. We will searching all the village which are in the searching zone (all the village under the castle in this case) and sort them according to the distance between them and the castle.
 +
 
 +
This distance will be a 'dummy' distance, we won't ake the field into account.
 +
 
 +
But we will restrict our choice! In fact, we won't take into account villages which are to far away. As a default value, I will take village for which the distance is equal to 60% of (distance + enemy distance).
 +
 
 +
* Create paths
 +
The aim of the algorithm is to create paths for having the number of scout ;) But how do we create these paths? First, we will take the nearest village. In the example, it's the village in area 2. It's now the moment to use the ''searching direction'' found earlier! First, let's have a look at the village information:
 +
 
 +
Location: 11 - 4
 +
Searching Direction: 6
 +
 
 +
This mean that we need to find villages which have a location as x <= 11 and y >= 4. In our example, we are lucky! One village is in the zone: location 5 - 9. It will be our next step :) We redo the same thing on this village until we found no more village in the zone. We have one path :) Then, we choose the nearest no-marked village and do it again.
 +
 
 +
In the case of the village in area 3, we can see that they are two village in the searching zone. We always will chose the nearest one!
 +
 
 +
At the end, when all our village are marked, we will have our number of paths corresponding to the scout number. In our example, we will recruit 3 of them (red arrows).
 +
 
 +
Of course, certain villages can be ommited bu this algorithm. One behind the castle for example.
 +
 
 +
 
 +
'''Limitations'''
 +
We can ameliorate this algorithm into may ways:
 +
* First, the villages recognition. Infact, some villages can be inaccessible (for example, a village surrnouded by any unwalkable field). In this case, the village might be ignored. For this, we can use a ''pathfind'' to determine the movement cost.
 +
* As an extention of the first point, some field aren't walkable for certain unit, or some other can be faster. It might be interresting to know them.
 +
 
 +
===== Important area =====
 +
 
 +
"Important area" are areas where battles might be. As a consequence, it might be very important to determine these zones in order to choose unit on which they are good. The problem is "How to determine an important area?"
 +
* '''Blue zone''' : If we refer to the picture above, the blue zone might be one of these important zoe. In fact, it represent the area were battle might be.
 +
* '''villages''' : villages are places with an important strategic aspect
 +
 
 +
But, if the ennemy (or the AI) doesn't have a castle? Well, we can determine the path between the enemy and his goal (point to reach for example).
 +
 
 +
'''''But do we do next?'''''
  
The number of scoots necessary will be N.
+
When we have determine these areas, we can determine a percentage of battle for a couple of terrain type. For example, ''att->flat vs def->swamp'' with a number equal to 2. It means that we can have 2 battle with these caracteristics on the map. Warning: the ''def->flat vs att->swamp'' is count as the same context.
  
 +
Structure used for storing these informations:
 +
struct battle {
 +
    std::string first_field;
 +
    std::string second_field;
 +
    int number;
 +
};
  
'''How to determine the blue zone'''
+
'''first_field''' and '''second_field''' refers to the terrain type.
The blue zone represent the straight line between two castle with a width we will fix. With the location of the two castle, it would be easy the determine the straight line formula.
+
'''number''' refers to the number of this ''type'' of battle we found on the map.
  
 
==== MinMax ====
 
==== MinMax ====
Line 613: Line 717:
 
When we choose to recruit one unit, we must not forget to taken it into account for the next one. Otherwise, AI will choose the same unit indefinitely.
 
When we choose to recruit one unit, we must not forget to taken it into account for the next one. Otherwise, AI will choose the same unit indefinitely.
  
==== Current Code? ====
+
== Wanna test some functions? ==
 +
incoming!
  
 
= Practical considerations =
 
= Practical considerations =
Line 621: Line 726:
 
Moreover, I coded in c, c++, python, prolog and I think it's all.
 
Moreover, I coded in c, c++, python, prolog and I think it's all.
  
  * Subversion - I have my own svn.
+
  * Sub&shy;&shy;version - I have my own s&shy;&shy;v&shy;&shy;n.
 
  * C++ - I developed in c++ some years ago but I will remember since the start of GSoC
 
  * C++ - I developed in c++ some years ago but I will remember since the start of GSoC
 
  * STL, Boost, Sdl  - never used.
 
  * STL, Boost, Sdl  - never used.

Latest revision as of 23:59, 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


Description

Aline Riss Recruitment Proposal

For the moment, AI recognize only one leader even if he has more. Moreover, the recruitment algorithm is very basic. So we can set the list of possible amelioration below:

  • support recruiting with multiple leaders
  • support per-leader recruit/recall lists.
  • support easy limiting of recruitable units.
  • analyze map terrain better
  • recruit units that are more useful
  • improve counter-recruiting strategies.
  • improve recruiting for AI-playable campaigns where AI has to not spend all the gold.

In order to treat these problematic, I have highlight two points which will be my principals axes for this project and will be treat separately :

  • The placement of leaders
  • The recruitment algorithm

Each point are, at begin, independent for each other.

First, I will treat the recruitment algorithm which is the principal problem of this project. It's only in a second part that I will treat the placement problem.

About me

I'm a 22 french student girl. I'm currently studying computer science and I would like to specialize myself in development. I'm fond of open source things but never took part of an project. So GSoC is, for me, a first step in this world. I'm studying computer science in the University of Technology of Belfort Monbéliard (France). I'm a 3-year student. For the moment, I'm studying very various things (dev, network, ...) but I clearly want to be a dev. You can join me at aline.riss[at]gmail.com and also on IRC with the nickname Akihara. Moreover, I have an irssi server running without interruption so I will always be connected. So, I'm more joinable and, even if i'm not in front of my screen, I will see messages and things like that. I'm generally here at 9am (France - GMT + 2).

My holidays begins end June. But I won't forget Wesnoth and work as much as possible for it :)

IRC

Akihara

Experience

None. It's the first time I will be working on a "real" project. All I have done is school projects for the moment. For example, I developed a graphic interface in order to learn graph theory in a team environment. We were 6.

It's the first time I want to participate to the Google Summer of Code. As I said before, I never took part in any open source projects.

Gaming

I'm a real gamer. I'm between a mid-core and hardcore gamer :) I can play video game without interruption but I limit myself. I play very various games. I really like RPGs in which I can discover a new world but also FPS, very relaxig for me (strange, isn't it?), and also Strategy game for reflexion and the joy of aiming the goal. Generally, I prefer play against AI. But mostly, they are too weak too fast. On the other hand, playing against people is very fun when they are not yelling around.

The reason I can stop myself is the discovering of the environment and also the story. I can difficulty stop myself playing until I know the end. Because of that, I'm attracted to RPG and other game with an unknown world. But I must admit that a good gameplay is very important. Without it, a game isn't a game anymore.

I played Wesnoth some years ago (4? 5?) so didn't remember lot of things but I always played as a single player. But, in order to know the environment, I will play a little until the beginning of the GSoc.

My contribution to Wesnoth

Patches

Patch # Description Link

3237

TRANSFORM_UNIT needs a variable renamed

Link

3238

"maximum auto saves" setting seems ignored

Link

3275

AI - units spread poison around

Link

Communication skills

I'm daily reading English so I have a good reading comprehension. In written english, I will do my best. I can do some mistakes but nobody didn't understand me.

I think that the player community can be a bit rough as in mostly communities. I have no problem speaking with them. I'm a player too so I can understand what they say and how they feel. I won't be distracted by some rough players.

In the dev community, If I can give some advice, I will. I'm not a specialist but I'm always here to help. If I have an idea, why not submit it? And the reciprocal is right too, even if I'm not agree this it. In this case, we can confront both idea. If I am right, the other person will learn something and reciprocally. I think that it is the magic of team work. Of course, part of them can be useful and others useless. I'm the type of person who will think about it again and again. Finally, I will be able to take the good part of them.

Concerning my behavior when developing, I will say that generally, I need to know the environment (here the game). If I have an idea, I will first search how I can implement it. Parallel, I really like to talk with someone interested in my work in order explain and, why not, improve it.

If I have no idea, I look sources at the beginning.

Then, I will "see how it turn out" so I can have a better idea of what I am doing. I prefer doing it this way before losing time on something which will no work.

Project

Why

I choose a project from the list: "Refactor recruitment algorithm". I'm very interrested in AI algorihtm and how make them more intelligent. It's really interresting. I think that recruitment, in a game like this, is the beginning of everything. And it's also a question i'm asking to myself when I'm playing.

I hope gain some experience from this project , and a view of how dev a game works. I'm very curious about this. And if I'm well integrated, I will stay and continue developing it.

Timeline

+ 21 May - 23 May Familiarize myself with the current Wesnoth AI -> recruitment process, unit control ....
+ 23 may - 28 May Working on some patches in order to continue to explore and understand the current AI
+ 29 May - 31 May AI recognition of multiple leader. The goal is for the AI to use several leaders in a very basic way -> recruit unit with only gold and unoccupied place on keep limits.
+ 1 June - 3 June Work on an AI vs AI environment in order to watch a battle between the current and the new AIs.
+ 3 June - 12 June Implementation of the algorithm
+ 13 June - 1 July Determination of the formula - The formula must score correctly a unit according to the current situation.
+ 1 July - 7 July Repartition of the recruitment list to each leaders
+ 8 July - 15 July Working on leaders limitation - AI must understand herself if he can recruit certain unit according to his limits.
+ 16 July - 13 August Placement of leaders. AI must know how to place his leaders according to number of keep, number of leaders and leaders' race.
+ 13 August Take a week to scrub code, write tests, improve documentation, etc.

Second Period

+ 16 June - 20 June Working on the terrain analyzing. I will describe my idea later in a specified section.
+ 21 June - 23 June Begin the implementation of simulation battle. They will give more specific stats in ordre to choose the right unit to recruit.
+ 24 June - 27 June Working on scout/ village capture analyzing. We only evaluate battle thusfar, but capturing villages is also an important point.
+ 28 June - 30 June Evaluate support unit.
+ 31 June - 2 July Leader must recruit unit. Test the algorithm and modify if necessary.
+ 3 July - 7 July Working on leader limitation - AI must understand herself if he can recruit certain unit according to his limits.
+ 8 July - 13 August Placement of leaders. AI must know how to place his leaders according to number of keep, number of leaders and leaders' race.
+ 13 August Take to test or continue to work!

Goals

# PRIORITY SUBPROJECT TODO STATUS
0 MUST Recognition of leaders AI must recognize all leaders he have To do
1 MUST Placement of leaders AI must find unoccupied keep and place leader on them To do
2 MUST Placement of leaders If the targeted keep became occupied by the enemy, AI should move him back and search an other keep to move him. To do
3 SHOULD Placement of leaders Find a way to determine which leader should be on a particular keep.

The current objective is to find the fastest <leader, keep> couple in order to occupied keeps as quickly as possible.

To do
4 SHOULD Placement of leaders If there is several leaders on a single keep, they should be moving in order to have a mix of recruited unit. To do
5 SHOULD Placement of leaders If there is more leaders than keeps, AI must find a good leader/keep attribution

The current objective is to give the player the occasion to play against a maximum of unit type/race. Having a mix of race on a keep could be a good beginning.

To do
6 MUST Placement of leaders Testing a case where there is n leaders and m keeps, n >> m. To do
- MILESTONE - Formula - The AI should be capable of place his leaders in a intelligent way. Not yet
7 MUST Recruitment Creating of an AI vs AI environment. DONE
8 MUST Recruitment Finding a way to limit each leaders according to the scenario To do
9 MUST Recruitment Implement the minmax algorithm with a basic formula. On going
10 MUST Recruitment Formula - Determine a good scoring concerning the analyse of the requested unit type To do
11 MUST Recruitment Formula - Determine a good scoring concerning the analyse of the number of requested unit To do
12 MUST Recruitment Formula - Determine a good scoring concerning the analyse of the number of requested unit To do
13 MUST Recruitment Formula - Determine a good scoring concerning the analyse of limits we know To do
14 MUST Recruitment Formula - Determine a good scoring concerning the analyse of the terrain To do
15 MUST Recruitment Formula - Determine a good scoring concerning the analyse of the number of requested unit To do
16 MUST Recruitment Formula - Determine a good scoring concerning the analyse of the enemy's unit level To do
- MILESTONE Recruitment AI should be able to determine his unit need Not yet
17 SHOULD Recruitment AI should analyse the situation and determine which leader should recruit a specific unit. To do
- MILESTONE Recruitment AI should be capable of determined which leader is the more useful to recruit a specific type of unit. To do

My idea

I will certainly use existing code and file in order to ameliorate the recruitment algorithm.

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

General idea

The general idea of the project is to use several leaders to recruit useful unit. To do so, we have a few steps to follow:

  • Place intelligently the leaders -> the placement of leaders will determine firsts limits of recruitment like the number of unused placement per keep. We will also know which leader can recruit
  • Determine the recruitment list for each leader
  • Recruit unit

These steps are the general algorithm the AI should follow at the end. According to it, we can highlight two main points:

  • Leaders' placement
    • Recognize all leaders
    • Find a good leader distribution on keeps
    • Move them on keep
  • Recruitment algorithm
    • Determine points and limit in order to have a good choice of unit
    • Implement the algorithm
    • Test and ameliorate the algorithm

Support multiple leaders

Current situation: For the moment, AI only use the first leader to recruit even if a 2nd leader is on keep an can recruit. Other point, if leaders are not on keep, AI must figure out a good leep for each leader, and move them to keeps.

Recognize all leaders

All units (whatever their side) are currently stored into a unit_map which associate unit with their location.

To get leaders associated to a specific side, we have the unit_map::unit_iterator unit_map::find_leader(int side) function which will return the first leader belonging to the right side.

unit_map::unit_iterator unit_map::find_leader(int side) {
	unit_map::iterator i = begin(), i_end = end();
	for (; i != i_end; ++i) {
		if (static_cast<int>(i->side()) == side && i->can_recruit())
			return i;
	}
	return i_end;
}

So, in the case we have several leaders, the others will not be recognize. In order to recognize them, we simply need to chance this function in order to returning a list of leaders

std::vector<unit_map::unit_iterator> unit_map::find_leader(int side) {
       std:vector<unit_map::unit_iterator> leaders;
	unit_map::iterator i = begin(), i_end = end();
	for (; i != i_end; ++i) {
		if (static_cast<int>(i->side()) == side && i->can_recruit())
			leaders.push_back(i);
	}
	return leaders;
}

Recruit with all leaders

The current function recognize only one leader (according to the find_leader()) and return BAD_SCORE if:

  • there is no leader available
  • the leader is not on keep
  • if there is no available place on keep
double testing_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();
}

At least, this function must consider the state of each leader.

double testing_recruitment_phase::evaluate()
{
   const std::vector<unit_map::const_iterator> leaders = resources::units->find_leader(get_side());

   for (unit_map::const_iterator i, leaders) {
      if(i == resources::units->end()) {
         return BAD_SCORE;
      }
    
      if (resources::game_map->is_keep(leader->get_location())) {
         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 get_score;
      } 
   }
   
   return BAD_SCORE;
}

Placement

We can have several cases with different number of leaders and different number of keeps. We will look as each separately. These paragraph treat one case and introduce the behavior leader will should have in a particular situation.

Case 1.1: several leaders (same type) - one keep

If we have two, for example, leaders of the same type on a unique keep, we need to know which one will stay on the keep. We know that two different leaders can have different characteristics, so if one of them can be better in battle, he will leave and let the other on the keep.

But the second leader mustn't go alone. He need to be surrounded. If he can, he will capture the enemy's keep (see case 2).

In this case, we have:

  • a single list of recruitment
Case 1.2: several leaders (different type) - one keep

In this case, we have at least two leaders of different types with only one keep. Let's name them A for the first (on the keep) and B the other one. The problem here is to use the two of them. The choose of the unit will be explain in the recruitment part (see recruitment).

In this case, we have:

  • two recruitment_list

So, we have several cases:

  • If we only have unit A can recruit in the recruitment list, A will stay. B can go fight but not really far. He also can recruit on the next turn.
  • If we only have unit B can recruit in the recruitment list, A will go away and can fight. B will go on the keep in order to recruit.
  • If we have unit of both type, we will recruit the A list and then the B list.
Case 2: several leaders - several keep

Moving leaders on the right keep is the first problem. In fact, leaders can have different characteristic like moving faster for example. In this case, we must know the better way to reach the nearest keep as soon as possible. Of course, we can have a "basic" behavior which will assign the fastest leader to the nearest keep. A good things to do will be to calculate the best couple <leader, keep> for having all keeps reached as quickly as possible. It can be also useful to create a new class for having this couple in memory. If so, we aren't obliged to recalculate each path a second time. But we must calculate the state of keeps each time. I explain: Each turn, the enemy can put one of his leader on a keep the AI was watching. In this case, the leader must go back and find an other keep if there is any.

In this case, we have

  • two recruitment list
Case 3: m leaders - n keeps (m > n)

If we have a number of leader superior than the number of keeps (and > 2), we will do:

  • choose leaders which will stay on keep. If leaders are from different types, we will chosen one of each to be on a keep. It will give to the player an good opportunity to play against various unit.
  • the other leaders will go to the front keep. If we can make a mix of type on front keep, we will do so. Otherwise, leaders will fight.

In that case, we have:

  • between n and m recruitment list
General behavior

According to these different cases, we can highlight the steps AI must follow in order to place leaders correctly on map

  • Count the number of races we have (number R)
  • Count the number of keep unoccupied (number K)
  • If K >= R then
    • We will try to use of the possible keeps -> Determine <keep, leader> couple in order to occupied all keeps as quickly as possible
  • If R > K
    • Determine the quickest leader of each race
    • Determine <keep, leader> couple in order to occupied all keeps as quickly as possible
    • For the rest of them:
      • Place them on keep for having a maximum of races mix on each keep
  • Move them on keep

Support per-leader recruit/recall list

How to tell limits to AI

Leader's limitation is one feature I want to refactor.

[ai]
  [recruit]
    unit_max="10"
    unit_min="2"
    [unit]
      name="Scout"
    [/unit]
    [type]
      name="fighters"
      unit_max="3"
      level="2"
    [/type]
    [race]
      name="Troll"
    [/race]
    [level]
      level="2"
      unit_max="3"
    [/level]
  [/recruit]
[/ai]
Looking at WML structure

When we will change AI recruitment behavior or impose limits, each rules will be in a recruit tag. We can see different type of rules:

  • unit : can specify rules applied to a specific unit (i.e up to 2 scout)
  • type : can specify rules applied to a specific type of unit (i.e. up to 3 fighters )
  • race : can specify rules applied to a specific race (i.e. up to 3 Trolls)
  • level : can specify rules applied to units' level. (i.e. up to 3 units of levels 2+)

With these structures, AI will easily recognize what type of limit he had to follow.

Key list we can also use:

  • name : name of a unit or a unit type. Cannot be use on leveltag.
  • level : specify a min level.
  • max : specify a maximum number of unit we can have.

With only these keys, AI will choose himself which unit to recruit. Moreover, it doesn't ensure a mix of unit. If we want to change AI behavior, we can add some other key:

  • min : specify a minimum number of unit we should have. Force AI to have a certain mix of unit. AI will at first check if the minimum number of unit required is reached.
  • turn : specify on which turn AI can recruit this sort of unit.


CONCERNING RECRUIT TAG

As you can see in the example, max is used in the recruit. If a such a key is used in the recruit tag, he will be applied to all children tag. If, in the children tag, the key is redefined, the value will be replaced. If we look at the example, we will have a maximum of 10 scouts (and a minimum of 2) but between 3 and 2 fighters. Keys which can be used in the recruit must be usable in ALL children tag.

Others key might be appearing according to scenario designers wishes

void ai_default_recruitment_stage::on_create() read and memorize limits. We also need to fix it in order to have the right limits.

Memorize limits

In the case we can found different leader with different limitation, we will need a new attribute to the unit class.

For saving there limitation, we can use a mapping I will explain. We know that we have different type of limitation: per level, per unit and per type. We could have three mapping for each rules, but it complicate the code for nothing. In fact, I propose a mapping like this:

key {TYPE}_{NAME} - value {LIST} with the different limit name (unit_max, etc..)
key {TYPE}_{NAME}_{LIMIT} - value : {INT} value of limitation

If we take the previous example, we will have:

 key UNIT_SCOUT - value [MAX, MIN]
 key UNIT_SCOUT_UNIT_MAX - value 10
 key UNIT_SCOUT_UNIT_MIN - value 2
 key TYPE_FIGHTERS - value [MAX, MIN, LEVEL]
 key TYPE_FIGHTERS_MAX - value 3
 key TYPE_FIGHTERS_MIN - value 2
 key TYPE_FIGHTERS_LEVEL - value 2
 key LEVEL - value [MAX, MIN, LEVEL]
 key LEVEL_MAX - value 3
 key LEVEL_MIN - value 2
 key LEVEL_LEVEL - value 2

This way, we can find, for each unit, each type and each level his limitation.

In the case we recruit a fighter (i.e), we will decrease the value of key TYPE_FIGHTERS_MAX - value 3 and key TYPE_FIGHTERS_MIN - value 2 so the AI will always know if he can recruit a specific unit.

Recruitment strategie

Choose useful unit

In order to choose useful unit, we need to know a several things:

  • gold available and other limits
  • list of enemy's unit types

These three points are the main axes on which I will work on for choosing the best unit. The idea is to have a final list of available unit mapped with a score.

Gold available The gold available will give us a first list of unit we can recruit. We will it UNIT_LIST.

Others limits According to limits scenario designers have specified, some unit will be recruited. so we don't need to analyze them.

List of enemy's unit types When I am talking about a good unit, I'm talking about a unit which is efficient with the maximum of enemy unit. In order to do that, we need the complete list of enemy's unit type. Then, for each unit we can recruit, we will score' them. We will create three constant: BAD_TYPE, MEDIUM_TYPE and GOOD_TYPE.

And we have a list! The final step in to sort the list according to scores in order to have a clean list of unit we can recruit.

All the algorithm need to be done once in order to have the final list. When we decide to recruit a unit, the only thing to do is to cancel unit we cannot recruit anymore according to gold.

Scoots and village

Scoots are very special unit. They are usually used to take villages around . The problem here is "How many scoot should be recruit?".

First, we need to analyze villages. In fact, we can choose a number of scoots according to the number of villages, but it's seems not be a good solution. Some unit can take villages if they are on there way.

scheme.png

Let's take the situation above. The blue zone represent the fastest way between the two castles. We can make the supposition that it's the way unit will take to attack the enemy. So it might be useless to create one or more scoots to capture villages in this zone while units on it can capture them without losing to much time.

At least, we will have two zones to explore: zone A and B. The two of them will be explored in the same way.

For the moment, we will forget the notion of BlueZone. It will come later :)

Let's take an example !

scout_example.png

This screen is a part of the ai_arena map. There is a lot of informations on this picture, but we will take them one by one.

  • The crisscross

The crisscross permit to divide the map in different areas. In this example, the map is divided into 9 areas. The aim of this is to determine in which direction we will research villages for the determination of the scout number. For this, the position of the castle is the key! Let's go to the next point ;)

  • The searching direction

If we look at the picture, the castle is located into area 2 which is the most particular area (with 4,6 and 8). Indeed, they are 'middle' areas, so the direction searching direction depend of the village location. Let's take the example of the village on area 2, and the nearest one in area 3. They don't have the same search direction (green area) !!

Well, the explanation is simple: the castle is in area 2, a middle area. So the searching direction depend of the village location. Let's imagine that area 2 is divided into two parts verticaly: villages which are on the right of the castle will have DOWN and RIGHT for searching direction, wheareas villages on the left will have DOWN and LEFT.

If a castle is in area 1 for example, the searching direction will be RIGHT and DOWN. In this case, the village position don't matter for the direction :) We always use the castle as our first research position.

In code format, these information will be stored in a int according to a enum type:

enum searchDirection { UP = 1, DOWN = 2, LEFT = 4, RIGHT = 8}

The values are chose in order to have a unique value when adding one to an other.

5 = UP + LEFT
6 = DOWN + LEFT
9 = UP + RIGHT
10 = DOWN + RIGHT
14 = DOWN + RIGHT + LEFT
...
  • Searching villages

We will search villages according to the searching direction. In the case of our example, the castle is in position 15 - 2 with a searching direction equal to 14. We will searching all the village which are in the searching zone (all the village under the castle in this case) and sort them according to the distance between them and the castle.

This distance will be a 'dummy' distance, we won't ake the field into account.

But we will restrict our choice! In fact, we won't take into account villages which are to far away. As a default value, I will take village for which the distance is equal to 60% of (distance + enemy distance).

  • Create paths

The aim of the algorithm is to create paths for having the number of scout ;) But how do we create these paths? First, we will take the nearest village. In the example, it's the village in area 2. It's now the moment to use the searching direction found earlier! First, let's have a look at the village information:

Location: 11 - 4
Searching Direction: 6

This mean that we need to find villages which have a location as x <= 11 and y >= 4. In our example, we are lucky! One village is in the zone: location 5 - 9. It will be our next step :) We redo the same thing on this village until we found no more village in the zone. We have one path :) Then, we choose the nearest no-marked village and do it again.

In the case of the village in area 3, we can see that they are two village in the searching zone. We always will chose the nearest one!

At the end, when all our village are marked, we will have our number of paths corresponding to the scout number. In our example, we will recruit 3 of them (red arrows).

Of course, certain villages can be ommited bu this algorithm. One behind the castle for example.


Limitations
We can ameliorate this algorithm into may ways:
* First, the villages recognition. Infact, some villages can be inaccessible (for example, a village surrnouded by any unwalkable field). In this case, the village might be ignored. For this, we can use a pathfind to determine the movement cost.
* As an extention of the first point, some field aren't walkable for certain unit, or some other can be faster. It might be interresting to know them.
Important area

"Important area" are areas where battles might be. As a consequence, it might be very important to determine these zones in order to choose unit on which they are good. The problem is "How to determine an important area?"

  • Blue zone : If we refer to the picture above, the blue zone might be one of these important zoe. In fact, it represent the area were battle might be.
  • villages : villages are places with an important strategic aspect

But, if the ennemy (or the AI) doesn't have a castle? Well, we can determine the path between the enemy and his goal (point to reach for example).

But do we do next?

When we have determine these areas, we can determine a percentage of battle for a couple of terrain type. For example, att->flat vs def->swamp with a number equal to 2. It means that we can have 2 battle with these caracteristics on the map. Warning: the def->flat vs att->swamp is count as the same context.

Structure used for storing these informations:

struct battle {
   std::string first_field;
   std::string second_field;
   int number;
};

first_field and second_field refers to the terrain type. number refers to the number of this type of battle we found on the map.

MinMax

In order to make an effective counter-recruiting, an idea will to implement an 2-depth minmax algorithm.

In order to make it, AI needs to cheat a little (all AI cheat... no?) in order to know what the player can recruit.

This algorithm works very well, but has some negative points:

  • he can be a little slow... but it will be ok for a 2-depth algorithm.
  • depends on the formula. If the formula is precise, the algorithm will have better result.

For the formula, according to my experience (I implemented it last year), it's the game experience which will give it. In fact, it can be precise if we don't play. The main question we need to answer is When I am in a good situation or in a bad situation?.

If it works well, it can also solve few problem of recruitment:

  • Knowing how much unit type recruit according to a situation
  • Not spend all gold for nothing
  • Not overestimating the value of high-level recruits
  • Recruit more suitable unit for the terrain
Formula

In order to choose the recruitment list, we need to know a few things:

  • number of specific enemy unit type and number of unit we already have

In order to know how much unit AI must recruit, we must calculate a good number of unit which are enough to attack the enemy. For the moment, we will try to take the same number of unit as the player. So we can image a basic formula like

number of enemy - number of ally
  if >0 recruit!
  else not recruit
  • the level of enemy's unit and number of these unit

In fact, if we have a 3 level enemy unit, one 1 level unit isn't enough to face it. So the level is an important point to considerate. In fact, a level 3 unit is stronger than a level 1, but 3 level 1 unit have probably a better lifetime than a level 3. So we need to link both facts.

  • Terrain

Unit are more or less better according to the terrain. But, before that, we need to know "Which terrain should I analyze?". An idea which sounds good is to analyze terrain which is between two keeps. In fact, the battle will be there. For that, we will need to know keep's location (A way to do this is to search leaders -> if they can recruit, they are on keep). Then, calculate an average estimation of the location between the two keeps and then, choose a value x and y for having a zone to analyze. In order to analyze it, we can do a mapping <terrain, percentage> so we can have an idea of the terrain. Here again, we will attribute to the current unit score values according to terrain. We can also use the previous constant: BAD_TYPE, MEDIUM_TYPE and GOOD_TYPE.

Working on several recruitment list

General idea

Before speaking about the general idea, we should highlight the problem here.

We have a list of unit associated to a score which represent their utility for the current situation. But now, we need to know two things: Which unit recruit? and Which leader should recruit it?. In order to do that, we will looking at the current situation for EACH leader and for EACH unit.

In fact, depending on the leader, the unit utility can change. So we will work on each unit separately and attribute it directly to the best leader.

When we choose to recruit one unit, we must not forget to taken it into account for the next one. Otherwise, AI will choose the same unit indefinitely.

Wanna test some functions?

incoming!

Practical considerations

When using a PPO language, I like using an application like Eclipse. It's very usefull and I can be faster with it. Otherwise, I simply use vim in a shell. I really like PPO language like JAVA. JAVA is obviously the language I have more experience with. Moreover, I coded in c, c++, python, prolog and I think it's all.

* Sub­­version - I have my own s­­v­­n.
* C++ - I developed in c++ some years ago but I will remember since the start of GSoC
* STL, Boost, Sdl  - never used.
* Python  - I know it, used some times.
* build environments - I know cmake but not scons
* WML - no :(
* Lua - neither.
This page was last edited on 20 March 2013, at 23:59.