A New Algorithm for Generating Equilibria in Massive Zero-Sum Games

In normal scenarios, computer scientists often consider the numberof states in a game to capture the difficulty of learning anequilibrium. However, players do not see games in the same light:most consider Go or Chess to be more complex than Monopoly. In thispaper, we discuss a new measure of game complexity that linksexisting state-of-the-art algorithms for computing approximateequilibria to a more human measure. In particular, we consider therange of skill in a game, i.e., how many different skill levels exist.We then modify existing techniques to design a new algorithm tocompute approximate equilibria whose performance can be captured bythis new measure. We use it to develop the first near Nashequilibrium for a four round abstraction of poker, and show that itwould have been able to win handily the bankroll competition fromlast year's AAAI poker competition.