User:PL kolek

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.

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]

The less accurate we estimate, the smaller damage we predict. 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.