Hi,

Let's say we have two players, P1 and P2
We know their ranges, range(P1) = [As2s,KdKh], range(P2) = [2s2h,2c2h]

We want to deal random hands in a way that will land each player with a hand in his range and we also want the dealt hands to have the correct distribution.

The correct algorithm is: but it is very very slow. Obviously this is a simple example but I have in mind more complex ranges and more than 2 players.

In this example P1 will get As2s 33% of times and KdKh 67% of times, P2 will get 2s2h 58% and 2c2h 42%.

Faster would be to deal two cards for P1 until they are in his range, then deal 2 cards for P2 until they are in his range but that doesn't produce the correct distribution (obviously P1 gets each hand in his range 50% of times).

I want to do this programatically but I thought that maybe there is some theoretical idea that I could use. Any suggestions highly appreciated.

Thanks,
L.

Spitballing: maybe figuratively mark each card in the deck according to which players ranges it's part of? For instance a 52xN array of booleans where N is the #players.

Then for each player you deal 2 of their designated cards until they have a hand in their range. For P1 in this example you'd still need a do-over 2/3 of the time, but that's an improvement on what was previously 99.85%.

It might be possible to take it further. Maybe you come up with a mapping from 1-1326 to each two-card combo and mark each of those for each player. Here, P1 has two combos, maybe #'s 542 and 1320. You deal P1 a random one of those #'s. Say it's the As2s. Now you need a good way to remove all the combos with each of those cards from the "combo deck", which is a total of 101 combos. Then you deal to P2 from the remaining combo deck.

Regardless of algorithm, you might want to randomize the order in which players are dealt. Unlike when dealing normally, the order of deals matters. Normally, if P1 gets KK, that increases the chance of P2 getting 22. That compensates for the times P1 gets dealt a deuce and reduces P2's chances. But when dealing from forced ranges, P1 getting KK doesn't influence the chance of P2 getting 22. Only when P1 gets As2s does that alter P2's range. Overall, if P1 is dealt before P2, P2's chance of 2s2h is 1/4, whereas if P2 is dealt first it's 1/2. If you randomize the order it's 3/8.

Another thing to watch out for is an edge case where some players are dealt exactly the hands that make it impossible for the last player to be dealt a hand in their range. I guess then you just redeal to everyone. It shouldn't happen often.

It's been a while since I had to deal with this, but as I recall, I basically assigned a percentage change to each hand in each person's range. Randomly assign person 1 a hand in his range by weight, then do the same for person 2. If person 2's pick is impossible due to card removal, then start over for the whole deal - you can not just re-deal person 2.

So you still have to start over a lot, but not as often as in your original explanation. I know I'm not explaining this super well.

Another way to do it is to consider all the pairs (or triples or whatever) of possible hand matchups, and calculate the chance of each one, and then put each pair into a hat and draw one at random.

Like say there are 10 cards numbers 1 through 10, no suits. p1 range is [1,2] and p2 range is [1,2,3]. Each player gets one card. So there are 90 ways to deal hands to 2 players, but only 4 combos are valid
[(1, 2), (1, 3), (2, 1), (2, 3)]
if each card in the range is the same chance then the possibility of each deal is 1/4 so you just pick a number from 1 to 4.

If each hand in the range has it's own probability then you do the same thing, but weight them, i.e. you calculate the probability of each particular matchup. These add up to 100% so I just put them into some order, generate a random number from 0 to 1 inclusive, and pick the hand where the cumulative probability is over that hand's place and before the next hand. Again, I know I'm explaining this badly, but say that for our 4 hands above, the relative probabilites where
(1, 2) 50%
(1, 3) 30%
(2, 1) 10%
(2, 3) 10%
then your cumulative probabilities are like

(1, 2) 50%
(1, 3) 80%
(2, 1) 90%
(2, 3) 100%

I pick a random number. <0.5 means hand1, .5 to .8 means hand2, .8 to .9 means hand3, and above .9 means hand4.

Although I guess there's a bit more to my 2nd method because you have to account for removal. Like I said, it's been a long time since I've done it. The best way to check your method is to make a ton of weird test cases and check them against existing known good calculators.

Can I go back to the very basics?

Given the ranges of P1 and P2 given in OP, what is the "correct" distribution of the hands in each person's range?

I think it is "obvious" that P1 should get As2s 33% and KhKd 67% (if the deals are completely random).

Why do you say that P2 should get 2s2h 58% and 2h2c 42%?

Maybe this is also obvious, but I don't see it. (Maybe I'm an idiot.)

I programmed a range-vs-range equity calculator several years ago (probably like many others in this forum).

My idea was to run through all the "viable" deals which had a hand in each person's range (each deal gets prob 1/D where D is the total number of "viable" deals). The algorithm simply looped sequentially over each hand in each person's range, looping over all N players' ranges one at a time.

For OP's example above, there are three viable deals: {[As2s, 2h2c], [KhKd, 2s2h], [KhKd, 2h2c]}. So D=3 and each of those elements (deals) would have probability 1/3.

Since it is deals that are random, the use of 1/D seemed correct to me at the time. Now that I see this thread I wonder if that was correct and gave correct equities??

I still think P(KK vs 2s2h) = P(A2 vs 2h2c) = 3/8, and the other deal is 2/8.

[KK, 2s2h] and [A2, 2h2c] are sometimes arrived at by force, making them more probable than [KK, 2h2c].

But I'm not confident, so I'll code a sim if I can do so without begging the question.

Haven't coded a sim yet but now I'm leaning 1/3 because I feel like I'm making the same mistake I made in my overset thread.

The problem with making sims here is that your sim is going to reflect your assumption on how the outcome should work. To a certain extent it depends on what you "mean" when you give ranges for players. This is a lot more complicated when giving 2 players ranges than it is when giving one player ranges, because of the interaction between ranges

Good point Rusty.

Also (relatedly), poker players often have "weighted" ranges. For example, a range can contain all pocket pairs, but the range can be skewed toward the high pairs. I might play 1/4 of my 22-44, 1/3 of my 55-66 and 1/2 of my 77-99 (and all of my TT-AA).

Since there is software out there that does range vs range equities, I wonder how those cases are handled (I am fairly sure that the 1/D method is how "unweighted" ranges are handled).

To come full circle, as Rusty suggests, weighted ranges vs weighted ranges can be problematic since the different players' weights may "interact" in weird ways.

The above is certainly true, although this:

and I can't see how, if you follow the above, you can have 58%/42% as indicated in the OP. What whosnext said in post #6 is correct IMO: you land in one of the three equally likely possible cases.

I'd like if the OP could explain how he got his numbers.

Yeah, using Rusty's "full discard and resample" method, I get:

#1
{As2s, 2s2h} = (0.25)
{As2s, 2c2h} = 0.25
{KdKh, 2s2h} = 0.25
{KdKh, 2c2h} = 0.25

#2
{As2s, 2s2h} = (0.25*0.25)
{As2s, 2c2h} = 0.25*0.25
{KdKh, 2s2h} = 0.25*0.25
{KdKh, 2c2h} = 0.25*0.25

#3
{As2s, 2s2h} = (0.25*0.25)
{As2s, 2c2h} = 0.25*0.25*0.25
{KdKh, 2s2h} = 0.25*0.25*0.25
{KdKh, 2c2h} = 0.25*0.25*0.25

.
.
.

{As2s, 2c2h} = 0.25 + 0.25^2 + 0.25^3 + ... = 1/3
{KdKh, 2s2h} = 0.25 + 0.25^2 + 0.25^3 + ... = 1/3
{KdKh, 2c2h} = 0.25 + 0.25^2 + 0.25^3 + ... = 1/3

No idea where the "2s2h 58% and 2c2h 42%" values come from, but I'm also questioning whether this method is correct (could it be something to do with "2h" being in each hand)?

BTW: The "full discard and resample" method is what PokerStove used for it's monte-carlo sim. See this old thread for a discussion about some of the different possibilities to use instead (afaik, none of them work properly though...):

http://archives1.twoplustwo.com/show...fpart=all&vc=1

and if you look at the bottom of the thread for the posts by Andrew Prock, his attempt to improve on the "full discard and resample" method, also ended up bugged and he had to revert to his code.

Juk

The "Simple" method is given in the original post: Keep dealing combinations of hands until you get one that's possible.

An improvement is given by both heehaww and Rusty: Pick a random hand from the range for the first, and then do the same for the 2nd, and if the result is impossible, start over.

A further improvement is to:

1. Start with each hand in P1's range having a weight of 1.
2. For each hand in P1's range, discount that "1" by the probability that it collides with something in P2's range.
3. Pick a hand for P1 with the new weighted probability.
4. Then pick a hand for P2 from whatever's left from their range.

Using the example from the OP:

P1's range is { As2s KdKh }
P2's range is {2s2h 2c2h }

So for P1, we start with:

As2s: 1
KdKh: 1

As2s collides with P2's range 50% of the time. KK never collides. So we end up with:

As2s: 0.5 (1 discounted by 50%)
KdKh: 1 (no collisions so no discount)

which works out to a 1/3 probability of As2s and a 2/3 probability of KdKh. Deal P1 a hand with these probabilities.

If you deal P1 the As2s, 2s2h is removed from P2's range, so the hand must be 2c2h. If you deal P1 KdKh both of P2's cards are possible. So you end up with:

As2s vs 2c2h: 1/3
KdKh vs 2c2h: 1/3 (2/3 * 1/2)
KdKh vs 2s2h: 1/3 (2/3 * 1/2)

After Multiple Edits (sorry, I wrote something that I thought was wrong, but it's actually right):

This implies that all possible combinations will always have the same probability (so long as the initial weightings were uniform). This is because...

Suppose there are x cards in the P2's range. For a particular hand in P1's range, suppose there are y collisions. Then each combo including that hand will be weighted (x-y)/x * 1/(x-y) = 1/x, which is independent of y.

So the ultimate shortcut:

Pick randomly and uniformly from all possible combinations

This assumes that the initial weightings of all the cards in a particular range are uniform.

Yeah I obliquely mentioned it but also didn't explain it very well. I think if you were careful you could generate combinations properly for weighted ranges too but it's a lot harder.

No, it's not too hard. You just start with the weights and discount appropriately.

Eg:

P1 Weighted range:

7 AhKh
3 AcAd

(representing 70% / 30%)

P2 Weighted range:

1 AhKc
3 AdKd

(representing 25% / 75%)

So you can just multiply the weights of possible hands, and omit / set weight to 0 for impossible ones (if everything is weighted 1 we don't bother with the multiplication because the weight of any possible combo is always 1 * 1 = 1)

So we get:

AhKh vs AhKc: 0 (impossible)
AhKh vs AdKd: 21 (7*3)
AcAd vs AhKc: 3 (3*1)
AcAd vs AdKd: 0 (impossible)

And so we have a 21/24 = 7/8 probability of AhKh vs AdKd and a 3/24 = 1/8 probability of AcAd vs AhKc.

It's fairly easy to code -- just two nested loops. In Go it would look something like this:

Thank you everyone for the smart comments and analysis!

I am writing a sim for this, I have a test suite for various player vs player situations and I double checked those with other sims for accuracy so I know when the algorithm works and when it doesn't.

I thought I was dealing cards but no, I was dealing hands from each player range and using "full discard and resample" method and it works out well, however with 9-10 players and big ranges it generates too many discards and I was thinking about an alternate algorithm so I posted here a simplified situation for two players.

Following the discussion I implemented weights for two players and it works great! Same results as "full discard and resample". Right now I am looking into extending for 3 players when ranges collide and once I figured this out I will know how to do it for any number of players.