Heads Up Hold'em Solved?
10-13-2013
, 08:43 AM
Quote:
FullyCompletely
Some comments, that will be kinda long so if anything please just answer my questions at the end
Quote:
Heads-up no-limit with $1/$2 blinds and 100-big-blind ($200) stacks, where you can only make whole dollar bets, has 8.72*10^38 game states and 8.81*10^35 decision points, and a lossless abstraction only gets you down to 3.81*10^34. That's enormous.
Calculating stuff like bet 1$, raise 2$, raise 3$ etc in every situation is just waste of time.
What you need to do is to solve the game with some reasonable betsizes then apply some generic strategy to deal with small bets of the opponent and just show that he can't exploit it for more than some epsilon.
Quote:
and the cards are a much smaller part of no-limit than the betting is
Quote:
This no-limit game is so big that if you used just one byte to represent the probability of each action in the preflop alone (assuming you can recompute subgame strategies as needed, like you claimed), it'd take 5.5 petabytes of disk just to write down the first round of a strategy. It'd take nearly 6,000 yottabytes if you wanted to store the flop as well.
It's obvious that walking whole no-limit tree is pointless endeavour so we can just as well stop thinking about ever doing it.
The same goes for using 20 different bet sizes on every street and similar stuff. It's just not feasible.
Quote:
To measure exploitability, you have to measure how much you could lose against an opponent that can make any bet sizes, not just the ones in your betting abstraction
Trying all 0.1$ 0.2$ ... bets is really waste of time for practical purposes imo.
Quote:
In the numbers you listed before, you said it took 0.5 seconds per flop. It takes us a couple of minutes (for heads-up limit)
I claimed it for no-limit with fixed bet sizes which is significantly smaller than limit.
I will do estimations how long would it take for full limit tree with 4bet cap. Out of my head I don't even know how many nodes there are in such tree unfortunately so I can't give quick estimation.
If you want compare implementations: for mine calculating full flop equity (1326 hands vs 1326 hands with different weights represented as arrays of 1326 floats) by naive way of iterating over all 1176 boards and calculating river equities on them and then summing it all up takes about 0.007s on i7 (using one core).
This includes exact amount of matchups/wins for every hand, dealing all the board and summing things up.
Dividing by 1200 and then amount of cores will give good approximation of time needed for one river node which goes to showdown.
It's much faster for nodes where one player folds (because then you only need to know how often that happens).
Quote:
100-blind no-limit is 10^20 times larger; 3.4*10^20 hours is 3.88*10^16 years, so you're going to be waiting for a while before you can claim to have solved heads-up no-limit.
I can can try 1$ bet, 5$ bet and if neither options brings anything (when calculating BR) I can safely assume option in between doesn't either (for max exploitability).
It won't be accepted as mathematical proof (at least without proving formally that the technique works) but it's good enough in practice.
It's like with river bets, if there is 100$ on the river, 100$ in the stacks and you allow for all kind of bets you will quickly see that adding 100 options won't change much (or anything sometimes) comparing to just 2 options (checking and going all-in).
This is as long opponent can check-raise and have non stupid range (ie not only bluff catchers). If that turns out to be trues on say 1k river situations (I didn't test for that many) then we can safely assume we don't need to ever bet anything else and just focus on strategy for dealing with opponent using those options.
Quote:
To measure exploitability, you have to measure how much you could lose against an opponent that can make any bet sizes, not just the ones in your betting abstraction
You seem to be focused on the idea of ever travelling full NL tree. It won't work. It's not necessary. It's waste of time to even think about it.
Quote:
At 0.5 seconds per subgame, that's 3.4 hours for heads-up limit. But 100-blind no-limit is 10^20 times larger
Quote:
t's why research has made such great progress on perfect information games like chess and checkers: in those games, you can break up the game tree, solve each piece to get a perfect fragment of a strategy, and then provably be able to recombine them to form a perfect strategy
99% of play in chess is still calculated from scratch by engines during play. The main realization which allowed for big progress in chess was that you can recalculate the searching tree at every iteration (using some hints from previous one) instead of storing it in RAM as well as some very clever tricks to make alpha-beta algorithm faster.
Quote:
That's what you're suggesting for poker.
I don't want to store solutions and reuse them in next iteration I want to recalculate them with new ranges at every point using hints from previous ones.
Quote:
In the simplest approach, you solve the trunk using CFR, use that strategy to compute the players' ranges for each subgame, then compute optimal strategies for the subgames. You do that once, then take all the pieces, combine them back to a complete strategy, and declare victory.
I appreciate you went that far to explain why it doesn't work but let's focus on reasonable ideas like:
Quote:
>You could try alternating back and forth between the trunk and the subgames foreve
If you store enough informations about subgames from previous interations the subsequent ones will be faster (because if strategies in the trunk doesn't move mcuh you can start from somethign reasonable instead of random)
Quote:
These days, we instead just use single big shared memory machines with lots of cores. We have machines with lots of RAM now, and speed is just as important.
Quote:
But you were describing something different - your goal was related, but you also wanted to throw away the subgame strategies and recompute them from scratch as needed, both when running CFR for training the trunk strategy and for playing the game.
Quote:
But CFR-D requires some very unusual bookkeeping at the boundary between the trunk and the subgames that allows you to compute or recover the subgame strategies to avoid the problem I described with the Rock-Paper-Scissors example. You didn't mention CFR-D or any of the extra details required to make that work, so it sounds like you didn't go that route
Can you give some details about "unusual bookkeeping"? It seems simple to me: you just store say preflop strategy. Solve subtrees for every exit (for example only sampling some flops instead of doing them all)
Once you have the solution, you calculate payyoff for every hand, average them to preflop hand groups and update regrets for those - repeat.
Quote:
>CFR-D also converges much, much more slowly than CFR: not in the speed of the code, but also the convergence rate of the algorithm
Still, I think preflop converges relatively fast but it's only based on intuition so no proof nor argument here.
Quote:
>but it wouldn't have any guarantee of converging to a Nash equilibrium
Again I only want to use cues from previous iteration to have better starting point not to reuse them with changed trunk.
Quote:
> I have access to a cutting-edge supercomputer (a single ccNUMA machine, not a cluster) with 2048 cores and 16 TB of RAM.
Quote:
>This is the approach I think is most likely; we were already at 37 mbb/g in 2012 going this route.
Could you give some numbers for to NLHE HU bots ? At least for their postflop strategies. That would be very useful and also probably put a lot of peace in most people's hearts
For example I observed that it relatively easy to go to 100mb/g in games which start wit 4bb pot (and use say 70% bet size) but it's much more difficult in 3bet pots where starting pot is about 14bb).
Quote:
>>Just using CFR with decomposition the way you suggested, though, almost certainly won't solve the game because it has no guarantee of converging to equilibrium
Quote:
>>So, to sum up: I think you might be a bit optimistic on the no-limit thing.
I have no doubt that going full tree (or even approximation of full tree) way is computational suicide.
I think you can engineer good generic strategies to deal with different bet sizes than were used to calcualte equilibrium in simplified games and don't use too many betsizes yourself.
It's similar to what humans do: nobody spend mental cycles on thinking what happens if he bets 0.01 of the pot and I raise him to 0.03 and he raise me to 0.07. It's just waste of time which can be dealt with in generic way.
Also my observations so far shows that you can safely ignore all the small bets in most situations or at least reduce them to one as having 0.15, 0.25 and 0.35 available doesn't improve over having only 0.25
It makes sense as there is cost of splitting bet amounts (it's difficult to keep all the ranges balanced) and there is huge cost of betting small: you open yourself to raise/bet/bet attack otherwise not available to opponent but you only can hope to profit very little by making small bet and having opponent call it with required frequency while you have to sacrifice some good value betting hands to do that (which you could made big bet with) to make sure you are not vulnerable to check-raise/bet things.
If that is correct the focus should be on generic way to deal with those small (presumably suboptimal) bets and to approximate strategies vs bets in the middle having it solved for similar sizes.
As to limit I don't have any experience nor intuition but did try measuring how much removing some possibilities from game tree cost ?
For example:
-let's say we never donk bet on the flop, how much does it cost OOP player ?
-never 3bet in position preflop
-never 3bet preflop (some top pros were doing it for some time in the past)
-never check-call/donk turn
Especially cutting 3betting in position seems very promising to me (it's very promising in shallow no-limit when you can bet turn/shove river anyway) so overall exploitability of a player who doesn't ever raise in position on the flop doesn't change much.
Thanks very much for the response. Your remarks are very useful and informative
Last edited by punter11235; 10-13-2013 at 09:04 AM.
10-13-2013
, 11:42 AM
10-13-2013
, 03:25 PM
Note that I said it is very difficult, not impossible. You can build computers with learning algorithms where they try to solve things themselves. You can allow them to rewrite there own source code etc and as they get smarter and smarter each time, it will slowly create its own personality.
The difference is, the human brain isn't limited to purely on or off signals, and it can effortlessly do things in parallel on a massive scale, but each node is significantly slower then a computer processor. It is the equivalent of 100,000,000,000,000 cores running at something like 10Hz each (1GHz = 1,000,000,000 Hz).
Quantum computing allows bits to be 1, 0, or somewhere random in between, and the first basic quantum computers are being made now. They will eventually allow for this massive parallel decision making to be done on the same level of the human brain, and in fact, it is actually estimated computers will over take humans in the not to distant future. It is called the technology singularity, you should give it a google if you are interested.
Humans only have personalities because it was necessary for us to survive. In effect, we were a learning algorithm with just the basic parameters of "How can we maximize our chances of survival", which slowly gets smarter as we evolved. It is quite depressing to think about it like that I guess, it is much more satisfying just believing in a sky daddy and following a special book
Thank you for posting by the way FullyCompletely, it is good to know we wont all be out of a job for at least a few years yet!
10-13-2013
, 10:50 PM
Holy crap this thread is awesome. Gazillion thanks to FullyCompletely for answering all our dumb questions 
I'm somewhat worried about upcoming NL bots so I figured I would analyze the 100 hand video between slumbot and hyperborean: http://www.youtube.com/watch?v=W4CqUw_VP_Q
I've played NLHU for a living for 6 years but mainly bumhunting vs fish and only recently started to develop balanced strategies so I realize I could be off on many points here. With that said, here's my analysis/criticism of the bots play:
In summary, both bots appeared super unbalanced and very exploitable. They sometimes do random stuff that doesn't appear to make sense and they mimick human fish in other ways too. Not convinced of the end of poker.
Preflop both bots appeared to 3bet bad hands for higher sizings and good hands for smaller sizings: Slumbot raises 5xR with 86s and 3xR with AQs. Hyperborean does 3xR with 99 and higher sizings with T7o,K6o,98s,KQs. Both bots also seemed to limp predominantly bad hands - even if they don't limp-fold much, they're still exploitable postflop. At least over this sample their preflop play seems very exploitable.
I also don't understand the need to "mix it up" with sizings with hands like K4o (sometimes 2.5BB sometimes 2BB). Preflop ranges are so wide anyway there's really no need for that. Find out which sizing is more optimal and use that 100% of the time.
Postflop both bots like to potbet predominantly nuts and minbet predominantly weak hands. Hyperborean minbets at least 10 times with bottom pair or similar and only 1 time with a good hand. It's as if the bots are imitating human fish.
Weird hands:
0:22 Hyperborean cc J2o on 8d8sJs, weak donk on turn 2, potdonk river J
This is funny in that it is exactly how many fish like to play J2. The line appears more "human-like" than I would expect. My issues with this hand from a GTO perspective:
Flop and turn sizings are small enough to allow the other person to call with drawing hands profitably. I would think the optimal sizing on flop & turn should be at least 1/2 pot, maybe 2/3 to 3/4 pot. Sizings are even more horrible if the bots use the same sizing for 8x, missing a ton of value from JX and giving really nice odds + implied odds for drawing hands. If that is not the case and the bots use a bigger sizing for 8x, then we have an issue of our range being capped with the small sizing and we are more vulnerable to bluffs.
River: Both players' ranges should be draw-heavy and the river bricked. How is potbet an optimal sizing for a river donk when both ranges contain mostly air? A smaller bet is almost as likely to make air fold, excluding A/K high draws. Also, our opponent should never have 8x or good PP after that flop+turn action, so when our potbet is called/raised we are splitting the majority of the time. So a smaller river bet increases our EV both when we have air and when we have a J.
1:12 hyperborean 3bets 99 and minbet-calls QT3r flop. Hand is checked down.
After hearing the argument for a minbet differing very little from checking I suppose this isn't as horrible as it first seemed. That's presuming our minbet-call range is actually balanced.
My issue with this hand is slumbot raising J5 from position with backdoor flush draw. I would understand it as an exploitative raise but not as part of a GTO-strategy. We have to have a calling range in that spot (otherwise we are vulnerable either by folding too much to the minbet or raising too much crap and then folding to a reraise). And since we must have a calling range, J5 with bdfd should be among THE MOST OPTIMAL HANDS FOR CALLING, since half the turn cards actually improve our hand (any spade, 9, K, J or 5) yet we don't have much equity on the flop. It should be more optimal to raise crappy hands which are less likely to improve on the turn + hands that have decent equity on the flop already.
1:46 slumbot raises 88 no club on KxQc6c2c from position.
I assume this is a spot where slumbot balances its valuerange by raising crappy hands x% of the time. My issue with it: our hand has 1 out to make a semi decent hand in case we get called. We're going to fold plenty of better hands to that turn bet and then we're going to bluff with a 1-outer? Why not bluff with something like a low pair from the board or a low club (which has sometimes outs against our opponent and has always blockers to his flushes) It's inconsistent to fold better hands and raise weaker hands in the same spot.
2:18 Board is 4-flush on the turn, the hand is checked down to river. BB checkraises a potbet with 9 high flush, which is 4th nuts
Here I'm just confused. I mean it must be value-raising, right? SB checked back the flop and turn so there should be fewer high flushes in his range, but I find it very hard to believe our range is not exploitable either by a river reraise bluff OR slowplayed nuts. Besides, what hands are we going to get called by?
3:34 SRP slumbot cc flop 2h2c8h with Kh6s. Turn is Qh and slumbot check-folds to 1/2pot bet
The best turn cards for us in order are K,8,6,2,H,A. If we fold hearts and worse, then we are folding the turn (1 - 11/46) = 76% of the time. Villain needs us to fold only > 34% of the time in order to bluff profitably with no equity. 76% means villain would be printing money against us by 2-barreling here. Therefore, calling the flop doesn't make sense if we are planning to fold to a heart. We either need to bet, cc or cr the heart on the turn OR we need to checkfold the flop. Otherwise we are exploitable.
4:00 slumbot 3bets 8c6c, flops 4s5c6s. Hyperborean defends with 99 and checks back the flop. Turn is 8s and Hyperborean minbets from position!
Minbetting oop is almost indistinguishable from checking, but minbetting from position is HORRIBLE. We could take a free card, instead we are risking a check-raise with a marginal holding. Not only that, we're also giving villain the odds to profitably call with anything. How is this even remotely close to GTO?
4:24 Slumbot checks back J93, turn is 9 rainbow, hyperborean potbets 94 from OOP
Regardless of slumbot's folding frequency on the turn, we can presume he is drawing dead against us. Earlier when the board was drawy and hyperborean's range included draws, slumbot made 1/4 pot bet with TPNK, giving draw hands the odds to call. Now the board is dry and hyperborean is likely drawing dead, so why are we potbetting now? We could check (or minbet like the bots enjoy so much) or bet 1/2pot. Any of these options should be more profitable for our range which presumably holds many more bluffs than 9x.
5:40 and 7:20 Hyperborean minbets from position again and again with BP
Any NLHU reg knows why this is horrible. Not only are we putting ourselves in a tough spot if we get raised, we are weakening our checkback-range AND we are giving villain good odds to call with any overcards.
In the 7:20 hand Hyperborean hits trips on the turn and potbets, establishing clearly that these bots like to potbet invulnerable nuts and make small bets with weaker hands.
Edit: at 15:40 Hyperborean actually minbets 64 IP on 443r
8:00 QJ3r board, Hyper CR /w QJ
By now I'm thinking these bots never slowplay good hands. The board is somewhat dry and we are blocking Q's and J's. If we ever check-call this flop with a good hand it would be with QJ/QQ. So I guess our check-call range is always going to be weak on the flop, how is that unexploitable? We're just revealing all our good hands by checkraising/donking, and then we're check/calling multiple streets with trash?
17:20 slumbot check-folds 75 on 4xAx3d9d to a 1/2pot bet
Pretty sure check-call is profitable here with implied odds against bluffs, strong made hands and against 2x (we're also crushing 65) And I'm 100% sure betting would be better than check-calling. This is what I mean when I was talking earlier about making bluffs with 1-outer hands and folding better hands. When you relate this to the 88 bluff, it seems really inconsistent. Like a human fish playing.
17:42 Hyperborean check-calls a potbet with 96o on KT7r
Of course, villain has 95o and the turn is going to be 8, so great call!
I'm somewhat worried about upcoming NL bots so I figured I would analyze the 100 hand video between slumbot and hyperborean: http://www.youtube.com/watch?v=W4CqUw_VP_QI've played NLHU for a living for 6 years but mainly bumhunting vs fish and only recently started to develop balanced strategies so I realize I could be off on many points here. With that said, here's my analysis/criticism of the bots play:
In summary, both bots appeared super unbalanced and very exploitable. They sometimes do random stuff that doesn't appear to make sense and they mimick human fish in other ways too. Not convinced of the end of poker.
Preflop both bots appeared to 3bet bad hands for higher sizings and good hands for smaller sizings: Slumbot raises 5xR with 86s and 3xR with AQs. Hyperborean does 3xR with 99 and higher sizings with T7o,K6o,98s,KQs. Both bots also seemed to limp predominantly bad hands - even if they don't limp-fold much, they're still exploitable postflop. At least over this sample their preflop play seems very exploitable.
I also don't understand the need to "mix it up" with sizings with hands like K4o (sometimes 2.5BB sometimes 2BB). Preflop ranges are so wide anyway there's really no need for that. Find out which sizing is more optimal and use that 100% of the time.
Postflop both bots like to potbet predominantly nuts and minbet predominantly weak hands. Hyperborean minbets at least 10 times with bottom pair or similar and only 1 time with a good hand. It's as if the bots are imitating human fish.
Weird hands:
0:22 Hyperborean cc J2o on 8d8sJs, weak donk on turn 2, potdonk river J
This is funny in that it is exactly how many fish like to play J2. The line appears more "human-like" than I would expect. My issues with this hand from a GTO perspective:
Flop and turn sizings are small enough to allow the other person to call with drawing hands profitably. I would think the optimal sizing on flop & turn should be at least 1/2 pot, maybe 2/3 to 3/4 pot. Sizings are even more horrible if the bots use the same sizing for 8x, missing a ton of value from JX and giving really nice odds + implied odds for drawing hands. If that is not the case and the bots use a bigger sizing for 8x, then we have an issue of our range being capped with the small sizing and we are more vulnerable to bluffs.
River: Both players' ranges should be draw-heavy and the river bricked. How is potbet an optimal sizing for a river donk when both ranges contain mostly air? A smaller bet is almost as likely to make air fold, excluding A/K high draws. Also, our opponent should never have 8x or good PP after that flop+turn action, so when our potbet is called/raised we are splitting the majority of the time. So a smaller river bet increases our EV both when we have air and when we have a J.
1:12 hyperborean 3bets 99 and minbet-calls QT3r flop. Hand is checked down.
After hearing the argument for a minbet differing very little from checking I suppose this isn't as horrible as it first seemed. That's presuming our minbet-call range is actually balanced.
My issue with this hand is slumbot raising J5 from position with backdoor flush draw. I would understand it as an exploitative raise but not as part of a GTO-strategy. We have to have a calling range in that spot (otherwise we are vulnerable either by folding too much to the minbet or raising too much crap and then folding to a reraise). And since we must have a calling range, J5 with bdfd should be among THE MOST OPTIMAL HANDS FOR CALLING, since half the turn cards actually improve our hand (any spade, 9, K, J or 5) yet we don't have much equity on the flop. It should be more optimal to raise crappy hands which are less likely to improve on the turn + hands that have decent equity on the flop already.
1:46 slumbot raises 88 no club on KxQc6c2c from position.
I assume this is a spot where slumbot balances its valuerange by raising crappy hands x% of the time. My issue with it: our hand has 1 out to make a semi decent hand in case we get called. We're going to fold plenty of better hands to that turn bet and then we're going to bluff with a 1-outer? Why not bluff with something like a low pair from the board or a low club (which has sometimes outs against our opponent and has always blockers to his flushes) It's inconsistent to fold better hands and raise weaker hands in the same spot.
2:18 Board is 4-flush on the turn, the hand is checked down to river. BB checkraises a potbet with 9 high flush, which is 4th nuts
Here I'm just confused. I mean it must be value-raising, right? SB checked back the flop and turn so there should be fewer high flushes in his range, but I find it very hard to believe our range is not exploitable either by a river reraise bluff OR slowplayed nuts. Besides, what hands are we going to get called by?
3:34 SRP slumbot cc flop 2h2c8h with Kh6s. Turn is Qh and slumbot check-folds to 1/2pot bet
The best turn cards for us in order are K,8,6,2,H,A. If we fold hearts and worse, then we are folding the turn (1 - 11/46) = 76% of the time. Villain needs us to fold only > 34% of the time in order to bluff profitably with no equity. 76% means villain would be printing money against us by 2-barreling here. Therefore, calling the flop doesn't make sense if we are planning to fold to a heart. We either need to bet, cc or cr the heart on the turn OR we need to checkfold the flop. Otherwise we are exploitable.
4:00 slumbot 3bets 8c6c, flops 4s5c6s. Hyperborean defends with 99 and checks back the flop. Turn is 8s and Hyperborean minbets from position!
Minbetting oop is almost indistinguishable from checking, but minbetting from position is HORRIBLE. We could take a free card, instead we are risking a check-raise with a marginal holding. Not only that, we're also giving villain the odds to profitably call with anything. How is this even remotely close to GTO?
4:24 Slumbot checks back J93, turn is 9 rainbow, hyperborean potbets 94 from OOP
Regardless of slumbot's folding frequency on the turn, we can presume he is drawing dead against us. Earlier when the board was drawy and hyperborean's range included draws, slumbot made 1/4 pot bet with TPNK, giving draw hands the odds to call. Now the board is dry and hyperborean is likely drawing dead, so why are we potbetting now? We could check (or minbet like the bots enjoy so much) or bet 1/2pot. Any of these options should be more profitable for our range which presumably holds many more bluffs than 9x.
5:40 and 7:20 Hyperborean minbets from position again and again with BP
Any NLHU reg knows why this is horrible. Not only are we putting ourselves in a tough spot if we get raised, we are weakening our checkback-range AND we are giving villain good odds to call with any overcards.
In the 7:20 hand Hyperborean hits trips on the turn and potbets, establishing clearly that these bots like to potbet invulnerable nuts and make small bets with weaker hands.
Edit: at 15:40 Hyperborean actually minbets 64 IP on 443r
8:00 QJ3r board, Hyper CR /w QJ
By now I'm thinking these bots never slowplay good hands. The board is somewhat dry and we are blocking Q's and J's. If we ever check-call this flop with a good hand it would be with QJ/QQ. So I guess our check-call range is always going to be weak on the flop, how is that unexploitable? We're just revealing all our good hands by checkraising/donking, and then we're check/calling multiple streets with trash?
17:20 slumbot check-folds 75 on 4xAx3d9d to a 1/2pot bet
Pretty sure check-call is profitable here with implied odds against bluffs, strong made hands and against 2x (we're also crushing 65) And I'm 100% sure betting would be better than check-calling. This is what I mean when I was talking earlier about making bluffs with 1-outer hands and folding better hands. When you relate this to the 88 bluff, it seems really inconsistent. Like a human fish playing.
17:42 Hyperborean check-calls a potbet with 96o on KT7r
Of course, villain has 95o and the turn is going to be 8, so great call!