Implementation of "true" probability calculator


  • 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%?


  • 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.


  • 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.


  • 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


  • 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.


  • 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


  • 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

  • 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.  :-)


  • 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.


  • 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

Suggested Topics

Axis & Allies Boardgaming Custom Painted Miniatures

24

Online

17.0k

Users

39.3k

Topics

1.7m

Posts