• Moderator

    I think he means that the Infantry gets a 95% chance at winning but I could be wrong…


  • Correcto guerilla. It’s possible in finite numbers for an odds calculator to generate a 95% chance of winning for the 1 inf. It’s also possible for a person to run through a brick wall, technically speaking, though.


  • As hard as the standard problem would be to produce a completely deductive odds calculator, it would be a lot easier to produce one for lowluck! Unlike standard dice where all battles can potentially last infinitely long (if both sides only roll 6s), a large proportion of LowLuck battles are guaranteed to be finite, and those that are not (ones that can potentially see both sides with not enough forces to make one guaranteed hit) have exactly 25 different “possibly infinite” scenarios, which of course can just be worked out in advance by hand and loaded into the calculation on demand.


  • @Avin:

    …it would be a lot easier to produce one for lowluck!..

    This is a good observation, but battles with units like subs and fighters (and destroyers) tend to mess everything up as they can’t hit certain units.

    What are the official rules regarding this?  Say 3 fighters and two subs attack a battleship and 5 subs in lowluck what happens? is it the same as a normal battle?

    I have now the option for low luck, but it only combines units of the same type, so for 7 infantry and 3 armor attacking 15 infantry, three dice are rolled.  Is this incorrect?

    Because of this situation with units can/can’t hit other units the possible outcomes is greater than  25, also with aa guns the outcomes are greater too.  I see this as not being an easier problem to solve programming, but computationally much easier for a computer to calculate exact odds with low luck.

    I would like to note also that for small battles with my calculator my computer rolls 500,000 rounds a second and converges to the nearest tenth of a percentage  a second.  Theoretically the odds will converge after an infinite amount of time, but for practical purposes they will converge always correctly, and you can see this.  If the calculator reports otherwise, then the random number generator is at fault.  Calculators that only roll 100 or 1000 battles have serious problems, that is why I have my program always rolling in the background, so if needed it could calculate a battle with thousands of units given enough time.

    How should I graph retreats?  I have now a plot of all the outcomes by likelyhood, but I would like to also plot battles that result in retreating, I’m not sure what goes on what axis.  Do I need two plots?

    Thanks for all the ideas


  • I have it working now for exact odds to some degree :(  It will do one unit vs 1 unit.  It is close for other battles but there is a bug somewhere… give me a few days.

    For 1 armor vs 1 infantry

    
    Exact Odds mode
    Attack:  50.00%     Attack takes: 50.00%
    Defense: 50.00%     Annihilation: 25.00%
    
    

    any programmers have an idea on a good way to write exact odds?  I have now two co-recursive functions calling eachother with for loops and ahaha it’s messy!  It then has to keep track of the situation where neither unit hits the other, and re-normalize the values at the end of a round.  I’m happy I did it with random numbers first!


  • ok I fixed it, exact odds for small battles converges instantly, but as I thought it takes very long for large battles

    It is exponentially slow to calculate, and my algorithm isn’t great, but the best I can do is maybe a 10x speedup with a lot of work.  With a battle with 9 units it takes 3 seconds.  It takes 30 seconds for 10 units!

    It’s true that exact odds is very interesting,  but for large battles, it does not converge in a reasonable amount of time, so I should include both methods at least in the calculator, really iteratively is adequete, this is just for fun.

    So, please think of a very fast way to do this calculation!!

    I will add low luck support (as soon as I learn the correct rules) and hopefully it will always be reasonable for this.

    btw, sorry for all the posts :(


  • Your query for the programming is what I suggested originally. I had previously mentioned pre-calculated results of battles, but it’s pretty simple from there to throw in some good dynamic programming that would make it even faster. I’ll describe an algorithm below.

    First, the rules for LowLuck are that all units are grouped together regardless of type. So in the example you gave (7 infantry and 3 armor attacking 15 infantry) the attacker has a strength of (7+33=) 16 and the defender a strength of (152=)30, so the attacker has (16 / 6 =)2  guaranteed hits and rolls one die to determine if he gets an additional hit if the result is (16 mod 6=)4 or less . The defender has (30/6=)5 guaranteed hits and does not need to roll any dice.

    You’re right in that subs are treated special; the attacker has a choice in how he wants to use his subs in a naval battle: he can choose to either use their first strike ability or forgo it for each sub on each round. So for instance, in the example you give (3 ftrs 2 subs vs 1 BB 5 subs) the 2 attacking subs can choose to take their first strike at a strength of 4, so they would roll one die, and then the fighters would attack as normal at a strength of 9 so they get one guaranteed hit and roll one die at a strength of 3. Or they could choose to use one sub for its first strike ability at a strength of 2, and use the other sub like normal with the fighters at a strength of 11, so that way having one guaranteed hit and roll one die at a strength of 5 for another. Or they could forgo the first strike completely (for this round) and then their total strength would be 13; they would get two guaranteed hits and roll one die to hit on a 1.

    Now, I found this rather interesting: I tried out some sample battles on DAAK’s LowLuck server and got some very interesting results!

    Battle 1: 5 fighters vs 20 subs - Attacker has 2 guaranteed hits and rolls 1 die at 3 for another hit. The defender does not roll because his subs cannot hit back.

    Battle 2: 5 fighters, 1 sub vs 20 subs (Attacker does not use first strike) - Attacker has 2 guaranteed hits, and rolls 1 die at 5 for another hit. The defender has 6 guaranteed hits and rolls 1 die at 4 for another, BUT is only able to sink the sub, so the remaining “hits” are wasted.

    Battle 3: 5 fighters vs 20 subs, 1 trn - Attacker has 2 guaranteed hits and rolls 1 die at 3 for another; the subs cannot fire but the transport can, so the defender rolls 1 die at 1 (no guaranteed hits).

    Battle 4: 5 fighters, 1 sub vs 20 subs, 1 trn (Attacker does not use first strike) - Now this is the intesting one! All the ones above seemed to make sense, but this one defies reason. Attacker has 2 guaranteed hits and rolls 1 die at 5 for another hit - so far so good. The defender has 6 guaranteed hits and rolls 1 die at 5 for another, AND THE HITS ARE NOT WASTED! The defender wins the battle, killing all five fighters even though it is obvious that the fighters could not have all been hit by the single transport.

    Maybe this is a bug in DAAK’s LL roller : I will submit it to them and see what they say. I’m sure this situation doesn’t come up that often of course, since it’s not very likely for anyone to amass subs like that.

    Anyway, let me propose to you a recursive algorithm for computing land battles without AA guns and you can generalize pretty easily I’d think. For AA guns, simply add a single round of combat in which no units fire but the AA gun does, and for naval combats, perhaps you could include a couple option boxes reflecting the strategy for how subs are to be used: “Always use first strike” “Never use first strike” “Use first strike only if there are enough subs for a guaranteed hit, and use remaining subs in regular combat” “Save enough subs for regular combat to bring the combat strength up to either a 5 or 6, and use remaining subs for first strike”.

    1. Test whether the current battle is an “end case”: that is, whether the total strength of both attacker and defender is less than 6. If so, assign a precalculated probability to all outcomes that you can load from a file, and return these values.
    2. Test whether this battle has already been calculated previously while running this algorithm. If so, load the results and return these values.
    2. Analyze the possible outcomes of the current round of battle and assign each of the (up to 4) different outcomes a probability, so that the sum of the probabilities is 100%
    3. Recursively call this algorithm on each of these outcomes, and multiply their return values for the final outcomes they predict by the probability for that individual outcome you computed in step 2.
    4. Return the result, adding probabilities for any identical final outcomes.

    Note: Steps 1 and 2 are distinct; step 1 refers to the 25 different “infinite” battles I referred to above, whereas step 2 is a dynamic programming method of caching already determined results that will significantly prune the tree you are searching.

    Take as an example this battle: 3 inf 3 arm vs 6 inf

    Note that my algorithm above corresponds more closely to a DFS approach, but I will be taking a BFS delineation of it to simplify for the reader.

    The possible results after the first round are:
    1 inf 3 arm vs 4 inf (100%)

    There is only one result, so we recursively look at it. The possible results for the second round are:
    3 arm vs 3 inf (2/9 chance)
    3 arm vs 2 inf (4/9 chance)
    2 arm vs 3 inf (1/9 chance)
    2 arm vs 2 inf (2/9 chance)

    So we recusrively look at each of these.

    The outcomes of the (2/9 chance) 3 arm vs 3 inf battle are:
    3 arm vs 2 inf (1/4 chance)
    3 arm vs 1 inf (1/4 chance)
    2 arm vs 2 inf (1/4 chance)
    2 arm vs 1 inf (1/4 chance)

    The outcomes of the (4/9 chance) 3 arm vs 2 inf battle are:
    3 arm vs 1 inf (1/3 chance)
    3 arm vs 0 inf (1/3 chance) - battle over
    2 arm vs 1 inf (1/6 chance)
    2 arm vs 0 inf (1/6 chance) - battle over

    The outcomes of the (1/9 chance) 2 arm vs 3 inf battle are:
    2 arm vs 2 inf (1/2 chance)
    1 arm vs 2 inf (1/2 chance) - end case

    The outcomes of the (2/9 chance) 2 arm vs 2 inf battle are:
    2 arm vs 1 inf (2/3 chance)
    1 arm vs 1 inf (1/3 chance) - end case

    At this point, to eliminate step (2) in my algorithm, let’s simply add up the common outcomes:
    3 arm vs 2 inf (1/4 * 2/9)
    3 arm vs 1 inf (1/4 * 2/9) + (1/3 * 4/9)
    2 arm vs 2 inf (1/4 * 2/9) + (1/2 * 1/9)
    2 arm vs 1 inf (1/4 * 2/9) + (1/6 * 4/9) + (2/3 * 2/9)
    1 arm vs 2 inf (1/2 * 1/9) - end case
    1 arm vs 1 inf (1/3 * 2/9) - end case
    3 arm vs 0 inf (1/3 * 4/9) - battle over
    2 arm vs 0 inf (1/6 * 4/9) - battle over

    So, you can see how this will end up, right? The two end cases present would be calculated in advance, so there is no need to calculate a potentially infinite battle. This algorithm would work to calculate any battle in a relatively short amount of time, particularly since you could even store outcomes in a file and load them in step 2 between battles and then the more you use this, the easier it becomes for the program to calculate battles!


  • If you just want to download the program:
    http://www.firethroat.com/aaodds/aaodds-0.30.tar.gz

    I see what you are saying, I already did this for non-low luck battles,

    The program can calculate battles using random numbers or it can calculate the battle mathmatically using some sick convoluted co-recursion I came up with, feel free to read the code I added extra comments in calcodds.c

    I was mainly asking for a more efficient algorithm I don’t think one exists.  This method works great for small battles, just don’t try 30 units, it will take years.

    I did not do caching, but I don’t think it would matter much, either the database is massive, or the speed up won’t be noticable, am I wrong?

    If there is a bug with a single transport can hitting 5 planes,  it is exactly the situation I don’t understand.  What really does happen?  What is the official rule on battles where certain units  can’t hit other certain units?

    Calculating the battles manually is O(n!) operation, so it works ok for small numbers but above a certain value it is ridiculous (above 9 units), of course 5inf vs 5 inf takes longer than 5arm vs 5 inf since there are many more rounds involved.  and much deeper recursion.

    maybe I will do lowluck soon,  (or maybe you can try all the source is included)  It has a basic lowluck setup for regular dice, if I knew the real rules maybe I can make it fully complient.  My way is roll one dice for each type of unit, I think it’s is simple and reduces luck a lot.  Honestly it’s kind of pointless since the calculations are within .05% after a second for the iterated approach, and it works for huge battles.

    For subs I would just have two types of subs, first strike and non-first strike to solve this, that is already done.  There is not a good way to move subs between stacks between rounds.

    Thanks for the feedback.


  • Two things:

    First, this approach is understandably going to be extremely large for non-LowLuck because the algorithmic complexity is O(n!) as you said. However, Low-Luck is only O(4^n) which is still exponential, but much better.

    Second, caching will make a HUGE difference, as it is the difference between polynomial complexity and exponential, both for LowLuck and for ADS. In fact, the benefits of caching will be even more obvious in ADS.


  • Oh, by the way, I was able to come up with another completely different algorithm that is more space-intensive involving utilizing one K dimensional array of probabilities per battle round (where K is the number of different types of units) but this approach does not improve over the previous one in terms of time, provided you do utilize caching as I just mentioned.


  • http://home.centurytel.net/khb/aa/aa_odds_grapher_install.exe is an actual odds calculator (rather than simulator) I wrote that mostly works (there’s a bug with heavy bombers and first strikes from subs I never got around to fixing).

    The help file has the formulas, etc., I used.

Suggested Topics

Axis & Allies Boardgaming Custom Painted Miniatures

46

Online

17.0k

Users

39.3k

Topics

1.7m

Posts