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

WARNING: Unfinished

Description

PL_kolek - AI 'total defense strategy'

My goal is to make AI play more cautiously. Currently it only tries to kill as many units as possible without taking into account possible enemy moves. I'm going to build into the current algorithm some mechanism to improve AI behavious.

IRC

PL_kolek, PL_kolek_, PL_kolek__, PL_kolek___

The project

Introduction

How complicated wesnoth AI is everyone knows. But there is no single recipe how to improve its behaviour. My plan is to incorporate into current RCA AI several mechanisms, that, working together, will make it better opponent. Predicting damage dealt in the next turn wouldn't give much advantage if used separately, but it's a bulding block of forming defensive lines, which can be programmed as Candidate Action. There is also one mechanism, that is required to devise working AI: statistics.

WML parameters

New AI behaviour involves many new tunable parameters. I'd like to expose them in WML for scenario creators, so that AI can behave differently in every scenario, or in case defaults don't fit this particular use case. For example:

[Prevent_enemy_moves]

Value indicating how focused the AI should be on limiting enemy's movement choices.

[max_group_size]

If the AI considers the units in groups, how big should the groups be.

Statistics logging

Algorithms play a big role in my project and generally in AI, but it won't work without lots of experimentation, tuning and tweaking. Every constant, unit value and so on needs to be set carefully to ensure proper behaviour. For that I'll need a logging system to gather all important information, that I can then plot and analyse. Exemplary data to gather:

Estimated enemy damage

What our function computed (described in next chapter).

Enemy damage

What harm the enemy caused in reality.

Group move value

How we estimated value of chosen move of group of units.

Separate move value

As before, but for moves made separately.

Heuristics to evaluate enemy response

First and most important step in making AI smarter is teaching it to take into account enemy actions in the following turn (by turn I mean what happens direcly after I click 'end turn'). In a perfect world that would suffice - we could even learn from the computer new tactics for ideal balance between my and enemy losses. But we all know that Wesnoth game tree branches so quick, that PCs cannot even check all it's possible moves, not to mention the next level of the tree. To siplify calculations, RCA AI takes unit after unit, move after move and considers them in separation. While it decreases complexity exponentially, it makes is impossible to think about setting up a wall, backstabbing and so on. Assuming the AI doesn't change it in the next few months, we need to quickly evaluate our losses in enemy's turn. For that we need something like:

[Damage_estimation] tag

While finding (with experiments) 'the best' evaluation algorithm and making the AI use it a good solution, why not let the user/developer choose or even write it on his own? This way scenario creator could choose more accurate (but computation heavy) algorithm in small scenario and lightweight (but less accurate) for bigger ones.

[Iterative_damage_estimation] tag

That's similar to previous tag, but this function takes previous map situation and evaluation, a move and calculates new one from that data. That's different from former approach, because it required recalculating everything after every move. This one should evaluate only subset of data, and thus will be faster. On the other hand, I still don't know if such iterative approach is possible in the world of wesnoth AI. If it turns out that it doesn't fit at all, I'll drop that tag.

[Estimation constant]

Provided that functions for estimating damage are simplified turn simulation (that will be always the case), the less accurate we estimate, the smaller damage we predict. That's because we anticipate to receive expected value of damage dealt with optimal strategy. If we simplify calculations, well get much less optimal choices. Set this constant to 1.25 (or some other magic value) and the results should be in proximity of real outcome. Simple, but better than current magic 'aggression constant', because relevant to calculated enemy damage.

Now some proposals for damage_estimation algorithms:

Simulate enemy turn

Simplify a lot CAs, cut out not needed and play it! Simple idea, providing that AI is really good at killing things, the results will be accurate. But... the CPU will burn. With some work, maybe on little 1 vs 1 maps it would work.

Farthest first heuristic

Order units from the farthest, choose best attack possible, evaluate outcome. The order is chosen that way, so that no unit will be blocked from its attack by other units having more possibilities.

Random order heuristic

Choose order of units randomly, simulate, calculate result. Repeat a few times and take the worst case scenario. If the evaluation is quick, it may be repeated many times (controllable by [random_evaluation_repetitions] tag).

Curtailing enemy movements

Damage is only one of the parameters we need to take into account. Next one is how our choice affects enemy possibility to make actions. Basically the less hexes he cn reach the better. The more our move limits the enemy, the higher it's score is. I hope this would make AI catch the enemy between two of its units naturally, without special CA for that. Morevoer, every time we prevent the enemy from reaching our/neutral/his village (leader, unit, etc.) it will be reflected in higher score for that move. Again - this won't solve all the problems AI has, but gives it more ways to think about the battle.

Connecting moves together

The trickiest part of whole wesnoth AI. Because of complexity, thinking of turns in terms of moving all units at once is impossible. But, every CA requires a global plan and coordination of units. For example:

1. Attacking with first unit in a turn usually means that at a first glance, that unit will die according to our evaluation: Our unit is in line with other units, can't be killed. Then it moves, attacks, takes some damage and is alone in the front. Now the evaluation will return that we will lose at least one unit, without killing any. But if we could think a little more, we would notice that our next moves will bring the rest of army together, protecting that lonely unit.

2. Forming a defensive line. First unit doesn't give us anything - neither it deals massive damage, nor it protects injured friend in the village. The second and third will form an impassable wall. Currently not possible to bypass.

3. Backstabbing. There is no point in attack a full health enemy protected from sides. Taking into account second move - backstab, it turns out that it was profitable.

Possible solutions to that problem: -Give higher scores to CAs in range of many friendly units which haven't moved yet. That solves (1.).

-Add specific CAs just for that. With mechanisms decribed earlier, such CAs should be easy to write and easy to evaluate. There is not that much such tactics, and that would be sufficient.

-Refactor AI and allow it to move units in small groups. For example the AI would consider 3 adjacent units, plan a move for them together, then separately and choose better option. This will require to devise special algorithms for choosing units which should go to one group. That's hardest of the solution.

Timeline

May 3 - May 27 (pre-GSoC)

Further improve proposal
Dig deeper into the AI and AI code
Try to implement simple ideas as a training

May 27 - June 17 (community bonding period)

Get into details of the AI
Exams at the university
Start coding

June 17 - July 25

Writing movement and damage evaluation heuristics
Integrating some log for easy comparison of AI algorithms

July 25 - August 2 (midterm evaluation)

Test, test, test
Find out magic constants
Resolve any issues

August 2 - August 31

Implementing CAs for walls, backstabs, retreats, etc...
Heuristics for taking into account other moves

September 1 - September 16

Test, test, test
Improve code, so that it can be merged into master
Tweaking and benchmarking the AI

September 16 - September 27 (final evaluation)

Stop playing around, polish to state of 100% finished product
Write documentation.
Update wiki pages.

Goals / Milestones

Note: Optional goals are goals that I really want to do, and are optional, because I can resign of them if the more important things will take too much time. I plan to implement them though. Moreover, I am sure, that more optional ideas will come to my mind while working on the project and will be added here (and implemented, I hope).

ID	PRIORITY	DESCRIPTION
1	MANDATORY	Learn everything current AI and plan where to change it
2	OPTIONAL	Implement simplified version of some ideas decribed here
3	OPTIONAL	Analyze current work on Fred AI, decide how much of this can be used in the project.
4	MANDATORY	Use results of previous steps to detail and improve proposal as much as possible.
-	MILESTONE 0	Have all mandatory steps and at least one optional above done when the coding period starts (Jun 16)
5	MANDATORY	Write one good and general heuristic calculating estimated value of enemy's damage dealt.
6	OPTIONAL	Write other heuristics (fast, randomised, precise) for that purspose.
7	MANDATORY	Write one good and general heuristic calculating estimated value of enemy's possible moves.
8	OPTIONAL	Write other heuristics (fast, randomised, precise) for that purspose.
9	MANDATORY	Add possibility for users to choose and implement their own heuristics (WML)
10	MANDATORY	Implement logging of important AI statistics and results.
11	MANDATORY	Experiment a lot and choose best values for all involved parameters.
11	OPTIONAL	Let the user configure those parameters in WML
-	MILESTONE 1	Have at least all mandatory steps above done until August 2.
12	MANDATORY	Add support for group Candidate Actions
13	MANDATORY	Implement Canditate Actions for group moves like backstab, defensive wall etc..
14	MANDATORY	Revisit all Canditate Actions, change scoring if necessary, so that it becomes comparable with group CAs
15	OPTIONAL	Allow AI to think in terms of groups of units in general, any case, not only in those specific CAs
16	MANDATORY	Experiment a lot and choose best values for all involved parameters.
17	OPTIONAL	Let the user configure those parameters in WML
-	MILESTONE 2	Have at least all mandatory steps above done until Sep 9
18	MANDATORY	Clean up the code
19	MANDATORY	Benchmark, optimise, compare performance with previous AI
20	MANDATORY	Write documentation
21	MANDATORY	Update/add wiki pages with detailed and friendly description
22	MANDATORY	Test, Test, Test
-	MILESTONE 3	Have at least all mandatory steps above done until Sep 23.

Questionnaire

User:PL kolek

Contents