Implementation of "true" probability calculator

[Dash_Riprock]

Boredom can do amazing things.
I finally made a “true” probability calculator.  It takes an exponentially longer time to run based on the number of units, but it is still very fast unless you try ridiculously massive battles, especially with lots of subs or an AA gun.
Making an algorithm to calculate the chance was surprisingly easy, but making it efficient enough to be practical was somewhat of a challenge.  :-)
You will also need Java.  And remember to click the “details” button.
http://www.filefactory.com/file/7236f2/n/AAProbability_jar

EDIT: I just fixed a bug and posted the fixed version. The old one had a problem with setting the unit loss order.

[cyan]

this looks really cool. i you got some competition now frood.  :-) but i people were argureing for awhile how to do this. they couldn’t agree how did you do it? ( i won’t be able understand the computer stuff probably)

[Dash_Riprock]

Well…  here it goes.
The basic idea is that it follows every possible path the battle can take, along with the chance that it will take each given path, until all the paths end, that is, one or both sides run out of units, or the number of rounds has reached the “hit and run” value. At this point the number of units for each player and the chance of arriving at that situation are stored for the result.  For a given situation, it has to figure out the chance that each side will hit every given possible number of times, e.g. the chance that 2 infantry and 1 armor will hit zero, one, two, or three times.  It then has to do the same thing for the defender, and then create every possible offshoot from the current situation.

For instance, a situation of 1 infantry on attack and one on defense will have 4 possible outcomes after one round of rolling:
attacker hits 0, defender hits 0
attacker hits 1, defender hits 0
attacker hits 0, defender hits 1
attacker hits 1, defender hits 1
The chance of, for example, the second one occurring is (1/6)*(2/3)*c, with c being the chance that this particular situation would arise in the first place.
In this situation, all possible outcomes will result in the battle being over, i.e. they wont have to create any new paths that have to be further calculated.

Of course, there is a problem: this will result in an infinite loop of each side missing forever, which is where some math comes in.  That possibility is ignored, and c has to be increased by the chance that both sides will miss, plus the chance that both sides will miss again, etc., forever. Conveniently, it works out that this particular infinite series just equals 1/(1-n), where n is the chance that both sides will completely miss.  In the 1 inf. vs. 1 inf. example this would mean that the first situation would never be calculated, and c would be multiplied by 1/(1-(5/6)(2/3)) = 2.25. None of this is necessary if “hit and run” is enabled, though, since the number of battles is limited anyway.

The way it calculates the probability of a given number x of units hitting is by using a formula (n choose k)p^k(1-p)^(n-k), where n is the number of events, k is the number that must be true, and p is the probability of each event being true.  It has to set up 5 different sets of events for the 5 different chances of a unit hitting, i.e. defending bombers or transports are in the first set of 1/6, while defending jet fighters are in the set of 5/6. It then has to use an algorithm to find every possible combination of x different hits, and add all the probabilities up.  In a battle with lots of attacking infantry and tanks, the chance that exactly two units hit is the chance that exactly 0 infantry and 2 tanks hit, plus the chance that 1 inf. and 1 tank hits, plus 0 inf. and 2 tanks.

The current product has a number of improvements over the original, most notably that it allows paths to re-converge and add their probabilities together rather than calculating the same parallel paths over and over again.

sits back in chair, panting

[Motdc]

Good work, I always wanted to do that, and I posted extensively on the method but never found the time to do the implementation.  Kudos to you!

Question:

When you hit details, should all the percentages in the Exactly mode add up to 100%?

[bananaman]

Hmm, I saw a topic about someone wanting this to be done and I was thinking about creating one, but it seems that I am already beaten.

My method for calculating the possibilities was pretty similar.  To simplify, let’s start with a battle of 4 inf attacking 2 inf.

We need to find out the probability for the attacker hitting between 0 and 4.  This is quite easy.  We take the fourth row of Pascal’s Triangle.

1  4  6  4  1
We will use this as a modifier value.  This would be the chance that you would hit at a die roll of 3.

Because inf hit at 1 value and miss at 5 values.  We will use the following row to multiply our modifiers by…
5^4  5^3  5^2  5^1  5^0

After the multiplication this yeilds…
625  500  150  20  1

These numbers represent the chance out of 6^4 (1296).

So the attacker will have the following outcomes…
0 hits = 625/1296 = 48.225%
1 hits = 500/1296 = 38.58%
2 hits = 150/1296 = 11.57%
3 hits = 020/1296 = 01.54%
4 hits = 001/1296 = 00.077%

If we do the same thing for the defender we get
2 hits = 4/36 = 11%
1 hits = 16/36 = 44%
0 hits = 16/36 = 44%

Now we have to combine all these possibilities to arrive at the chances for the new amount of troops left.
For this specific case we can combine the 2,3, and 4 hits for the attacker b/c they all arive at the same point.
We end up with the following probabilities after the first round of attacks.
2inf - 0inf = 1.466%
3inf - 0inf = 5.864%
4inf - 0inf = 5.864%
2inf - 1inf = 4.287%
3inf - 1inf = 17.147%
4inf - 1inf = 17.147%
2inf - 2inf = 5.358%
3inf - 2inf = 21.433%
4inf - 2inf = 21.433%

Now we have the probabilities for the remaining units after the battle.  We have to analyze each of these possibilities to see what results from the new battle.

Of course we complicate this with the addition of multiple types of units, but you get the general picture of my proposed idea.  It looks like I can stop trying to implement it b/c your version works fine.

Great job, thx for all the hard work.

[Dash_Riprock]

Right, we essentially had most of the same ideas.  The choose function is the same thing as a given position on Pascal’s triangle. For efficiency, it pre-calculates the first 300 or so levels of Pascal’s triangle, as well as the first 300 powers of 1/6, 2/6, 3/6, 4/6, and 5/6 when the program is launched.

The thing that makes it really complicated is when you not only have multiple unit types but also subs involved, since you have to consider the number of normal hits, and for each one of those you also have to consider every possible number of naval-only hits for each side.

[losttribe04]

I opend the link you posted and this is I found.

“Invalid Quickkey. This error has been forwarded to MediaFire’s development team.”

I opened it several times and always came to the same conclusion.

LT

[Dash_Riprock]

It seems that the sharing site decided my file wasnt important enough.

In other news, I fixed  a small bug with how the AA worked.  I thought that the total number of hits was decided by the dice and then the attacker chose which of his planes he lost, but now I know that the dice gets rolled for each individual plane, which can make a slight difference in the odds.

[losttribe04]

Dash keep in mind that in some rule sets the AA will fire upon the FTR’s and casulties will be removed then the AA will fire upon the BMR’s then those casulties will be removed.

I have seen this rule become more popular b/c once you get the the closing stages of a game you may but say 10 FTR’s to absorb AA fire and let the 10 BMR’s do the dirty work.

LT

[mshih]

This is in response to Dash’s comments about how to compute the probability terms used in his calculator.

P(n units getting k hits, if p is the probability of 1 unit getting one hit) = (n choose k)p^k(1-p)^(n-k).

Since axis & allies has non-homogenous forces (i.e. infantry + armor + bombers), these terms need to be further combined with complicated algorithms.

There’s a simplification to this problem, if we assume fixed order of loss.

Let p(i) == the probability of the ith unit getting a hit.  (e.g. for attacking inf ==> 1/6, attacking armor 3/6, etc…)
Let p(i) be defined in the reverse order of loss.  This can be initialized trivially.

Let P(i, j) == the probability that i units gets j hits.  This is the matrix that we’re trying to fill in.

The following recurrence relation holds:
  P(i, j) = P(i-1, j-1) * p(i) + P(i-1, j) * (1-p(i))

We then just need to define the initial conditions:
  P(0, 0) = 1
  P(0, j) = 0 for all j > 0
  P(i, 0) = P(i-1, 0) * (1 - p(i))

We can now fill in P(i, j) for all i, j and compute all of the probability terms that will be needed for the attackers.

The beauty of this formulation:

• No powers
• No factorials
• No special logic needed to handle non-homogenous forces.
• Complexity to compute all probability terms needed is O(n^2) :).
• All of the subproblems solved are needed and will be used.

Unfortunately, I believe updating the probabilities themselves is O(n^4).  So the computation of the probability terms themselves shouldn’t really be the bottleneck if they are precomputed.

• Mitchell

[Dash_Riprock]

Sorry for the slow response, obviously I haven’t been on here in a while.

mshih:  You idea looks like it would work very efficiently, except that the order of loss is not determined.  Things like AA guns, subs only hitting ships, and in AA50 planes not hitting subs unless destroyers are present would make this extremely complicated.  It might still be possible to make a more efficient algorithm using a very complicated implementation of this, but I’m not going to be the one to do it.  :-)

[dinosaur]

Good Job.

I have been working on some probability problems myself, but I use spreadsheets and do the calculations in a sort of assisted longhand mode.  Then I print tables of results for different situations.  I have a thread in AAG with an example of my results.

If we had a straightforward 1/3-2/3 hit rule or something like that, then we would have a very simple calculation that resembles the battles for Risk.  But because our “to-hit” chances change for the units, things get much more involved.  And then to top it all off, the defender gets to decide what to remove.  This isn’t too difficult in most land battles, but becomes involved in sea battles.  And then sometimes we get anti-aircraft artillery.  All this makes the probabilities in A&A very complex.

In my opinion, there would probably be a limit where the probabilities could be precomputed, and everything below say 20 units is stored in a matrix for recall later.  Then, only battles with more than 20 units on a side would get a calculation.  These would be resolved down to the 20 unit level, and the matrix results would be applied below that.  Unfortunately, the fact the defender chooses losses may foil this approach.

Ultimately, I hope to even have the calculation tell the attacker when he should stop attacking and withdraw.  In every battle, there comes a point when the attacker has taken such ridiculous losses, he shoul withdraw.  I’d like the program to indicate this in the result.

[mshih]

Actually fixed order of loss is pretty reasonable assumption for odds calculator…. We have to assume some type of standard order of loss.  It doesn’t have to be strictly decreasing…  For example, if attacker wants to capture at all costs, we can lose fighters and bombers before tanks.  Or if attacker wants to capture with at least 10 ground units, that’s also possible.

AA guns can be handled by constructing separate tables corresponding to number of AA gun hits.

So if attacker has 2i, 2a, 2f, and we’re facing AA gun, we need to solve
F(f, f, a, a, i, i)  ;; 0 AA hits
F(f, a, a, i, i)  ;; 1 AA hit
F(a, a, i, i)  ;; 2 AA hits

Subs only hitting ships can be handled in similar approach…
Suppose the defending force is 2 fighters, 1 carrier, 1 battleship

If the attacking force has some subs, then we may need to remove units out of order.  So we need to compute:
F(B, C, f, f)    ;; 0 naval hits
F(B, f, f) ;; 1 naval hit
F(f, f) ;; 2 naval hits