For decades, researchers have been pitting artificial intelligence (AI) against the top game players in the world. The heads-up no-limit Texas hold'em variant of poker may be the final frontier in the battle of man vs. machine over games. And it may be about to fall.
In 1997, IBM chess computer Deep Blue defeated world chess champion Garry Kasparov. In 2011, IBM Watson defeated Ken Jennings and Brad Ruttner, the two winningest Jeopardy players in that game show's history. In 2015, Google DeepMind's AlphaGo defeated South Korean professional Go player Lee Sedol, considered one of the best players in the world.
But as games go, heads-up no-limit Texas hold'em is an entirely different beast. Unlike the others, it is a game of imperfect information - the players know only some of the cards in play, and they can bluff and use other ploys to mislead their opponents. Tuomas Sandholm, computer science professor at Carnegie Mellon University, says the game features 10161 information sets, significantly more than all the atoms in the universe. Limit hold'em, which restricts bets and raises to a pre-determined amount, has 1013 information sets.
"For a given game size, incomplete information games are much harder to solve than complete information games," Sandholm says. "In complete information games, it's basically decomposable. You can solve what's best to do just by looking at the end game. But if I'm in an end game where I have four aces, I can't just bet aggressively. And I can't just bet weakly when I have a weak hand. That would be too transparent. You have to balance across the subgames and therefore the problem is not decomposable."
Humans masters of the incomplete and misleading
In practical terms, humans encounter situations in which they must make decisions on incomplete and misleading information all the time. An AI capable of making good decisions based on such information has real-world applications in areas like negotiations, finance, military strategy, cybersecurity and even medicine. Sandholm notes he just received funding for a project to use AI to steer the adaptation and evolution of the immune system to better treat cancers and autoimmune diseases.
But to get there, AI need to surpass humans' ability to solve imperfect information games.
"When it comes to these strategic situations, you don't want to use an AI that's dumber than you," Sandholm says. "That would make you worse off. You want an AI that's stronger than you. In negotiations, I don't want to delegate that to an AI that's worse than I am. It's the same for military strategy and cybersecurity. You don't want it to be worse than what we can do manually. It has to put together better strategies than any human."
Sign up for CIO Asia eNewsletters.