In game theory, generalists sometimes win out over specialists

MIT researchers have found that general-purpose algorithms can beat specialized game-theory methods in imperfect-information games. The work, presented in April at the International Conference on Learning Representations in Rio de Janeiro, challenges a long-held assumption in the field.

Imperfect-information games are situations where players don't know everything about their opponent's position. Poker is one example. A bidding war for a house is another. In these zero-sum contests, one player's gain is the other's loss.

The researchers compared two classes of algorithms. Specialized game-theoretic algorithms were designed specifically for these games. Policy gradient methods, a general-purpose class of algorithms used to train neural networks, came into use for decision-making in the 1990s. The field had assumed the specialized algorithms would outperform the generalists.

"It had been pretty much taken for granted that specialized game-theoretic algorithms were the right approach for this setting," said Samuel Sokota, a co-author from Carnegie Mellon University. "Our study showed that policy gradient methods can work better than these specialized algorithms."

The team built a benchmark to evaluate algorithms fairly. They measured performance using a concept called exploitability, which scores how well a player does against the worst-case adversary. A score of zero means perfect play. Higher scores mean worse play.

The experiments covered five games. Two were versions of Phantom Tic-Tac-Toe, where players cannot see their opponent's moves. Two were imperfect-information variants of the board game Hex. The fifth was Liar's Dice, a game of deception.

Neural networks trained with policy gradient algorithms achieved lower exploitability scores than networks trained with game-theory algorithms. In head-to-head competitions, the policy gradient networks also won.

"Those results were reassuring," said Max Rudolph, a co-author from the University of Texas at Austin. "They give us more confidence in our benchmarking approach."

The biggest challenge was computing exploitability for games with up to 30 billion states. A state includes the entire history of the game, not just board positions. Previous researchers typically used exploitability for games 100,000 times smaller.

The team made their benchmarking software freely available. It runs on an ordinary laptop and requires adding a single line of code to OpenSpiel, a commonly used collection of benchmarking tools.

The results have implications beyond recreational games. "Hidden information is a very important property of the world," said Eugene Vinitsky of New York University, another co-author. "It pervades a range of things, including military operations and trading scenarios, all of which are carried out under conditions of hidden information."

Ian Gemp, a computer scientist and game theory expert at Google DeepMind who was not involved in the study, said the work serves as a reminder that modernizing classical tools like policy gradient methods remains a productive path for solving complex strategic problems.