Poker-bots Hit a New Milestone in AI

Two separate artificial intelligence (AI) programs recently surpassed humans in a game that was once considered too difficult for artificial intelligence to master. Each one of these events represents a significant milestone in AI by beating professional poker players at Heads-up (two player only) No-Limit Texas Hold'em, one of the more complex variants of poker.

The first reported computer program to outplay human professionals in Heads-up no-limit Texas Hold'em poker came in December 2016, when an AI system called DeepStack played a total of 44,852 hands against 33 professional players. Developed by a team of computer scientists from the University of Alberta along with research collaborators from Charles University in Prague and Czech Technical University, DeepStack beat each of the 11 players who finished their match, 10 of them by statistically significant margins. The team recently published their study in the March issue of Science.

One month after DeepStack’s publicized victory over human poker players, Carnegie Mellon University’s poker-bot ‘Libratus’ also achieved the feat. In January, Libratus challenged four human poker experts with more than four decades worth of combined experience in a grueling 20-day poker tournament called “Brains vs. Artificial Intelligence: Upping the Ante” held in Pittsburgh. After playing 120,000 hands of heads-up, no-limit Texas Hold’em, Libratus defeated a team of the world’s top-ranked human poker players by 1,776,250 chips. This was a huge accomplishment-- researchers can now say that the victory margin was large enough (at least 99.98 percent was not due to chance) to be considered a statistically significant win.

Poker: An Incomplete Information Game

Computers have already mastered games like checkers, chess, and Go. Games have long served as tools for measuring the capabilities of AI systems and benchmarking breakthroughs in AI. Last year, Google's AlphaGo famously defeated a legendary champion in the game of Go, a game that has been described as the “Mount Everest of board games.” It was a feat reminiscent of the controversial victory by IBM’s Deep Blue over world chess champion Garry Kasparov.

Checkers, chess, and Go are described as complete information games. Both players are able to observe the full state of the game at any time. While players might keep their strategies secret, what opportunities they have available are commonly known. Texas Hold'em Poker, on the other hand, is an incomplete information game. Each player has private information which the other players do not know. Players, therefore, must reason about their opponents probabilistically.

Playing the Hand

In Heads-Up Texas Hold'em, two players are randomly dealt two face down cards, referred to as the “hole cards.” The hand begins with a betting round called the “pre-flop,” in which players have the options to check, call, raise or fold. Once all the betting in the pre-flop has finished, three community cards called “the flop” are dealt face up in the middle of the table. After the flop, there is a second betting round, and then a single community called “the turn” is dealt, followed by a third betting round. A single final shared card called “the river” is then dealt, followed by the fourth round of betting. All five cards are visible to every player. Due to the random nature of the game and two initial concealed cards, the players’ bets during each of betting round are predicated on guessing what their opponents might do, using intuition.

Once the five cards are laid out, if a player places a bet that forces all other players fold, the remaining player wins the pot. But if two or more players remain after the final betting round, the players enter into the showdown. At this point, each player must make the best poker hand using any combination of their two hole-cards and five community cards. Poker hands must have five cards, and the best poker hand wins the pot.

Given the structure of poker, it is possible for an AI program to calculate the odds and play accordingly, but the approach to betting is less straightforward. For example, if the AI had a pattern of betting high every time it had a good hand, a human player could quickly figure this out and strategize accordingly. For this reason, designing an AI player not only requires the ability to bluff but also correctly interpret ambiguous information to win.

Variations in Hold’em

It’s also important to note that the no-limit Hold’em poker variation is considerably more complex than limit Hold’em.

In limit Hold’em, bets are structured with betting amounts capped to a fixed sum. Understanding the mathematical principles guiding the game is most important, and being able to calculate the implied odds can help determine an appropriate play. An earlier AI poker-bot developed by the University of Alberta researchers, called Cepheus ), solved Heads Up limit Hold’em using ‘brute force’. According to Cepheus’ developers, there is a “perfect play” that can be determined by running through a massive table of all possible permutations in limit poker.

On the other hand, in no-limit Hold'em, the minimum bet is equal to the big blind, and players can always bet much more as they want. A player can create situations that could isolate players by raising 4x or 5x the big blind, forcing most players to fold most hands. This pre-flop betting/isolation strategy gives a player a better 'read,' but there are no set moves for each situation. A game between two players in Heads-Up no-limit poker produces 10,160 possible game scenarios (which is on par with the 10,170 possible moves in Go), compared to 1,014 possible situations in limit poker. This takes some degree of brute force to build as close to an optimal strategy as possible.

No-Limit Poker Bot Strategies

In an incomplete information game like no-limit poker, one way to find the best strategy is to find a Nash equilibrium for the game, which is exactly what the two AI programs, Libratus and DeepStack, attempt to do. A Nash equilibrium is a pair of strategies for playing the game where neither player can improve their reward by changing their strategy as long as the other player’s strategy remains the same. When playing such a pair of strategies, neither player has any incentive to change strategies. To compute the Nash equilibria of the game, both Libratus and DeepStack use an algorithm called counterfactual regret minimization (CFR).

DeepStack's intuition

To determine the best play, DeepStack draws on a set of possible moves by calculating the likelihood of the type of scenario it could encounter-- something its developers like to compare to intuition. DeepStack’s researchers train the AI’s intuition using two neural networks: one learns to estimate the counterfactual values after ‘the flop’ cards are dealt, and the second neural network recalculates the values after ‘the turn’ card is dealt. Using the CFR algorithm, DeepStack comes up with the best possible play in a given situation by comparing different possible outcomes using game theory. By itself, CFR would still run into the same problem of trying to calculate all possible possible plays. DeepStack gets around this by only having the CFR algorithm solve for a few moves ahead instead of all possible moves until the end of the game. This simplifies the number of situations and effectively prunes the decision tree it has to compute, thereby making it easier to approximate the Nash equilibrium. Researchers at the University of Alberta and two Czech universities wrote in Science, “DeepStack computes this strategy during play and only for the states of the public tree that actually arise during play.” This means that DeepStack doesn’t have an overarching strategy decided before the game and doesn’t need to keep tabs on all possible abstract situations; therefore, it can computer the decision in seconds. In this case, the DeepStack team trained their AI on the best solutions of the CFR algorithm for random poker situations. That allowed DeepStack’s intuition to become a “fast approximate estimate” of its best solution for the rest of the game without having to actually calculate all the possible moves.

How did Libratus win?

Unlike DeepStack, Libratus does not use neural networks and plays with end-game solving, which requires a supercomputer to run 15 million core hours. CMU researchers also claim that Libratus uses faster method to find a Nash equilibria and develops better endgame-solving approach, which are powered by the Pittsburgh Supercomputing Center's Bridges supercomputer. Although the exact details behind Libratus’s mechanism will remain vague until researchers from Carnegie Mellon University publish their work in a paper, Libratus generally relies on three different systems that work together. The first system uses a trial-and-error process known as reinforcement learning, which is what Google’s DeepMind lab used in building AlphaGo. However, there’s a key difference between the two AI programs: instead of learning from the play of human experts, like AlphaGo did, Libratus learned from scratch by playing trillions of simulated hands against itself. Using a special variant of Counterfactual Regret Minimization, Libratus was able to learn from its own experiences and play strategies at a complexity in ways humans could not match—playing a much wider range of bets and randomizing and mixing these bets with different bluff ranges and play styles. A second system, called an end-game solver, allows Libratus to learn from games as it was actually playing. With the help of this second system – detailed in their paper published in March 2017 - the first system doesn’t have to run through all the possible scenarios. These two systems together would have been sufficient, but a third system was put in place to prevent the other players from finding patterns in Libratus’ play and exploit them. This third system would run an algorithm overnight to identify patterns and remove them so that Libratus would be pattern-free for play the next day.

So which one is better? It’s hard to compare the abilities of Libratus with DeepStack without them playing against each other. Both poker bots can only play against one other player. Both AIs also played just enough hands to have statistically significant wins. Perhaps the next challenge for both Libratus and DeepStack to tackle would be to play against multiple players all at once.

Conclusion

Poker involves unique challenges not present in complete information games, and these two poker-bots mark a huge milestone in AI. Game-playing AIs that can understand incomplete information scenarios have important real-life implications. One of the next challenges for AIs is to learn how mimic complex human decision-making to tackle real-world issues with incomplete information.