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.

关键词： combinatorial games computational complexity

作者: Alessandro Cincotti

作者单位: School of Information Science Japan Advanced Institute of Science and Technology 1-1 Asahidai, Nomi, Ishikawa 923-1292 Japan

会议类型: 国际会议

会议名称: 2010 3rd IEEE International Conference on Computer Science and Information Technology(第三届IEEE计算机科学与信息技术国际会议 ICCSIT 2010)

会议地点: 成都

会议语种:英文

页码: 481-483

在线出版日期: 2010-07-07（万方平台首次上网日期，不代表论文的发表时间）