Provably Difficult Combinatorial Games
Larry J. Stockmeyer, Ashok Kumar Chandra · SIAM Journal on Computing · 1979
For a number of two-person combinatorial games, the problem of determining the outcome of optimal play from a given starting position (that is, of determining which player, if either, has a forced win) is shown to be complete in exponential time with respect to logspace-reducibility. As consequences of this property, it is shown that (1) any algorithm which determines the outcome of optimal play for one of these games must infinitely often use a number of steps which grows exponentially as a function of the size of the starting position given as input; and (2) these games are “universal games” in the sense that, if G denotes one of these games and R denotes any member of a large class of combinatorial games (including Chess, Go, and many other games of popular or mathematical interest), then the problem of determining the outcome of R is reducible in polynomial time to the problem of determining the outcome of G.