Selecting a valid hand configuration for Monte-Carlo simulation

[stinkypete]

[ QUOTE ]

(1) Surely there must be a better way to do this than simply assign each player a hand independently from their distribution, then check if any of them have been assigned the same cards and keep restarting until a valid configuration is reached?

[/ QUOTE ]

here's an idea that may be feasible depending on the application.

use method 1 as above, but if you're finding a large number of "collisions", forget monte carlo and enumerate all the possible combinations and apply weights accordingly.

this should work since in practice, if you're getting a lot of collisions, you're probably selecting from a small number of hand combinations anyway and enumerating them all shouldn't be too much work.

in some extreme cases, this wouldn't be particularly feasible - but it would probably work well in practice. (examples when it wouldn't work: if there's 10 players with all having wide ranges, or if there's 3 players who all have AK 99% of the time and any of the 168 other hands 1% of the time)

[jukofyork]

[ QUOTE ]
[ QUOTE ]

(1) Surely there must be a better way to do this than simply assign each player a hand independently from their distribution, then check if any of them have been assigned the same cards and keep restarting until a valid configuration is reached?

[/ QUOTE ]

here's an idea that may be feasible depending on the application.

use method 1 as above, but if you're finding a large number of "collisions", forget monte carlo and enumerate all the possible combinations and apply weights accordingly.

this should work since in practice, if you're getting a lot of collisions, you're probably selecting from a small number of hand combinations anyway and enumerating them all shouldn't be too much work.

in some extreme cases, this wouldn't be particularly feasible - but it would probably work well in practice. (examples when it wouldn't work: if there's 10 players with all having wide ranges, or if there's 3 players who all have AK 99% of the time and any of the 168 other hands 1% of the time)

[/ QUOTE ]
Hi, sorry for the slow reply - been away for a few days, then had problems logging onto 2+2 until I cleared my IE cache and cookies.

Yep, I agree that enumerating is prolly a good idea for the cases where the ranges are very constrained and possibly even adding something too do it after so many failures (I think detecting an impossible configuration before you run though is going to be O(n!), as you will has to test all possible player orderings to be sure).

I haven't had time to do much more with the code since my last post, but overall it seems to be working quite well and sometime over the next few days I'll write a simple CLI app to let you input a hand vs a distribution of opponent hands and maybe somebody will find it useful and/or extend it to do something more useful.

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

[matt42s]

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

Further to that, my code determines the 'tightness'/size of a players weight table and allocates the tightest players cards first, I use a selective resample on collision. Due to the ordering, collisions are minimised.

I have also had success using a pre-generated table of random numbers, at first it was only to remove the RNG code/overhead from the inner loop, but reusing a sufficiently long table has caused significant speed improvement and no notable bias (the requirements for random poker are FAR less than the double precision, infinite length stream provided by the algorithm you are using) Even if you're not convinced yet, write your code to use a random table lookup and populate it before entering the MonteCarlo routines - in the real world, populate it while the bot dealing is shuffling [img]/images/graemlins/smile.gif[/img]

[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 ]
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]

[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]

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