Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How can a computer deal a poker hand?

fermatslibrary.com

Post reply on HN
Print view View original

11–20 of 32 posts

Re: How can a computer deal a poker hand?

#11

Post by Chinjut »

wyldfire wrote: post #8

> It is easy to generate a random sequence of inte- gers in the range l..N, so long as we don’t mind dupli-cates Is it? I was surprised to learn of modulo bias [1]. Does the "Randint(1, J)" implementation take it into account? It's a very easy mistake to make and can have an impact on the uniformity of the shuffle. If you haven't heard of it it has to do with the relationship between the range spanned by your system'…

Any random number generator library worth its salt should have a properly implemented RandInt(1, J) function available, instead of just a RandInt(1, RAND_MAX) primitive.

Behind the scenes, mind you, it's easy to implement such things from random number generators of a fixed range. For example, it could be done as follows (for convenience, I'll speak as though our fundamental randomness primitive just produces random bits, though all sorts of things would work just as well):

We ought keep track, internally to our random number generator library, persistently of some interval [Low, High) in [0, 1) (which can be initialized to all of [0, 1) itself); any time a RandInt(1, J) is required, we partition [0, 1) into J many equal intervals, find which one [Low, High) lies entirely within, use the corresponding number as the value to return, and also modify [Low, High) by applying to it the affine transformation which would take that particular subinterval to all of [0, 1). If ever, while doing this, we find [Low, High) spans multiple subintervals, we first do the following until it does not: generate a random bit and then replace [Low, High) with either its lower or higher half accordingly.

Essentially, we are using [Low, High) to keep track of an underspecified value uniformly distributed throughout [0, 1), and then pulling out leading "digits" in arbitrary bases of this value as required by the user, zooming our window in accordingly after doing so. Random bits are used to further and further specify this value, and thus no randomness ever goes to waste. At all times, we will have made the minimum number of invocations of random bits necessary to power the amount of random integers of whatever varying sizes asked for so far.

Re: How can a computer deal a poker hand?

#12

Post by psyc »

waqf wrote: post #2

> After solving a challenging problem, I solve it again from scratch, retracing only the insight of the earlier solution. I repeat this until the solution is as clear and direct as I can hope for. Then I look for a general rule for attacking similar problems, that would have led me to approach the given problem in the most efficient way the first time. Often, such a rule is of permanent value. This has been one of my…

I solve every programming problem this way. The first few iterations have lumps that seem necessary, but still lumpy. The final iteration is nothing but a small set of aesthetically pleasing rules that seem self-evident in hindsight.

Re: How can a computer deal a poker hand?

#14

Post by bhickey »

Chinjut wrote: post #11
wyldfire wrote: post #8

> It is easy to generate a random sequence of inte- gers in the range l..N, so long as we don’t mind dupli-cates Is it? I was surprised to learn of modulo bias [1]. Does the "Randint(1, J)" implementation take it into account? It's a very easy mistake to make and can have an impact on the uniformity of the shuffle. If you haven't heard of it it has to do with the relationship between the range spanned by your system'…

Any random number generator library worth its salt should have a properly implemented RandInt(1, J) function available, instead of just a RandInt(1, RAND_MAX) primitive. Behind the scenes, mind you, it's easy to implement such things from random number generators of a fixed range. For example, it could be done as follows (for convenience, I'll speak as though our fundamental randomness primitive just produces random…

> pulling out leading "digits" in arbitrary bases of this value

Generally this bookkeeping isn't worth the complexity. Modern PRNGs are super efficient: PCG is about 3x faster than Mersenne Twister.

Re: How can a computer deal a poker hand?

#15

Post by emmelaich »

Great article from a classic series that every programmer should read.

Here's an odd thing -- when I copy'n'pasted the awk implementation the pasted copy had errors reminiscent of OCR. For example the (j became Cj, the ARGV[2] become ARGV121.

What's going on here? Is the website detecting the copy and make the browser get something else? Is it Chrome - or something else doing some guessing?

Re: How can a computer deal a poker hand?

#16

Post by cyberferret »

This looks very familiar. I think I read part of it back in the 80's when I was first learning programming. I think it was in reference to "How to truly 'shuffle' a deck of cards using a computer algorithm. Lots of discussion on techniques to do close to true random shuffling of ordered decks.

Re: How can a computer deal a poker hand?

#18

Post by vilhelm_s »

emmelaich wrote: post #15

Great article from a classic series that every programmer should read. Here's an odd thing -- when I copy'n'pasted the awk implementation the pasted copy had errors reminiscent of OCR. For example the (j became Cj, the ARGV[2] become ARGV121. What's going on here? Is the website detecting the copy and make the browser get something else? Is it Chrome - or something else doing some guessing?

I think the document is scanned from a paper copy. The pixels shown on the screen is from the scanned image, but the text for copy-and-paste was created by OCR when the document was scanned and prepared. You often see this with pdf files, I guess the software used to create them has OCR functionality built in.

If you use "inspect element" in your web browser you can see how it is displayed. Each page is a which contains first a big image (with the scanned document page), and then a for each word, which are positioned using absolute positioning to be placed over the corresponding word in the image. The s each have "color: transparent", so you can't see them but you can still select them.

Re: How can a computer deal a poker hand?

#19

Post by jbritton »

Is this a mathematically sound shuffle? It removes a random element from a sorted deck and then adds the element to a new deck. Python code below:

import random

def shuffle():

    random.seed()   
    sorted_deck = range(52)  # [0..51]
    shuffled_deck = []
    slots_avail = 52
    while slots_avail:

        idx = random.randint(0, slots_avail - 1)
        shuffled_deck.append(sorted_deck[idx])
        del sorted_deck[idx]
        slots_avail -= 1

    return shuffled_deck

Re: How can a computer deal a poker hand?

#20

Post by conistonwater »

jbritton wrote: post #19

Is this a mathematically sound shuffle? It removes a random element from a sorted deck and then adds the element to a new deck. Python code below: import random def shuffle(): random.seed() sorted_deck = range(52) # [0..51] shuffled_deck = [] slots_avail = 52 while slots_avail: idx = random.randint(0, slots_avail - 1) shuffled_deck.append(sorted_deck[idx]) del sorted_deck[idx] slots_avail -= 1 return shuffled_deck

Try your algorithm with a smaller n first, instead of n=52, such as n=2 or n=3, and slots_avail=n.

For n=3 it generates the permutation {1,2,3} with probability that is 11% higher than the correct probability.

Post reply on HN