论文标题
国际象棋即使对于单个球员来说也很难
Chess is hard even for a single player
论文作者
论文摘要
我们介绍了可以在Chess.com上玩的游戏的单人游戏变种“ Solo Chess”的概括。该游戏的标准版本由单个玩家在常规的8 x 8棋盘上播放，只有白色零件，使用以下规则：每一步都必须捕获一块，没有任何一件件可能捕获超过2次，如果板上有国王，则必须是最后一件。目的是清除董事会，即进行一系列捕获，之后只剩下一块。 我们将此游戏概括为具有$ n $零件的无限板，每个游戏都有允许制作的给定数量的捕获数量。我们表明，即使只有剩下两个捕获的菜鸟，也只有众所周知，普遍的独奏国际象棋是NP完整的。事实证明，即使每一块都是女王，它也是NP的完整，而在初始配置中剩下两个捕获。相比之下，我们表明，当游戏是：a）由Rooks在一维板上扮演的时，可以完全表征通用独奏国际象棋的实例，而b）由Pawns播放，并在2D板上剩下两个捕获物。 受到广义独奏棋的启发，我们还介绍了图形捕获游戏，该游戏涉及通过沿边缘捕获清除令牌图。该游戏包含骑士扮演的广义独奏国际象棋。我们表明，对于无向图和DAG，图形捕获游戏是NP填充游戏。
We introduce a generalization of "Solo Chess", a single-player variant of the game that can be played on chess.com. The standard version of the game is played on a regular 8 x 8 chessboard by a single player, with only white pieces, using the following rules: every move must capture a piece, no piece may capture more than 2 times, and if there is a King on the board, it must be the final piece. The goal is to clear the board, i.e, make a sequence of captures after which only one piece is left. We generalize this game to unbounded boards with $n$ pieces, each of which have a given number of captures that they are permitted to make. We show that Generalized Solo Chess is NP-complete, even when it is played by only rooks that have at most two captures remaining. It also turns out to be NP-complete even when every piece is a queen with exactly two captures remaining in the initial configuration. In contrast, we show that solvable instances of Generalized Solo Chess can be completely characterized when the game is: a) played by rooks on a one-dimensional board, and b) played by pawns with two captures left on a 2D board. Inspired by Generalized Solo Chess, we also introduce the Graph Capture Game, which involves clearing a graph of tokens via captures along edges. This game subsumes Generalized Solo Chess played by knights. We show that the Graph Capture Game is NP-complete for undirected graphs and DAGs.
