User:Dragos/GsoC 2013/AI: Refactor recruitment algorithm

This page is related to Summer of Code 2013

See the list of Summer of Code 2013 Ideas

This is a Summer of Code 2013 student page

Description

Dragos Ristache: Refactor the recruitment algorithm

I propose to work on the "Refactor the recruiting algorithm" project. The new implemented algorithm should be very customizable from LUA (this will be extremely useful to help campaign creation). The new recruiting algorithm should also be capable of doing the listed features in the project description.

IRC

dragos

Project

I will divide the project in 3 main ideas, each will its own small ideas.

Optimal recruiting

The recruitment algorithm will choose the best unit to recruit by taking into account many factors and combining them. It’s very important that the AI will recruit optimally (or at least as optimal as possible). This includes recruiting with more than one leader and selecting the best units for each leader. The algorithm should take into account the enemy units, their position and the map in general to make the best recruiting decisions. (This is already taken into account, but we should still integrate it with multiple leader recruit, as sometimes, for instance, it is better to only recruit with the second leader than only with the first.)

One important idea is making the AI recruit units that are good against the closest enemy units, since the closer a unit is, the more important it will be when choosing what to counter-recruit. This is to try to get through the first line of defense. It does not matter if our new units are good against the units far away if they are bad with the closer units that they would have to get through to reach the other units.

At the same time, we need to consider the next wave of units. In many cases the AI/ player in the next recruitment wave recruits units that will complement the current units. There are many small factors that will influence our decisions, like mostly ignoring the units with low HP, except the case when they are about to level up (since if it has low HP but levels up, it will have full HP and be a bigger threat to our side).

Another idea that I consider important to the decision is to simulate the next state to some extent, as this will help us make the decision on what to recruit. A small note on this idea: we can compress the number of states and ignore irrelevant information about the game-state (in short, simulating the next turn recruitment-wise will be way easier than for other purposes - like attacking for instance). Because of this, the most important thing we need to focus is having the best function to express the advantage of a certain state.

We should also take into account the units that are already on the field. So, if our group of units already counters archers, we should not try as hard to recruit archers.

Moreover, we should consider what happens when the AI recruits first, as it should be as hard as possible for the enemy to counter-recruit. Also, it should stop recruiting when it has a noticeable advantage in the field and wait to counter the next wave of enemy units.

Unit purpose and goals

We should implement a method to recruit units with a purpose. This purpose can be to control the waterway, scout as much as possible, protect a certain hex/zone and so on. These goals should be mainly controlled by a created scenario, but I believe it would be possible to make the AI detect which goal are important and select them. This will be useful as it will make the AI more organized and try to accomplish small goals one by one, each goal making the AI closer to victory.

This also leads to the problem of ‘forcing’ the units we just recruited for a certain goal to try and accomplish that goal. So, if we make 3 scouts for scouting they should scout, not attack. One idea to do this is implementing a kind of unit based formula. For instance, a unit that scouts should try to maximize a formula related to scouting, such as the total area covered by the AI’s units.

Customizability

The new recruiting algorithm should be fully controlled by LUA commands. This can make writing scenarios easier and configuring how the AI recruits could be done directly from the WML. This includes limiting the number of units of each type, or the percentage of a unit that should be in field (example: maximum 5 archers or maximum 50% archers of all the units).

All the recruiting features should be fully controlled by flags in WML. So, if we want to disable the counter-recruit we should simply state that in the scenario. This should also have a timestamp so we can force the AI to begin counter-recruiting after a certain number turns (7 for example).

Questionnaire

Basics

Write a small introduction to yourself.

My name is Dragos Florian Ristache, and I am 20 years old. I have been a Computer Science student for a semester at Jacobs University Bremen, and starting this fall, I will study Computer Science at the University of Southampton. I have been working in C++ and participating in numerous competitions since the 9th grade (so for around 5 years).

In the later years I started working with other languages and technologies (Python/C#).

State your preferred email address.

drasisu [at] yahoo [dot] com

or

ristachedragos [at] gmail [dot] com

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

dragos on the forum and the IRC.

Why do you want to participate in summer of code?

I think summer of code is the perfect way to gain a lot of practical experience. In addition, working at big project will also help my programming and thinkings skills.

Because I’ve been participating and training for many competitions in high school I haven’t had the chance to focus on the practical part of Computer Science and I think this would be the perfect chance to do so.

What are you studying, subject, level and school?

I will be studying Computer Science, starting this fall at University of Southampton.

(note* This year, I’ve studied a semester at Jacobs University Bremen. I have also had the chance to take many online courses during the ‘gap’ semester. The two most important I would like to mention would be: Berkley’s Introduction to Artificial Intelligence and Caltech’s Machine Learning course)

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

I’m from Romania and will mostly be available from 7 am to 7 pm GMT.

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

I do not have any commitments or vacations planned so far.

Experience

What programs/software have you worked on before?

I’ve only worked at small individual projects.

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

I haven’t developed software on my own, but on numerous occasions I’ve worked in team environments at Computer Science competitions. This competitions ranged between 5 hours to months and this is one of the main reasons I believe I work well in a team environment.

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?

No, I haven’t participated before.

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

No, this would be my first open source development project.

Gaming experience - Are you a gamer?

Yes, I do consider myself a gamer. I also think that this is one of the main reasons I chose this project (and even why I started studying computer science)

What type of gamer are you?

I consider myself a competitive gamer in some regards. When I find a game that is at the same time challenging and fun I usually invest a lot of time at getting really good at the said game.

What type of games?

I generally play all types of games. I really like strategy games ( I constantly play Starcraft 2 for example). RPG are one of my favorite types, the same can be said about shooters and puzzle games.

What type of opponents do you prefer?

I usually prefer challenging opponents and I like it when the game has a high difficulty.

Are you more interested in story or gameplay?

When I’m playing a game I’m usually interested in both, with a little inclination to story, but when I analyze a game and decide if I should keep playing or not, the gameplay is the biggest factor.

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

I’ve been playing Wesnoth for a couple of weeks. I’m inclined to play the single player mainly because of the AI.

We do not plan to favor Wesnoth players as such, but some particular projects require a good feeling for the game which is hard to get without having played intensively.

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 repository (during the evaluation period or earlier) please state so.

I’ve worked on 3 “demo-patches” as instructed by Crab_.

1. I’ve created a lua function to display a label over each hex.

2. I’ve also created a mirror recruit for the AI in C++. This is in case the AI is playing a 1v1 against the same race. Using this function the AI will recruit the exact units the enemy recruited.

3. I’ve created a naive retreat function. When used the AI units will start retreating away from the enemies and to the safest positions on the map.

Communication skills

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 studied one year at an international high school and semester at an international university (where the teaching and working language was English). I also scored a 110 (out of 120) on the TOEFL iBT. Those are the main reasons I consider myself good at written english.

What spoken languages are you fluent in?

Romanian and English.

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

I occasionally spend the time on internet forums discussing strategies or other game related information so yes, I would consider myself good at interacting with other players.

Do you give constructive advice?

When I have the necessary knowledge to give someone advice, I do.

Do you receive advice well?

Yes! I think advice from other people is one of the best ways to grow as a programmer and as a person.

Are you good at sorting useful criticisms from useless ones?

When I reach a high enough level at something to have an outline on what areas I need improving and what areas I reached a ‘good enough’ level for my task I am able to sort useful from useless criticism.

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

This depends on what stage I am at learning the code base. When I just want to learn how everything works and how everything is structured I will probably just code a proof of concept, but when I gained enough information about the project I think well ahead of the code I write, as to not waste time.

Project

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’ve selected “AI: Refactor recruitment algorithm”.

Why did you choose this project?

I chose this project because I would really like to see these ideas in Wesnoth and because I believe that it is suited for me. Also, I would really like to learn and work with LUA. In the last weeks I saw the basics of how LUA is integrated with C++ in Wesnoth, and it seemed really interesting, and it is an idea I would like to work on.

Include an estimated timeline for your work on the project. Include as much technical detail about your implementation as you can

Time Frame	Milestone
14 June - 23 June (10 days)	Adding support to recruit with more leaders
24 June - 28 June (5 days)	Making the AI recruit more optimally considering the multiple leaders
29 June - 4 July (6 days)	Reworking the recruiting algorithm to make it hard for enemies to counter recruit
5 July - 16 July (12 days)	Adding the feature to Counter-recruiting when necessary/good
17 July - 21 July (5 days)	Testing the changes so far, adding small Customization features from idea 3
22 July- 29 July (8 days)	Adding simple goals when recruiting, making units respect those simple goals.
30 July- 2 August (4 days)	Preparing for mid term Evaluation and start working on more complex goals
3 August - 8 August (6 days)	Adding the complex goals
9 August - 21 August (13 days)	Optional: Making the AI detect useful goals that will help win the game and testing all changes
22 August - 4 September (14 day)	Customization: Limiting number of units
5 September - 14 September (10 days)	Customization: Adding general customization features
15 September - 23 September (9 days)	Testing all the features and preparing for final evaluation
After SOC (PLAN)	Continue working for Wesnoth

What do you expect to gain from this project?

Working at a project like Wesnoth will provide invaluable experience. It will also expand my practical knowledge of AI and algorithms and will help me better understand the LUA programming language. Moreover, I’m sure that this Summer of Code will prepare me for working in the future for open-source organisations and programs. (I always felt that I wanted to work for an open-source project, but lacked guidance or a clear goal).

What would make you stay in the Wesnoth community after the conclusion of SOC?

I plan to continue coding for Wesnoth after the SOC. I believe that continually working for an open-source project offers both individual benefits and, especially, benefits for the community.

Practical considerations

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

   Git (used for all commits)

I’ve used Git a couple of times and I am somewhat familiar

   C++ (language used for all the normal source code)

I’ve been working in C++ for around 5 years, so I would consider myself good at it

  STL, Boost, Sdl (C++ libraries used by Wesnoth)

I’ve been using STL for a long time but I only have minimal experience with Boost and Sdl/

  Python (optional, mainly used for tools)

I’ve worked with Python numerous types so I find myself familiar with the language

   build environments (eg cmake/scons)

I used scons and cmake in the weeks before the applications

   WML (the wesnoth specific scenario language)

Minimal experience

   Lua (used in combination with WML to create scenarios)

While working on a demo-patch for wesnoth I learned a bit of Lua and LuaAI

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

I mainly use Code::Blocks and Eclipse. I use Code::Blocks because it suited my needs in high school while programming for competitions and I started using Eclipse because it helped me in some projects I worked on. (But for Wesnoth I only used Code::Blocks)

What programming languages are you fluent in?

I worked in C/C++,C# and Python. I consider that I know C/C++ at a high level and Python/C# at a medium-level.

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!

In general, students should be as verbose as possible in their answers and feel free to elaborate.

I agree and will add my phone number in the google application.