Feature - Poker, parallelism and payoff

Image courtesy of PSC

You won’t find them at the Vegas casinos and what they do is hard to call gambling, but it’s fair to say that Tuomas Sandholm and grad student Andrew Gilpin of Carnegie Mellon’s School of Computer Science are professional poker players. Last July in Chicago — at the AAAI (Association for the Advancement of Artificial Intelligence) Computer Poker Competition, involving 19 programs from six countries — they walked away with no pile of cash but, nevertheless, were the biggest winners.

Their field, game theory, in which Sandholm’s work is internationally recognized, describes conflict in which the payoff is affected by actions and counter-actions of intelligent opponents. Head-to-head poker between two players is a prominent example of what’s called two-person zero-sum games: One player wins what the other loses.

In recent years, poker has emerged as an AI challenge much as chess was for many years.

"But poker is far more demanding,” says Sandholm. “In poker, a player doesn’t know which cards the other player holds or what cards will be dealt in the future.”

Tuomas Sandholm  Used with permission from T. Sandholm

Like many games, poker can be formulated mathematically, but the formulations are huge. Two-player poker has a game-tree of a billion-billion (10¹⁸) nodes, notes Gilpin.

“To solve that requires massive computational resources,” he says. “Our research is on scaling up game-theory solution techniques to those large games, and new algorithmic design.”

The most computationally intensive portion of their algorithm is a matrix-vector product, where the matrix is the payoff matrix and the vector is a strategy for one of the players. This operation accounts for more than 99 percent of the computation, and is a bottleneck to applying game theory to many problems of practical importance.

To drastically increase the size of problems the algorithm can handle, Gilpin and Sandholm devised an approach that can potentially exploit massively parallel systems of non-uniform memory-access architecture, such as Pople, an SGI Altix 4700 TeraGrid resource at the Pittsburgh Supercomputing Center. By making all data addressable from a single process, shared memory simplifies a central, non-parallelizable operation performed in conjunction with the matrix-vector product. Sandholm and Gilpin have revised their code to run on Pople, and are doing experiments to learn how much parallelism can help, and possibly point to areas for further algorithmic improvement.

—Michael Schneider, Pittsburgh Supercomputing Center