Difference between revisions of "User:Flixx/GSoC 2013/AI: AI: Refactor recruitment algorithm"

From The Battle for Wesnoth Wiki
m (Timeline)
m (Timeline)
Line 60: Line 60:
 
| style="width: 125px;" | May 27 || ''Accepted student proposals announced by Google''  
 
| style="width: 125px;" | 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.   
+
| 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  
 
| Jun 18 - Jul 01 || Time off. See  

Revision as of 22:16, 27 April 2013


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