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

Comments (18)

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

  2. Pierre Denis 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.

  3. Pierre Denis 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).

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

  5. Pierre Denis 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)?

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

  7. Pierre Denis 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?

  8. Pierre Denis 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.

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

  10. Pierre Denis 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!

  11. Pierre Denis 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>>

  12. Log in to comment