论文标题
逆行和助手国际象棋问题的复杂性：即使是合作国际象棋也很难
Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard
论文作者
论文摘要
我们证明，当概括为N-N板上时，我们证明了两种经典的国际象棋问题类型的Pspace完整性。 “逆行”问题询问是否有可能从自然的起始位置达到职位，即该职位是“有效”还是“合法”还是“可及”。大多数真实的逆行国际象棋问题都要求这样的序列的最后几个动作。我们分析了一个决策问题，该问题呈指数长的移动序列存在。 “助手”问题询问玩家是否有可能通过从给定位置进行任何移动序列进行检查。一个助手问题本质上是国际象棋的一种合作形式，两个球员都共同努力，使特定的球员获胜。它也出现在常规的国际象棋游戏中，只有时间（标志）的玩家只有从当前位置进行检查（即，救助者问题具有解决方案），才能损失。我们的pspace-hardness降低来自一个名为Subway Shuffle的益智游戏的变体。
We prove PSPACE-completeness of two classic types of Chess problems when generalized to n-by-n boards. A "retrograde" problem asks whether it is possible for a position to be reached from a natural starting position, i.e., whether the position is "valid" or "legal" or "reachable". Most real-world retrograde Chess problems ask for the last few moves of such a sequence; we analyze the decision question which gets at the existence of an exponentially long move sequence. A "helpmate" problem asks whether it is possible for a player to become checkmated by any sequence of moves from a given position. A helpmate problem is essentially a cooperative form of Chess, where both players work together to cause a particular player to win; it also arises in regular Chess games, where a player who runs out of time (flags) loses only if they could ever possibly be checkmated from the current position (i.e., the helpmate problem has a solution). Our PSPACE-hardness reductions are from a variant of a puzzle game called Subway Shuffle.
