True odds calculator

@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

That’s a little beyond my depth… If someone wrote it though I could implement it as the engine for AACalc.

Sorry, that was a very stream-of-conciousness kind of posting.  I’m sure if I spent some time I could have laid that out better.  It just tapped into something I recall having fun with a ways back and then I just went nutz :)

Mot

What is AACalc written in?

@Motdc:

What is AACalc written in?

PHP

I’ve never done any PHP, what language is it similar to?

Mot

That looks long enough and detailed enoght to read not when I’ve had a drink or two.  Thanks for the link, I’ll check it out this weekend!

Mot

@Motdc:

I’ve never done any PHP, what language is it similar to?

Mot

http://en.wikipedia.org/wiki/PHP I think will tell you what you want to know. PHP is a scripting language that was developed in C, so I think the syntax may be similar to C, but I don’t know C.

It is easy to learn, as I picked it up on my own and have no other programming knowledge other than BASIC and Turbo Pascal from high school in 1992-1994.

I’ve always thought that the creators of Perl got together and said:  “You know, all those funny puntion marks never get used enough, lets create a progarmming language where you have to use every funny symbol on the keyboard.  We’ll make a killing selling replacement SHIFT keys when they get worn out from being used in every third character typed while coding”

:-D

I made a calculator in a non-internet based Java application that runs the simulation 1 mil, 4 mil, or 16 million times divided by the number of units in the battle, depending on the settings.  So, for instance, if you run a battle with 10 units on each side on high accuracy, it will run 800000 times in about 5 seconds, and come within 1/10th of a percent every time.  And Java is even considered slow compared to other languages like c++.

Your problem, Frood, is just that its going to run allot slower on an internet based program, unless there is some alternate language or method that works better. I guess it ends up being a trade-off between accuracy/time and convenience.

@Dash_Riprock:

I made a calculator in a non-internet based Java application that runs the simulation 1 mil, 4 mil, or 16 million times divided by the number of units in the battle, depending on the settings.  So, for instance, if you run a battle with 10 units on each side on high accuracy, it will run 800000 times in about 5 seconds, and come within 1/10th of a percent every time.  And Java is even considered slow compared to other languages like c++.

Your problem, Frood, is just that its going to run allot slower on an internet based program, unless there is some alternate language or method that works better. I guess it ends up being a trade-off between accuracy/time and convenience.

Does your sim handle submarines and abort conditions and such? I think those things really slow it down too.

Not that it matters, do you REALLY need to know to an accuracy of 1% or less?

@Frood:

Does your sim handle submarines and abort conditions and such? I think those things really slow it down too.

Not that it matters, do you REALLY need to know to an accuracy of 1% or less?

Yes, it does, to the best of my understanding of the rules, and I think I have everything down right.  The only real problem it has that I know of is that the IPC lost details assume that units always die in the same order, so it just gives the results in numbers of units remaining, but in the case of AA guns and subs, this is not always the case.  I didnt think of that, though, until later and I dont feel like changing it now.  Not that its really a big deal, since it doesnt affect the actual chances.

As far as the accuracy thing, well, I didnt really think it was necessary either, but apparently some people want it REALLY accurate. :-)

I’d like to build a Java version of AACalc, but sadly I do not speak Java :(

A Java app would have much greater portability, obviously. What yours lacks is some of the flexibility and detailed output that AACalc generates. I’d be interested in collaborating on a java-based tool.

True Odds calculation would be even better, if we could do that. Maybe me, you and Mot could all contribute - Mot seems to understand the math involved in true odds calculation.

Im not really that interested in this anymore, but I could give you the source if you want and you can do whatever you want with it-I warn you though, it wasn’t exactly designed for anyone else to read.

BTW you know there are more options and results in separate windows right?

No I hadn’t noticed. (runs to check) Hey that’s cool! Except the bar graphs do this transparent thing that shows whatevers behind the window there, it’s very distracting.

I wouldn’t mind playing with the source, be a good way to learn Java maybe. PM me for my e-mail addy.

@Frood:

I’d like to build a Java version of AACalc, but sadly I do not speak Java :(

A Java app would have much greater portability, obviously. What yours lacks is some of the flexibility and detailed output that AACalc generates. I’d be interested in collaborating on a java-based tool.

True Odds calculation would be even better, if we could do that. Maybe me, you and Mot could all contribute - Mot seems to understand the math involved in true odds calculation.

I’ve done some Java and I am slightly tempted…once we are in the fall and things get more sane…hmmm…

http://en.wikipedia.org/wiki/Pascal’s_triangle

oo pascal u secksy fiend, you cut down calculation time so much . . . leaves time for other things.

Maybe if we get nekkid pix of Jen then I can be um, inspired, to write a true odds calculator.

@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).

Honestly, I dunno wat a “memoization” is.

I will say tho that large complex battle computations take a lot LONGER than a dice simulator.

Me am Dice Simulator.  Me say “You hit twice.”

Me am Large Complex Battle Computer.  Me say “You hit 20%.  You miss 30%.  Ur enemy hits 15%.  35% of time scenario repeats.”

Here’s wat u do (simple)

First you get Microsoft Excel and someone that knows how to plug in formulas and stuff and use concatenation etc.  Then you put the first 100 or so lines of Pascal’s triangle into a big array of arrays.  (So the first array element of the array of arrays will be “1”, the next will be “1, 1”, the next will be “1, 2, 1”)

You need to do this because it cuts down on calculation time a lot.

Then you write the bit that gets the user input.

Then you split the user input into types.  Like, let’s say that the user input is “3 infantry 1 tank attacking 2 infantry”.  You split that into “3 attacking infantry”, “1 attacking tank”, and “2 defending infantry”.

Then you use Pascal’s triangle to generate a list of possible outcomes for each of those types.  Like let’s say you attack with 3 infantry.  You have a (1/6) ^ 3 to hit 3 times, a 2 * ((1/6)^2*(5/6)) to hit 2 times, a 2 * ((1/6)*(5/6)^2) to hit 1 time, and a (5/6) ^ 3 to hit 0 times.  You can see the Pascal’s triangle element; “1, 2, 2, 1” here.  (You can use combination mathematics, but just making a fat Pascal’s triangle array is a lot more efficient on calculation time).

Okay, so once you have a list of possible outcomes for each of those types, you multiply the attackers list together (and give the appropriate output), and then you multiply the defenders list together (and give the appropriate output).

Now, there’s a certain probability that nobody will get a hit.  If you want to rerun the battle if nobody gets a hit on the first round, or report the result, whatever.  But realize that you can’t ask the program to “resolve” an unresolvable battle.  If you don’t write in something to account for the probability that nobody gets a hit, you could stick your program into an infinite loop.

Easiest way to do it is to make each probability outcome fraction (use fractions, not percentages for in-program calculation) have a common denominator.  Then you whack out the probability of all missing, and add up the remaining numerators to get a single denominator.

I’d do it myself, but I need nekid Jen pix for inspiration . . .