During the GCI, a simple recruitment algorithm ("algorithm A") was coded for wesnoth (see http://www.google-melange.com/gci/task/show/google/gci2010/wesnoth/t129000004288 ) , which selects 'best' units to recruit and is quite similar to the algorithm already present in wesnoth but allows to 'limit' the specific unit types present on the battlefield and allows to weight quality-vs-quantity ratio.

However, there's a problem that we need to fix in that algorithm - it picks the 'best' unit and recruits it multiple times, so, on the next turn, it is possible for the opponent to counter-recruit to it. It is better to recruit a mix of units which are harder to counter-recruit.

We should design a new algorithm, "algorithm B", which will take counter-recruiting into account.

Initially, we have :

1) algorithm A - 'simple' recruitment. We can run it as a similation, without actually recruitng anything.

2) knowledge about all enemy teams:

      - how many units they can recruit next turn

      - what's the amount of gold they'll have next turn

      - what units they can recruit next turn

      - what units they have in recall list (yes, the ai is cheating here :) )

3) knowledge about own units

      - units on the battlefield

      - gold

      - allied units on the battlefield

4) a function to recalculate unit quality (by looking at all units on the battlefield and comparing combat efficiency)

A stub code will be provided for all the above

What should be done: code a new algorithm which will be based on algorithm A and will have the same API, but will do the following instead of recruiting 'best' units :

- for each unit that we can recruit, check opponents best response to it (by running algorithm A in a simulation)

- recruit a set of units for which our new 'total unit quality' is highest. it's essencially a maxmin problem [ maximize our army quality at the start of our next turn after opponent tries to minimize it by counter-recruiting ]

Discuss with Crab_ on #wesnoth-dev