Go to page content

Garbett.org On NO, he's attempting to organize again!

Article — , 20 January 2011

Twilight Imperium Dice Battles Revisited Part 2

How to combine lot's of different binomial probabilities via discrete convolution

TI3 Hacan In a previous article I looked at some simple cases of dice probabilities in Twilight Imperium. To go forward and compute probabilities of several dice rolls, convolution of binomial distributions is required. For example, let's assume that one player has 6 fighters with a 20% chance of scoring a hit and 1 war sun with 3 rolls of 80% chance of a hit. The probabilities of outcomes of each of these is a set of probabilities. But I'm getting ahead of myself, first one needs a way to generate the binomial distributions for these. I'm going to use Haskell for these examples as my language of choice.

The first tool is the ability to efficiently calculate binomial coefficients. Fortunately this is provided by Mark Dominus on The Universe of Discourse blog. Here's the code he provides:

choose :: Integer -> Integer -> Integer
choose n 0 = 1
choose 0 k = 0
choose (n+1) (k+1) = (choose n k) * (n+1) `div` (k+1)

I've added simple binomial distribution calculation by using the formula from Wikipedia:

Probability Mass of Binomial Distribution 

dbinom :: Integer -> Integer -> Double -> Double
dbinom k n p = binomCoef*(p^k')*((1-p)^(n'-k'))
               where binomCoef = fromInteger (choose n k)
                     k'        = fromInteger k
                     n'        = fromInteger n

With this one can compute the probabilities for each of the two above cases:

*Main> map (\x -> x*100) $ map (\x -> dbinom x 6 0.2) [0..6]
[26.214400000000015,39.32160000000003,24.576000000000015,
  8.192000000000004,1.5360000000000011,0.1536000000000001,
  6.400000000000004e-3]
*Main> map (\x -> x*100) $ map (\x -> dbinom x 3 0.8) [0..3]
[0.7999999999999995,9.599999999999996,38.4,51.20000000000001]

Each of these are a list of percents, in order of possibility. The first entry in the list is the percent probability of getting zero hits, the second entry the probability of getting one hit, etc. In the second example only 4 entries are needed, since the war sun can never get 4 or greater hits on 3 dice. The oddities of computer floating point math are becoming apparent with the odd decimals way out at the end, adding a bit of error to the computations.

Throwing Dice Now the magic of discrete convolution is needed to mix these two distributions together. With a total of 9 dice, we should have 10 possible outcomes in terms of hits. Unfortunately, the derivation of this algorithm in an efficient manner isn't very easy to explain, but the concept is exactly the same as the previous post but with a lot more lines dividing up the probability space.

Discrete Convolution 

--Convolution
convolute a b = if (length a) <= (length b)
                  then convolute' a b
                  else convolute' b a
convolute' a b = map f [1..s] where
                    s    = la+lb-1
                    la   = length a
                    lb   = length b
                    f n = if n <= la
                            then cross (take n a) (reverse (take n b))
                            else cross (take t (drop da a)) (reverse (take t (drop db b)))
                            where
                                 t    = if (s-n +1) > la then la else s-n+1
                                 da   = if (n-lb) < 0 then 0 else n-lb
                                 db   = n-la

-- Compute the sum of the products of two lists of numbers
cross a b = sum $ map (\(x,y) -> x*y) $ zip a b

As a test, let's see if the previous post's example works:

*Main> let warsun =  map (\x -> dbinom x 3 0.8) [0..3]
*Main> let fighter =  map (\x -> dbinom x 6 0.2) [0..6]
*Main> map (\x->x*100) $ convolute warsun fighter
[0.20971520000000002,2.8311552000000004,14.037811200000005,
 30.94609920000002,30.368563200000025,15.877324800000011,
 4.7989248000000035,0.8460288000000008,8.110080000000007e-2,
 3.276800000000003e-3]

Example TI3 Outcome 1 Player Roll So now the probability of hits generated by one set of rolls for a mixed set of units is easily computed. Further for the outcomes of many units, simply convolute the first pair of outcomes and then convolute with the next outcome until the list is exhausted. For the sake of completeness, here's the code to roll multiple outcomes from a configuration list.

 

roll [] = []
roll ((dice,prob):[]) =  map (\x -> dbinom x dice prob) [0..dice]
roll ((dice,prob):xs) = convolute (map (\x -> dbinom x dice prob) [0..dice]) (roll xs)

Using this and the square division of the space between two players outcomes, a framework to add the probabilities can now be created. A simple state space search that keeps number of units each player has, and a probability tree of where they end up could efficiently compute the probabilities using these tools. That'll be in part 3 when I get around to finishing this investigation.

Comments