In another giant leap for A.I. and game theory, Carnegie Mellon and Facebook engineers have built an artificial intelligence program that has consistently defeated experts in a multi-player game of ‘imperfect information’.
Why is this considered such an enormous achievement?
First let‘s revisit professor Josh Nash and economic game theory definitions for some clarity.
In two-player games of ‘perfect information’ both players have all the information to make an optimal or correct decision. In chess for example, all of the game pieces are clearly visible, all the moves are seen and you only have to defeat one opponent. There is zero ambiguity. It's a perfectly solvable game with enough raw brain power. No bluffing. No surprises. Grandmaster crushes amateur. Supercomputer defeats the world champion.
Conversely in multi-player games of ‘imperfect information’ all of the participants only have partial information to make a statistically optimal solution against several opponents.
In no-limit hold ‘em, amateur players only know their two cards. The most successful experts will know their statistical likelihood to win at the end of the hand, their opponents' physical tells and the probability of their opponents actions. All of the other vital information (i.e, other cards) are hidden. Perfect decisions are impossible in a fairly played game. Bluffing is a mandatory tactic at the highest levels of competition. An amateur can beat the world’s best. See the World Series of Poker Main Event.
Computing power and games of information
Now it's not a surprise that computers solved two-player games of ‘perfect information’ like chess decades ago (most notably when IBM’s supercomputer Deep Blue defeated world champion chess player Garry Kasparov in 1997).
That was 22 years ago.
So why are many leaders in AI considering this Carnegie and Facebook breakthrough on multiple player games of imperfect information to be such a noteworthy achievement?
Without getting too nerdy and complex in both game theory and artificial intelligence, if a game of imperfect information doesn't have a Nash equilibrium optimal solution AI engineers believed they couldn’t ‘solve’ the game at a consistently optimal level regardless of computing power.
Simply put, the problem in solving no limit hold 'em wasn't just an issue of brute number crunching and permutation calculations. It was a vastly more complex problem especially with the added variables of five expert opponents making decisions versus just one. Artificial intelligence needed to solve a partially hidden puzzle with missing pieces against thinking opponents capable of disguising the strength of their hands through bluffing.
This required an A.I. program to learn creativity. This required it to adapt to its opponents' tendencies. The computer need to bluff. The computer needed to 'read' a bluff.
The computer required 'artificial intelligence'.
So why is this important?
It's not because a computer program can now mint money in online poker. The real world implications and learnings from this project will go well beyond gaming and eventually will affect cyber-security, autonomous transportation, trade, national defense and more.
It won't happen over night but it was a giant leap for AI.
To read more you can visit the MIT Technology Review or for more details the Science Magazine article.