GSoC Akihara Proposal
| 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
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 .
In priority, I will treat the placement problem. In fact, AI cannot play with more than one leader for the moment and make it happen will be a good beginning. And, even if is basic, the AI can recruit. The recruitment part will be treat in a second time in order to ameliorate the existing one.
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).
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 |
|
|
3238 |
"maximum auto saves" setting seems ignored |
I'm currently working on an AI problem: in fact, it seems that a unit prefer to repoison an poisoned unit instead of poison other unit.
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
- Get to know how the current AI work (unit behaviour, recruitment, etc...) (~ 1 week)
- AI can use more than one leader: (~ 3 week)
- Recognition of all leaders (few days)
- Work on case 2: 2 leaders - 2 keeps (~ 1,5 week)
- AI can move leader to keep
- AI can determine the best couple <leader, keep>
- AI can recruit with all leader
- Work on case 1.1: 2 leaders - 1 keep - same type (1 week)
- AI can determine which leader will stay on keep
- if a keep is unoccupied, the second leader will go on it
- Work on case 1.2 2 leaders - 1 keep - different type (few days)
- AI can make the change of leader
- AI can recruit with all leaders
- Limit each leader (few days)
- Begin work about the recruitment algorithm (~ 4 week)
- Implementation of minmax algorithm (1 week)
- Determine formula (~ 1,5 week)
- calculate enemy's unit type
- number of specific enemy unit type and number of enemy unit which can counter the AI specific unit
- number of unit we already have
- knowing the terrain
- the level of enemy's unit
- Test with a single unit and debug (few days)
- Test with complete list of recruitment (~1,5 week)
- Determine the full list
- Associate each list to their leader
My idea
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. So, in the case we have several leaders, the others will be treated like simple unit and not like leaders.
In order to recognize all leaders belonging to a specific side, we need to change this function for having a function returning a list of leaders.
Placement
We can have several case with different number of leaders and different number of keeps. We will look as each separately.
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
Support per-leader recruit/recall list
In the case we can found different leader with different limitation, we need to create, I think, a specific class for them which will inherit the unit class.
In fact, Leader are very special unit: they are the only one which can recruit and they will be the only one which will have a sort of limitation.
Of course, we can add an other attribute to the unit class.
For saving these limitation, we can use a mapping <unit, number> which will associate a unit to his limitation. If two leader have the same limitation, they will share the same mapping. Otherwise, they will have their own. The principle is to decrease the number associate to a specific unit when we recruit it. If one dies, the number is increased. With this method, the AI knows automatically which unit he can recruit.
Recruitment strategie
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:
- enemy's unit type: AI must privileged the correct unit type in order to strike back. If we can find a type that can counter several enemy's unit, it will be better to privileged it.
- number of specific enemy unit type and number of enemy unit which can counter the AI specific unit: 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 but also cover some killed unit.
- number of unit we already have: for a specific unit, and in order to have a good mix of unit, we need to know how much unit of a specific type we have for knowing if we can, or not, recruit an other one.
- knowing the terrain: some unit are better on some specific terrain. We can look at the map and calculate the most used terrain between two keeps (Ai's and enemy's).
- the level of enemy's 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.
- gold: of course, gold is the final limit of recruitment.
Working on several recruitment list
General idea
To create a good recruitment list for each leader, the minmax algorithm will work on 'one general recruitment list. This one will contain all the unit to recruit, all leaders combined.
To do so, we will need the list of recruitable unit from each leader (or each leader race) for having a good idea of which unit we can recruit in this turn. According to these, we will make several general recruiting list which we will test with the minmax algorithm.
When we find the best general recruiting list, we will sort it by race and chose, in the case we have several leaders of same race, the best leader for each unit. Of course, this attribution will follow maps limit like unoccupied place on keep.
In other word, we will find a general recruitment list and separate it into sublist we will affect to each leaders.
Some requirement
In order to do that, we must know the number of possible recruitment for each keep. The sum of all these number will the maximum list length. We also need the list of recruitable unit of each leader (or each race recruitable unit)
- In the case of same race leader, we need to determine which leader will recruit the chosen unit. For that, we can look at proximity with the enemy unit (and there type) for example.
- In the case of different race leader, we need to take care of the limitation of each leader in order to not recruit more unit than possible.
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.
* Subversion - I have my own svn. * 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.