井字游戏：井字游戏规则算法

井字游戏

EE-551 Python 项目

客观的：

这个 EE-551 项目旨在使用 python 开发一个 Tic Tac Toe 游戏。它主要包括开发和实现一个计算机程序，该程序可以与另一个玩家玩 Tic Tac Toe。
为了了解什么是井字游戏以及如何玩游戏，以下是说明。

游戏说明：

Tic Tac Toe 是一种两人游戏（其中一个由计算机或人类玩）。在这个游戏中，有一个 3 x 3 方格的棋盘。

两名玩家轮流在 3x3 棋盘上打分。Tic Tac Toe 游戏的目标是成为在 3 x 3 网格上水平、垂直或对角线获得三个相同符号的玩家之一。最先获得 3 个他/她的符号（标记）的玩家 - 垂直、水平或对角线赢得游戏，另一个玩家输掉游戏。游戏可以由两个玩家玩。玩家有两种选择：(a) 人类 (b) 计算机

游戏规则：

玩家可以与对手在两个符号之间进行选择，通常的游戏使用“X”和“O”。

实施计划：

本项目的实施工作流程如下：

为了可视化定义的游戏规则和描述，游戏如下图所示。

首先，游戏将从空棋盘开始。

然后玩家 1 将通过在该板上打标记“X”来移动。然后玩家 2 将通过在该板上打标记“O”来移动。这将继续下去，直到棋盘上满是分数。

然后程序将检查是“X”的玩家 1 获胜还是“O”的玩家 2 获胜，并且该场景将如下：（可以是垂直、水平或对角线）。

如果没有玩家获胜，程序将检查平局。

所有这些决策都是通过使用 Minimax 算法完成的。

极大极小算法

Minimax 是一种应用于两人 Tic Tac Toe 游戏的人工智能算法。这种游戏被称为零和游戏，因为在数学表示中：一个玩家赢（+1），另一个玩家输（-1）或两个人都输（0）。

Minimax 是一种递归算法，用于选择导致 Max 玩家赢或不输（平局）的最佳移动。它考虑游戏的当前状态和该状态下的可用移动，然后对于它播放的每个有效移动（交替最小和最大），直到找到最终状态 - 赢、平或输。

它的目标是最小化最大损失，即最小化最坏情况。

举例说明

为了应用这一点，让我们举一个游戏快结束时的例子，轮到我了。我是 X。显然，我在这里的目标是最大化我的最终游戏得分。

如果这张图片的顶部代表轮到我时的游戏状态，那么我有一些选择，我可以玩三个地方，其中一个明显导致我获胜并获得 10 分。如果我不这样做，O 很容易获胜。而且我不希望 O 赢，所以我在这里的目标，作为第一个球员，应该是选择最大的得分动作。

但是O呢？

我们应该假设 O 也在玩赢得这场比赛，但相对于我们，第一个玩家，O 想要选择给我们带来最差分数的移动，它想要选择一个可以最小化我们最终的移动分数。让我们从 O 的角度来看事情，从上面的另外两个游戏状态开始，我们不会立即获胜。

选择很明确，O 会选择任何导致得分为 -10 的动作。

描述极小极大

Minimax 算法的关键是两个玩家之间的来回，其中“轮到它”的玩家希望选择得分最高的移动。反过来，每个可用移动的分数由对方玩家决定其可用移动中的哪个具有最低分数来确定。对手玩家移动的分数再次由试图最大化其分数的轮流玩家决定，依此类推，一直到移动树到结束状态。

算法的描述，假设 X 是轮到玩家：

• 如果游戏结束，从 X 的角度返回分数。
• 否则，获取每个可能移动的新游戏状态列表。
• 创建分数列表。
• 对于这些状态中的每一个，将该状态的极小极大结果添加到分数列表中。
• 如果轮到 X，则返回分数列表中的最高分数。
• 如果轮到 O，则返回分数列表中的最低分数。

让我们用完整的走法树来看看算法的执行过程，并从算法上看，如何选择即时获胜的走法：

• 轮到 X 进入状态 1。X 生成状态 2、3 和 4，并在这些状态上调用 minimax。
• 状态 2 将 +10 的分数推送到状态 1 的分数列表，因为游戏处于结束状态。
• 状态 3 和 4 不在结束状态，因此 3 生成状态 5 和 6 并对其调用 minimax，而状态 4 生成状态 7 和 8 并对其调用 minimax。
• 状态 5 将 -10 的分数推送到状态 3 的分数列表，而状态 7 也会发生同样的情况，将 -10 的分数推送到状态 4 的分数列表。
• 状态 6 和 8 生成唯一可用的移动，即结束状态，因此它们都将 +10 的分数添加到状态 3 和 4 的移动列表中。
• 因为在状态 3 和状态 4 中轮到 O，所以 O 将寻求找到最小分数，并且在 -10 和 +10 之间进行选择时，状态 3 和 4 都将产生 -10。
• 最后，状态 2、3 和 4 的得分列表分别用 +10、-10 和 -10 填充，寻求最大化得分的状态 1 将选择得分为 +10 的获胜棋步，状态 2。

让我们通过查看可能的移动树来看看这里发生了什么：

• 给定棋盘状态 1，其中两个玩家都玩得很完美，而 O 是计算机玩家。O 在状态 5 中选择了移动，然后当 X 在状态 9 中获胜时立即失败。
• 但是如果 O 像状态 3 那样阻止 X 的胜利，那么 X 显然会阻止 O 的潜在胜利，如状态 7 所示。
• 如状态 10 和 11 所示，这为 X 带来了两次确定的胜利，因此无论 O 在状态 7 中选择哪一步，X 最终都会获胜。

该算法的另一个重要因素是深度。

该算法的关键改进是考虑到游戏结束的“深度”或回合数，无论棋盘安排如何，完美的玩家都会完美地玩。基本上完美的球员应该完美地打球，但尽可能地延长比赛时间。

所以每次我们调用 minimax 时，深度都会增加 1，当最终计算结束游戏状态时，分数会根据深度进行调整。

由于这是一个非常复杂的算法，我们有一台计算机来执行这个算法。

代码实施

• 为了运行此代码，需要安装 pygame 库。要安装它，请打开命令提示符并键入“pip install pygame”。

• 运行完整代码 TicTacToeGame.ipynb。

• 运行代码后，屏幕上将显示以下窗口（空板）：

• 游戏包含两个按钮 - vs Human 和 vs AI，以便我们可以选择我们的对手。一旦我们点击按钮，通过点击游戏板开始玩游戏。由于我们先玩，我们将被定义为玩家 X。

• 游戏结束后，游戏屏幕上将显示获胜者姓名（X 或 O）或抽奖游戏的消息。