 |
| Tuomas Sandholm (center) and Ph.D. student Noam Brown (via CMU) |
For those unfamiliar with Texas hold 'em
Two cards, known as the hole cards or hold cards, are dealt face down to each player, and then five community cards are dealt face up in three stages. The stages consist of a series of three cards ("the flop"), later an additional single card ("the turn") and a final card ("the river"). Each player seeks the best five card poker hand from the combination of the community cards and their own hole cards. Players have betting options to check, call, raise or fold. Rounds of betting take place before the flop is dealt, and after each subsequent deal.Unlike the computers that defeated the best humans in chess, Jeopardy and go, Liberatus comes directly from academia, from Tuomas Sandholm and his student Noam Brown at Carnegie-Mellon.
Unlike chess and go, poker is a game of incomplete information in many forms.
- Information both players have: the community cards already played.
- Information only one player has: the hole card
- Information neither player has: the community cards yet to be played.
Betting in poker plays the primary role of raising the stakes but betting can also signal what hole cards you have. Players can bluff (betting large amounts without a corresponding strong hand), trying to cause other players to misread the signal. There is no perfect play in poker, just a mixed equilibrium though we still don't know how to compute the equilibrium and even if we could we might deviate from the equilibrium to gain an advantage. Deviating also make you vulnerable.
All of this makes poker a far more complicated game for computers to tackle. But through persistence and new tools in machine learning, Sandholm and Brown have found success.
If history holds up, it won't be long before we have champion-caliber poker apps on our phones. Will we see cheating like has been happening in chess? Will online poker sites just disappear?
What is the next great game to fall to computers? I'm guessing NASCAR.
How much online poker is just two player? It is not at all clear to me that anything from this poker bot generalizes even to Texas Hold'em with 3 or more players. Playing a minmax equilibrium no longer necessarily makes sense in multi-player zero sum games, and certainly doesn't guarantee a win.
ReplyDeleteUntil there will be so many bots playing that they determine the equilibrium! Imagine that from 8 players 7 are bots. Then the human is forced to adopt to the equilibrium they use. Poker with 3+ players anyhow always had a huge theoretical contradiction, as for any 2 players it's worth cooperating (even without knowing each other's cards).
DeleteSure -- but you don't need to bring bots into the picture to start worrying about the risk that your opponents are colluding.
DeleteThis would have been a great April Fool's day post in 1997, the year
ReplyDeleteDeep Blue beat Kasporov in Chess. And now its reality!
Lance asks "What is the next great game to fall to computers?"
ReplyDelete--------
If we read "great game" Kipling-style — that is, as "Great Game" — then this week's Science article by Microsoft's Giuseppe Carleo and Matthias Troyer, "Solving the quantum many-body problem with artificial neural networks", postulates that the answer is "The Great Game of condensed matter theory."
The possibility (perhaps likelihood? even inevitability?) of a relatively near-term computer conquest of condensed-matter theory was much discussed at last month's QIP 2017.
Many QIP attendees are finding it surprising that quantum simulation problems classified as "hard" (sensu strictissimo) by complexity theorists are proving to be "easy" (sensu amplissimo) by cut-and-try algorithmists. In contrast, proposals for experimentally demonstrating "Quantum Supremacy" are proving (so far) to be not obviously more feasible than demonstrating scalable quantum computing. Ouch!
Summary Whatever it is that's transforming (and simultaneously confusing) the AI community, is transforming (and simultaneously confusing) too the quantum information and condensed matter communities … along with many other STEAM communities and enterprises.
How well do AIs do on the GREs? I was 20 points less than perfect... The work I do may contribute to them beating my score. I have a transformation from a cnf in dimacs form to a large boolean formula that decides all 2^n qbfs; imo, very useful for AI.
ReplyDelete