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

A 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. The problem is, that the RCA AI uses not much more than this analysis. Therefor it happens, that the AI will overestimate strong units according to the current game situation. It is often better to have more weaker units. Furthermore it can happen, that only one type of unit is recruited. But I think the Combat Analysis as such doesn't need a big refactoring. The goal should be to weight Combat Analysis against other methods like Map Analysis.

Therefore I want to spend only little time in testing and improving the current Combat Analysis. (But of curse I want to determine a appropriate weight and find the right place for Combat Analysis in the overall solution)

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.

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 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. In order to retain the 'recruitment_pattern' configuration I should keep the idea of heaving the helper method recruitment_phase::recruit_usage() currently used in the RCA AI. So the main-part takes places in this function and when initializing the score map only units according to it's usage are considered.
4. 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)
5. 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.
6. The Cost could influence the score too. Without cost the AI would only recruit good and expensive units.
7. 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.

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. All configurations can be implemented by aspects (inside the [ai] tag).

I want to seperate my Ideas for configurations in two parts:

Easy understandable configurations

The following configurations are intended to be easy understandable without knowing details about how the recruitment analysis works. Some of those configurations are often requested features in the forum.

recruitment-more-diverse = yes

When this flag is set the AIi will recruit more units which are currently rare on the map. I will decide later how much more is. For a exact tweak of diversity see below.

recruitment-more = "Grunts"

This is meant to let a scenario editor make a easy hack when he/she wants the AI to recruit more units of a specific type. I will decide later how strong this configuration will be considered during the recruitment phase. One could also think about doing something like recruitment-more = "Grunts, Grunts" to make the instruction to recruit more Grunts even stronger.

recruitment-level-pattern = "0111223"

This one is inspired by this idea in the forum. When a recruitment_level_pattern is given the AI will similar to recruitment_pattern only recruit units according to given level ratios.

recruitment-counter-strategy = yes

When this flag is activated the AI will also do a counter-recruitment analyses. I cannot say yet how exactly will the ai behave when this flag is set.

Tweaking Configurations

The following configurations are intended to tweak some inner functions and weights. In order to use them one should have a idea of how the recruitment works.

Most likely I will implement those things:

recruitana-combat-weight = 1
recruitana-map-weight = 1
recruitana-counter-weight = 1
recruitana-counter-counter-weight = 1
recruitana-diversity-weight = 0

With this configurations one could adjust the weights of the scores coming from the analyse-algorithms. I want to normalize the default weight to 1 (or 0 if the analyse-algorithm is not activated by default). So one could double the impact of a algorithm by setting the weight to 2 or half the impact by setting the weight to 0.5.

This is a rather a vague guess about how some specific analysis-functions could be tweaked further. I will not specify them further yet.

recruitana-combat-range = 100
recruitana-map-village-range = 1
recruitana-counter-turns = 2

I will pay attention not to break the existing configurations 'recruitment', 'recruitment_pattern', 'recruitment_ignore_bad_combat' and 'villages_per_scout'.

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

TODO

Set of Goals - Brief overwiew

• Refactor the "Formula AI dev"-Recruitment in C++, test it, improve it and make it easy to configure.
• Implement a Counter- and Counter-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
• 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
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
2	MANDATORY	Completely understand the Map Analyses of "Formula AI dev" and write a explanation in this wikipage.	1
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
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
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
-	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
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
9	MANDATORY	Test implementation of Map Analyses.	1
10	OPTIONAL	Extract parameters which could later be configured by aspects.	1
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
13	OPTIONAL	Test and improve current Combat Analysis if possible.	2
14	OPTIONAL	Extract parameters of Combat Analysis which could later be configured by aspects. Batch Test parameter variations	2
-	MILESTONE 1	Have at least all mandatory steps above done until July 28.	8 + 10
15	MANDATORY	Implement Counter-Recruitment-Strategies.	2
16	MANDATORY	Extract parameters of Counter-Recruitment-Strategies which could later be configured by aspects.	1
17	OPTIONAL	Implement 'Counter-Counter-Recruitment-Strategies' and test it.	3
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
20	MANDATORY	Set up a parameterizable weight-system.	1
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
-	MILESTONE 2	Have at least all mandatory steps above done until Aug 25.	8 + 5
22	MANDATORY	Review Configuration Specifications from Step 1 and adjust them if necessary.	1
23	MANDATORY	Defin Aspects for the Configurations and implement missing aspects (like 'recruit-more=') and make them work with the score map.	2
24	MANDATORY	Test those new aspects.	1
25	MANDATORY	Write a separate wikipage for scenario-editors about those aspects and provide some examples and describe use-cases.	2
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
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.	7 + 9

IRC

flix

Questionnaire

I put the Questionnaire on a separate page. I can join it later.

User:Flixx/GSoC 2013/Questionnaire