TI3 Dice Battles Revisited Part 3
For the third installment an actual table of results is computed.
In some earlier posts on this thread, part 1 and part 2, I explored the math of computing probabilities of dice battles in Twilight Imperium. Now to put it to the test and see the final results of recreating the table from the post on science of board gaming.
The following are some examples of how I chose to set up the basic data structures in Haskell. I used pairs to represent each side in the conflict. So I needed a list of probabilities and number of dice per unit on each side, which is simple enough. The state is a bit more complicated, because hits possible are also needed to be represented. So I used another list inside, for example a fully loaded war sun is [1,0], and a war sun with one hit is simply [1].
exampleProb = ([0.8], [0.2]) :: ([Double], [Double]) exampleDice = ([3], [1]) :: ([Int], [Int]) exampleState = ([[1,0]], [[1]]) :: ([[Int]], [[Int]])
Some helper functions for working with pairs are useful.
pmap f (a,b) = (f a, f b) pzip (a,b) (c,d) = (zip a c, zip b d)
Now to compute total units present from a state (removing the odd hit point structure), so that can be folded into number of dice per unit. This is used to compute the hit probabilities for each side. A normalization factor is computable from these as well, so that the null case of both sides missing can be removed.
units state = pmap (map sum) state dice state d = pmap (map (\(x,y) -> x*y)) $ pzip (units state) d hitProb state d p = pmap odds $ pzip (dice state d) p nullFactor a b = 1/(1-(head a)*(head b))
Now this bit is critical. The strategy of removing hits determines the outcome. I assume that first hits are removed from units with more than one hit. They still can shoot and there's a possibility of recovery during reset. Then hits are removed in the order in the list. The code to do this is a bit cryptic, and makes a language like Ruby shine for it's readability in dealing with such things.
-- For the multi-hits, knock down to bottom category
multiHit h (x:[]) = (h, [x])
multiHit h (x:xs) = if x <= h
then multiHit (h-x) $ (x'+x):t
else (0, x-h : x'+h : t)
where x' = head xs
t = tail xs
-- When no multi-hit units are left, go for the singles
singles h x = singles' h $ map head x where
singles' h x = map (\x -> [x]) $ snd $ mapAccumL f h x
f acc u = if acc > u then (acc-u, 0) else (0, u-acc)
--apply hits to a state
damage side hits = if h > 0 then singles h s else s
where (h, s) = mapAccumL multiHit hits side
--example : damage [[10], [2,1]] 5
Now from the possible outcomes of a conflict, the probability of a win can be computed.
outcomes s d p = map f g where (ha, hb) = hitProb s d p n = nullFactor ha hb ob = zip ha $ map (damage (snd s)) [0..((length ha)-1)] oa = zip hb $ map (damage (fst s)) [0..((length hb)-1)] o = sort $ tail [ (((snd a, snd b)), n*(fst a)*(fst b) ) | a <- oa, b <- ob] g = groupBy (\x y -> (fst x) == (fst y)) o f x = (sum (map snd x), fst (head x)) wins s d p = foldl f 0.0 o' where o = outcomes s d p o' = map (\(a,b) -> (pmap sum (units b), a, b)) o f total ((them, us), prob, state) = if them == 0 then total + prob else if us > 0 then total+prob*(wins state d p) else total -- probability of n fighters versus a war sun fighters n = 100 * (wins ([[1,0]],[[n]]) ([3],[1]) ([0.8],[0.2]))
That was a bit of a whirlwind at the end, but means of counting wins easily be changed to count the occurrence of other criteria. The grouping and sorting in the outcomes was needed to pull together similar outcomes. Further this code is very inefficient, it computes the same results over and over. One could actually just compute a grid of outcomes, and store it in an array based on total hits available. The array would compute a result as needed and store it so that computation wouldn't require recomputing. Presently this code recomputes nodes on the probability tree over and over.
The part I find most interesting is the results of n fighters battling a war sun. What are the odds that the war sun is eliminated (including surviving and mutual destruction).
| Fighters | My Prediction | Swenson's Prediction |
| 1 | 0.0324136 % | 0.00026 % |
| 2 | 4.74044 % | 0.43 % |
| 3 | 15.2180 % | 5.36 % |
| 4 | 32.0342 % | 20.20 % |
| 5 | 49.6767 % | 34.96 % |
| 6 | 66.3731 % | 55.28 % |
| 7 | 79.8336 % | 73.54 % |
| 8 | 88.8660 % | 84.31 % |
| 9 | 97.4902 % | 92.18 % |
So right at 5 fighters there's close to even odds of the war sun going down by my program's prediction. The article which started me on this TI3 Dice Battles, stated that 5 fighters had a 34.96% chance of defeating a war sun. I think the difference is due to how we defined winning in that I included mutual destruction as a win as well as some surviving fighters. I think that in Swenson's post his math is correct. The question now, that numbers and code is thrown around and the numbers aren't the same, is there any way to validate these numbers?
I chose to use a statistical experiment and pit 5 fighters versus a war sun for 100 trials. I got some volunteer help from my two daughters and we knocked out the test in 15 minutes. Turns out the fighters eliminated the war suns 53 of the 100 times. Is this close enough? Is the 34.96% close enough? Was my daughter cheating? I used hypothesis testing on both of these estimates of the number of wins and the value of 49.6767 results in a Z-score of 0.6646739, and the value in the other article (34.96%) results in a Z-score of 3.783211. The 95% confidence interval has a Z of ~1.98. Hence, there is sufficient evidence to reject 34.96% as the true value with 95% confidence and, there is insufficient evidence to reject 49.6767 as the true value. So with this simple experiment the value of 49.6767% survives. To be truly a statistical test more experiments are required, at a minimum 2 more, but the results are promising.
This opens up a can of worms, as in many gaming scenarios a point system is used to rate equivalence of different playing pieces. 5 fighters can defeat a war sun about half the time, but some of these times they survive to fight another day and are probably worth a bit more than a war sun. It gets very tricky when 3 differing types of units are involved and the relationships are asymmetric. One has to take all these factors and find a minimum in there somewhere. Overall, a difficult problem.
The next feat I think will be moving on to writing an iPad app for all this. I'll include some optimizations I mentioned and probably recode the whole thing in Javascript.
Comments