User:Flixx/GSoC 2013/AI: 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

flix: Refactor recruitment algorithm

An AI opponent have to decide in a separate phase which units to recruit. Right now the default recruitment algorithm is very simple and can be improved in many ways. I want to make the AI recruiting better, more fun to play against and more configurable by a scenario editor.

Make it better

(In terms of harder to play against)

Map Analysis

Previous attempts have been made to this:

• analyze_potential_recruit_movements() analyzes nearby targets and how to reach them.
• the "Formula AI dev"-Recruitment uses the terrain near to villages ("important locations") and recruits units which defend good in those areas. According to Crab_ the algorithm easily beats the RCA AI (default-AI). The algorithm is written in Formula-AI and hard to understand (and probably therefore not in use). Additionally Formula-AI is not longer supported in future developments.

In my project I want to refactor the "Formula AI dev"-Recruitment in C++, test it, improve it and make it easy to configure.

Combat Analysis

The current RCA AI make much use of a combat analysis. This works actually pretty well. Although there are still some improvements possible. In context of my Game Theory Algorithm, I already tried to weight the attacks in a different way. Tests have shown that this was a good thing to do.

A lot of things that have a minor effects in combat analysis are not considered yet. Examples for this are traits, movement-costs, daytime, abilities like leadership or healing.

I will give the combat analysis a refactoring and try to include all those specialties.

Counter Recruitment Strategies

In order to recruit the best units for a set of enemy units and make the best use of a combat analysis, it is sometimes useful to wait for the enemy to recruit. (Not spend all money in the first round). The RCA AI will always recruit when it has enough gold available. This can be improved. The hardest part when implementing this is to decide when such a strategy is appropriate.

I want first to introduce a state "Counter Recruitment". When the AI is in this state it will first wait (and discover) enemy units before spending all the money. Then I will test (via benchmarking) in which cases it is useful for the AI to enter or leave this state.

Counter-Counter Recruitment Strategies

Note: I need a better name for this ;)

We don't want the enemy to counter easy our own units. This could happen when all of our recruited units can be easily countered by one unit type of the enemy. So when we recruit we need to recruit in a way our units will look diverse from a combat point of view.

As a part of the proposal I already implemented a Proof of Concept for such a strategy. For this I've used tools from Game Theory. (Finding a mixed strategy Nash Equilibrium). See User:Flixx/Game Theory for Recruiting for more.

Make it more Fun

In terms of recruitment more fun is achieved when the AI is recruiting not only one type but a good mix of all available units. This can easily be achieved by just favor rare units. The hard part here is again, how to weight it against other options.

Implementation Details: Score Map

So far I spoke about several analyze algorithms: map-analyze, combat-analyze, counter- and counter-counter strategies, and some possibility to boost diversity. Here I want to say something how this algorithms could work together.

At the beginning of the recruitment phase (but after filtering units according to configurations) a score map is created with all possible units which can be recruited. In the analysis phases (map analysis, combat analysis, ...) it will be filled with scores. More specifically:

Let i denote a analysis algorithm and j a unit.
Score_j = sum_over_all_i (score_ij * weight_i)

After the score-map is completed the recruitments will be executed according to it. One Example:

Unit		Score		percentage
  A		  50		    1 %
  B		2000		   40 %
  C		 450		    9 %
  D		1000		   20 %
  E		 500		   10 %
  F		1000		   20 %

If 5 Hexes are available for recruiting the Leader will recruit 2 B's , 1 D, 1 F and 1 E.  

Notes:

1. To make the recruitment-analysis efficient, all analyses algorithms should only run once per CA Execution.
2. The score map will most likely also have a score for 'recruit no unit' for making Counter-Recruiting-Strategies work.
3. To make this work with multiple leaders: The score-map can be expanded so there are scores for each leader. The separate analyse-algorithms can then set for a unit a different score for leader 1 then for leader 2. To start easy on this we can first assume that for all leaders the scores will be the same. Later one could extend the analyse-algorithms so they can set different scores for leaders. (This could be useful for example if the Combat-Analysis can figure out that one specific unit can fight better against the units around leader 1). After the score-map is completed each leader will recruit according to their score-map (They could swap after each recruitment if money is rare so the units will be split equally)
4. One could also think about negative scores. For example when the combat-analyzes wants to make sure that we not recruit Woses when there are fire-units around, although Woses seemed best for Map-analysis.
5. The Cost could influence the score too. Without cost the AI would only recruit good and expensive units.
6. Even when diversity is weighted to zero, the current units on the map should influence the scores too. Otherwise if the leader can only recruit one unit per turn he would always recruit the same unit.
7. One could also think about giving scouts in the first rounds a higher score.

Make it more configurable

For a better *development flow* I want first specify the configurations (in the wiki) before implementing them. Before it comes to implementation I will also use the forum to discuss my suggestions.

See User:Flixx/Configuration Specifications

Purposes Idea

For the Idea see this page: User:Flixx/GSoC 2013/Idea AI Recruitment: Purposes

In the scope of this project I want to take some time to implement a Proof of Concept of this idea for further evaluation. I think it is a good idea but I don't want to define the implementation of this as a project goal. Probably Purpose-Driven-Recruitment will get too complex, and I don't want to fail the goals. Though I want to plan some time at the end of the summer for this idea to see if it's worth something.

Multiple Leader

Although the AI could have multiple recruiters available it will currently only recruit with one leader. I want to change this. All necessary configurations for this are already in place (a scenario-editor can specify multiple leaders and leader specific recruitment lists).

I already wrote some thoughts how to make the recruitment work. I will repeat it here:

To make this work with multiple leaders: The score-map can be expanded so there are scores for each leader. The separate analyse-algorithms can then set for a unit a different score for leader 1 then for leader 2. To start easy on this we can first assume that for all leaders the scores will be the same. Later one could extend the analyse-algorithms so they can set different scores for leaders. (This could be useful for example if the Combat-Analysis can figure out that one specific unit can fight better against the units around leader 1). After the score-map is completed each leader will recruit according to their score-map (They could swap after each recruitment if money is rare so the units will be split equally)

Additionally I need to extend the Move_Leader_To_Keep CA so that both leaders will advised to return to a keep. I want to implement this early so I can test everything with multiple leaders from the beginning on.

When I have time I want to make the Move_Leader_To_Keep CA actually intelligent so it can be decided if it is really necessary to move all recruiters back to a keep (and if not decide which recruiter). I marked this as 'optional'.

Set of Goals - Brief overwiew

• Refactor the "Formula AI dev"-Recruitment in C++, test it, improve it and make it easy to configure.
• Refactor Combat analysis
• Implement a Counter-Recruitment-Strategy and find good conditions when to use it
• Implementing a system to favor rare units
• Find good default-weights for all sub-algorithms
• Make those weights configurable
• Introduce easy understandalbe configurations
• Support recruitment with Multiple Leaders
• (optional) Implementing a Proof of Concept for the Purpose Idea and test it

Timeline

May 27	Accepted student proposals announced by Google
May 28 - Jun 17	Before the official Coding Phase: Do Step 1 to Step 5 (Goals). Start Coding already. Maybe provide some patches with have not necessarily something to do with recruitment to familiarize more with the Code.
Jun 18 - Jul 01	Time off. See 1.7) in the Questionnaire
Jul 02 - Jul 28	Do everything (mandatory) up to Milestone 1.
Jul 29 - Aug 02	Mid term evaluation
Aug 03 - Aug 25	Do everything (mandatory) up to Milestone 2.
Aug 26 - Sep 15	Do most steps up to Milestone 3.
Sep 16	Suggested 'pencils down' date. Take a week to scrub code, write tests, improve documentation, etc.
Sep 16 - Sep 23	Do documentary steps up to Milestone 3 and finish at least mandatory steps of Milestone 3
Sep 23 - Oct 01	Final Evaluation, submitting required code samples to Google
Afterwards	If Purpose-Driven-Recruitment works -> improve it. Otherwise I'm sure I'll find something to work on ;)

Goals / Milestones

(Note: I added a column "complexity" and filled it with values between 1 (easy) and 3 (complex). This is a rough guess but it helped me to balance the steps between the Milestones.)

ID	PRIORITY	DESCRIPTION	COMPLEXITY	PROGRESS
1	MANDATORY	Specify configurations and discuss them in the Forums. Write the results in this wikipage.	2	done without feedback
2	MANDATORY	Completely understand the Map Analyses of "Formula AI dev" and write a explanation in this wikipage.	1	done
3	MANDATORY	Set up a own CA for recruitment, implement a score table. Let units recruit according to some mock values in the score table.	1	done
4	OPTIONAL	Collect experimental recruitment algorithms which were written over the last years. Evaluate them and think if they could be of some use. Write results down.	2	80 %
5	OPTIONAL	Think about what to pay attention so all following steps will be implemented to work with multiple leaders. Maybe implement Multiple Leader Support in the current Recruitment Algorithms.	2	done
-	MILESTONE 0	Have at least all mandatory steps above done when the coding period starts (Jun 16)	4 + 4
6	MANDATORY	Add Multiple Leader support for the Move_Leader_To_Keep CA.	2	done
7	OPTIONAL	Make this implementation (Multiple Leader in MLTK CA) 'intelligent', so that it can be decided which leader shall go to a keep.	3
8	MANDATORY	Refactor the Map Analyses of "Formula AI dev" in C++.	3	done
9	MANDATORY	Test implementation of Map Analyses.	1	done
10	OPTIONAL	Extract parameters which could later be configured by aspects.	1	done
11	OPTIONAL	Batch test Map Analyses (with parameter variations)	2
12	MANDATORY	Integrate current Combat-Analysis to work with the score map. When weighting the Map-Analysis with 0 the AI should now exactly recruit the same as it did before the refactoring.	2	skipped
-	MILESTONE 1	Have at least all mandatory steps above done until July 28.	8 + 6
13	MANDATORY	Refactor current Combat Analysis.	3	done
14	OPTIONAL	Extract parameters of Combat Analysis which could later be configured by aspects. Batch Test parameter variations	2	done
15	MANDATORY	Implement Counter-Recruitment-Strategies.	2	done
16	MANDATORY	Extract parameters of Counter-Recruitment-Strategies which could later be configured by aspects.	1	done
17	OPTIONAL	Implement 'Counter-Counter-Recruitment-Strategies' and test it.	3	done
18	OPTIONAL	Batch-test and improve Counter- and Counter-Counter Recruitment Strategies.	2
19	MANDATORY	Implement 'Diversity'. When weighting all other phases with 0 the AI should only recruit units, which are currently rare on the map.	1	done
20	MANDATORY	Set up a parameterizable weight-system.	1	done
21	MANDATORY	Batch-test with different weights. Document results in this wiki page, define default weights (they will be normalized to 1 for easy configuration then)	3	done / not necessary
-	MILESTONE 2	Have at least all mandatory steps above done until Aug 25.	11 + 7
22	MANDATORY	Review Configuration Specifications from Step 1 and adjust them if necessary.	1	done
23	MANDATORY	Define Aspects for the Configurations and implement missing aspects (like 'recruit-more=') and make them work with the score map.	3	done
24	MANDATORY	Test those new aspects.	2	done
25	MANDATORY	Write a separate wikipage for scenario-editors about those aspects and provide some examples and describe use-cases.	2	done
26	MANDATORY	Test recruitment with multiple leaders (I should implement and test every step with multiple leaders so there is hopefully not much to do here)	1	done
27	OPTIONAL	Introduce a purpose memory for the AI-Units	2
28	OPTIONAL	Implement a Proof of Concept for my Purpose-Driven-Recruitment Idea	3
29	OPTIONAL	Test this Implementation.	2
30	OPTIONAL	If successful write further steps for Purpose-Driven-Recruitment in a wikipage (e.g. how the purposes could be work in other phases)	2
31		Clean everything up and document	n/a
-	MILESTONE 3	Have at least all mandatory steps above done until Sep 23.	9 + 9

IRC

flix

Questionnaire

1) Basics

1.1) Write a small introduction to yourself.

Hi! I'm Felix, 22 and from Germany/Berlin. I'm currently as a exchange student in Amman/Jordan (until June) studying Computer Science at Princess Sumaya University for Technology.

1.2) State your preferred email address.

I will add my address in the google application.

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

flix

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

I've played with the thought to join a Open Source Community for some time now. And GSoC seems like a great way to to this. I admire the idea of Open Source and the way how international communities can assemble such great software!

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

When I'm not in Jordan I study something fancy called "Science in the Information Society" at Technical University in Berlin. I'm currently in my 3rd year. This courses are great because we have over 50% optional courses and we could study nearly anything (Physics, Math, Chemistry, ...) I chose to focus on Computer Science very early (in my first year). So I had a lot courses with the Computer Scientists and consider myself at the same level as a Computer Scientist in his/her 3rd year.

Here in Jordan I learnt to love MOOCs. I mention this because I also finished the course Artificial Intelligence (BerkeleyX) It was the best course I ever had (online and offline).

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

Germany (UTC+01:00) My favorite time to work is between 4 pm and 2 am. Although I'm quite flexible with times and can try to be online when my mentor is.

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

Yes! I'm currently in Amman/Jordan as a exchange student. I will go back to Germany on the 24th of June. And around this date I need some time off. More specific: I'm only partly available from 18th of June to the 1st of July.

Apart from that I have no other commitments and would consider SoC as a full-time job. Also I can start early (before 18th of June) to work on my project.

2) Experience

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

• In High-school I started to tweak phpBB for my purposes (don't work on this anymore)
• In my first year in university I developed for a project a AI for the Game Hive (Java).
• I'm currently developing a mobile-tagging software for images in Java (Tomcat Server) and Android.

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

Yes, for the AI I mentioned for example (team of 8). I strongly prefer to develop in teams.

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?

No.

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, I'm not :(

2.5) Gaming experience - Are you a gamer?

I wouldn't consider myself as a gamer...

2.5.1) What type of gamer are you?

...although I love to play once in while. Especially multi-player games with friends. In a month I maybe play 6 nights long ;)

2.5.2) What type of games?

• Turnbased Stategy games like Wesnoth, Civilisations,
• Old-school realtime strategy games like Empire Earth, WarcraftIII

2.5.3) What type of opponents do you prefer?

I prefer AI opponents.

2.5.4) Are you more interested in story or gameplay?

Definitely gameplay. I'm a story-skipper ;).

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 to play Wesnoth half a year ago and have played it with a friend once in a while since. I play the mainline campaigns too. I like both.

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

Yes, I enjoyed it to dig into the code and trying to do some things from the EasyCoding Page.

• Added new aspect 'advancements'
• Improved ai behavior when using goto_x / goto_x in WML
• Command 'lua wesnoth.debug_ai(side).ai

• Additionally: Some work on the ai-testing suite and my Game-Theory-Algorithm can be found here.

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.

Should be more then enough to communicate with the community.

3.2) What spoken languages are you fluent in?

German, English (Arabic is way too hard ;) )

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

Yes, I think so.

3.4) Do you give constructive advice?

When I can, sure!

3.5) Do you receive advice well?

Depends on who want to advice me. But in general of course!

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

I think so, yes.

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 think I am the autonomous developer who would code a proof of concept. Although since i'm new to this community I would definitively ask questions and discuss the project goals so the risk of failing them is minimized.

I always try to figure out problems of technical nature myself.

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?

The Project "AI Refactor recruitment algorithm".

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

-

4.3) Why did you choose this project?

Basically because Crab_ said so ;). When I first read the project page I wanted to do the "defensive AI" project. But after some advice I concentrated on the Recruitment Idea. And meanwhile I really like this Idea and prefer it over the others. I would love to improve the AIs recruitment.

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

See above.

4.5) Include as much technical detail about your implementation as you can

See above.

4.6) What do you expect to gain from this project?

I would finally be part of a Open Source Community. Furthermore I expect to gain experience in C++ (and Lua). I'm quite new to C++ and I think Wesnoth is great for improving C++-skills.

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

A failed project would be demotivating, but otherwise I would love to stay in the community if I find some time when university starts again.

5) Practical considerations

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

• Git (used for all commits)
  • Yes
• C++ (language used for all the normal source code)
  • I'm new to C++. But since I worked on some patches I've already learned a lot and feel capable to work with Wesnoth's code.
• STL, Boost, Sdl (C++ libraries used by Wesnoth)
  • I've heard of it and made use of it in the patches, but without big background knowledge.
• Python (optional, mainly used for tools)
  • Yes
• build environments (eg cmake/scons)
  • I know how to build. That's it.
• WML (the wesnoth specific scenario language)
  • Yes
• Lua (used in combination with WML to create scenarios)
  • Not really, but ironically I know how C++ and Lua are communicating through the Lua Stack since I worked on two patches dealing with this. Lua seems easy enough though.

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

I use Eclipse on ubuntu. I am used to it from Java development.

5.3) What programming languages are you fluent in?

I list them from most fluent to *I have coded once with it*

Java, Python, PHP, C++, JavaScript, Ruby, Scala, Pearl, Lua.

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 will add my number in the google application.