Abstract. Amazons is a board game which combines elements of Chess and Go. It has become popular in recent years, and has served as a useful platform for both game-theoretic study and AI games research. Buro showed that simple Amazons endgames are NP-equivalent, leaving the complexity of the general case as an open problem.

Konane is an ancient Hawaiian game, with moves similar to peg solitaire. Konane has received some attention in the combinatorial game theory community, with game values determined for many small positions and one-dimensional positions. However, its general complexity seems not to have been previously addressed.

Cross Purposes was invented by Michael Albert, and named by Richard Guy at the Games at Dalhousie III workshop, in 2004. It is played on a Go board. Cross Purposes is a kind of two-player version of the popular puzzle Tipover: it represents stacks of crates tipping over and blocking others from tipping over.

We show that generalized versions of these games are PSPACE-complete. We give similar reductions to each game from one of the PSPACE-complete two-player formula games described by Schaefer. Our construction also provides an alternate proof that simple Amazons endgames are NP-equivalent.

Introduction

Combinatorial game theory is concerned with the attempt to find and analyze winning strategies for combinatorial games, or for tractable families of game positions.