Calculation time for AI

[Saphy]

Currently, AI is slow when berserker is involved, and even worse when there is drain on both side. Currently, AI calculated the chance to kill by running a simulation per unit for all permutation. Instead, why don't we use a rough estimation, to see if a unit can be killed by doing damage x strike x chance_to_hit when either side have more than 5 strikes or berserker. The same can apply for the damage preview. When the actual attack is made, then the simulation can be ran for real.

[Kymille]

This would also help a lot for Survival Extreme scenarios, so much so I have to think it's been discussed.

[Zachron]

Except, a computer has no way of doing "rough" estimations. It gets exact values from specific sources. Designing an algorithm for it to be less exact, might even make the computer take longer. What the AI has to do essentially, is sort, then search. The search can be made optimized, and the sort can be optimized, but even to make a "rough estimation," if there really is such a thing, would still require the AI to examine every possible move at least once. If we're talking simply the CTH/CTK calculations, then more can be done. Perhaps have the AI look only at CTH/CTK over a limited number of attack cycles. (i.e. calculate the CTK calculation for Berzerk as if it is Berzerk(3) or something along those lines.) The potential problem here is, the check for how many attacks to run the algorithm for, would end up being applied to all considerations, including the vast majority of iterations where the number of attacks for each unit is less than 5. This would make it slightly slower on each of those considerations, making the algorithm only faster in situations where the (usually uncommon) units with 5+ attacks or Berzerk are the majority of units in the field. Every situation where there were lots of units with less than 5 attacks (a very common situation in Wesnoth) would result in the AI running slower.

A far simpler solution would be to alter algorithm, which calculates these probabilities, to make it more efficient, yet just as accurate. (although I cannot be sure the developers have not already optimized this algorithm as far as it would optimize... there may not be much room for improvement.)

[AI]

It has been optimized so far it can be hard to figure out how it does what it does. The only real alternative would be going back to just running X simulations and then generating some approximate probabilities from that. But that would be empirical rather than exact.

[Rya]

Well for survival and several other "vs ai" scenarios a more dumb ai might actually play better because it's just supposed to walk towards the closest target and attack the target it can deal most damage to (especially in survivals). It doesn't even have to consider more complex things.

We already have a selection for the "AI" in 1.6.5 but only one is available so far. Maybe a faster one that doesn't consider all complex attack combinations (maybe just goes through the units one by one and just decide for a single unit how to move at a time) would be plausible for certain scenarios.

[Yoyobuae]

I wonder just how much good for the AI comes from being exact.

I mean, in very simple terms, the AI just needs to search for a good set of moves to do. Doing an overly complex calculation to evaluate the worth of one move can possibly make the search much slower, thus reducing the amount of searching that can be done without having players get bored while waiting.

Then again, it would be extra work to code an alternative method to get an approximate to the probability calculations and that is good enough to be used but faster. So I can understand why the current AI works like it does.

[pinkdwarf]

Currently, AI calculated the chance to kill by running a simulation per unit for all permutation.

Surely this can't be true as the number of permutations is infinite. It's always perfectly possible for an ulf to fight with e.g. a mage for 1000, 1000000 or no matter how many rounds, although that is very unlikely. So the algorithm already has to stop after a certain number of rounds, thereby making a "rough" estimate. I'm just guessing here (haven't looked at the code), but I think the optimizing that it has gone through could have something to do with having the number of simulated rounds depend on things like hitpoints and chances to hit.

[thespaceinvader]

Incorrect. The longest that an ulf (or anything with berserk) can fight for is 30 rounds, for precisely the reason you suggest. The ability has an artificial limitation at that point.

[pinkdwarf]

Ok good to know. One simple thing it could do would be to assume no sequence of misses less likely than, say, 5% ever happens. That would mean hitting at least once every four attacks with 40% defense for example, which could keep the number of calculated rounds fairly small while not affecting accuracy much. It probably already does something like this? Well anyway, drain and 70% defense would still be poison.

[m0ta]

Except, a computer has no way of doing "rough" estimations. It gets exact values from specific sources. Designing an algorithm for it to be less exact, might even make the computer take longer.

Good luck with a route planning algorithm, that doesn't estimate roughly...

[Gambit]

Except, a computer has no way of doing "rough" estimations. It gets exact values from specific sources. Designing an algorithm for it to be less exact, might even make the computer take longer.

Good luck with a route planning algorithm, that doesn't estimate roughly...

The answer may be "rough" or rounded, but the process consists of steps based on hard, accurate, data. Is how computers work.

[Sapient]

Since this is ostensibly a coding discussion, I have moved it to the Coder's Corner.

[Ant]

About a year ago, i looked at the code for the damage calculation, so if my recall is patchy, please be forgiving.

In earlier versions of Wesnoth the damage prediction was done by doing several (10, 50 i am not sure) simulated attacks using the RNG and averaging over the outcome.

This was changed to an exact calculation using a probability matrix, covering every possible outcome. This works really good for standard game play and is the preferable solution.

Where it does not work so well is in scenarios like Survival Fusion, or Survival Xtreme, where units get 10-30 times the standard health and up to 20 the number of strikes. As a rough estimate for the size of the probability matrix you can say it is linear in hp and linear in strikes. If both are high you get immensely big probability matrices. If drain or berserk is involved it gets only worse. But the worst offender is the ability swarm, which makes the probability matrix quadratic in hp.

These matrices are allocated, initialized, calculated, and deallocated for every single damage calculation. For SurvivalXtreme at later turns involving units with 3000 hp, this can easily mean, that for every damage calculation matrices of the size of 200-400 MB are used. This is of course slow, when the ai has to do it for several hundreds? possible moves.

Perhaps it would be an easy fix to include an if-branch in the damage calculation if any of the units involved has more than 250 hp, to switch to the older damage calculation using the RNG and a simple averaging.

Another possibility could be to replace some of the overhead generated by the use of the STL in this part of the code and switch to simple c-style arrays, since it is such a performance relevant part of the game. Further the allocation/deallocation of the memory does not have to been done anew for every single damage calculation, but only if the damage calculation does not fit in the already allocated one, which could stay persistent in memory until a bigger one is needed.

[m0ta]

Good luck with a route planning algorithm, that doesn't estimate roughly...

The answer may be "rough" or rounded, but the process consists of steps based on hard, accurate, data. Is how computers work.

If you do it the computer science way, the answer you get has to be correct or you're doing estimations based on heuristics or approximations. Yes, the steps a computer takes are deterministic but nevertheless for a given model the steps are only approximating the way it should be computed. Travelling Salesman or Route Planning is a classic problem were correctly computing (e.g. almost all paths in the search space have to be evaluated) is infeasible for even a very small number of "cities" or nodes in a graph.

[Sapient]

I believe Ant is correct except that the code is already using C-style arrays for the probability matrices.
A patch to implement one or both of his other suggestions, however, would be welcome.
The if-branch may also be needed if extended formulas or ActionWML becomes allowed in AbilityWML.