GSoC Akihara Proposal

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).

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

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

First, i will take i few days to know the implementation structure. (1-3 days)

Second, see the current solution and understand it. It's always usefull to know how it works now before changing everything.(1-2 days)

Then, even if I have my own idea, I will probably speak to wesnoth players. In fact, I will need different point of view concerning the subject. I will probably also go to the forum. (few days)

I will begin coding. Of course, the third point is never really closed. It's always usefull to have new argument.

Test & Play

If it goes to the right way, it's ok. Otherwise, I will reconsider the third point.

My idea

I don't know the code structure yet except that it is in C++. I work on a AI once using a min-max algorithm which can be a good start. But I don't think that it is the better solution.

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.

Structure

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

First, I think that leaders should be in a separated unit_map. This separation can be useful in the move and recruitment treatment. In fact, the currently solution works for one leader, but it can be heavy when we have more than one leader on each side. My best option will be to create different list of leaders for each side so we can easily access to the number of leaders a side have, but also access to each leader but it's not an obligation.

An other solution is to change the function unit_map::unit_iterator unit_map::find_leader(int side) in order to returning the list of leaders of a particular side.

But with the currently solution, the AI can only use the first leader in the list as a leader (recruitment and move on keep).

For me, the first solution is the best because we don't need to search each turn the list of leaders. Of course, it means more dependency because if a leader dies, the list need to be updated.

We also have leader_list used for multiplayer game. We can think of a way of using it.

Moving leaders

I think that moving leaders must be the first thing to do when the turn begin. In fact, if a leader can join a keep it will be able to recruit immediately and the strategy can change.

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.

Support per-leader recruit/recall list

Current situation: extension of the previous point. Each leader can have their own linitations.

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.

Analyse map terrain better

in coming

Recruit units that are more useful

in coming

Improve Counter-recruiting strategies

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

If you don't know these algorithm, the minmax algorithm will treat, here, all the possible recruitment situation and analyse them according to a formula we need to fix. When it's done, he will recruit the best unit according to his results. The 2-depth means that the AI will search two turn far away (his turn and the player turn). If we take a 4-depth algorithm, AI will be better but slower. 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? .

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.