After each hand, Cepheus calculated a measure of regret, exploiting the benefit of hindsight to determine how much it had strayed from the optimal strategy. The team developed an algorithm called Cepheus that gradually approached perfection by playing against itself. The game has more than 300 trillion different situations in which a player must call the bet, raise the bet or fold. Two players receive two cards each and then can bet a fixed amount a certain number of times as five community, or shared, cards are revealed.

“Most algorithms can’t cope with that kind of uncertainty,” Bowling says.īowling and his colleagues at Alberta’s 20-year-old Computer Poker Research Group chose to tackle heads-up limit Texas Hold’em because it is popular and relatively simple. But in poker, it’s wise to bluff every now and then, perhaps increasing the bet some fraction of the time with a weak hand to throw the opponent off. In checkers, the best move in a given situation is the same for every game. Another wrinkle is that successful poker players are unpredictable. That luxury is not afforded to a computer poker player because it doesn’t know what cards an adversary holds. It was an impressive achievement, yet the algorithm had a relatively straightforward task: For each turn, it would review the positions of all the pieces, evaluate its options and then choose the best one. In 2007, Alberta computer scientist Jonathan Schaeffer and colleagues solved the game of checkers by simulating the actions of players making the perfect move every turn ( SN: 7/21/07, p. Game theory is the branch of mathematics that computes optimum strategies in competitive encounters. Just as poker players must act without knowing the cards their opponent is holding, researchers want algorithms that can make effective decisions based on robust but incomplete sets of data.įor decades, scientists have tried to create algorithms that win human games by blending the calculating prowess of computers with the decision-making strategies of game theory.

The algorithm, developed by computer scientist Michael Bowling and his team at the University of Alberta in Edmonton, is the first to tackle a commonly played imperfect-information game, in which participants do not have full knowledge of past events.

Limit texas hold em solved