Beda: /* Additional Information */

2013-04-13T03:06:32Z

‎Additional Information

Crab: /* Description */

2013-03-26T20:45:05Z

‎Description

Crab at 20:31, 26 March 2013

2013-03-26T20:31:04Z

Crab: /* Description */

2013-03-26T20:29:17Z

‎Description

Crab: /* Description */

2013-03-26T20:28:52Z

‎Description

Crab: /* Description */

2013-03-26T20:27:56Z

‎Description

Crab: Created page with '{{Template:SoC2013Idea}} = Description =

AI: Refactor recruitment algorithm [5]

Page for the idea: SoC_Ideas_AI_Recruitment_2013 We need to refactor existing wesno…'

2013-03-26T20:23:37Z

Created page with '{{Template:SoC2013Idea}} = Description = <h2>AI: Refactor recruitment algorithm [5]</h2> Page for the idea: SoC_Ideas_AI_Recruitment_2013 We need to refactor existing wesno…'

New page

{{Template:SoC2013Idea}}
= Description =
<h2>AI: Refactor recruitment algorithm [5]</h2>

Page for the idea: [[SoC_Ideas_AI_Recruitment_2013]]

We need to refactor existing wesnoth's recruitment algorithm to:
# support recruiting with multiple leaders.
# support per-leader recruit/recall lists.
# support easy limiting of recruitable units.
# analyze map terrain better
# recruit units that are more useful
# improve counter-recruiting strategies.
# improve recruiting for AI-playable campaigns where AI has to not spend all the gold.

{{#dpl:
|resultsheader=''There are %PAGES% submitted student proposals for this idea''
|oneresultheader=''There is 1 student proposal for this idea''
|suppresserrors=true
|noresultsheader=''There are no student proposals for this idea''
|category=Summer of Code 2013 Student Page&SoC_Ideas_AI_Recruitment_2013
|notcategory=SoC 2013 Not Submitted To Google
|include=#Description
|nottitlematch=SoC2013_Template_of_Student_page
|mode=userformat
|format=,,<br/>See [[%PAGE%|%TITLE%]] for more information.<br/><br/>,
}}

=Additional Information=

Recruiting is important for both player and AI.
Units are recruited each turn.

We now have an implementation of recruiting routine, which tries to recruit units which are good in combat against units already in the field, taking into account the entire map.
But, there are a number of issues, and we want to solve them.

1) AI only uses first leader to recruit - but, if there are multiple leaders, it might be useful to recruit with all of them.

2) AI cannot use per-leader recruit lists - but, leaders can have unique recruit lists (ask fendin about this feature).

3) Scenario editors want the AI recruit all units or most of the units, even if some of them might seem suboptimal from 'combat' point of view, but, as AI only considers combat/movement 'for the entire map', it might miss units which seem suboptimal. An example situation is where a unit has a specific role in the strategy, serving as auxiliary unit or as a hard counter to some specific opponent unit.

4) One of the tool that scenario editors usually use to make the AI recruit more diverse units (and also for limiting difficulty), is limiting the number of concurrent recruits of specific type in the field. Now they are doing it via a WML macro - it's better if recruiting would allow parameterization, allowing scenario creators to easily specify some 'what to recruit' hints and limitations. An example would be 'consider recruiting water-based because I want this leader to control the waterways' or 'recruit enough scouts in the first three turns because I want the AI to start capturing more villages early'. The optimal number of scouts varies with the map, of course.

5) This leads to another problem - if AI recruits some units thinking of particular purpose, it must use them properly - i.e., if a fish is recruited, it should not be used to move it to land to fight - otherwise, it makes little sense to recruit the fish in the first place'

6) Several years ago we tried an approach where the AI was finding 'most important' hexes on map and using the terrain on those hexes to affect it's recruitment patterns (instead of using the entire map)

7) Recruiting first is a huge disadvantage, because of possibility to recruit counters to enemy units. So, if the AI recruits first, it should recruit to minimize the potential for counter-recruiting (i.e., by making a balanced army which can't be hard countered by enemy potential recruits)

8) Sometimes it makes sense to hold back and not recruit even if gold is available - for example, if you're playing a campaign and current scenario is already 'beaten', or if you're waiting for the enemy to recruit units to counter them. This makes sense for the AI which usually defends and which usually wins if time runs out - so, the AI can afford to let the player come to it's position, so, it can afford to recruit some scouts and wait for the human to approach before committing to specific types of units. Also, AI has problems with grouping units so if units are recruited one-by-one, they would be would not be sent in a group.

= More info (irc transcript) =
ok, "1.support recruiting with multiple leaders."
by definition, leader is unit which can recruit. each leader can have his own recruit list in additional to side's recruits (it's a new feature added recently).
now, AI only uses the first leader to recruit (so, if 1st leader is not on keep, it might not recruit even if 2nd leader is on keep and can recruit) 14:07
we need a way for the AI to figure out the fastest way to spend it's gold
for example, if there are two leaders on different keeps, they can both recruit
and, if those leaders are not on keep, AI should figure out a good keep for each leader, and move them to keeps
for now, it doesn't matter if the AI is not splitting the recruits intelligently enough (but it'd be a plus) - i.e. if AI would recruit half of units with leader 1 and half of units with leader 2, that would be better than today.
but, of course, it's possible to figure out a way to recruit units closer to where they'll be needed.

next, "2. support per-leader recruit/recall lists. " - that is the extension of the previous problem - if we have multiple leaders, they can have their own limitations on what they can recruit/recall.
next, "3. support easy limiting of recruitable units. " - we might want to limit AI to 'up to 3 units of levels 2+' or 'up to 5 Trolls'
currently scenario creators do that by modifying AIs recruit lists on the fly when units recruited or die.
but, it would be much better if they would be simply able to provide values/formula about units which can be recruited now.
for example, before recruiting, AI would be able to check what units are available to recruit, and how many of units of particular type can be now recruited.
note that the desire to limit the recruits is, sometimes, to set the difficulty level - but, sometimes, it is to make the AI recruit more varied units.
generally, usually scenario creators want each unit that the AI is able to recruit, to be recruited even if it is bad - they want player to see a variety of opponents.
moreover, currently AI is overestimating the value of high-level recruits - they cost more, they are good in combat, but they die easily because 3 1st-level units usually survive for longer than 1 3rd-level unit.
so, they would be glad if the AI would recruit a good mix of units. such mix arises naturally from math in some formulas - for example, if AI would recruit 10 woses, an enemy would be able to counter it with units like fire archers or skeletons, which are effective against them.
but, currently-used formulas don't provide a good mix of units.

next, "4. Analyze map terrain better". basically, on each map, the terrain is varied, but some terrain is not interesting because it's far away from where the combats will be.
generally, on a 2-player map, the area between the combatants is the most interesting, and the corners of the map are not that important
so, it makes sense to recruit units which are better in the middle of the map, where most of the combats would happen
also, sometimes, it's important to recruit some specific units to get villages or to get to targets which are over water - but it's important to recruit only the amount needed to do so
i.e., on starting the game, it makes sense to recruit some fast 'scouts' to get the villages faster - but the AI should determine the correct number of scouts (or let the scenario editor tell it)

next, "5. recruit units that are more useful " - currently, AIs recruitment and AIs usage of units are independent. so, AI can happily recruit a merman (fish) and then send it to fight over land. so, if AI is recruiting a unit, it'd be good to recruit units for some particular purpose (so, later, AI would remember that and use them for their purpose)
i.e., we should be able to store somewhere in the unit that 'this unit was recruited because we want to get some villages with it', or 'this unit was recruited because we have a target in a forest, and this unit is good there'
this would help both in debugging, and in teaching the AI to send those units where they make most sense
the reverse is also true - we might want to tell the recruitment about our priorities and targets, so it'd recruit units which are useful there
for example ,if we have 3 leaders, in the west, in the east, and in the center, and our target is in the west, it would make sense to recruit with the western leader first and most.

Next, "6. improve counter-recruiting strategies. " - if human would recruit a unit which is vulnerable to cold, the ai would like to recruit a unit with a cold attack , such as dark adept. this makes sense. But, if the AI would recruit 10 dark adepts, putting all the money there, it's a problem
because, on next turn, human would be able to recruit some units which are useful against dark adepts
but the AI won't have any more money to respond..
so, the AI should recruit a mix of units which can't be countered easily, and which are good both against units human currently has, and against units human can recruit/recall
this is especially bad in campaigns, where human player might have a horde of high-level recalls - so, if AI spends all the gold on 1-2 unit types, human player would be able to recall proper counters

and the AI is supposed to cheat a little and know what human can recruit.
basically, even a simple minmax calculation would allow the AI to recruit some kind of mix of units - for example, "recruit units which are best in combat over all possible human counters next turn"
if AI recruits a mixed set, it's hard to find a hard counter to it.
i.e., if the AI recruits a dark adept and a skeleton, it can't be countered by berserker easily (since berserker would die to the skeleton)
while, if the AI would recruit two skeletons, they can be countered by dwarven infantry with hammers
and, if the AI would recruit two dark adepts, they can be easily countered by berserker
so, 'mixed recruiting' arises naturally here.
and, last from that list, "7. improve recruiting for AI-playable campaigns where AI has to not spend all the gold."
sometimes, the scenario is already almost won, but the gold would be useful in the next scenarios - it makes sense to stop recruiting or only recruit a handful of units in this case.
so, there should be a way to switch recruitment into 'conserve resources' mode (and back, if necessary)
that's all for the basic list of ideas
it's ok if not all of them are implemented, or if you add some of your own ideas
but, the resulting recruitment should be better than the one we have now.

=Whom to ask about this=
Crab_ on irc.

@@ Line 16: / Line 16: @@
 Most likely, a new implementation would be coded from scratch, taking parts of existing C++ code as a guideline.
-Required skills: mainly C++, a bit of lua (can be learned during the project)
+Suggested skills: mainly C++, a bit of lua (can be learned during the project)
 {{#dpl:

@@ Line 14: / Line 14: @@
 # improve recruiting for AI-playable campaigns where AI has to not spend all the gold.
-The implementation would be coded from scratch, taking parts of existing C++ code as a guideline.
+Most likely, a new implementation would be coded from scratch, taking parts of existing C++ code as a guideline.
 Required skills: mainly C++, a bit of lua (can be learned during the project)

← Older revision		Revision as of 20:28, 26 March 2013
Line 15:		Line 15:

	The implementation would be coded from scratch, taking parts of existing C++ code as a guideline.		The implementation would be coded from scratch, taking parts of existing C++ code as a guideline.
		+	Required skills: mainly C++, a bit of lua (can be learned during the project)

	{{#dpl:		{{#dpl:

@@ Line 41: / Line 41: @@
 ) AI only uses first leader to recruit - but, if there are multiple leaders, it might be useful to recruit with all of them.
-) AI cannot use per-leader recruit lists - but, leaders can have unique recruit lists (ask fendin about this feature).
+) AI cannot use per-leader recruit lists - but, leaders can have unique recruit lists (ask fendrin about this feature).
 ) Scenario editors want the AI recruit all units or most of the units, even if some of them might seem suboptimal from 'combat' point of view, but, as AI only considers combat/movement 'for the entire map', it might miss units which seem suboptimal. An example situation is where a unit has a specific role in the strategy, serving as auxiliary unit or as a hard counter to some specific opponent unit.

@@ Line 1: / Line 1: @@
 {{Template:SoC2013Idea}}
 = Description =
-<h2>AI: Refactor recruitment algorithm [5]</h2>
+<h2>AI: Refactor recruitment algorithm</h2>
 Page for the idea: [[SoC_Ideas_AI_Recruitment_2013]]

@@ Line 13: / Line 13: @@
 # improve counter-recruiting strategies.
 # improve recruiting for AI-playable campaigns where AI has to not spend all the gold.
 {{#dpl:

SoC Ideas AI Recruitment 2013 - Revision history

Beda: /* Additional Information */

Crab: /* Description */

Crab at 20:31, 26 March 2013

Crab: /* Description */

Crab: /* Description */

Crab: /* Description */

Crab: Created page with '{{Template:SoC2013Idea}} = Description =

AI: Refactor recruitment algorithm [5]