We often approach life as if it were a chess match, assuming every piece is visible. But that's seldom true. As Tuomas Sandholm of Carnegie Mellon University's School of Computer Science sees it, life is more like a hand of poker. Other players have cards we can't see, and they often try to trick us. Could our decisions be better if we leveraged artificial intelligence (AI)?
That's the question Sandholm and graduate students Noam Brown and Sam Ganzfried set out to answer. Using the Blacklight system at the Pittsburgh Supercomputing Center (PSC), they built Claudico, an AI poker player.
"We really didn't write a program called 'Claudico,'" Sandholm is quick to point out. "Claudico emerged from general-purpose algorithms we developed for solving incomplete information games."
The algorithms approximate game-theory-optimal play, subject to computational limitations. Heads-up, no-limit Texas Hold'em poker contains 10161 situations that a player might face. That outnumbers the atoms in the universe, and transcends any foreseeable computing capability.
"The first step is creating an abstraction," Sandholm explains. "The algorithm takes the rules of the game and outputs a smaller game that's strategically similar."
The algorithm abstracts by conflating similar hands - for example, possibly equating two Jacks with two Queens. But as the game progresses, this 'rounding off' error amplifies. To avoid this pitfall, CMU researchers used an allocation on Blacklight, a supercomputer in theUS National Science Foundation's XSEDE network. Blacklight's large cache-coherent memory allowed a much finer-grained abstraction than otherwise possible - in computing the strategy for Claudico, the researchers used an enormous 8 Terabytes of RAM.
Claudico outstrips the team's earlier AI, Tartanian7, which dominated the 2014 Annual Computer Poker Competition. But could Claudico surpass humanity's best, like when Deep Blue bested Kasparov in 1996 or Watson dominated Jeopardy! in 2011?
Playing a Martian
Claudico took on four of the world's 10 best poker players at the Rivers Casino in Pittsburgh, Pennsylvania, US from April 24 through May 8, 2015. Statistically, the contest was a tie, but in the end Claudico lost to human opponents. Wagers totaled $170 million virtual dollars, and Claudico wound up $732,713 behind.
"Claudico was a very strong opponent," said Doug Polk, the number one ranked poker player in the world. "It's extremely aggressive."
Polk noted that Claudico would risk tens of thousands of dollars to win hundreds. Human players often hesitate to take such risks, and pros succeed by being willing to lose in the short term for a strategy that will pay off in the long run. "Claudico just takes that to the next level," he says.
"Playing Claudico is like playing a Martian," Sandholm says. In particular, it likes to 'pass' on the first move - meeting the other player's bid without raising it or folding. Pros denigrate that as a rookie move, calling it 'limping.' But Claudico (from the Latin for 'I limp.') owns that strategy.
More than just a poker player
Despite losing against top human poker players, Claudico holds tremendous promise for enhancing our knowledge in other incomplete information domains.
For instance, in the uncertain world of threat assessment, deciding how to allocate physical and cyber security resources might be done more efficiently if AI could weigh the odds of a threat at a given place and time.
The medical field offers perhaps the most exciting possibilities. "Most medical treatment today is myopic," Sandholm explains. "We throw one treatment at a problem at a time. AI might help doctors design multi-step treatment plans with better outcomes."
A series of pharmaceutical 'nudges' might steer treatment of an HIV infection in which mutant viruses within a patient have different virulence and vulnerability. Similarly, therapies could steer cancer-cells toward less malignancy, or colonies of bacteria away from antibiotic resistance.
"That's a big vision and I'm very excited about it," Sandholm says.
--Ken Chiacchia, senior science writer at the Pittsburgh Supercomputing Center