Dice probability problem

Discussion in 'Python' started by Tomi Lindberg, Apr 4, 2006.

  1. 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
    Tomi Lindberg, Apr 4, 2006
    #1
    1. Advertising

  2. Tomi Lindberg <> 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, Apr 4, 2006
    #2
    1. Advertising

  3. Op 2006-04-04, Tomi Lindberg schreef <>:
    > 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
    Antoon Pardon, Apr 4, 2006
    #3
  4. Alexander Schmolck <> 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
    Alexander Schmolck, Apr 4, 2006
    #4
  5. 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
    Tomi Lindberg, Apr 4, 2006
    #5
  6. 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
    Gerard Flanagan, Apr 4, 2006
    #6
  7. 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]
    Dave Mandelin, Apr 4, 2006
    #7
  8. Op 2006-04-04, Tomi Lindberg schreef <>:
    > 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
    Antoon Pardon, Apr 5, 2006
    #8
  9. 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
    Tomi Lindberg, Apr 5, 2006
    #9
  10. Tomi Lindberg <> 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
    Alexander Schmolck, Apr 5, 2006
    #10
  11. 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
    Tomi Lindberg, Apr 5, 2006
    #11
  12. On 2006-04-05, Tomi Lindberg <> 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
    Antoon Pardon, Apr 6, 2006
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Richard Buckle
    Replies:
    4
    Views:
    435
    Steven Bethard
    Sep 13, 2006
  2. Replies:
    13
    Views:
    1,588
    Roedy Green
    Oct 14, 2007
  3. Replies:
    1
    Views:
    708
    Patricia Shanahan
    Oct 16, 2007
  4. Bill Cunningham

    dice generator problems

    Bill Cunningham, Dec 9, 2009, in forum: C Programming
    Replies:
    43
    Views:
    1,401
    Richard Bos
    Dec 12, 2009
  5. Ruby Quiz

    [QUIZ] Dice Roller (#61)

    Ruby Quiz, Jan 6, 2006, in forum: Ruby
    Replies:
    106
    Views:
    888
    Morus Walter
    Jan 10, 2006
Loading...

Share This Page