Add helper functions for games (dice, coins, card decks, etc)
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 (21)
-
reporter -
reporter - changed status to open
-
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 :-) -
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.
-
reporter Add ordered argument in leaf.diceSeq, integrating the dice_unordered function of Paul Moore (refs
#30)→ <<cset 4542c0807b53>>
-
reporter I've put your implementation in Lea 2.2.0-beta.8 (see on PyPI).
diceSeq
function has now an extra-argumentordered
, False by default. So,diceSeq(2,6)
shall call your function (21 tuples returned), whilediceSeq(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 ;-))
-
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.
-
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!
-
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...)
-
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) : ifsorted
isTrue
andreplacement
isFalse
, then it checks whetherself
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.
-
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>>
-
reporter - changed status to resolved
-
reporter - changed status to closed
-
reporter Add leaf.py module with helper functions for games (refs
#30)→ <<cset 898b7a974ec6>>
-
reporter Add ordered argument in leaf.diceSeq, integrating the dice_unordered function of Paul Moore (refs
#30)→ <<cset 142a22405b0c>>
-
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 cb7c53e4ef25>>
- Log in to comment
Add leaf.py module with helper functions for games (refs
#30)→ <<cset cf62c7eb4995>>