Selecting a valid hand configuration for Monte-Carlo simulation

[matt42s]

I think we need to do a full re-sample AND permute the player orders on every collision, the frequencies will then work themselves out.

ie. our target frequency is P(P2|AK)=1/3
P1 is dealt first and receives 1 of 6 AA combinations.
P2 chooses 1 of 16 AK or 16 KQ combinations. 8 of the AK combinations 'collide' with P1's cards and the deal is invalidated. 8 of the AK's are OK and all 16 KQ's are OK.

When P2 is dealt first, he receives 1 of 16 AK or 16 KQ's
P2 chooses 1 of 6 AA combinations. 50% of the time P2 has KQ and any AA is valid. 50% of the time P2 has AK and a collision will occur 50% of those times. 25% of deals are invalid. The makeup of the remaining 75% is 2/3 KQ and 1/3 AK. Re-sampling P1's cards at this point, leaving P2 with AK in his hand is where the bias is introduced. When a collision occurs we have to take AK out of his hand and shuffle the play order.

[jukofyork]

[ QUOTE ]
It's not just a ghost, there is a very real problem with the Monte Carlo card selection algorithm and even the "slowest" Full re-sampling on collision does not fix it.
The practical implication is that for tight ranges, more iterations are required to converge to a result. The bigger problem is that the monte carlo sim will converge to the WRONG result.

<BOLD STATEMENT>
Pokerstove contains this flaw.
</BOLD STATEMENT>

Pump in AA vs AKs,KQs,AKo,KQo -
Enumerate all results and you get AA=87.997%
Run MonteCarlo and it converges to AA=88.479% (even after letting it run for a really really really long time)
The monte carlo code converges to a higher number because AK is being assigned more often than it should and AA=91.8% against AK and only 86.1% against KQ

OK so its less than half of one percent, barely significant, but certainly not a ghost. Who can say what effect it has when there are 5 reasonable players in a capped preflop matchup? And how many unnecessary iterations were performed to "converge"?

EDIT: I'll post the results of this Pstove matchup when it finishes, (prob sometime in early 2013)
Hand 0:{ TT+, AJs+, KQs, KQo }
Hand 1:{ JJ+, AQs+, KQs, AQo+ }
Hand 2:{ QQ+, AQs+, KQs, AKo }
Hand 3:{ KK+, AKs, AKo }
Hand 4:{ AA, AKs, AKo }

[/ QUOTE ]
Very interesting. Have you any idea what is causing this flaw? As far as I knew the way pokerstove works is to do a full discard and re-sample.

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

[jukofyork]

[ QUOTE ]
When P2 is dealt first, he receives 1 of 16 AK or 16 KQ's
P2 chooses 1 of 6 AA combinations. 50% of the time P2 has KQ and any AA is valid. 50% of the time P2 has AK and a collision will occur 50% of those times. 25% of deals are invalid. The makeup of the remaining 75% is 2/3 KQ and 1/3 AK. Re-sampling P1's cards at this point, leaving P2 with AK in his hand is where the bias is introduced. When a collision occurs we have to take AK out of his hand and shuffle the play order.

[/ QUOTE ]
I can see why this explains that you have to do a full re-sample each time, but whats the reason you need to permute the player order aswell? It looks like it is because when P1 is first we get a collision 1/3 of the time and when P2 is first we only get one 1/4 of the time? (Bear in mind I've just woken up and might just be stating the obvious or be reading this wrong...). If this is so then this must explain the discrepancy in the pokerstove results you found.

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

[jukofyork]

[ QUOTE ]
Hand 0: 20.729% { TT+, AJs+, KQs, KQo }
Hand 1: 17.923% { JJ+, AQs+, KQs, AQo+ }
Hand 2: 19.387% { QQ+, AQs+, KQs, AKo }
Hand 3: 20.707% { KK+, AKs, AKo }
Hand 4: 21.255% { AA, AKs, AKo }

[/ QUOTE ]
If you put these in a different order to they converge to different values?

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

[matt42s]

No, we get collisions 1/4 of the time either way.
I was thinking that a collision is a 'completed' sample of our distribution. We determine the probability of that search branch to be zero. We assign zero wins to P1 and zero wins to P2, then we move on to the next sample - which I thought would only be valid if it includes randomly selecting the 'first' player.
Now though, I'm not so sure.
I pointed Andrew to this thread earlier today, hopefully he'll chime in and tell us what method stove uses.

[matt42s]

[ QUOTE ]
[ QUOTE ]
Hand 0: 20.729% { TT+, AJs+, KQs, KQo }
Hand 1: 17.923% { JJ+, AQs+, KQs, AQo+ }
Hand 2: 19.387% { QQ+, AQs+, KQs, AKo }
Hand 3: 20.707% { KK+, AKs, AKo }
Hand 4: 21.255% { AA, AKs, AKo }

[/ QUOTE ]
If you put these in a different order to they converge to different values?

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

[/ QUOTE ]

looks like the same values after a short run (40M)

[matt42s]

I've flipped back again to thinking order doesn't matter at all - as long as you do a full resample.
I think this is/was the key.
[ QUOTE ]
Re-sampling P1's cards at this point, leaving P2 with AK in his hand is where the bias is introduced.

[/ QUOTE ]
must go bed before brain pop.

[jukofyork]

[ QUOTE ]
I've flipped back again to thinking order doesn't matter at all - as long as you do a full resample.
I think this is/was the key.
[ QUOTE ]
Re-sampling P1's cards at this point, leaving P2 with AK in his hand is where the bias is introduced.

[/ QUOTE ]
must go bed before brain pop.

[/ QUOTE ]
LOL, I know the feeling well! It's this, no it's that, no it's this, no it's that, ... pop [img]/images/graemlins/grin.gif[/img]

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

[Andrew Prock]

Yes, that's right. It's actually a bit more complicted than that, but that's the basic version. On collisions, I resample from only one hand, not the entire distribution. I'll see if I can get a fix up soon.

- Andrew

[Andrew Prock]

Ok, the (re) fix is in. It may not have been clear but previous versions of PokerStove were doing full resampling on collisions. But a specific scenario convinced me to try something else. Specifically, ten players holding broadway cards. Because there are 20 broadway cards, all cards are used in the scenario and satisfying the scenario with full resampling was nearly infeasible. So I started resampling on a hand by hand basis.

Clearly hand by hand resampling causes the MC results to skew away from the true results. But I still want difficult to realize scenarios to be workable.

I've just now implemented a hybrid MC evaluator. The basic behaviour is to do full resampling of all hands, but if collisions start to dominate the number of samples more and more collisions are resolved by resampling of the hand which collides. It's important to note here that full resampling is not turned off unless a very high proportion of generated scenarios result in collisions. Even then hand by hand resampling is only gradually allowed. The details are rather mechanical and boring, but if anyone is interested, let me know.

So in general, for basic scenarios the MC results should converge to the Enumerate All value (unless you are unlucky), but for scenarios which are very difficult to satisfy using resampling, there will be some divergence.

I'll see if I can get the installer up later today.

- Andrew