Cepheus: 2 player limit Texas hold 'em has been solved

Two-player limit Texas hold’em poker has finally been solved, according to a study published in Science yesterday. Scientists have designed a computer program, named Cepheus, with a strategy for the game that is so close to perfect that statistical analysis shows it can’t be defeated by a human poker player, even if that player competed against the computer for an entire lifetime.

If two Cepheus machines play, the winner will be whoever ends up getting the best cards, over the time period the two play.

Mathematicians Michael Bowling and Neil Burch at the University of Alberta picked Heads-Up Limit Hold’Em (HULHE) because, in poker terms, it is about as simple as it gets. Only two can play, and betting is heavily restricted. This means only 1.38x1013 (13.8 trillion) different circumstances can arise within it. Still, that is quite a large number, so previous attempts at solving even this form of poker have involved some simplification. But such simplification means losing important details, and the resulting strategies are an imperfect fit to the real game. By speeding up the algorithms, Dr Bowling’s team managed to bring the full game within reach of computational brute force, in the form of 200 computers, each sporting 24 processors, working in parallel for more than two months.

Previously, Burch has cracked checkers.

Call me ignorant, but I can¡¦t imagine how a game with imperfect information could be solved.

The problem is not the number of combinations involved, but rather, how do you know if the other player is bluffing you?

If there is a fixed optimal strategy then you are predictable and exploitable.

If the strategy involves random variables then it is less than optimal and the game cannot be considered solved.

The worst the strategy wiill do in "Fixed-Limit TH" is break-even, unless the opponent makes a mistake.

Is the "optimum strategy" solved? Against humans, it would appear so.

TH-NL has not been solved AFAIK.

Quote: 98Clubs

The worst the strategy wiill do in "Fixed-Limit TH" is break-even, unless the opponent makes a mistake.

Is the "optimum strategy" solved? Against humans, it would appear so.

The article says that its expected value is a win, but it won't win or tie 100% of the time. I do not consider this a "solve" in the way that checkers or 4x4x4 tic-tac-toe have been solved. (A "solve" is a strategy where one player will win or tie in every game played.)

Wizard already solved 1-card heads-up limit poker with his game one card poker.

Quote: sodawater

Wizard already solved 1-card heads-up limit poker with his game one card poker.

Yeah, I was wondering about that, too.

Quote: andysif

Call me ignorant, but I can¡¦t imagine how a game with imperfect information could be solved.

The problem is not the number of combinations involved, but rather, how do you know if the other player is bluffing you?

If there is a fixed optimal strategy then you are predictable and exploitable.

If the strategy involves random variables then it is less than optimal and the game cannot be considered solved.

GTO. Predictable and exploitable are two different things. You don't need to know if you're opponent is bluffing, you just need to use GTO and in a rake free environment you can't lose long term.

Actually using GTO in real life is essentially impossible, and it would be better to exploit your opponents in real poker than to protect yourself from being exploited... but that's not the point of this bot - it's more of a math exercise for those who made it.

Quote: ThatDonGuy

The article says that its expected value is a win, but it won't win or tie 100% of the time. I do not consider this a "solve" in the way that checkers or 4x4x4 tic-tac-toe have been solved. (A "solve" is a strategy where one player will win or tie in every game played.)

You can't solve random. The game knows what to do for all possible combinations of cards in terms of what is mathematically the best strategy. You can still catch bad cards, the question is whether or not it will inevitably win in the long run, regardless of opponent, and they claim the answer is, 'Yes.'

There's nothing random about checkers, the pieces always start in the same place and there is a limited number of moves that can be performed, in any scenario. This is the same with the other games.

I'd say it is solved if it is guaranteed to win in the long run, regardless of the opponent. If you get dealt 7-2 and your opponent is dealt K-K and raises, you don't even know what the opponent has, you fold 7-2. There's no winning that hand. You lose, but you've doubtlessly made the best possible play. It's not going to win every hand because of the randomness. The checkers game will win every game because nothing is random...unless the opponent also plays a strategically perfect game.

Mission, heads-up limit holdem is now considered solved because for every possible game state, the computer knows the optimal move. That means that it will be guaranteed to win (in the long run) against anyone not also playing a perfect strategy.

Just because a game has imperfect information doesn't mean it is not solved.

Quote: sodawater

Mission, heads-up limit holdem is now considered solved because for every possible game state, the computer knows the optimal move. That means that it will be guaranteed to win (in the long run) against anyone not also playing a perfect strategy.

Just because a game has imperfect information doesn't mean it is not solved.

I agree with that, that was the point I was trying to make.