Information Processing

See earlier post Hail Libratus!

AI already dominates humans in any narrowly defined task. Perhaps another 30-50 years until AGI?

IEEE Spectrum: Humanity has finally folded under the relentless pressure of an artificial intelligence named Libratus in a historic poker tournament loss. ...

Libratus lived up to its “balanced but forceful” Latin name by becoming the first AI to beat professional poker players at heads-up, no-limit Texas Hold'em. The tournament was held at the Rivers Casino in Pittsburgh from 11–30 January. Developed by Carnegie Mellon University, the AI won the “Brains vs. Artificial Intelligence” tournament against four poker pros by US $1,766,250 in chips over 120,000 hands (games). Researchers can now say that the victory margin was large enough to count as a statistically significant win, meaning that they could be at least 99.98 percent sure that the AI victory was not due to chance.

... the victory demonstrates how AI has likely surpassed the best humans at doing strategic reasoning in “imperfect information” games such as poker. The no-limit Texas Hold’em version of poker is a good example of an imperfect information game because players must deal with the uncertainty of two hidden cards and unrestricted bet sizes. An AI that performs well at no-limit Texas Hold’em could also potentially tackle real-world problems with similar levels of uncertainty.

“The algorithms we used are not poker specific,” Sandholm explains. “They take as input the rules of the game and output strategy.”

... Libratus played the same overall strategy against all the players based on three main components:

First, the AI’s algorithms computed a strategy before the tournament by running for 15 million processor-core hours on a new supercomputer called Bridges.

Second, the AI would perform “end-game solving” during each hand to precisely calculate how much it could afford to risk in the third and fourth betting rounds (the “turn” and “river” rounds in poker parlance). Sandholm credits the end-game solver algorithms as contributing the most to the AI victory. The poker pros noticed Libratus taking longer to compute during these rounds and realized that the AI was especially dangerous in the final rounds, but their “bet big early” counter strategy was ineffective.

Third, Libratus ran background computations during each night of the tournament so that it could fix holes in its overall strategy. That meant Libratus was steadily improving its overall level of play and minimizing the ways that its human opponents could exploit its mistakes. It even prioritized fixes based on whether or not its human opponents had noticed and exploited those holes. By comparison, the human poker pros were able to consistently exploit strategic holes in the 2015 tournament against the predecessor AI called Claudico.

... The Libratus victory translates into an astounding winning rate of 14.7 big blinds per 100 hands in poker parlance—and that’s a very impressive winning rate indeed considering the AI was playing four human poker pros. Prior to the start of the tournament, online betting sites had been giving odds of 4:1 with Libratus seen as the underdog.

Here's a recent paper on deep learning and poker. The program DeepStack is not Libratus (thanks to a commenter for pointing this out), but both have managed to outperform human players.

DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker

https://arxiv.org/abs/1701.01724

Artificial intelligence has seen a number of breakthroughs in recent years, with games often serving as significant milestones. A common feature of games with these successes is that they involve information symmetry among the players, where all players have identical information. This property of perfect information, though, is far more common in games than in real-world problems. Poker is the quintessential game of imperfect information, and it has been a longstanding challenge problem in artificial intelligence. In this paper we introduce DeepStack, a new algorithm for imperfect information settings such as poker. It combines recursive reasoning to handle information asymmetry, decomposition to focus computation on the relevant decision, and a form of intuition about arbitrary poker situations that is automatically learned from self-play games using deep learning. In a study involving dozens of participants and 44,000 hands of poker, DeepStack becomes the first computer program to beat professional poker players in heads-up no-limit Texas hold'em. Furthermore, we show this approach dramatically reduces worst-case exploitability compared to the abstraction paradigm that has been favored for over a decade.

Video game training allows younger players to take on a dozen tables at a time in online poker? This seems harder than a simul in chess, where a master can "chunk" the position on the board quickly. If there are many players at each of those dozen tables the poker genius has to keep track of perhaps 30 or 50 hands at a time, and the psychological profile of each of those players. The guy in the article seems to be doing this with the help of software. How long until it's all bots, all the time?

NYTimes: ... Within 18 months, Cates went from routinely losing at local $5 games to winning at the highest stakes of online poker for anywhere between $10,000 and $500,000 per night. In 2010, his reported $5.5 million in online earnings was more than $1 million higher than the nearest competitor. Unlike other young poker millionaires who make the bulk of their money by winning televised tournaments — a proposition that, because of the high number of players and the unpredictability of their actions, involves roughly the same amount of luck as winning a small lottery — Cates earned his stake by grinding, the term used to describe the process of pressing a skill advantage over an extended period of time. Because poker is a game of high variance, where a significant difference in ability can be mitigated by a bad run of cards, a player’s Expected Value (E.V.) must be actualized over thousands of hands. Every year, a few dozen kids go on hot streaks and take a shot at the big time. Almost invariably, these kids are eventually ground down by higher caliber players. What made Cates’s run different wasn’t his total winnings or the speed with which he earned his millions. What caught the attention of the poker world was that the 20-year-old top online earner of 2010 won almost all of his money in head-to-head confrontations with poker’s elite.

The gospel of E.V. that keeps the poker hierarchy in order was shaken. Cates had taken on all comers in 2010, including highly publicized matches against top-flight pros like Phil Ivey, Patrik Antonius, Ilari (Ziigmund) Sahamies and his fellow young gun Tom (durrrr) Dwan. Each of these men has helped turn poker into a multimillion-dollar celebrity enterprise. Each ranks among the 20 or so most recognized players in the world. And in each of his matches with poker royalty, Cates came out hundreds of thousands of dollars ahead.

... The vast sums of money shuttled among the accounts of these young professionals — and the shocking aggressiveness and recklessness with which they played — deepened the divide between the young online players and the older guard who earned their millions when poker was still a game played by men sitting around a table. Since the rise of online poker in the early 2000s, every principle of the game, every lesson learned over hundreds of thousands of hours of play, every simple credo uttered in some old Western gambling movie — all those tersely stated, manly things that made up the legend of poker — has been picked apart and, for the most part, discarded.

Patience is no longer rewarded. If an 18-year-old online whiz can play 12 hands at once, then by his 19th birthday, he is no less experienced than a career gambler who has sat for a dozen years at the big-money table at the Bellagio. It didn’t take long before the young players began crushing established gamblers online, and the question rang out across the poker world: How were these kids, many of whom were too young to set foot inside a casino, outsharking the sharks?

In Command and Conquer, the video game that consumed much of Cates’s childhood, a player leads an army into a real-time battle. The combat units are vaguely futuristic and highly specialized. Success depends on the efficiency with which a player can build his resources and the speed with which he can deploy them. It is a difficult game to play and an even harder game to master. The best players develop a predatory instinct for detecting the exact moment when an opponent has weakened. High-end strategy combines lightning-fast reflexes, unabashed aggression and razor-thin resource management. Reckoning comes by way of particle cannon. By the age of 15, Cates told me repeatedly, he was one of the world’s best Command and Conquer players.

Phil Gordon, a 40-year-old poker professional who has won $3 million in tournaments, written three best-selling books and hosted several TV shows, including Bravo’s Celebrity Poker Showdown, says he believes that the early and immersive training offered by video games, paired with online poker’s increasing space in the mainstream, has laid out a practice ground for a militia of young, fearless, invincible players. “The prototypical successful young gun is fast and unpredictable,” Gordon says. “Those traits make them nearly impossible to beat, especially when playing at warp speeds. The manual dexterity required to play 12 or even 16 or 20 tables at one time is enormous. The mental dexterity required to play well while making that number of decisions in a very short amount of time is even more impressive. Many of the video games the kids grew up with like Command and Conquer or Call of Duty required a similar dexterity and gave these kids a leg up — the more tables they could play accurately, the more decisions they got to make, and the quicker they were able to learn.”

Then there’s the fact that high-stakes poker rewards aggression. A player who cannot fire off a bluff because he is worried about his daughter’s private-school tuition will be quickly run over by the players who don’t have such concerns. While heightened dexterity, comfort with snap decisions and the stamina gained from years spent sitting in front of a computer screen give the young online pro an edge over his older counterpart, the greatest benefit borne from a life spent playing video games lies somewhere in the strange, disconnected relationship between what is simulated and what is real. The armies of Command and Conquer do not suffer real casualties. An unsuccessful session of Minesweeper does not result in the loss of a leg.

In online poker, lost money registers only as debits in the player’s offshore account. When a player loses a million-dollar pot, the action plays out in cartoon animation.

“Most of us young kids who play at nosebleed stakes don’t really have any clear idea about the actual value of the money we win or lose,” Cates says. “Most of us see the money more as a points system. And because we’re all competitive, we want to have the highest score. But really, we don’t know what making $400,000 or losing $800,000 means, because we don’t have families or whatever. This blind spot gives us the freedom to always make the right move, regardless of the amount at stake, because our judgment isn’t clouded by any possible ramifications.”

It is unclear whether Cates actually does understand that the money is real. On the second day of my visit, we took a trip to Best Buy. Cates had grown bored of playing poker and wanted to buy a video game. As we stood in the PS3 aisle, discussing which games looked good, I asked him if he had ever walked into a store like Best Buy — or perhaps a car dealership — and thought to himself, Hey, I can buy out this entire place. Cates smiled sheepishly. He said: “I’m not really into material wealth. Plus, I need to save up some more money. My fiscal goal for 2011 is to reach $10 million in liquid cash.” I asked what the difference might be between $5 million and $10 million, especially for a 21-year-old whose relative spending habits sit somewhere on the line between modest and monastic. He explained: “You can do anything with $10 million. Like, you can buy a house and still have around $5 million left over.”

Hmm... do we need drug testing for neuroenhancers?

I wouldn't be surprised to find that there are individuals who naturally function in the kind of state induced by Adderall or Provigil. Think of those hyper-productive people who start companies, write lots of books and papers and still manage to have hobbies and a social life. If a little pill helps the average guy achieve that level of capability, why not?

Provigil (modafinil) is used by the militaries of several countries, for example by fighter and bomber pilots.

New Yorker: ...The BoredAt Web sites—which allow college students to chat idly while they’re ostensibly studying—are filled with messages about Adderall. Posts like these, from the BoredAtPenn site, are typical: “I have some Adderall—I’m sitting by room 101.10 in a grey shirt and headphones”; “I have Adderall for sale 20mg for $15”; “I took Adderall at 8 p.m., it’s 6:30 a.m. and I’ve barely blinked.” On the Columbia site, a poster with an e-mail address from CUNY complains that her friends take Adderall “like candy,” adding, “I don’t want to be at a disadvantage to everyone else. Is it really that dangerous? Will it fuck me up? My grades weren’t that great this year and I could do with a bump.” A Columbia student responds, “It’s probably not a good idea if you’re not prescribed,” but offers practical advice anyway: “Keep the dose normal and don’t grind them up or snort them.” Occasional dissents (“I think there should be random drug testing at every exam”) are drowned out by testimonials like this one, from the BoredAtHarvard site: “I don’t want to be a pusher or start people on something bad, but Adderall is AMAZING.”

...Zack, who has a book being published this summer, called “The Neuro Revolution,” said, “We live in an information society. What’s the next form of human society? The neuro-society.” In coming years, he said, scientists will understand the brain better, and we’ll have improved neuroenhancers that some people will use therapeutically, others because they are “on the borderline of needing them therapeutically,” and others purely “for competitive advantage.”

Zack explained that he didn’t really like the term “enhancement”: “We’re not talking about superhuman intelligence. No one’s saying we’re coming out with a pill that’s going to make you smarter than Einstein! . . . What we’re really talking about is enabling people.” He sketched a bell curve on the back of a napkin. “Almost every drug in development is something that will take someone who’s working at, like, forty per cent or fifty per cent, and take them up to eighty,” he said.

...Paul Phillips was unusual for a professional poker player. When he joined the circuit, in the late nineties, he was already a millionaire: a twenty-something tech guy who had started off writing software, helped found an Internet portal called go2net, and cashed in at the right moment. He was cerebral and, at times, brusque. His nickname was Dot Com. ...Most unusual of all, Phillips talked freely about taking prescription drugs—Adderall and, especially, Provigil—in order to play better cards.

He first took up the game in 1995, when he was in college, at U.C. San Diego. He recalled, “It was very mathematical, but you could also inject yourself into the game and manipulate the other guy with words”—more so than in a game like chess. Phillips soon felt that he had mastered the strategic aspects of poker. The key variable was execution. At tournaments, he needed to be able to stay focussed for fourteen hours at a stretch, often for several days, but he found it difficult to do so. In 2003, a doctor gave him a diagnosis of A.D.H.D., and he began taking Adderall. Within six months, he had won $1.6 million at poker events—far more than he’d won in the previous four years. Adderall not only helped him concentrate; it also helped him resist the impulse to keep playing losing hands out of boredom. In 2004, Phillips asked his doctor to give him a prescription for Provigil, which he added to his Adderall regimen. He took between two hundred and three hundred milligrams of Provigil a day, which, he felt, helped him settle into an even more serene and objective state of mindfulness; as he put it, he felt “less like a participant than an observer—and a very effective one.” Though Phillips sees neuroenhancers as essentially steroids for the brain, they haven’t yet been banned from poker competitions.

Last summer, I visited Phillips in the high-desert resort town of Bend, Oregon, where he lives with his wife, Kathleen, and their two daughters, Ivy and Ruby. Phillips, who is now thirty-six, seemed a bit out of place in Bend, where people spend a lot of time skiing and river rafting. Among the friendly, faithfully recycling locals, he was making an effort to curb his caustic side. Still, when I first sent Phillips an e-mail asking him to explain, more precisely, how Provigil affected him, he couldn’t resist a smart-ass answer: “More precisely: after a pill is consumed, tiny molecules are absorbed into the bloodstream, where they eventually cross the blood-brain barrier and influence the operation of the wetware up top.”

In person, he was more obliging. He picked me up at the Bend airport driving a black convertible BMW, and we went for coffee at a cheery café called Thump. Phillips wore shorts and flip-flops and his black T-shirt displayed an obscure programming joke. “Poker is about sitting in one place, watching your opponents for a long time, and making better observations about them than they make about you,” he said. With Provigil, he “could process all the information about what was going on at the table and do something about it.” Though there is no question that Phillips became much more successful at poker after taking neuroenhancers, I asked him if his improvement could be explained by a placebo effect, or by coincidence. He doubted it, but allowed that it could. Still, he said, “there’s a sort of clarity I get with Provigil. With Adderall, I’d characterize the effect as correction—correction of an underlying condition. Provigil feels like enhancement.” And, whereas Adderall made him “jittery,” Provigil’s effects were “completely limited to my brain.” He had “zero difficulty sleeping.”

...Drugs like Ritalin and Adderall work, in part, by elevating the amount of dopamine in the brain. Dopamine is something you want just enough of: too little, and you may not be as alert and motivated as you need to be; too much, and you may feel overstimulated. Neuroscientists have discovered that some people have a gene that leads the brain to break down dopamine faster, leaving less of it available; such people are generally a little worse at certain cognitive tasks. People with more available dopamine are generally somewhat better at the same tasks. It makes sense, then, that people with naturally low dopamine would benefit more from an artificial boost.

...Zack Lynch, of NeuroInsights, gave me a rationale for smart pills that I found particularly grim. “If you’re a fifty-five-year-old in Boston, you have to compete with a twenty-six-year-old from Mumbai now, and those kinds of pressures are only going to grow,” he began. Countries other than the U.S. might tend to be a little looser with their regulations, and offer approval of new cognitive enhancers first. “And if you’re a company that’s got forty-seven offices worldwide, and all of a sudden your Singapore office is using cognitive enablers, and you’re saying to Congress, ‘I’m moving all my financial operations to Singapore and Taiwan, because it’s legal to use those there,’ you bet that Congress is going to say, ‘Well, O.K.’ It will be a moot question then. It would be like saying, ‘No, you can’t use a cell phone. It might increase productivity!’ ”

...Paul McHugh, a psychiatrist at Johns Hopkins University, has written skeptically about cosmetic neurology. In a 2004 essay, he notes that at least once a year in his private practice he sees a young person—usually a boy—whose parents worry that his school performance could be better, and want a medication that will assure it. In most of these cases, “the truth is that the son does not have the superior I.Q. of his parents,” though the boy may have other qualities that surpass those of his parents—he may be “handsome, charming, athletic, graceful.” McHugh sees his job as trying to get the parents to “forget about adjusting him to their aims with medication or anything else.”

...Of course, the idea behind mind-hacking isn’t exactly new. Fortifying one’s mental stamina with drugs of various kinds has a long history. Sir Francis Bacon consumed everything from tobacco to saffron in the hope of goosing his brain. Balzac reputedly fuelled sixteen-hour bouts of writing with copious servings of coffee, which, he wrote, “chases away sleep, and gives us the capacity to engage a little longer in the exercise of our intellects.” Sartre dosed himself with speed in order to finish “Critique of Dialectical Reason.”

But only due to a bad decision by the human designers of the robot team! :-)

Earlier post here.

NYTimes: The human team reached a draw in the first round even though their total winnings were slightly less than that of the computer. The match rules specified that small differences were not considered significant because of statistical variation. On Monday night, the second round went heavily to Polaris, leaving the human players visibly demoralized.

“Polaris was beating me like a drum,” Mr. Eslami said after the round.

However, during the third round on Tuesday afternoon, the human team rebounded, when the Polaris team’s shift in strategy backfired. They used a version of the program that was supposed to add a level of adaptability and “learning.”

Unlike computer chess programs, which require immense amounts of computing power to determine every possible future move, the Polaris poker software is largely precomputed, running for weeks before the match to build a series of agents called “bots” that have differing personalities or styles of play, ranging from aggressive to passive.

The Alberta team modeled 10 different bots before the competition and then chose to run a single program in the first two rounds. In the third round, the researchers used a more sophisticated ensemble of programs in which a “coach” program monitored the performance of three bots and then moved them in and out of the lineup like football players.

Mr. Laak and Mr. Eslami won the final round handily, but not before Polaris won a $240 pot with a royal flush than beat Mr. Eslami’s three-of-a-kind. The two men said that Polaris had challenged them far more than their human opponents.

This blog has live updates from the competition. See also here for a video clip introduction. It appears the machine Polaris is ahead of the human team at the moment.

The history of AI tells us that capabilities initially regarded as sure signs of intelligence ("machines will never play chess like a human!") are discounted soon after machines master them. Personally I favor a strong version of the Turing test: interaction which takes place over a sufficiently long time that the tester can introduce new ideas and watch to see if learning occurs. Can you teach the machine quantum mechanics? At the end will it be able to solve some novel problems? Many humans would fail this Turing test :-)

Earlier post on bots invading online poker.

2007

World-Class Poker Professionals Phil Laak and Ali Eslami
versus
Computer Poker Champion Polaris (University of Alberta)

Can a computer program bluff? Yes -- probably better than any human. Bluff, trap, check-raise bluff, big lay-down -- name your poison. The patience of a monk or the fierce aggression of a tiger, changing gears in a single heartbeat. Polaris can make a pro's head spin.

Psychology? That's just a human weakness.

Odds and calculation? Computers can do a bit of that.

Intimidation factor and mental toughness? Who would you choose?

Does the computer really stand a chance? Yes, this one does. It learns, adapts, and exploits the weaknesses of any opponent. Win or lose, it will put up one hell of a fight.

Many of the top pros, like Chris "Jesus" Ferguson, Paul Phillips, Andy Bloch and others, already understand what the future holds. Now the rest of the poker world will find out.

It looks like we will soon add poker to the list of games (chess, checkers, backgammon) at which machines have surpassed humans. Note we're talking about heads up play here. I imagine machines are not as good at playing tournaments -- i.e., picking out and exploiting weak players at the table.

How long until computers can play a decent game of Go?

Associated Press: ...Computers have gotten a lot better at poker in recent years; they're good enough now to challenge top professionals like Laak, who won the World Poker Tour invitational in 2004.

But it's only a matter of time before the machines take a commanding lead in the war for poker supremacy. Just as they already have in backgammon, checkers and chess, computers are expected to surpass even the best human poker players within a decade. They can already beat virtually any amateur player.

"This match is extremely important, because it's the first time there's going to be a man-machine event where there's going to be a scientific component," said University of Alberta computing science professor Jonathan Schaeffer.

The Canadian university's games research group is considered the best of its kind in the world. After defeating an Alberta-designed program several years ago, Laak was so impressed that he estimated his edge at a mere 5 percent. He figures he would have lost if the researchers hadn't let him examine the programming code and practice against the machine ahead of time.

"This robot is going to do just fine," Laak predicted.

The Alberta researchers have endowed the $50,000 contest with an ingenious design, making this the first man-machine contest to eliminate the luck of the draw as much as possible.

Laak will play with a partner, fellow pro Ali Eslami. The two will be in separate rooms, and their games will be mirror images of one another, with Eslami getting the cards that the computer received in its hands against Laak, and vice versa.

That way, a lousy hand for one human player will result in a correspondingly strong hand for his partner in the other room. At the end of the tournament the chips of both humans will be added together and compared to the computer's.

The two-day contest, beginning Monday, takes place not at a casino, but at the annual conference of the Association for the Advancement of Artificial Intelligence in Vancouver, British Columbia. Researchers in the field have taken an increasing interest in poker over the past few years because one of the biggest problems they face is how to deal with uncertainty and incomplete information.

"You don't have perfect information about what state the game is in, and particularly what cards your opponent has in his hand," said Dana S. Nau, a professor of computer science at the University of Maryland in College Park. "That means when an opponent does something, you can't be sure why."

As a result, it is much harder for computer programmers to teach computers to play poker than other games. In chess, checkers and backgammon, every contest starts the same way, then evolves through an enormous, but finite, number of possible states according to a consistent set of rules. With enough computing power, a computer could simply build a tree with a branch representing every possible future move in the game, then choose the one that leads most directly to victory.

...The game-tree approach doesn't work in poker because in many situations there is no one best move. There isn't even a best strategy. A top-notch player adapts his play over time, exploiting his opponent's behavior. He bluffs against the timid and proceeds cautiously when players who only raise on the strongest hands are betting the limit. He learns how to vary his own strategy so others can't take advantage of him.

That kind of insight is very hard to program into a computer. You can't just give the machine some rules to follow, because any reasonably competent human player will quickly intuit what the computer is going to do in various situations.

"What makes poker interesting is that there is not a magic recipe," Schaeffer said.

In fact, the simplest poker-playing programs fail because they are just a recipe, a set of rules telling the computer what to do based on the strength of its hand. A savvy opponent can soon gauge what cards the computer is holding based on how aggressively it is betting.

That's how Laak was able to defeat a program called Poker Probot in a contest two years ago in Las Vegas. As the match progressed Laak correctly intuited that the computer was playing a consistently aggressive game, and capitalized on that observation by adapting his own play.

Programmers can eliminate some of that weakness with game theory, a branch of mathematics pioneered by John von Neumann, who also helped develop the hydrogen bomb. In 1950 mathematician John Nash, whose life inspired the movie "A Brilliant Mind," showed that in certain games there is a set of strategies such that every player's return is maximized and no player would benefit from switching to a different strategy.

In the simple game "Rock, Paper, Scissors," for example, the best strategy is to randomly select each of the options an equal proportion of the time. If any player diverted from that strategy by following a pattern or favoring one option over, the others would soon notice and adapt their own play to take advantage of it.

Texas Hold 'em is a little more complicated than "Rock, Paper, Scissors," but Nash's math still applies. With game theory, computers know to vary their play so an opponent has a hard time figuring out whether they are bluffing or employing some other strategy.

But game theory has inherent limits. In Nash equilibrium terms, success doesn't mean winning — it means not losing.

"You basically compute a formula that can at least break even in the long run, no matter what your opponent does," Billings said.

That's about where the best poker programs are today. Though the best game theory-based programs can usually hold their own against world-class human poker players, they aren't good enough to win big consistently.

Squeezing that extra bit of performance out of a computer requires combining the sheer mathematical power of game theory with the ability to observe an opponent's play and adapt to it. Many legendary poker players do that by being experts of human nature. They quickly learn the tics, gestures and other "tells" that reveal exactly what another player is up to.

A computer can't detect those, but it can keep track of how an opponent plays the game. It can observe how often an opponent tries to bluff with a weak hand, and how often she folds. Then the computer can take that information and incorporate it into the calculations that guide its own game.

"The notion of forming some sort of model of what another player is like ... is a really important problem," Nau said.

Computer scientists are only just beginning to incorporate that ability into their programs; days before their contest with Laak and Eslami, the University of Alberta researchers are still trying to tweak their program's adaptive elements. Billings will say only this about what the humans have in store: "They will be guaranteed to be seeing a lot of different styles."