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

todo

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
1	MANDATORY	Specifying configurations and discussing them in the Forums. Write the results in this wikipage	2
2	MANDATORY	Completely understand the Map Analyses of "Formula AI dev" and writing a explanation in this wikipage	1
3	MANDATORY	Set up a own CA for recruitment, implementing a score table. Let units recruit according to some mock values in the score table.	1
4	OPTIONAL	Collecting 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	Thinking about what to pay attention so all following steps will be implemented to work with multiple leaders. Maybe implementing Multiple Leader Support in the current Recruitment Algorithms.	2
-	MILESTONE	I want the steps above done when the coding period starts (Jun 16)
6	MANDATORY	Refactor the Map Analyses of "Formula AI dev" in C++.	3
7	MANDATORY	Test implementation of Map Analyses.	1
8	OPTIONAL	Extract parameters which could later be configured by aspects.	1
9	OPTIONAL	Batch testing Map Analyses (with parameter variations)	2
10	MANDATORY	Integrating 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
11	OPTIONAL	Testing and improving current Combat Analysis if possible.	2
12	OPTIONAL	Extract parameters of Combat Analysis which could later be configured by aspects. Batch Testing parameter variations	2
-	MILESTONE	All steps above are done until July 28.
13	MANDATORY	Implementing Counter-Recruitment-Strategies.	3
14	MANDATORY	Extracting parameters of Counter-Recruitment-Strategies which could later be configured by aspects.	1
15	MANDATORY	Implementing 'Counter-Counter-Recruitment-Strategies' and testing it.	3
16	OPTIONAL	Batch testing and improving Counter- and Counter-Counter Recruitment Strategies.	2
17	MANDATORY	Implementing 'Diversity'. When weighting all other Phases with 0 the AI should only recruit units, which are currently rare on the Map.	1
18	MANDATORY	Setting up a parameterizable Weight System.	1
19	MANDATORY	Batch testing with different weights. Documenting results in this wiki page, defining default weights (they will be normalized to 1 for easy configuration then)	3
1	MILESTONE	All steps above are done until Aug 28.
20	MANDATORY	Review Configuration Specifications from Step 1 and adjust them if necessary	1
21	MANDATORY	Defining Aspects for the Configurations and implementing missing aspects (like 'recruit-more=') and make them work with the score map.	2
22	MANDATORY	Test those new aspects.	1
23	MANDATORY	Writing a separate wikipage for scenario-editors about those aspects and providing some examples and describing use-cases.	2
24	MANDATORY	Adding Multiple Leader support for the Move_Leader_To_Keep CA.	2
25	OPTIONAL	Making this implementation (Multiple Leader in MLTK CA) 'intelligent', so that it can be decided which leader shall go to a keep.	3
26	MANDATORY	Testing recruitment with multiple leaders (I should implement and test every steps with multiple leaders so there is hopefully not much to do here)	1
27	OPTIONAL	Introducing a purpose memory for the AI-Units	3
28	OPTIONAL	Implementing a Proof of Concept for my Purpose-Driven-Recruitment Idea	3
29	OPTIONAL	Testing this Implementation.	2
30	OPTIONAL	If successful writing 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, Documenting	n/a
-	MILESTONE	All steps above are 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

User:Flixx/GSoC 2013/AI: AI: Refactor recruitment algorithm

Contents