井字棋

井字棋游戏，也拼写为 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 定理没有帮助，因为它是存在性的，而不是构造性的。