@djensen:
I would like to see a true odds calculator. The problem is that my math is rusty and I’m not sure how to handle complex probability calculations such as would be required for Axis & Allies.
Anybody good with probability computations? I just need help with the math.
I have already figured out that a true odds calculator should use memoization otherwise large complex battle computations will take as long as a dice simulator. (Memoization is basically caching results of previous calls to a function for future use, it’s perfect for these math related operations).
Hmmm…
I had started such a thing a ways back, and had to research and document some probability formulas before I started, too so I might be able to dig up some useful info.
The approach I was looking at was along the lines of a depth-first search kind of like the classic min/max (or MiniMax) AI algorithm, with a lot of the intermediate propablity calculations pre-calculated and put into lookup tables.
(Ignoring 1st strike subs etc for now)…
Given any Attack (A) by a number of units (N) there are actually only N+1 distinct taack outcomes (O):
If you have 3 Inf, and 2 Arm at first glance it looks you have 5d6 for each round to deal with, which is 6^5 or 7776 permutations.
But you can simplify that based on looking at each die as a hit or a miss so that is conceptually like rolling 5d2, which is 2^5 only 32 permutations.
We can simplify that further because if when viewed as 2 groups of similar units 3@1 (for the infantry) and 2@3 (for the armour) the 3@1 has 4 distinct outcomes (0 hits, 1 hit, 2 hits, and 3 hits) and the 2@3 only has 3 distinct outcomes (0, 1, and 2 hits). That yeilds 4*3 = 12 disctinct outcomes.
***It’s at this level that I’d start having the probabilities cached. See DB samples at the end of the post ***
And of course we can boil that down one more time, as the battle as a whole (with 5 total units) can have 6 different outcomes (0 thru 5 hits).
What makes it possible to simplify like this is that you track the weight of permutation or outcome.
When looking at both sides put together the total possible number of final outcomes is:
number of attacking units + number of defending units + 1 …(actually it’s +2 because there is an “undefined” bucket as well, more on that later).
These become “buckets” where out final result can be accumulated.
So now for each weighted attack outcome AO0, AO1, AO2, etc the same process is applied to the Defense (D). Each attack/defense outcome pairing (AO1DO1, AO1DO2, etc) has a weight and new state (that basically being the new number of attacking and defending units).
Now using either a recursive or stack-based approach you feed that back into the process above. As you are drilling down, you are calculating a smaller and smaller slice of the probablity pie. (If you were just flipping coins it would go from 1/2 to 1/4 to 1/8). You stop drilling down and exit when the resultant state has found a winner or (very importantly) you reach a minumum weight where you bail out. This is because there is a non-zero prbobality of a battle lasting forever (imagine a battle where nothing but 6’s are rolled). On exiting you take the probablity amount you just calculated and add it to the bucket that matches you final state (of put it in the “undefined bucket” if you reached your minimum threshold).
When the stack unwinds it should yield a true probablity distribution of each outcome possible.
Phew!!!
Mot
*** Back to the DB caching I mentioned earlier:
For those 3 infantry attacking at 1 imagine you can do:
select hits, weight from outcomes where strength = 1 and quantity = 3
Yielding
hits weight
---- ------
0, 0.5787037037037037037037037037037
1, 0.34722222222222222222222222222222
2, 0.069444444444444444444444444444444
3, 0.0046296296296296296296296296296296
You can even let the DB handle both the infantry and armour at once:
select
(inf_outcomes.hits + arm_outcomes.hits) comb_hits,
(inf_outcomes.weight * arm_outcomes.weight) comb_weight
from
(select hits, weight from outcomes where strength = 1 and quantity = 3) inf_outcomes,
(select hits, weight from outcomes where strength = 3 and quantity = 2) arm_outcomes
And to let the DB the final bit of heavy lifting:
select comb_hits, SUM(comb_weight)
from (
select
(inf_outcomes.hits + arm_outcomes.hits) comb_hits,
(inf_outcomes.weight * arm_outcomes.weight) comb_weight
from
(select hits, weight from outcomes where strength = 1 and quantity = 3) inf_outcomes,
(select hits, weight from outcomes where strength = 3 and quantity = 2) arm_outcomes
) inf_arm_outcomes
Group by inf_arm_outcomes comb_hits