Topic: New soldiers fights program

Hi everyone!

My last thoughts were around soldiers problem: my fight simulation was doing great job, but it wasn't exact. My target was to create complete and exact simulation of fights. It isn't an easy job. So I was thinking about this for a long time and finished with (another) program .

The code:

You can see the code here:
https://github.com/einstein13/wl_soldiers_exact

Old program:
https://github.com/einstein13/wl_soldiers

The old one is checked many times and should not contain any bug. The new one is rather "new" and I don't know if there is any problem. Hope not!

Comparison between tables:

Old one:

(taken from: https://wl.widelands.org/forum/post/19573/)

New ones:

How I calculated all the stuff?

I have splitted calculations into three parts:

1. Probability of killing any soldier by any other soldier in N hits (with no miss!)
2. Probability of killing any soldier at exactly M tries and N no-miss hits
3. Probability of not-killing any soldier at exactly M-1 tries and up to N' no-miss hits

So for example if we have soldier A and B, A is an attacker (attacks first).
Then we calculate how many hits are needed to kill A -> B and B -> A, and all probabilities for that. So we will have a matrix of all possibilities:

To calculate that probabilities I was trying to calculate convolution (https://en.wikipedia.org/wiki/Convolution) of continuous uniform distribution (https://en.wikipedia.org/wiki/Uniform_distribution_(continuous)) and then calculate cumulative distribution function (https://en.wikipedia.org/wiki/Cumulative_distribution_function) for each result to get probabilities p(N_aX) & p(N_bX). But I failed. I've noticed that for N hits you can just draw N-dimensional cube and cut N-dimensional pyramid based on one apex of this cube. The probability is a ration between two volumes. OK, not exactly, but after a few modifications you will get it!
I can't prove this, so if there is a problem, please prove it. If not, please prove that too!

After that we have to calculate how possible is to kill B with N_a hits while he can kill A with N_b hits. That contained some steps inside:

Possibility of killing B: we know exactly how many are miss-tries and a possibility of that, also how many are hit-tries and a possibility of that. The only missing factor is how many times we can "pick" those tries between all tries. That is binomial coefficient (https://en.wikipedia.org/wiki/Binomial_coefficient).

Possibility of not-killing A: we have to calculate all the possibilities of correct miss-hit correct combination. After that we sum all them and get the result. With binomial coefficient in use we can simplify that a bit and make it faster for the computer.

Last part is to make the calculations working. Because we have infinite sum of all possibilities of 5-tries fights, 6-tries fights, 7, 8, ... and so on fights (with N_a and N_b kill-wins), we have to pick a border. Let it be 0.000...1 (10^-10) of "best" probability. So approximately after 15 cases, the calculations stopped and you can sum all the possibilities.

After all those problems solved I've spotted another one: computer calculations aren't exact (about 15-digits exact for standard floating point numbers). So I've researched a bit and found that Python has rational numbers and calculations on them are exact (you can't lose information with infinite numerator and denominator precision).

In short version that is whole my engine and hope it has no mistakes. Probably in a few weeks I will provide a pdf with all the equations I've used, but I am not sure if anybody is interested on that .

If you have any questions, please write them! Maybe I've made terrible mistake or you proved something else - check that!

einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/
backup website files: http://kartezjusz.ddns.net/upload/widelands/

Top

Quote