When poker pro Bryce Paradis first played an early version of the University of Alberta computing science department’s poker-playing computer program, he was impressed. “It played differently from a human, but it was still good,” he recalls in a rapid clip. “Odd, but good.” Odd because it didn’t really understand how aggressively to play, or how to bluff in a way that a human player would believe.
Paradis would know: When he played poker professionally in the mid-2000s, he played a lot – thousands upon thousands of hands online in a day.
That experience gave Paradis insights into the game that few other human players have. “Because of all the poker I’ve played, my perspective is almost more computer-like,” he admits. “I’m a bit desensitized to variants, short-term luck and long-term luck.”
He realized that the program, then called Polaris, was playing “a good strategy. Even if it wasn’t what humans were doing, it was very similar.”
Polaris evolved into Cepheus, which, earlier this year, “solved” poker. The U of A research group, headed first by Jonathan Schaeffer and currently by Michael Bowling, and its project shone an international spotlight on the incredible artificial intelligence (AI) work incubating at the university. But it’s more than just games – Cepheus has shown us how the work that goes into solving games like poker and checkers has the ability to change how we solve other problems, in realms such as medicine and politics.
In the late 1970s, Jonathan Schaeffer was a high-level chess player and undergraduate computer science student at the University of Toronto. That was when he happened to take a course on the then-nascent field of artificial intelligence.
At the time, AI research was dominated by those exploring “expert systems,” of which computer programs diagnosing medical disorders were the poster children. While Schaeffer could appreciate the importance of such work, it didn’t resonate with him. “I didn’t know the medical jargon,” he explains. “But I knew games. I decided to use games to demonstrate research into artificial intelligence.” He began to dream about developing a chess-playing computer program.
“I thought maybe I could write a program that could defeat the world chess champion.”
Chess was a near-miss. In 1986, his program, Phoenix, tied the World Computer Chess Championship, which pitted computer against computer. But Deep Thought, the IBM-backed program that eventually had its name changed to Deep Blue in 1989, was clearly better, Schaeffer says. It ended up defeating then-world champion Garry Kasparov in 1997.
In 1989, when it was clear to Schaeffer that he couldn’t compete with Deep Blue, he turned his attention to checkers. In 1994, his program, Chinook, was the first computer program to win a world championship. But, you know – checkers? Isn’t that just a simple children’s game?
“Who cares?” agrees Schaeffer, tongue in cheek, about the accomplishment. “Checkers isn’t the world’s most earth-shattering problem.”
But, he points out, Chinook required the development of new algorithms that could research large volumes of information more efficiently. These developments formed the core technology of a company called BioTools that Schaeffer and three friends started up in 1995 to research the human genome and analyze human DNA and proteins. In other words, these games served as ideal testing grounds for real-life problems.
“Politics can be expressed as a game,” explains Schaeffer. “Issues in the environment can be expressed as a game. So can the spread of disease.” The United States government has long recognized the similarities between games and geopolitical manouevring, sponsoring conferences that seek to apply the insights of gaming programs to international affairs. Think of Cold War brinksmanship, George W. Bush versus Saddam Hussein and Iraq’s nuclear weapons arsenal. Who’s bluffing? All of these and more are, as Schaeffer puts it, “enormously complicated problems.”
When Schaeffer came to the University of Alberta, he was still fascinated by the potential of games-based computing programming to elucidate broader problems. He formed the GAMES (Games, Analytical Methods and Empirical Studies) research group devoted to the subject. This was the inadvertent foundation for what would become, decades later, the university’s reputation as a world leader in artificial intelligence.
While one of the games it was first interested in was checkers, the research interest of the group rapidly expanded. From this group, Schaeffer name-checks researchers like Brian Sheppard, who built a Scrabble program that was picked up by Hasbro for use in its online games. Others in the department have worked on games such as Hex, Lines of Action, Go and Othello.
Many of these programs are very good or “superhuman,” which means that humans will likely lose. “Solving” a game is harder: it means that the computer program simply cannot lose.
Or, as Schaeffer puts it: “Chess is a game where the programs are superhuman. Humans have no chance against the computer, but the program could still make a mistake and lose. For checkers – a game which is ‘solved’ – if you play perfectly, you will draw. You will never win. And if you make a mistake, the computer will beat you.”
For many real-world problems, poker is a better match, as far as games go. Unlike chess or checkers, where all the information about the next best move is clear by looking at the game board, poker involves hidden information. No computer program knows (without cheating) what the cards the other player has. And then there’s bluffing: Players can pretend to have better cards than they actually do. In the lingo, it’s an “imperfect information game.” You have to act without knowing all the variables at hand. And everyone can lie.
So that’s exactly what the U of A team taught a computer program to do. In 1995, Schaeffer started up a research group devoted to poker, specifically Texas Hold ‘Em, which he directed until 2007. That’s when Cepheus’s predecessor – the Polaris program that Paradis helped to perfect – made history by being the first bot to take on two human professional players at the Association for the Advancement of Artificial Intelligence conference, which also hosted an international competition between computer poker programs. It held its ground with one win, two losses and a draw.
Since then, Cepheus has risen to dominance by playing a lot of poker against itself, getting very good at bluffing, and getting just a little bit faster. “If you look at [heads-up limit Texas Hold ‘Em] poker, it’s actually a very big program. There are only about 16,000 possibilities for betting,” explains Neil Burch, one of the researchers on the team. “All the rest is the different cards that can be dealt out.” Programs in the past would discard some of the information about the cards, assigning the same value, for instance, to high-ranking pairs like two kings and two aces. This made the program more manageable in size and speed, but also less accurate. With a slightly faster algorithm, “some engineering work” and more computer resources, Cepheus was able to differentiate between the cards.
Imperfect information games are better analogies for many real-life situations, says Burch.
“Where do you want the coast guard to patrol and when? You can write that as a game as a well-defined problem. What if there is someone who is trying to attack – because that’s the point of a coast guard, to defend – where could they be, what could they do?”
Ironically, some of the research is circling back to what Schaeffer found so unappealing 30 years ago: the medical applications of computer games. Several years ago, graduate student Kit Chen developed an algorithm, based on some of the work done towards solving poker, about how best to administer insulin to diabetics. It turns out that patients who are dependent on insulin require different levels and frequencies of the hormone.
“Surprisingly,” comments Burch, “you can frame this problem as an imperfect information game. It’s sort of like poker, where you don’t know exactly what’s going on.”
