Dice probability problem

[Tomi Lindberg]

Hi,

I'm trying to find a way to calculate a distribution of
outcomes with any combination of dice. I have the basics
done, but I'm a bit unsure how to continue. My main concern
is how to make this accept any number of dice, without
having to write a new list comprehension for each case?

Here's a piece of code that shows the way I'm doing things
at the moment.

-- code begins --

# A die with n faces
D = lambda n: [x+1 for x in range(n)]

# A pool of 3 dice with 6 faces each
pool = [D(6)] * 3

# A List of all outcomes with the current 3d6 pool.
results = [x+y+z for x in pool[0] for y in pool[1]
for z in pool[2]]

# A dictionary to hold the distribution
distribution = {}

# If outcome is already a key, adds 1 to its value.
# Otherwise adds outcome to keys and sets its value
# to 1.
def count(x):
if distribution.has_key(x): distribution[x] += 1
else: distribution[x] = 1

# Maps the results with above count function.
map(count, results)

-- code ends --

Thanks,
Tomi Lindberg

[Alexander Schmolck]

Tomi Lindberg <to*******************@pp.inet.fi.invalid> writes:

I'm trying to find a way to calculate a distribution of outcomes with any
combination of dice. I have the basics done, but I'm a bit unsure how to
continue. My main concern is how to make this accept any number of dice,
without having to write a new list comprehension for each case?

You need to think about the right way to break the problem down into some
operation that can be repeated one fewer times than there are dice (if you
just have a single dice, nothing needs to be done) and then repeat it.

An obvious candidate is adding a single dice to the sums computed so far:

def addDice(sums, dice):
return [x+y for x in dice for y in sums]

If you have less than 1 dice the answer is
# len(pool) == 1
pool[0]

After that, each time you add a dice you need to call addDice on the sum
computed for all the previous dice and the new dice:

# len(pool) == 2
addDice(resultFor1, pool[1])
addDice(pool[0], pool[1])

then

# len(pool) == 3
addDice(resultFor2, pool[2])
addDice(addDice(resultFor1, pool[1]), pool[2])
addDice(addDice(pool[0], pool[1]), pool[2])

finally you get

# len(pool) == n
addDice(addDice(addDice(..., pool[n-3]), pool[n-2]) pool[n-1])

OK, so how do we get the repetition?

Conveniently the pattern f(...f(f(x[0],x[1]),x[2])...,x[n-1]) or equivalently,
if we write the infix operator * for f: x[0]*x[1]*...*x[n-1], can just be written as
reduce(f, x) in python. So we get:

reduce(addDice, pool)
== reduce(lambda sums, dice: [x+y for x in dice for y in sums], pool)

You should presumably also try writing this out as a single function, without
using reduce (but recognizing the (left) reduction pattern is useful, even if
you don't use python's reduce).

'as

[Alexander Schmolck]

Alexander Schmolck <a.********@gmail.com> writes:

addDice(resultFor1, pool[1])
addDice(pool[0], pool[1])

sorry should have spelled out that successive lines are meant to be
equivalent, i.e.

addDice(resultFor1, pool[1])
== addDice(pool[0], pool[1])

'as

[Antoon Pardon]

Op 2006-04-04, Tomi Lindberg schreef <to*******************@pp.inet.fi.invalid>:

Hi,

I'm trying to find a way to calculate a distribution of
outcomes with any combination of dice. I have the basics
done, but I'm a bit unsure how to continue. My main concern
is how to make this accept any number of dice, without
having to write a new list comprehension for each case?
IMO you are looking at it from the wrong side.

It would be better to construct distributions for one
die and make a function that can 'add' two distributions
together. So for 3D6 you first add the distribution of
a D6 to the distribution of a D6 and to this result
you add the distribution of a D6 again.

If you need more to start, just ask.
Here's a piece of code that shows the way I'm doing things
at the moment.

-- code begins --

# A die with n faces
D = lambda n: [x+1 for x in range(n)]

# A pool of 3 dice with 6 faces each
pool = [D(6)] * 3

# A List of all outcomes with the current 3d6 pool.
results = [x+y+z for x in pool[0] for y in pool[1]
for z in pool[2]]

This is very inefficient. I wouldn't want to calculate
the distribution of 10D10 this way.

Try to think how you would do this with only D2's.

(Triangle of Pascal) and generalize it.

--
Antoon Pardon

[Tomi Lindberg]

First, thanks to Antoon and Alexander for replying.

Antoon Pardon wrote:

It would be better to construct distributions for one
die and make a function that can 'add' two distributions
together.

As both replies pointed to this direction, I tried to take
that route. Here's the unpolished code I came up with. Does
it look even remotely sane way to accomplish my goal?

-- code begins --

# A die with n faces
D = lambda n: [x+1 for x in range(n)]

# A new die with 6 faces
d6 = D(6)

# Adds another die to results.
def add_dice(sums, die):
# If first die, all values appear once
if not sums:
for face in die:
sums[face] = 1
# Calculating the number of appearances for additional
# dice
else:
new_sums = {}
for k in sums.keys():
for f in die:
if new_sums.has_key(k+f):
new_sums[k+f] += sums[k]
else:
new_sums[k+f] = sums[k]
sums = new_sums
return sums

sums = add_dice({}, d6)
sums = add_dice(sums, d6)
sums = add_dice(sums, d6)

-- code ends --

Thanks,
Tomi Lindberg

[Gerard Flanagan]

Tomi Lindberg wrote:

# A die with n faces
D = lambda n: [x+1 for x in range(n)]

That can be written:

D = lambda n : range(1,n+1)

Gerard

[Dave Mandelin]

That looks reasonable. The operation you are implementing is known as
'convolution' and is equivalent to multiplying polynomials. It would be
a little more general if you had the input 'die' be a sequence of the
count for each outcome, so d6 would be [1]*6 (or [0]+[1]*6 if you
prefer). That would allow allow you to represent unfair dice and also
to add not just a die to a distribution, but to add any two
distributions, so you can play tricks like computing 16d6 as
(d6)*2*2*2*2. (The code above is a convolution that restricts the
second distribution 'die' to have only 0 and 1 coefficients.) The
general convolution can be implemented much like what you have, except
that you need another multiplication (to account for the fact that the
coefficient is not always 0 or 1). My not particularly efficient
implementation:

def vsum(seq1, seq2):
return [ a + b for a, b in zip(seq1, seq2) ]

def vmul(s, seq):
return [ s * a for a in seq ]

# Convolve 2 sequences
# equivalent to adding 2 probabililty distributions
def conv(seq1, seq2):
n = (len(seq1) + len(seq2) -1)
ans = [ 0 ] * n
for i, v in enumerate(seq2):
vec = [ 0 ] * i + vmul(v, seq1) + [ 0 ] * (n - i - len(seq1))
ans = vsum(ans, vec)
return ans

# Convolve a sequence n times with itself
# equivalent to multiplying distribution by n
def nconv(n, seq):
ans = seq
for i in range(n-1):
ans = conv(ans, seq)
return ans

print nconv(3, [ 1 ] * 6)
print nconv(3, [ 1.0/6 ] * 6)
print nconv(2, [ .5, .3, .2 ])

[1, 3, 6, 10, 15, 21, 25, 27, 27, 25, 21, 15, 10, 6, 3, 1]
[0.0046296296296296294, 0.013888888888888888, 0.027777777777777776,
0.046296296296296294, 0.069444444444444448, 0.097222222222222238,
0.11574074074074074, 0.125, 0.125, 0.11574074074074073,
0.097222222222222224, 0.069444444444444448, 0.046296296296296294,
0.027777777777777776, 0.013888888888888888, 0.0046296296296296294]
[0.25, 0.29999999999999999, 0.29000000000000004, 0.12,
0.040000000000000008]

[Antoon Pardon]

Op 2006-04-04, Tomi Lindberg schreef <to*******************@pp.inet.fi.invalid>:

First, thanks to Antoon and Alexander for replying.

Antoon Pardon wrote:

It would be better to construct distributions for one
die and make a function that can 'add' two distributions
together.
As both replies pointed to this direction, I tried to take
that route. Here's the unpolished code I came up with. Does
it look even remotely sane way to accomplish my goal?

-- code begins --

# A die with n faces
D = lambda n: [x+1 for x in range(n)]

# A new die with 6 faces
d6 = D(6)

# Adds another die to results.
def add_dice(sums, die):
# If first die, all values appear once
if not sums:
for face in die:
sums[face] = 1
# Calculating the number of appearances for additional
# dice
else:
new_sums = {}
for k in sums.keys():
for f in die:
if new_sums.has_key(k+f):
new_sums[k+f] += sums[k]
else:
new_sums[k+f] = sums[k]
sums = new_sums
return sums

sums = add_dice({}, d6)
sums = add_dice(sums, d6)
sums = add_dice(sums, d6)

-- code ends --

IMO you are making things too complicated and not general
enough. Here is my proposal.

-----

import operator

class Distribution(dict):

'''A distribution is a dictionary where the keys are dice
totals and the values are the number of possible ways
this total can come up '''

def __add__(self, term):

'''Take two distributions and combine them into one.'''

result = Distribution()
for k1, v1 in self.iteritems():
for k2, v2 in term.iteritems():
k3 = k1 + k2
v3 = v1 * v2
try:
result[k3] += v3
except KeyError:
result[k3] = v3
return result

def __rmul__(self, num):
tp = num * [self]
return reduce(operator.add, tp)

def D(n):

''' One die has a distribution where each result has
one possible way of coming up '''
return Distribution((i,1) for i in xrange(1,n+1))
sum3d6 = 3 * D(6)
sum2d6p2d4 = 2 * D(6) + 2 * D(4)

-----

--
Antoon Pardon

[Tomi Lindberg]

Antoon Pardon wrote:

IMO you are making things too complicated and not general
enough.

I believe that the above is very likely more than just your
opinion :) Programming is just an occasional hobby to me,
and I lack both experience and deeper (possibly a good chunk
of shallow as well) knowledge on the subject. I'll study the
code you posted, and make further questions if something
remains unclear afterwards.

Thanks,
Tomi Lindberg

[Alexander Schmolck]

Tomi Lindberg <to*******************@pp.inet.fi.invalid> writes:

# Adds another die to results.
def add_dice(sums, die):
# If first die, all values appear once
I'd add something like

sums = sums or {}

because otherwise your function will sometimes mutate sums and sometimes
return a fresh object, which usually is a very bad thing as it can easily lead
to quite nasty bugs.
if not sums:
for face in die:
sums[face] = 1
# Calculating the number of appearances for additional
# dice
else:
new_sums = {}
for k in sums.keys():
for f in die:
if new_sums.has_key(k+f):
new_sums[k+f] += sums[k]
else:
new_sums[k+f] = sums[k]
sums = new_sums
return sums

'as

[Tomi Lindberg]

Antoon Pardon wrote:

def __rmul__(self, num):
tp = num * [self]
return reduce(operator.add, tp)

sum3d6 = 3 * D(6)

One basic question: is there any particular reason not to
use __mul__ instead (that would allow me to use both 3 *
D(6) and D(6) * 3, while __rmul__ raises an AttributeError
with the latter)? Difference between the two methods is
slightly unclear to me.

Thanks,
Tomi Lindberg

[Antoon Pardon]

On 2006-04-05, Tomi Lindberg <to*******************@pp.inet.fi.invalid> wrote:

Antoon Pardon wrote:

def __rmul__(self, num):
tp = num * [self]
return reduce(operator.add, tp)

sum3d6 = 3 * D(6)
One basic question: is there any particular reason not to
use __mul__ instead (that would allow me to use both 3 *
D(6) and D(6) * 3, while __rmul__ raises an AttributeError
with the latter)?

Well 3 * D(6) is similar to the notation used in roleplaying,
while D(6) * 3 would make me think of the distribution
{3:1, 6:1, 9:1, 12:1, 15:1, 18:}
Difference between the two methods is
slightly unclear to me.

I have to look it up myself regularly. But in this case
it was more a matter of some intuition that 3 * D(6)
was not the same as D(6) * 3. You may have a different
intuition.

--
Antoon Pardon