# Add helper functions for games (dice, coins, card decks, etc)

Issue #30 closed
Pierre Denis
repo owner created an issue

From Pelle Nilsson: "(... ) Also maybe there is room for some default built-in functions to create dice, eg lea.die(sides) and lea.dice(nr, sides). Obviously those are trivial one-liners to implement for myself, but it would be nice to see them included to make it easier to explain for others how to use Lea for games. The R prob-package (on CRAN) includes a few shortcut functions to create dice, coin-flips and standard decks of cards. I think those things might fit nicely in Lea as well.(...)"

A useful function is the distribution of an unordered set of die rolls. The following functions produce this:

```from lea import *

from itertools import combinations_with_replacement
from math import factorial

def dice_set_freqs(n, m):
"""Sets of N M-sided dice, ignoring order, with relative frequencies.
"""
# The total number of permutations of N dice is N!
permutations = factorial(n)

# Use itertools to get the sets.
for outcome in combinations_with_replacement(range(1, m+1), n):
# For each set, the weight is N!/a!b!c!... where a, b, c... are
# the sizes of each group of equal values.
weight = permutations
# We run through the set counting an dividing as we go
run_len = 0
prev_roll = None
for roll in outcome:
if roll != prev_roll:
prev_roll = roll
run_len = 0
run_len = run_len + 1
if run_len > 1:
weight = weight // run_len
yield outcome, weight

def dice_unordered(n, m):
"""A Lea distribution representing an unordered set of N M-sided dice.

Combinations of dice which are the same apart from order are considered
equal. The particular value used is chosen to be in order from smallest
to largest.
"""
return Lea.fromValFreqs(*dice_set_freqs(n, m))
```

It would be nice to generalise this so that it could produce unordered sets from any distribution, not just `interval(1,m)`, but I need to work out the maths for that first :-)

1. reporter

Thank you for the idea. I was not aware of this `itertools.combinations_with_replacement` function. Nice!

Now, I can't resist providing another implementation, which is a one-liner using only Lea's building blocks and giving same results:

```def diceUnordered(n,m):
return Lea.interval(1,m).timesTuple(n).map(lambda v: tuple(sorted(v))).getAlea()
```

However, I must admit that your version scales much better as m and n grow. The reason is that my function has to generate m^n tuples, each of which is sorted to be able to merge the equivalent permutations; on the other hand, your function generates directly the target set of tuples (which is far less than m^n), then calculates weights by maths.

2. reporter

Add ordered argument in leaf.diceSeq, integrating the dice_unordered function of Paul Moore (refs #30)

→ <<cset 4542c0807b53>>

3. reporter

I've put your implementation in Lea 2.2.0-beta.8 (see on PyPI). `diceSeq` function has now an extra-argument `ordered`, False by default. So, `diceSeq(2,6)` shall call your function (21 tuples returned), while `diceSeq(2,6,True)` shall call the previous one (36 tuples returned).

That's nice, thanks.

I did actually generalise this to draw sorted (both with and without replacement) from any distribution. The code is as follows:

```from itertools import combinations, combinations_with_replacement
from math import factorial

def selections(dist, n, selector):
# First of all, get the values and weights for the distribution
vp = dict(dist.vps())

# The total number of permutations of N samples is N!
permutations = factorial(n)

# We will calculate the frequency table for the result
freq_table = []

# Use itertools to get the list of outcomes. We sort the input
# as itertools guarantees to give sorted output for sorted input, so
# this ensures our outputs are sorted.
for outcome in selector(sorted(vp.keys()), n):
# We calculate the weight in 2 stages.
# First we calculate the weight as if all values were equally
# likely - in that case, the weight is N!/a!b!c!... where
# a, b, c... are the sizes of each group of equal values.
weight = permutations
# We run through the set counting and dividing as we go
run_len = 0
prev_roll = None
for roll in outcome:
if roll != prev_roll:
prev_roll = roll
run_len = 0
run_len = run_len + 1
if run_len > 1:
weight = weight // run_len
# Now we take into account the relative weights of the values, by
# multiplying the weight by the product of the weights of the
# individual elements selected
for roll in outcome:
weight = weight * vp[roll]
freq_table.append((outcome, weight))

return Lea.fromValFreqs(*freq_table)

def draw_with_replacement_sorted(dist, n):
"""Draw N values from DIST, arranged in sorted order.

This can be used to simulate (for example) rolling N dice without
regard to order. The values are sorted to allow implementing things
like "pick the largest 3 from a roll of 5 dice" without needing an
extra sort step.
"""
return selections(dist, n, combinations_with_replacement)

def draw_without_replacement_sorted(dist, n):
return selections(dist, n, combinations)
```

In practice, I'm not sure how useful this would be for anything other than a uniform distribution (i.e., general N-sided dice) but I thought you might be interested.

And regarding your one-liner, yes that works. The only benefit to my functions is that they scale better for larger numbers. (But that was the reason I needed optimised versions, which is why I wrote them ;-))

4. reporter

This is a, intersting generalization indeed. Since these functions all have a distribution as argument, these will fit nicely as `Lea` methods. Now, I'm trying to see the most sensible way to integrate all this for the end-user. There are currently 4 closely-related "drawing" functions; these can be gathered by using two parameters: sorted (YES/NO) and replacement (WITH/WITHOUT). The four combinations are currently covered by the folloiwng functions:

```sorted replacement  current function
YES    WITH         draw_with_replacement_sorted
YES    WITHOUT      draw_without_replacement_sorted
NO     WITH         Lea.timesTuple
NO     WITHOUT      Lea.draw
```

I plan to streamline all this into one unique public method, `draw(self,n,sorted=False,replacement=False)`, which calls the right method depending on the last two arguments. Do you think it's sensible?

Other point: is it OK for you if I adapt your methods with camelCase (the convention used in Lea)?

Having a single method sounds OK to me. It's not my preferred approach in my own code (I tend to follow standard library conventions, which in turn follow Guido's preference, which can be described as "use separate functions rather than boolean arguments which are always constants") but consistency with the rest of Lea is what's important here, so please do merge the functions like that.

Equally, by all means adapt to use camel case. Again, it's not my personal preference, but I'm completely OK with following the library conventions.

5. reporter

Thanks, I appreciate your flexibility. When I started Lea, I was now aware of all these preferences in Python.

OK, I've integrated your work as I explained. I am writing now several test cases for the four cases... but I'm now stuck on your `draw_without_replacement_sorted`. Either the implementation is wrong or... I'm wrong myself (I'm a bit tired)! Let me explain my test: I use a biased die defined as follows:

```d = Lea.fromValFreqsDict({1: 2, 2: 1, 3: 1, 4: 1, 5: 1, 6: 1})
```

so the 1 has probability 2/7 and other values have probability 1/7. Now if I evaluate

```draw_without_replacement_sorted(d,2)
```

the probability displayed for (1,2) is 2/20. For checking this result, I consider the two cases :

• first 1, then 2 : probability 2/7 . 1/5 = 2/35
• first 2, then 1 : probability 1/7 . 2/6 = 1/21

then I add these two probabilities: 2/35 + 1/21 = 11/105. This is NOT 2/20. :(

What's wrong? Did I misunderstand something?

Hmm, I think you are right. I'll try to find some time over the weekend to determine the bug. My apologies, and thanks for spotting it!

6. reporter

No problem, take your time. BTW, you can check (what I consider as) the right answer by using this expression:

```d.draw(2).map(sorted).map(tuple)
```

As stated before, your method is expected to be much more efficient as n grows.

Yes, when I wrote the code I should have tested it like that.

Unfortunately, I'm not sure the method I used generalises to non-uniform distributions like I thought it did. Your example shows that if the probabilities of '1' and '2' differ, we need to look at 1,2 and 2,1 separately to get the final probability. If we have to do that, we have to look at the full set of (unsorted) outcomes anyway, so there's no benefit over doing draw-then-sort.

I had the same problem with another idea - some peoblems don't even need the numbers at all, they just need the pattern (3 of one, 2 of another - think of a full house in Poker). That needs even less outcomes to compute. I believe I can do this for uniform distributions, but I'm pretty sure that doesn't work for biased distributions.

So on reflection, these faster approaches may only be possible for uniform distributions. But I'll keep looking to see if I find a way to generalise.

(I have a friend who's implementing his own probability calculation program - that's how I got interested in Lea. I thrashed these ideas out with him at the time. He thought his program worked for sorted draws from non-uniform distributions, but he's going to check. If his code does work, I'll steal it from him :-) I suspect he has the bug too, though...)

7. reporter

OK. It's a pity but it's not so bad anyway because most of games show uniform probability distributions.

Now, let's be pragmatic... Following your assumptions and waiting something better, I propose the following implementation for the new extended `Lea.draw(self,n,sorted,replacement)` method (see above) : if `sorted` is `True` and `replacement` is `False`, then it checks whether `self` is a uniform probability distribution; if YES, then it shall use your efficient implementation, if NO, then it shall use the draw-then-sort one. The best of both worlds!

Nice! In effect, just a hidden optimisation. I like that idea.

8. reporter

Extend the Lea.draw method with 'sorted' and 'replacement' arguments; add the efficient combinatorial methods of P. Moore; change the diceSeq function to have a 'sorted' argument; add tests (refs #30)

→ <<cset 2f1bbf59741f>>