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

[Pierre Denis]

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.(...)"

[Pierre Denis]

Add leaf.py module with helper functions for games (refs #30)

→ <<cset cf62c7eb4995>>

[Paul Moore]

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 :-)

[Pierre Denis]

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.

[Pierre Denis]

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

→ <<cset 4542c0807b53>>

[Pierre Denis]

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).

[Paul Moore]

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 ;-))

[Pierre Denis]

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)?

[Paul Moore]

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.

[Pierre Denis]

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?

[Paul Moore]

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!

[Pierre Denis]

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.

[Paul Moore]

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...)

[Pierre Denis]

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!

[Paul Moore]

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

[Pierre Denis]

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>>

[Pierre Denis]

Add leaf.py module with helper functions for games (refs #30)

→ <<cset 898b7a974ec6>>

[Pierre Denis]

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

→ <<cset 142a22405b0c>>

[Pierre Denis]

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 cb7c53e4ef25>>