When to Stop Solving: Why a Longer Solve Can Make Your Strategy Worse

Every solver that groups hands has a best point. After it, each new iteration makes the strategy worse, not better. We measured this on five spots. This article explains where it comes from, what we found and how to find the best point yourself.

In short

We measure the quality of a strategy by its exploitability: how much an opponent wins per hand on average if they know the whole strategy and play the best answer to it. Lower is better. Every percentage in this article means the same thing: how much higher the exploitability is than at the best point of the solve. "10% worse" means the opponent wins 10% more against the strategy than against the best one.

• Every solver that puts similar hands into groups (buckets) reaches a point where it stops improving the strategy and starts to make it worse.
• If the solver also forgets which group a hand was in on the previous street, the effect is much stronger. Most solvers work this way, because it saves a lot of memory.
• On our spots the best point was at about 10 million iterations in Hold'em and Short Deck and at about 100 million in PLO4. If you solve to a billion, exploitability is 10% higher than at the best point in PLO4 and about 60% higher in Hold'em and Short Deck. On a PLO5 turn it did not start to rise before 10 billion iterations.
• How to find the point yourself. If you can compute the exact Best Response, stop where it is lowest. If Best Response is too slow, check LBR at 1M, 3M, 10M iterations and so on. When LBR is higher than at the previous checkpoint, solve one more checkpoint and stop.

How a solver simplifies the game

Poker has too many hands and boards to solve a strategy for each hand on its own. So the solver puts hands that play alike into groups, called buckets. All hands in one group play the same way. The result is a smaller game that fits in memory. This smaller game is called an abstraction.

The solver solves exactly this smaller game. But we will play the strategy in the real game, where every hand is different. So we measure the quality of a solution in the real game.

Why a long solve can hurt

At the start of a solve the strategy gets better fast, both in the smaller game and in the real one. But after some point the solver fits itself more and more closely to the smaller game, including its mistakes. For example, one group may hold hands that really play differently. The solver finds a strategy for the group that pays off on average. But the opponent sees their real hand, not the group, and can punish each hand on its own.

In machine learning this is called overfitting: a model learns its training examples too well and does worse on new ones. It is the same here. The smaller game is the training set, the real game is the test.

This effect has been known in research since 2011. Johanson and co-authors showed it in Limit Hold'em: quality in the real game first improves fast, then slowly and steadily gets worse, while in the smaller game everything keeps improving. Their chart shows it for two abstractions, one that remembers past streets and one that forgets them. So memory is not the whole story. The effect is there in every solver that groups hands.

Why forgetting makes it worse

Most solvers group hands again from scratch on every street. On the turn the solver no longer knows which group the hand was in on the flop. This is called imperfect recall. Solvers do it because it saves a lot of memory: the number of groups does not multiply from street to street.

It has a price. The proof that the CFR algorithm reaches an equilibrium only works for a player who remembers everything that happened. Without it there is no such promise, and the solve can drift away even inside the smaller game.

We tested this on small decks, where everything can be computed exactly. When the groups of each street were built inside the groups of the street before (the solver remembers the path of a hand), the loss after the best point was 3 to 5 times smaller: for example +17% instead of +60%, and +9% instead of +42%. But it did not go away until we removed grouping altogether. And without grouping the real game does not fit in memory.

How we measured

• Two players, the standard 100 big blind tree (fold, check, call, pot-size raise, all-in), our Balanced abstraction.
• Best Response. This is how exploitability is computed: how much an opponent wins if they know our whole strategy and see their real hand. It is the main measure of quality: lower is better. It is exact, but expensive.
• LBR (Local Best Response, Lisý and Bowling, 2017). A fast estimate from below. The opponent knows our strategy but plans nothing ahead. At each point where they act, they choose an action (fold, check or call, bet) as if the hand will then go to showdown with only checks and calls. They do not count on later bets. So they find only some of the weak spots of the strategy, not all of them. LBR is never higher than the true Best Response. So if LBR is above zero, there is a real leak. If it is near zero or below, that proves nothing.
• Checkpoints three times apart: 1,000, 3,000, 10,000 iterations and so on up to 1 billion. At each checkpoint we computed Best Response and LBR.
• All numbers are chips per hand. 10 chips are one big blind.

Five spots:

• PLO4, preflop, a smaller deck of 7 ranks, 28 cards. On the full deck one Best Response point for PLO4 preflop would take about two weeks.
• PLO4, flop, full deck, ranges 5-15% against the top 10%.
• Short Deck, preflop, the way it is played: both players post an ante, the button posts a blind.
• Hold'em, preflop, full deck, a tree without limps (a preflop call only against a raise). With the standard tree one Best Response point took 13 minutes, without limps 4.
• PLO5, turn, full deck, the same 5-15% against the top 10%. Here the checkpoints went up to 10 billion iterations, because Best Response kept falling for a long time. One Best Response point on a PLO5 turn takes about 16 seconds. PLO5 from the flop or preflop is out of our reach: one point there takes hours or days.

Results

On the charts the green band marks the lowest Best Response, the best point. The dashed violet line shows where the LBR rule from the section below stops. The violet ring marks the lowest LBR the rule starts from.

PLO4, preflop, 28-card deck

Full ranges, 100 big blinds, blinds 10/5.

Best Response falls tenfold, bottoms out at 100 million iterations and then rises: at a billion, exploitability is 11% higher. LBR on turn and river reaches zero at 10 million, while the solution can still be exploited for 1.5 big blinds per hand. Zero LBR does not mean the solution is done.

PLO4, flop, full deck

Pot 60, stacks 970, ranges 5-15% against the top 10%.

The bottom is at 100 million again, with a different deck, street and ranges. At a billion, 10% higher. Here LBR is more useful: it stays above zero the whole time and shows 40 to 70% of the true Best Response.

Short Deck, preflop, antes

Both players post an ante of 10, the button adds a blind of 10 and acts last. Stacks 1000.

The bottom is at 10 million. After it the strategy gets worse much faster than in PLO4: at a billion, exploitability is 59% higher.

Hold'em, preflop, full deck, no limps

Full ranges, 100 big blinds, blinds 10/5. The rule line uses LBR on all streets. The text below the chart says why.

The bottom is at 10 million, 1.06 big blinds per hand. At a billion, exploitability is 59% higher, as in Short Deck.

Here LBR on flop, turn and river and LBR on turn and river go far below zero. That is expected. This tree has no preflop call, so "playing preflop passively" means the small blind raises any two cards and the big blind calls with any two cards. That is very bad poker, and the greedy player on later streets cannot win it back. If you stop by these LBR types, exploitability is 18% higher than at the best point. If you stop by LBR on all streets, you land exactly on the best point.

PLO5, turn, full deck

Pot 60, stacks 970, ranges 5-15% against the top 10%. The chart starts at 1 million iterations, so the end of the curve is easy to see. Before that, Best Response falls from 182 chips.

No rise. Best Response falls fast until 300 million iterations (3.22) and then barely moves: 3.28 at 1 billion, 3.06 at 10 billion. LBR keeps falling slowly and shows 60 to 95% of Best Response. The rule does not stop this solve, and that is right: solving longer does no harm here. A possible reason: from the turn, hands are grouped again only once, on the river. From preflop that happens three times. This fits the finding that forgetting makes the effect stronger, but we did not test it directly.

Summary

How much higher the exploitability is than at the best point, for each way to stop.

BR min: where Best Response is lowest, the best point. The other columns show how much higher the exploitability is than there, for each way to stop.
1B: stop at 1 billion iterations.
LBR min: stop at the checkpoint where LBR is lowest.
LBR min ×3: stop one checkpoint later, at three times as many iterations.
LBR min ×10: stop two checkpoints later, at ten times as many iterations. This is our rule.

LBR is used with the default settings everywhere: turn and river for a preflop or turn spot, all streets for an Omaha flop. For Hold'em without limps, all streets. One checkpoint after the lowest LBR works better in Hold'em and Short Deck, two work better in PLO4. We chose two for every game. Over the four curves that rise, that is +3% on average and +8% at worst, against +5.5% and +16% for one checkpoint. Stopping late costs less than stopping early.

How to find the best point yourself

Omni does not stop a solve on its own yet. Best Response and LBR are expensive, so they cannot run after every iteration. But you can find the best point by hand.

1. Solve with stops. Use checkpoints three times apart: 1M, 3M, 10M, 30M, 100M iterations and so on. At each checkpoint stop the solve and save the solution under its own name.
2. If Best Response is available, compute it in the Exploitability (ε) window. It works for two players. On a flop or turn with real ranges it usually takes from tens of seconds to a few minutes. When Best Response has gone up twice in a row, the best point is behind you. Take the saved solution with the lowest Best Response.
3. If Best Response is too slow (Omaha preflop, wide ranges), compute LBR with the default settings at every checkpoint. When LBR is higher than at the previous checkpoint, solve one more checkpoint and stop there. For example: LBR is lowest at 10M, higher at 30M, so solve to 100M and take that solution. The final count is ten times the iterations where LBR was lowest. On our four curves that rise, exploitability at this point was 0 to 8% above the best, about 3% on average. If you stop right at the lowest LBR, it is about 30% on average.

Things to keep in mind about LBR:

• The lowest LBR comes before the lowest Best Response: one checkpoint earlier in Hold'em and Short Deck (three times fewer iterations), two earlier in PLO4 (ten times fewer). So when LBR starts to rise, the best point may still be ahead. That is why the rule waits one more checkpoint. In PLO5 and PLO6 the gap may be even bigger, we did not measure it. But in Omaha the strategy gets worse slowly after the best point, so solving a bit longer costs little.
• LBR is computed on a random sample of hands, so it is noisy. A difference smaller than the ± shown means nothing. More hands in the settings means less noise.
• If your tree has no preflop call (for example a tree without limps), use LBR on all streets for the rule. The other types go far below zero there and stop the solve too early.
• LBR near zero or below does not mean the solution is done. On PLO4 preflop LBR was near zero while the solution could still be exploited for 1.5 big blinds per hand.

If you do not want to measure anything,here is a rough guide from our spots. Hold'em and Short Deck preflop: about 10M iterations. PLO4 preflop and flop: about 100M. The bigger the tree and the more groups in the abstraction, the later the best point. On a PLO5 turn there was no rise before 10B iterations, and after 300M Best Response barely changed. We did not measure PLO5 from the flop or preflop, or PLO6. There the best point is probably later than in PLO4.

What we do not know yet

• Everything was measured for two players. For three or more players an exact Best Response does not exist, and we do not know where the best point is.
• Each curve is one run, with checkpoints three times apart. So the best point is known only to within a factor of three.
• The iteration guides belong to these spots and to the Balanced abstraction.
• We did not measure PLO5 from the flop or preflop, PLO6, or PLO4 preflop on the full deck. For PLO5 we have only the turn.
• Best Response is computed inside the same betting tree. An opponent with other bet sizes could win more.

Further reading

• Michael Johanson, Kevin Waugh, Michael Bowling, Martin Zinkevich. Accelerating Best Response Calculation in Large Extensive Games.IJCAI 2011. The "Overfitting" section and Figure 6: the same effect in Limit Hold'em, for abstractions with perfect and imperfect recall.
• Michael Johanson, Nolan Bard, Neil Burch, Michael Bowling. Finding Optimal Abstract Strategies in Extensive-Form Games. AAAI 2012. The CFR-BR method and the size of overfitting in Limit Hold'em: +10% and +20%.
• Viliam Lisý, Michael Bowling. Equilibrium Approximation Quality of Current No-Limit Poker Bots. 2017, arXiv:1612.07547. The LBR method.
• Kevin Waugh, David Schnizlein, Michael Bowling, Duane Szafron. Abstraction Pathologies in Extensive Games. AAMAS 2009. A similar name, but a different effect: a finer abstraction can sometimes give a worse strategy. There the size of the abstraction changes, not the number of iterations. It is not the same as overfitting.

The Getting started guide shows how to install the engine and run your first solve.