跳棋

跳棋是一種雙人遊戲，最常見的變體是在 棋盤上進行，每位玩家在棋盤的相對兩側以固定顏色開始，各有十二個棋子。最常見的跳棋變體是所謂的“美式跳棋”，也稱為“西班牙跳棋”、“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)。