Contents
Carnegie Mellon University’s LibratusIn card abstraction, similar poker hands are bucketed to- gether and treated identically. Libratus does not use any card abstraction on the first (preflop) and second (flop) betting rounds. The last two betting rounds, which are exponentially larger, are more coarsely abstracted. Brown and Sandholm built a poker-playing AI called Libratus that decisively beat four leading human professionals in the two-player variant of poker called heads-up no-limit Texas hold'em (HUNL). Poker playing robots – more realistically, poker programs that utilize artificial intelligence, or AI, to make their decision – have been under development for the last 20 or so years.
, an artificial intelligence computer program designed to play poker, started the year by proving it could beat four human poker pros. Now, a pair of university researchers behind the program are ending the year by telling the world exactly how the AI program managed to do it.Libratus beat pros Jason Les, Dong Kim, Daniel McCauley and Jimmy Chou in a 20-day competition held in January at Rivers Casino in Pittsburgh, Pennsylvania. In fact, it beat each of the players at heads-up no-limit hold’em. Over 120,000 total hands, Libratus managed to end the sessions up more than $1.8 million in chips.
This week, Carnegie Mellon’s professor of computer science Tuomas Sandholm and Ph.D. student Noam Brown published an article in the research journal Science,detailing how it managed to do all that.
According to the article, Libratus was programmed to use a three-pronged approach to the game of poker. Plus, it included more decision points than there are atoms in the universe.
Libratus adjusted on the fly
Poker involves bluffing. So, the researchers said the program was designed to recognize and understand the tactic. It really went deeper than just taking a simple black and white approach to the game.
Sandholm and Brown claim Libratus was able to break poker down into computationally manageable parts. That way it could fix weaknesses in its strategy based on its opponents’ play. Essentially, Libratus did what every good poker player has done for decades: It adjusted to the strategies employed by its opponents on the fly.
Libratus’ three-pronged approach to the game included:
- Creating an abstract version of the game which was easier to solve
- Creating a more detailed plan-of-action based on how the game was playing out
- Improving on that plan in real time by detecting mistakes in its opponent’s strategy and exploiting them
Poker Bratislava
Simply put, Libratus began with a basic strategy designed by looking at a simplified version of the game. That strategy became more complex as it learned how its opponents were playing. Finally, it adjusted the strategy even further to exploit weakness shown by its opponents.
If an opponent were to switch to a different strategy, Libratus also avoided opening itself up to exploitation by detecting potential holes in its own game.
Should bet sizing change, Libratus would add the missing decision branches and compute strategies for them. Then it would add those strategies to its plan going forward.
Libratus demoralizes opponents
After losing in January, Les described playing Libratus as a slightly demoralizing experience:
“Libratus turned out to be way better than we imagined. It’s slightly demoralizing. If you play a human and lose, you can stop, take a break. Here we have to show up to take a beating every day for 11 hours a day. It’s a real different emotional experience when you’re not used to losing that often.”
There may even be further reaching implications of Libratus’ success. Several bot rings employing AI have been discovered on online poker sites, including PokerStars. The success of Libratus could lead to an increase in the prevalence of bots online. However, this specific technology has yet to be tested in full-ring games.
The future of AI
In the end, they built an artificial intelligence computer program that can beat the pros at poker. However, Sandholm and Brown say they are hoping the AI can ultimately do a lot more:
“The techniques that we developed are largely domain independent and can thus be applied to other strategic imperfect-information interactions, including non-recreational applications. Due to the ubiquity of hidden information in real-world strategic interactions, we believe the paradigm introduced in Libratus will be critical to the future growth and widespread application of AI.”
The technology behind Libratus has now been licensed to Sandholm’s company Strategic Machine. The company aims to apply strategic reasoning technologies to many different applications.
The blueprints for Libratus – the poker AI bot that crushed professional players in a Texas hold ’em tournament earlier this year – were published on Monday in a research paper.
The software's victory over humans sparked a lot of headlines as it demonstrated a computer mastering an imperfect information game. Unlike chess or Go where players can see all the board pieces at all times, poker players have to come up with a strategy based more on probabilities since they do not know their opponent’s cards.
Libratus emerged as the clear victor after playing more than 120,000 hands in a heads-up no-limit Texas hold ’em poker tournament back in February. The machine crushed its meatbag opponents by 14.7 big blinds per game, drawing in $1,776,250 in prize money.
Now, a paper published in Science reveals how Libratus was programmed. The approach taken by its creators Noam Brown, a PhD student, and Tuomas Sandholm, a professor of computer science, both at Carnegie Mellon University in the US, employed three algorithms.
“Our game-theoretic approach features application independent techniques: an algorithm for computing a blueprint for the overall strategy, an algorithm that fleshes out the details of the strategy for subgames that are reached during play, and a self-improver algorithm that fixes potential weaknesses that opponents have identified in the blueprint strategy,” the pair's paper stated.
The first algorithm was briefly discussed after the competition as “counterfactual regret minimization.” It modeled a simpler version of poker – heads-up pot-limit Texas hold 'em – using a precomputed decision tree containing about 1013 nodes – much smaller than the 10161 nodes needed to cover all possible unique decisions in a no-limit game – and gradually learned to pick the best moves from the tree by playing simulated match after simulated match.
Flushed away
Similar hands were grouped together, Brown explained this week: 'Intuitively, there is little difference between a King-high flush and a Queen-high flush. Treating those hands as identical reduces the complexity of the game and thus makes it computationally easier.” Also, betting, say, $100 or $101 is basically the same, so again, the betting decisions could be simplified.
Libratus Poker Strategy
So, essentially, Libratus started off with a fairly simple weighted decision tree from which to select its moves depending on its hole cards and those on the board.
Next, to elevate the software to superhuman level, it would whip out a more advanced strategy in the latter betting rounds during a hand. Once play had reached that point, a more detailed, fine-grained abstraction model of Texas hold 'em would be produced in real time to best win the hand. This algorithm was dubbed 'nested subgame solving.'
Dong Kim, one of Libratus’ opponents, previously said the competition was “extremely tough as the AI keeps getting better.” This is where the third algorithm came in: Libratus wasn't just trained offline once and used inference to make decisions in real-time during hands – it had a “self-improver” module to refine its decision-making processes.
It used machine learning to fill in missing branches of the overall 'blueprint' decision model based on its opponents' moves. “In principle, one could conduct all such computations in advance, but the game tree is way too large for that to be feasible,” the paper stated.
By watching how its human rivals played, Libratus fleshed out the relatively simple 'blueprint' decision tree with extra nodes to help it win hands against those opponents. It would analyze the frequency of its opponents' bet sizes, and update itself overnight, improving throughout the competition.
Felted! AI poker bot Libratus cleans out pros in grueling tournament, smugly trousers $1.8m
READ MORELibratus is computationally expensive, and was powered by the Bridges system, a high-performance computer at the Pittsburgh Supercomputer Center. It could achieve, at maximum, 1.35 PFLOPS – or more than a quadrillion floating-point math calculations per second. Libratus burned through approximately 19 million core hours of computing throughout the tournament.
'The techniques that we developed are largely domain independent and can thus be applied to other strategic imperfect-information interactions, including non-recreational applications,' the paper concluded.
Libratus Poker Hand History
This is a high-level overview of the system, of course, and the paper goes into some more detail. The code, however, will not be released publicly as the technology behind Libratus has been exclusively licensed to Strategic Machine, a startup founded by Sandholm in March this year.
At the Neural Processing Information Systems conference (NIPS) this year, during a demonstration of Libratus, Sandholm told The Register that the AI could be used for calculating strategic decisions in the real world, such as in finance and information security.
Sandholm said it could be deployed to help organizations thwart hackers exploiting zero-day vulnerabilities, where bugs in software are unknown to the folks trying to defend against such attacks. Meanwhile, Noam and Sandholm's research on nested subgame solving [PDF] won best paper at NIPS 2017. ®