Selecting a valid hand configuration for Monte-Carlo simulation

[cbloom]

Juk, matt is right, doing the "hands collide so resample" thing works perfectly fine.

Here are some other approaches I use :

1.
Construct a "virtual deck"
Initialize the virtual deck with all 52 cards
Draw hand for player N ; remove those hands from the virtual deck
Draw further hands

2.
effective weight table zeroing

When you assign someone a hand, that "virtually" zeros those elements of everyone else's weight table

That is you dont actually zero them, but when other people access their weight table they ignore elements that conflict with other holes.

BTW the fast way to do all this stuff is with 52-bit masks.

[jukofyork]

[ QUOTE ]
[ QUOTE ]
Imagine if player #1 only plays AA and player #2 only plays AK and KQ. If you don't permute the order then the fact that player #1 has taken away two of the aces every time before player #2 gets his selection would mean that he would end up with KQ far more often than he should (as there will always only be 2 aces left to choose from). On the other hand, if you permute the player order then 50% of the time player #2 gets to choose when there are 4 aces still available and 50% of the time he has just 2 aces left to choose from.

[/ QUOTE ]

There is no bias introduced with a partial resample on collision.
When you say 'has 2 aces left to choose from' - what you really mean is '50% of the time the algorithm will encounter collisions if P2 chooses an Ace which was already used (50% x 50%)'

P2 by definition within your constraints must be dealt KQ far more often than AK.
Consider this - when P2 is first, 50% of the time P1 only has 3 aces to choose from. He still gets AA every time but the algorithm will encounter collisions with 1 of the aces when it has been used. The only variable is which player's cards collide and how many collisions occur.

[/ QUOTE ]
If P2 acts after P1 there will be: Ax, Ay, Kh, Ks, Kc, Kd, Qh, Qs, Qc, and Qd left for him to get dealt without causing a collision and if you keep re-sampling each time one of player 1's aces are chosen you end up with 8xAK and 16xKQ hands for P2 to get dealt, therefore P(P2|AK)=1/3 and P(P2|KQ)=2/3.

If P2 acts first he will have all 4 aces, kings and queens free, so he will end up with P(P2|AK)=1/2 and P(P2|KQ)=1/2 and since P1 only plays AA he will just re-sample until he gets AA whatever P1 chooses before him.

If you were to sample from all possible configurations by doing a full "discard and re-sample" each time then P(P2|AK)=(1/3+1/2)/2=5/12 and P(P2|KQ)=(2/3+1/2)/2=7/12.

Juk [img]/images/graemlins/smile.gif[/img]

[jukofyork]

[ QUOTE ]
Juk, matt is right, doing the "hands collide so resample" thing works perfectly fine.

Here are some other approaches I use :

1.
Construct a "virtual deck"
Initialize the virtual deck with all 52 cards
Draw hand for player N ; remove those hands from the virtual deck
Draw further hands

2.
effective weight table zeroing

When you assign someone a hand, that "virtually" zeros those elements of everyone else's weight table

That is you dont actually zero them, but when other people access their weight table they ignore elements that conflict with other holes.

BTW the fast way to do all this stuff is with 52-bit masks.

[/ QUOTE ]
I agree this appears to work so long as you permute the player orderings, but if you don't permute the orderings and just assign the cards from player 1 to N, or use a method like matt suggests (ie: choose an ordering to minimize collisions), then it appears to be biased? Either that or their is some flaw in the example I thought up to prove to myself that the orderings must be permuted (see here).

The actual code I wanted this for selects hands from histograms generated at showdown, so it's not possible to spend ages making a sparse lookup table, so I basically use almost the same code as I posted: Permute player orderings, then selected a bin based on the bin's weight and then use a fixed lookup table which takes account of the multiplicity of each hole-card within the bin. If I get a collision, then I keep re-selecting a new bin for the current player and do that until each player has a hand. This seems to work fine, but obviously I can't interpolate the bin centers as this would require a dynamic lookup (I just use a few more bins than needed to make up for it).

Juk [img]/images/graemlins/smile.gif[/img]

[matt42s]

[img]/images/graemlins/blush.gif[/img] Of course, what I meant to say was - the cumulative effect of thousands of samples combined with the convergence portion of the algorithm completely hide the bias introduced by partial resampling when all but the tightest of weight tables are used.
It felt dirty when I wrote it 2 years ago but I could never fault the output. Something about it still doesn't feel right - maybe it's just my gut telling me "surely there must be a better way" [img]/images/graemlins/smirk.gif[/img]

[matt42s]

[ QUOTE ]
If P2 acts after P1 there will be: Ax, Ay, Kh, Ks, Kc, Kd, Qh, Qs, Qc, and Qd left for him to get dealt without causing a collision and if you keep re-sampling each time one of player 1's aces are chosen you end up with 8xAK and 16xKQ hands for P2 to get dealt, therefore P(P2|AK)=1/3 and P(P2|KQ)=2/3.

If P2 acts first he will have all 4 aces, kings and queens free, so he will end up with P(P2|AK)=1/2 and P(P2|KQ)=1/2 and since P1 only plays AA he will just re-sample until he gets AA whatever P1 chooses before him.

If you were to sample from all possible configurations by doing a full "discard and re-sample" each time then P(P2|AK)=(1/3+1/2)/2=5/12 and P(P2|KQ)=(2/3+1/2)/2=7/12.

Juk [img]/images/graemlins/smile.gif[/img]

[/ QUOTE ]
All these approaches seem broken. If you have AA and villain has AK or KQ, doesn't a plain bayesian analysis 'prove' villain has P(P2|AK)=8/24=1/3
The logic from your example results in 5/12.
I'm thinking we cannot simply "ignore" the frequency of collisions.
(walks away muttering something about independent events while looking for a statistician) [img]/images/graemlins/confused.gif[/img]

[jukofyork]

[ QUOTE ]
[ QUOTE ]
If P2 acts after P1 there will be: Ax, Ay, Kh, Ks, Kc, Kd, Qh, Qs, Qc, and Qd left for him to get dealt without causing a collision and if you keep re-sampling each time one of player 1's aces are chosen you end up with 8xAK and 16xKQ hands for P2 to get dealt, therefore P(P2|AK)=1/3 and P(P2|KQ)=2/3.

If P2 acts first he will have all 4 aces, kings and queens free, so he will end up with P(P2|AK)=1/2 and P(P2|KQ)=1/2 and since P1 only plays AA he will just re-sample until he gets AA whatever P1 chooses before him.

If you were to sample from all possible configurations by doing a full "discard and re-sample" each time then P(P2|AK)=(1/3+1/2)/2=5/12 and P(P2|KQ)=(2/3+1/2)/2=7/12.

Juk [img]/images/graemlins/smile.gif[/img]

[/ QUOTE ]
All these approaches seem broken. If you have AA and villain has AK or KQ, doesn't a plain bayesian analysis 'prove' villain has P(P2|AK)=8/24=1/3
The logic from your example results in 5/12.
I'm thinking we cannot simply "ignore" the frequency of collisions.
(walks away muttering something about independent events while looking for a statistician) [img]/images/graemlins/confused.gif[/img]

[/ QUOTE ]
Hehe, this has got me thinking too. I agree that if you are dealt AA then the probability the opponent has AK=8/(50*49)=8/1225 and the probability that he has KQ=16/(50*49)=16/1225, so if your opponent only chooses to play AK and KQ P(AK)=1/3 and P(KQ)=2/3, but the problem arises now from his perspective: If he has AK then the probability you have AA=3/1225 and if he has KQ the probability you have AA=6/1225.

Now if you were observing this and couldn't see any of the player's cards, but knew that P1 only plays AA and P2 only plays AK and KQ and you saw them both decide to play, then I'm thinking that either of the two cases above must have happened with equal chances of either happening.

I'm hoping my post in the Probability forums gets and answer one way or another, but I agree in practice the differences caused by this bias (if it exists) are tiny and I have myself used the deal P1 some cards, then deal P2 some cards, etc before without really thinking/caring about this too much but it's only recently when I went hunting for an efficient algorithm to do the selections that I though harder about the possible bias this was introducing and came up with the idea of permuting the player orderings to cancel it out.

Juk [img]/images/graemlins/smile.gif[/img]

[matt42s]

I don't really know why but I just had a very distinct impression that we'll be hearing about Monty Hall in the next day or so.
Of course, my 3rd beer may have just kicked in.

[matt42s]

[ QUOTE ]
but the problem arises now from his perspective: If he has AK then the probability you have AA=3/1225 and if he has KQ the probability you have AA=6/1225

[/ QUOTE ]

um, not so much, the probability you have AA=1.
The frequency that this encounter will occur is double when he has KQ

[jukofyork]

[ QUOTE ]
[ QUOTE ]
but the problem arises now from his perspective: If he has AK then the probability you have AA=3/1225 and if he has KQ the probability you have AA=6/1225

[/ QUOTE ]

um, not so much, the probability you have AA=1.
The frequency that this encounter will occur is double when he has KQ

[/ QUOTE ]
The probability of you having AA is only 1 if you are the "AA only" player and choose to play, but before the "AA only" player acts it's still 6/1225 if you are holing AK and 3/1225 if you are holding KQ.

Juk [img]/images/graemlins/smile.gif[/img]

[jukofyork]

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
but the problem arises now from his perspective: If he has AK then the probability you have AA=3/1225 and if he has KQ the probability you have AA=6/1225

[/ QUOTE ]

um, not so much, the probability you have AA=1.
The frequency that this encounter will occur is double when he has KQ

[/ QUOTE ]
The probability of you having AA is only 1 if you are the "AA only" player and choose to play, but before the "AA only" player acts it's still 6/1225 if you are holing AK and 3/1225 if you are holding KQ.

Juk [img]/images/graemlins/smile.gif[/img]

[/ QUOTE ]
Hehe, my poor brain! I think the only way I'm going to answer this is by hoping somebody in the Probability forum has pity on me and puts me out of my misery, or if nobody answers falling back on good old simulation (but I'd much rather have it explained than just simulate and get a yes/no answer...).

Juk [img]/images/graemlins/smile.gif[/img]