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.

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.

IRC

PL_kolek, PL_kolek_, PL_kolek__, PL_kolek___

Questionnaire

User:PL kolek

Contents