battle odds bug

[gggol]

I found problems with the battle odds calculations.

In game 4246, twice I sent 2 pikemen to attack a city with a heavy infantry and +5 walls. The first time, on turn 8, the computed odds were 68.5%. I lost. The 2nd time, on turn 10, the odds were 71.4%, and I won. Should have been the same odds both times, wouldn't you say?

I worked out what the odds should be myself, and I got 68.6%. Below is the math.




According to the docs, damage is only done if one unit hits and the other misses. For a 15 str unit to hit a 20 str, it has to roll a hit (15% chance), and the other must miss (80% chance).

Chance of 15 str unit hitting = 0.15*0.8 = 0.12
Chance of 20 str unit hitting = 0.2*0.85 = 0.17
Chance of 1 hit occuring = 0.12+0.17 = 0.29
(Chance of both missing = 0.68, chance of both hitting = 0.03)

Since 0.71 of the probability is discarded, the real odds are 0.12/0.29 and 0.17/0.29, for 0.4138 and 0.5862 respectively.

The chance of 1 20 str unit beating 2 15 str units is the chance that it gets 4 hits in a row:
0.5862 ^ 4 = 0.1180874
Plus the chance that it suffers 1 hit somewhere between the 4 hits it gets. There are 4 ways that can happen (5 total hits delivered, any of the 1st 4 can be the hit it takes. Can't be the last hit.)
0.1180874 * 0.4138 * 4 = 0.195455
Just add the chances of these 2 mutually exclusive possibilities together:
0.1180874 + 0.195455 = 0.313542
1 - 0.3135 = 0.686458. That's a 68.6% chance that the 2 15 str units will win.

[KGB]

gggol,

The math in your odds calculation is correct.

I ran my simulator with this battle (10000 times per run). I got between 68.1 and 69.5 for a winning percentage on 10 runs. The random number generator accounts for slight inaccuracy in my results compared to the pure math calculation.

I suspect that the 71.4% represents a random number inaccuracy which is going to be higher in Piranha case because he only runs 1000 simulations (10000 is too CPU intensive in a script).

I've seen similar numbers (off by 2-3%) when I've made 2 identical attacks in the same turn. Not much can be done unless the number of simulations can be increased to 10000. That's because you can't calculate a 'pure' math chance for most attacks because some bonus's are situational (anti-air, critical strike) and on one run may be in play but on another may not be depending on how soon a unit dies or if a critical strike occurs.

KGB

[gggol]

I should have guessed you were figuring the odds by Monte Carlo methods (repeated simulation). It's a fine way, and easy... for you, not necessarily for the computer. If you could calculate odds directly, might that help with the server load? You could also run the simulations (or make the calculations) for a few dozen of the most common match ups, save them in a table, then just look them up as needed.

While things like ambushes, death of units that provide bonuses to entire stacks before the end of the battle, anti-air and other situational probabilities complicate the calculations, it most certainly is possible to compute them directly! If you didn't know how to do it, you just saw a fairly simple example above. What math are they teaching kids these days?? Ever heard of a binomial coefficient?

[KGB]

gggol,

I should have guessed you were figuring the odds by Monte Carlo methods (repeated simulation). It's a fine way, and easy... for you, not necessarily for the computer.

Well with a compiled program doing 10000 simulations takes about 1 ms of time. The problem is this game isn't using a compiled program but an interpreted language which is brutally slow by comparison. That's why on larger battles you see the long delay before the battle actually shows due to the simulation time.

The other reason for using the Monte Carlo method is because it's much more likely that you get it right since simulating is much easier than computing the actual odds due to complexities in the battle model.

While things like ambushes, death of units that provide bonuses to entire stacks before the end of the battle, anti-air and other situational probabilities complicate the calculations, it most certainly is possible to compute them directly! If you didn't know how to do it, you just saw a fairly simple example above. What math are they teaching kids these days?? Ever heard of a binomial coefficient?

I have an actual honest to goodness math degree and I got mine over 20 years ago and have been using it ever since. LOL. So I know all about computing odds and how to use probability theory to do stuff like the 5-chose-4 example you showed.

With that said, I doubt it's possible to compute the exact odds without hundreds of hours of manually figuring things out. Who would want to do that kind of manual computation when a simulation can be written in 1/10 the time and be about 100X as accurate (since a math mistake will be very hard to catch while a simulation one is easy to spot).

For example, consider a stack of 2 Lt infantry, 1 Dragon, 1 Devil and 1 hero vs 2 Hv Infantry, 2 Orcs, 2 Elves, 2 Giants. How are you going to compute this *exact* odds. You literally have to compute multiple branches of the same calculation for each Orc (due to the 6% instant kill and the fact that instantly killing a dragon is vastly different than instantly killing a Lt Infantry so you have to branch for every possible unit each Orc could face and could kill). Then the Elves also need branches for their anti-air against the dragon. So instead of 1 binomial calc you end up needing at least 10+ just for this example alone. In a more complex example you might need 20 or 30 or maybe 100+ separate calcs all summed together to get the exact odds. If you want to volunteer to do such calc's and show them mathematically I am sure they will get used but you will be literally doing hundreds of hours of math. Then for any new feature in the game you'll be back doing it all potentially again if a new branch gets added. Or the simulation can be written in 10 minutes

KGB

[gggol]

You could still use the technique known as memoization to speed things up. Keep the Monte Carlo methods, and just augment with memoization.

[piranha]

Server load is definitely something that matters. Both in terms of speed when playing but also to be able to have more active players without using the servers resources.
I'm the one writing the battle functions and I'm the only one without any math degree .
But anything to take away load is worth discussion.

Right now battle works pretty well and we have a long todo list.

Memoization that you mention, would that be storing results in a table to look that up?

[gggol]

Piranha: Yes, that's the essence of memoization.

Might try to make it a bit fancier. Don't save every result, only some, as it would take a lot of space to save all. Try to save only the most common fights, maybe only those involving fewer than 7 or 8 units, or with all cheap, 1 turn units, something like that.

[piranha]

I thought a bit about it.
If the identifier for normal units are armytypeID(1-40)blessed(0/1) 191 for example for a normal unit.
Then heroes would have to be ID,Bless,leadership/chaos with consideration to terrain,ambush,group ambush, heroes will be a pretty long string of numbers.
Then there is the fight order so units might not be in the same order all the time.

Seems like this string of numbers will be quite long with just 4 vs 4 armies.
At least 8X3 numbers if only normal units.

Thing is also that small battles with few units don't take much time for the simulation while bigger battles take time but those are also going to be harder to find a match for.

[LichKing]

Are you sure gggol idea isn't easier to implement as you think? Using memoization wouldn't be a big step forward, as it would be calculating the exact winning probabilities in real time for each battle. I don't think it would be as hard as KGB said. For example:

1. calculate total stack bonus modifiers: here that would be -2 for 1st stack, 0 for 2nd stack

2. then start calculating the battle in real time (using unit vs unit winning chances as in gggol's examples): once it happens that a unit has >90% (or what you decide) winning chance against its opponent, that step is rerolled if the weaker unit wins. It is possible that the weaker unit wounds the stronger one, so in the next step that strong unit will see its winning chances lowered and will not reach >90% again (probably). So the strong unit can die in the next step.

3. Combat goes on, until another >90% is reached, and again the same check (reroll if stronger unit is killed).

Since now a unit which has >90% chances to survive the battle *will* survive anyway, battle results shouldn't differ much. Battle would be rolled only once anyway, not 10000 times. Some simulations could be run to see if battle outcomes are similar to the current system.

What I mean is, instead of calculating the winning chances for the whole battle (that would be a very hard process), you can put a reroll check at a unit vs. unit level.

[KGB]

LichKing,

That's not how the 90% rule works at all. The rule could really be just as easily called the 10% rule as the 90% rule.

What happens is that all the outcomes for a battle are found by the simulation. So in an 8v8 battle there are 16 possible outcomes (each side wins with 1-8 men left). The results are then placed next to each other and 10% (the most extreme results, the 7 and 8 men surviving in the 8v8 case) are removed from each side.

A simple illustration will help. In an 8v8 where the units are identical (8 Lt Inf) the results for each side look like (10000 simulations): 1200 1050 950 800 600 300 45 5 where the 5 means 5 times out of 10000 you'll win with all 8 men left and 1200 you'll win with only 1 man left. The other side has the exact same numbers.

Place them next to each other in chronological order (ie 1 man left for side A goes next to 1 man left for Side B)

5 45 300 600 800 950 1050 1200 | 1200 1050 950 800 600 300 45 5

Then graph this to help visualize it. Then remove 10% extreme outcomes. If you graphed it, what I am talking about is the area under the curve at the edges. So in 10000 simulations you need to remove 10% or 1000 worth for each side. That works out to 5+45+300+600 = 945 (as close as possible to 10%).

So the final battle says that either side can win with 1-4 men left which is about what you'd intuitively expect.

Note that 10% is never exactly possible except in very very rare cases. Most times it's going to be in the 7-10% range so that you might need to be 93% likely to win to actually get the guaranteed win. On the other side of things, if you are sending a suicide stack at a someone it means you will be guaranteed to do some damage to that stack as long as your total outcomes (the sum of your side of the results) exceeds 10% (the amount each side loses).

What you proposed is something totally completely different.

KGB