Soc2012 Talbot Pierre Refactor Recruitment Algorithm

This page is related to Summer of Code 2012

See the list of Summer of Code 2012 Ideas

This is a Summer of Code 2012 student page

/!\ In construction.

Description

Talbot Pierre - Refactor Recruitment Algorithm

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

We must manage 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.

The units must be chosen for a specific purpose such as getting a village, fighting a specific units, 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.

The recruitment pattern will be improved to allow scenario designer to be more specific on which units should be recruited and a ratio of recruitment. For example: "unit1 4 unit2 3 unit3 3" means for 10 units recruited, 4 will be unit1, 3 unit2 and 3 unit3.

IRC

trademark

Questionnaire

1) Basics

1.1) Write a small introduction to yourself.

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

1.2) State your preferred email address.

ptalbot [at] mopong (dot) net

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

trademark

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

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

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

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

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

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

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

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

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

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

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

2) Experience

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

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

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

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

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

2.3) Have you participated to the Google Summer of Code before? As a mentor or a student? In what project? Were you successful? If not, why?

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

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

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

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

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

No.

2.5) Gaming experience - Are you a gamer?

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

2.5.1) What type of gamer are you?

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

2.5.2) What type of games?

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

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

2.5.3) What type of opponents do you prefer?

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

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

2.5.4) Are you more interested in story or gameplay?

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

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

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

2.6) If you have contributed any patches to Wesnoth, please list them below. You can also list patches that have been submitted but not committed yet and patches that have not been specifically written for GSoC. If you have gained commit access to our SVN (during the evaluation period or earlier) please state so.

A bug: Bug #19538.

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

3) Communication skills

3.1) Though most of our developers are not native English speakers, English is the project's working language. Describe your fluency level in written English.

I only write my program in English (even if there are unimportant) and I document them in English as well. I haven't problem to discuss in English.

3.2) What spoken languages are you fluent in?

French.

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

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

3.4) Do you give constructive advice?

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

3.5) Do you receive advice well?

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

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

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

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

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

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

4) Project

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

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

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

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

4.3) Why did you choose this project?

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

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

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 things I didn't watch in April.
21/05 to 11/06	Start the coding period. Code the recruitment of units more useful and adapted to the environment, and managing the position of recruiting (which leaders).
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.
10/08 to 20/08	Minimize the counter-recruiting, for example if AI recruit first. It's closely related to the gold management.
20/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.

5) Practical considerations

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

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

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

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

However I also programmed under Visual Studio the last year.

5.3) What programming languages are you fluent in?

C++ mostly but also C and Java.

5.4) Would you mind talking with your mentor on telephone / internet phone? We would like to have a backup way for communications for the case that somehow emails and IRC do fail. If you are willing to do so, please do list a phone number (including international code) so that we are able to contact you. You should probably *only* add this number in the application for you submit to google since the info in the wiki is available in public. We will *not* make any use of your number unless some case of "there is no way to contact you" does arise!

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.

Proposal

There are few points to refactor. I try to explain these with an incremental approach, for a specific point, there is few steps and they can't be jump. This is useful to code & test and directly spot the potential bugs.

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

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 execution phase, only one location is considered.

Goal

AI should consider multiple leaders and use a list of leaders which are on a keep.

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.

Implementation

The function find_leaders will help us to achieve this goal. We'll need to modify recruitment_phase::evaluate() 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.

std::vector<std::pair<unit_iterator, map_location> > get_neutral_village(std::vector<unit_iterator> &leaders);

Returns: The different location of neutral village per leaders. Every map_location is unique.

analyze_potential_recruit_combat should be leader specific.

Easy limiting of recruitable units

The scenario editors would like to control more easily the recruitment phase. WML markup can be implement and the recruitment pattern modify. A ratio could be use to specified the maximum units we want on the ground, or the minimum. More specific markup could be added to be accurate on when and what units should be recruited.

Analyse map terrain to recruit more useful units

As I said before, most of the units are chosen randomly. An analyse of which enemy units are on the map and which enemy units are recruitable should help us to choose better units. The criteria of an analysed unit should be the distance, how much of the same kind, the cost, and the threaten (if a enemy is close from our leader). 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 together on these parts).

Random units

A good part of the AI is to choose random units when it doesn't know what to do. We should improve it to recruit the best units against the closest enemies and against the most numerous units. Another criteria should be the units that threaten the leaders.