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.

Make it more configurable

Above I talked a bit about weighting things. Of course I should find the best default-weights for the multiplayer modus. But this weights could easily be changed by aspects. One could introduce aspects like "combat-weight, terrain-weight, counter-recruitment, diversity" and let a scenario editor pick the wished combination.

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 * to Step * (Goals). Start Coding already. Maybe provide some patches with have not nessecarily something to do with recruitment to familirize 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 02 - Aug 25	Do everything (mandatory) up to Milestone 2.
Aug 29 - 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)
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.
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.
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.

IRC

flix

Questionnaire

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

User:Flixx/GSoC 2013/Questionnaire