A new academic paper describes how DeepStack, using an algorithm for imperfect information settings such as poker, became the first computer program to beat professional poker players in heads-up no-limit Texas hold’em.
Computers have long triumphed over humans in games like chess and checkers, where all players have identical information (perfect information).
Perfect information is far more common in games than in real-world problems, though.
Poker is a game of imperfect information and it has been a longstanding problem for artificial intelligence.
To become good at a game with imperfect information, DeepStack combines:
- Recursive reasoning to handle information asymmetry.
- Decomposition to focus computation on the relevant decision.
- A form of intuition about arbitrary poker situations that is automatically learned from selfplay games using deep learning.