Meghan Bialt-DeCelie – ’19

Artificial Intelligence (AI) has improved significantly in recent years in games involving perfect information. This means all players are aware of all the elements in the current state of a game. The next milestone for AI is creating an algorithm that can defeat humans at games with imperfect information, a game where players can be uncertain of certain game elements.

An example of an imperfect information game is poker, which has intrinsic uncertainty. This means that players are unsure of the cards in others’ hands and what remains in the deck. They can also lie to protect their knowledge of the game’s state.

Computer scientists, led by Matej Moravčík from the University of Alberta and Martin Schmid of Charles University, developed a new algorithm named DeepStack, which fixes the existing problems with algorithms. This algorithm needs training to “learn” from situations and its strategies is much more difficult to exploit. The algorithm has three components to it. It computes and strategizes locally under specific game states, it uses learned strategies when looking ahead and predicting, and it has a limited set of look-ahead actions. When up against pro poker players in 44,000 hands of Hands Up No Limit Texas Holdem, the algorithm was victorious for 492 milli-big-blinds/game—compared to around 50 for most pro poker players—with four standard deviations from zero, making the data significant.

This study can be applicable beyond the realm of poker games. Many decisions in the real world have imperfect information qualities that AI can now explore.

References:

1. Moravčík, Matej, et al, DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker. Science (2017). doi:10.1126/science.aam6960
2. Image retrieved from: https://commons.wikimedia.org/wiki/File:Poker-Texas-Holdem-multiplayer.jpg