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

From The Battle for Wesnoth Wiki
< User:Flixx
Revision as of 20:52, 27 April 2013 by Flixx (talk | contribs) (Goals / Milestones)


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