Playing Disjunctive Sums is Polynomial Space Complete (1981)
F. Lockwood Morris
Abstract
A position in a disjunctive sum of games is simply a collection of positions,
one from each game: to move in a sum is to move in any one of its
constituents. Sums have been studied extensively by Conway and others, and
play an important role in Go.
It is shown that the problem of best play in a sum of trivial games is
polynomial space complete. Hence it may be conjectured that there is no
feasible algorithm for deriving a strategy of play in a sum from knowledge
about its constituent games.
