On the Complexity of n-player Cherries

摘要

Why are n-player games much more complex than twoplayer games? Is it much more difficult to cooperate or to compete? n-player Cherries is the n-player version of Cherries, a two-player combinatorial game. Because of queer games, i.e., games where no player has a winning strategy, cooperation is a key-factor in n-player games and, as a consequence, n-player Cherries played on a set of rows is PSPACE-complete.