跳棋

跳棋是一种双人游戏，最常见的变体是在 棋盘上进行，每位玩家在棋盘的相对两侧以固定颜色开始，各有十二个棋子。最常见的跳棋变体是所谓的“美式跳棋”，也称为“西班牙跳棋”、“draughts”或“draught”（在英国和一些其他国家）、美式跳棋和直跳棋。游戏在玩家之间轮流进行，所有棋子最初只能沿前对角线方向移动和吃子。如果棋子通过到达棋盘的另一侧而被“王冠化”，则允许的移动方向会发生改变，之后它可以向前或向后移动。可以通过沿对角线跳过对方的棋子来吃掉它，游戏的获胜方式是吃掉对方的所有棋子或使对方无合法移动。

最常见的跳棋套装由黑色和红色的棋盘和棋子组成。然而，在锦标赛中，棋子的颜色是红色和白色，而不是红色和黑色，棋盘方格的颜色通常是橄榄绿和浅棕黄色，其中“浅棕黄色”是一种颜色，其定义各不相同，可以是中等橙黄色或浅至中等黄色。（然而，方格的颜色仍然被称为“黑色”和“红色”。）

Schroeppel（1972）估计大约有 种可能的位置。然而，这与 Jonathan Schaeffer 估计的 种合理的局面不符，其中 种局面可以在游戏规则下达到。

已知在 棋盘上的跳棋是 EXPTIME 完全的（Fraenkel等人。 1978；Robson 1984）。

计算机跳棋程序现在已经变得非常出色（Schaeffer 1997），一个名为 Chinook 的程序已成为第一个赢得世界冠军的计算机程序（阿尔伯塔大学计算机科学系）。Schaeffer等人。（2007）解决了跳棋问题，证明如果双方都进行完美的游戏，结果将永远是平局。Schaeffer 使用多台计算机（平均 50 台）“弱解决”了跳棋，存储了棋盘上只有十个或更少棋子时的所有可能位置，然后使用启发式搜索算法，可以确定完美游戏的结果。然而，只需要评估 个位置即可“解决”跳棋，并证实了普遍认为的理论，即如果两位玩家都进行完美的游戏，结果将是平局。

根据计数方式的不同， 棋盘上的 欧拉回路 的数量为 1, 40, 793, 12800, 193721, ... (OEIS A006240) 或 1, 13, 108, 793, 5611, 39312, ... (OEIS A006239)。