I dont think this changes the game in any meaningful way, but if its simpler to think of it that way I think its ok.

I think this maps out what's required pretty well. I don't think it would even require any simulation. The heads up EV for any two hands is well charted by now so matchups against any two strategies as described above would just require straightforward calculations running through the probabilities for possible opposing holdings. The programming would take a little work but I don't see the computer taking much time getting it done.


PairTheBoard

I told David at the WSOP that I would solve this game when I got home; I'm kind of busy right now, but if noone posts a solution by the beginning of next week I'll do it. This post seems right on track to me.

"Absolute exact solutions" can be found by using some kind of gradient descent method, but fictitious play can find solutions to within any specified tolerance.

I'm curious as to why he's interested in this problem. It would be straightforward to solve using fictitious play but does he have some application in mind? Or is he just curious about how this kind of problem would be solved, but doesn't care about the actual solution? Because I'm not sure why he would.

A simulated solution is not what I mean by an exact solution.

Keep in mind that suits proabably matter. Not only might you get a different showing percentage for 96offsuit than 96 suited, there might sometimes be a switch from a call to a fold depending on whether the shown card matches one or both of his own suits.

When I toyed with this problem in my head I calculated that A2 would prefer everything but aces to fold, as opposed to being called by all the hands that would call if a random card was flipped and a deuce was exposed. Even though you will usually be a small favorite when called. Can someone verify that?

The method I described with fictitious play would converge on the Nash equilibrium mixed strategy for both sides with whatever degree of precision you require (more iterations = better precision). And as described it takes the suits into account fully, ie solving for the call probability for each of the 5005 distinct situations the caller might face. If that's not what you mean by an exact solution, I don't know what you mean. There's some work required from a programming standpoint but conceptually the problem isn't difficult.

He also gets to fold in spots where he would otherwise call, for example, he has KQ and we show an ace.

One thing about this problem is that it's not very obvious to solve with your brain, but easy to solve with a computer. (Witness the posts in this thread.) This makes it seem harder because you can't really puzzle out the general structure of the solution right away. By contrast, the jam-or-fold problem is kind of obvious (you just keep adding hands as the stacks get smaller and smaller) and the computer just tells you which and when. You feel smarter because you knew what the solution looked like, and the computer just did detail work.

I'm dumb, but I don't think you need to "go out on a limb" to predict that. Let's ignore suits temporarily, as they're just a slight complication.

A strategy 'S' for Player 1 is a map from an exposed rank 'r' to the range of hands 'H' that expose that rank. S[r] => H.

Say Player 2's hand is 'h'. Let 'H|h' denote a range discounted by this hand. Then, given that P1 exposes r, P2's calling EV = equity(h, S[r]|h).

Our goal is to find the S for P1 that minimizes P2's total EV across all hands. So consider any unpaired hand h:{r1, r2}. S may map h to either r1 or r2. (Every hand implies a distinct strategy pair.) There are 156 unpaired hands. Thus, there are 2^156 possible strategies.

I mean...wtf am I missing here? Barring a profound insight into the underlying structure of this game, there's no chance in hell of getting an exact solution.

I am obv missing something here, but... if there is no ante or blind to win, why are we ever shoving without aces? Also, if the deal alternates isn't the value of the game 0, and isn't never shoving an equilibrium?

I don't see why you couldn't get an exact solution. You would have to store matrix entries as exact rational numbers, and the numerators and (common) denominator would get quite large, and you would have to allow for storing integers of sufficiently many digits, but I think it's all doable.

must shove, may call

ahhh... ty. now it makes and is interesting.

2^156 pure strategies for the first player. Infinitely many mixed strategies. But that doesn't make it unsolvable. If it did, the push/fold game would have been unsolvable too.

I'll put this in terms of the push/fold game. The fictitious play algorithm converges on the solution (yeah, technically it never gets there exactly but so what, it gets however close you require), and it does this iteratively by finding the optimal counter-strategy to the opponent's current strategy. It goes back and forth doing this for both sides until the mixed strategy for both sides stabilizes sufficiently (it builds the mixed strategy by probabilistically combining the pure counter-strategies it finds in each step). Finding the optimal counter-strategies would be practically impossible if the algorithm had to consider all 2^169 possible pure strategies to find the best counter, but that isn't necessary. Instead it looks at each hand separately and finds the best strategy for that hand. Should we push with T7o against such and such a calling range, or should we fold? The answer to that question doesn't depend on the other 168 variables of the counter-strategy. So it's easy, just find the best strategy for each of the 169 hands individually. Put those components together and you have the counter-strategy for that round.

What does exact even mean? Computers can't get an "exact" solution for the value of Pi but I don't think that's what people are talking about.

The search space for checkers is 5x10^20, and it took 18 years to solve. The search space of DS game is 10^26 times as big!

Wow...and Jerrod said he thinks this is "easy to solve with a computer"...wtf am I missing...

Yeah, I guess you could say we've solved chess "exactly" enough, now that computers are unbeatable.

But that seems like a weird use of 'exact', especially for someone like Jerrod who's written a book on poker game theory...

I don't think the chess comparison is fair. We can't find the best strategy to any arbitrary degree of precision -- the problems, and the methods used to solve them, are of different types.

Yeah, I understand that...we can have a race to implement it if you want ...apparently my interpretation of 'absolute exact solution' was a bit perverse, lol.

That's well put; I retire in disgrace.

Solve 2x=3. Beware, the search space is infinite.

You can represent rational numbers exactly, and lots of other types of numbers too. I don't see any obstacle to solving the OP's problem exactly.

But we have profound insight into the structure of that search space. The search space for Sklansky-Poker, on the other hand...

Say we're standing on a strategy S. (Using my notation above.) Then the smallest step we can take (to some S') is to switch the mapping of a single hand. I.e. if h_{{r1, r2}} ∈ S[r1], then h_{{r1, r2}} ∈ S'[r2].

For S, P2 had minimum calling hands h1 and h2 vs. S[r1] and S[r2]. His net EV given an exposed r1 was EV_r1 = ∑EV(h≥h1, S[r1]); symmetrically for an exposed r2. For S', he has new minimum calling hands h1' and h2' and new EV'_r1 and EV'_r2. So P1 is probably happy if (EV'_r1 + EV'_r2) < (EV_r1 + EV_r2).

But should he be happy?! There were 155 other steps he could have taken instead of h. Maybe one of them was better. Maybe even if h was the best locally, it only leads to a dead end later. How is a P1 to know? (Remember, he has 2^156 places to look.)

Of course there are heuristic searching procedure. (Although my sense is that EvilSteve underestimates the difficulty of finding a good one.) But for my perverse notion of 'absolute exact solution', I demand a MAP with a bloody X marking THE SPOT.

If you can draw that map, I suspect you have a very exciting publication in your future.

http://en.wikipedia.org/wiki/Zero-sum_(game_theory)

http://en.wikipedia.org/wiki/Linear_programming