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

21–30 of 32 posts

Re: How can a computer deal a poker hand?

#21

Post by stephengillie »

pavel_lishin wrote: post #3
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…

Isn't that a bit like "Plan to throw the first one away"? https://en.wikiquote.org/wiki/Fred_Brooks

Buy the cheapest one the first time. Then keep a list of all your regrets and wishes, and refer to this when buying the next one.

Re: How can a computer deal a poker hand?

#22

Post by Chinjut »

bhickey wrote: post #14
Chinjut wrote: post #11

Earlier quoted context omitted.

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.

Well, supposing one wanted "true" randomness and had access to a source of such, but still cared to be efficient about using it.

Re: How can a computer deal a poker hand?

#23

Post by marak830 »

psyc wrote: post #12
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.

I'm the same. Not not wrong about hindsight, why does it look so painfully obvious after I have gone through 3-4 iterations haha.

Re: How can a computer deal a poker hand?

#24

Post by 6nf »

conistonwater wrote: post #20
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.

Would you mind sharing your proof of this? I don't think you are correct. It seems to me that OP's algorithm is correct and will yield all permutations with equal probability.

All he's doing is picking a random card from the sorted deck and moving it to the top of the un-sorted deck. The sorted deck then becomes one card smaller.

For N = 2, In position 1 you choose card 1 with 50% and card 2 with 50% probability, and card 2 is just the remaining card. Thus

    p(12) = 50%
    p(21) = 50%
For N = 3, In position 1 you choose card 1 with p=1/3, card 2 with p=1/3, and card 3 with p=1/3:

    p(1xx) = 33% = 1/3
    p(2xx) = 33%
    p(3xx) = 33%
Then using the remaining 2 cards you just do the N=2 case from before, and so you have:

    p(123) = 50% x 33% = 1/6
    p(132) = 50% x 33%
    etc

Re: How can a computer deal a poker hand?

#25

Post by jbritton »

conistonwater wrote: post #20
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.

So I collected data for 100,000 runs

delta = (abs(count - mean) / mean) * 100.0

sd is standard deviation

>>> shuffle.test(100000, 2)

(0, 1) count: 50127, delta: 0.3%

(1, 0) count: 49873, delta: 0.3%

mean: 50000.0, sd: 179.6, sd/mean 0.4%

>>> shuffle.test(100000, 3)

(0, 1, 2) count: 16873, delta: 1.2%

(0, 2, 1) count: 16506, delta: 1.0%

(1, 0, 2) count: 16667, delta: 0.0%

(1, 2, 0) count: 16761, delta: 0.6%

(2, 0, 1) count: 16498, delta: 1.0%

(2, 1, 0) count: 16695, delta: 0.2%

mean: 16666.7, sd: 146.0, sd/mean 0.9%

Re: How can a computer deal a poker hand?

#26

Post by mattb314 »

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

It looks correct to me, but keep in mind that deleting elements from the middle of an array is O(n), so overall your algorithm is O(n^2). You could fix this by always swapping your chosen element with the last element of the sorted_deck before removing it because removing from the end of an array is O(1).

Re: How can a computer deal a poker hand?

#27

Post by conistonwater »

6nf wrote: post #24
conistonwater wrote: post #20

Earlier quoted context omitted.

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.

Would you mind sharing your proof of this? I don't think you are correct. It seems to me that OP's algorithm is correct and will yield all permutations with equal probability. All he's doing is picking a random card from the sorted deck and moving it to the top of the un-sorted deck. The sorted deck then becomes one card smaller. For N = 2, In position 1 you choose card 1 with 50% and card 2 with 50% probability, and…

You're right, I think I misread the algorithm.

Re: How can a computer deal a poker hand?

#29

Post by jcranmer »

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

What you've described is essentially the Fisher-Yates shuffle implemented slowly (O(n²) implementation). The O(n) implementation would be:

  deck = range(52)
  for i in range(len(deck) - 1, 0, -1):
      j = random.randint(0, i)
      deck[i], deck[j] = deck[j], deck[i]
Intuitively, what the latter implementation is doing is keeping the sorted_deck and shuffled_deck variables in the same array, moving the partition each iteration. The big problem with this method is that it is very easy to make a mistake in its implementation, and any slight mistake will lead to horribly biased outputs.

Re: How can a computer deal a poker hand?

#30

Post by tuco86 »

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

random.sample(range(52), 52)
Post reply on HN