井字棋

井字棋遊戲，也拼寫為 ticktacktoe，也稱為三連棋或“圈圈叉叉”，是一種遊戲，玩家輪流將棋子（通常第一個玩家用 X，第二個玩家用 O）放在一個 棋盤上。第一個將三個棋子排成一行（垂直、水平或對角線）的玩家獲勝。對於通常的 棋盤，總是可以獲得平局，使其成為一個無用遊戲。

Wolfram (2022) 將 和 井字棋分析為多計算過程，包括透過使用分支圖。

廣義的 連棋也可以在 棋盤上考慮，也可以推廣到三維“棋盤”。在大小被認為是 或 的棋盤上，將五個（或更多）連成一線的遊戲被稱為五子棋。 井字棋的具體情況被稱為立體井字棋。

對於任何大於 的棋盤上的二連棋，先手玩家都有必勝策略。在“復仇”井字棋（其中 連棋獲勝，但如果對手在下一步可以形成 連棋則輸）中，即使是二連棋也不是微不足道的。例如，在 在 棋盤上，如果先手玩家從第二個或第四個方格開始，則會獲勝，但如果他從其他地方開始則不會贏。

在三連棋中，對於至少 的任何棋盤，先手玩家都會獲勝。先手玩家在帶有增強角格的 棋盤上也獲勝，有三種不同的獲勝先手走法 (Gardner 1978)。

如果棋盤至少是 ，則先手玩家可以為 獲勝（ 棋盤是平局）。據信對於 遊戲是平局，對於 遊戲結果未定，據信對於 遊戲先手玩家必勝，並且已被證明對於 遊戲先手玩家必勝，這是透過變異樹（Ma）證明的。

對於 ，在 棋盤上總是可以獲得平局，但如果棋盤至少是 ，則先手玩家可以獲勝。對於 和 7 的情況，對於 棋盤尚未完全分析，儘管對於 和 9 總是可以強迫平局。

在更高維度中，對於任何 連棋，都存在一個維度為 的棋盤 ()，先手玩家有必勝策略 (Hales and Jewett 1963)。Hales-Jewett 定理是 拉姆齊理論 中的一個核心結果，即使有超過兩名玩家，仍然會存在一個維度 ，使先手玩家獲勝。對於 和 ，先手玩家總是可以獲勝 (Gardner 1979)，從而確定了 對於 和 的情況。對於 ，Golomb 已經證明了 具有 Hales-Jewett 配對策略 (Ma 2005)。對於其他 的 值是未知的，Hales-Jewett 定理沒有幫助，因為它是存在性的，而不是構造性的。