javascript - 如何使用 Minimax Algorithm.and Alpha Beta Pruning 解决 Tic Tac Toe 4x4 游戏

Question

我使用 Minimax 和 Alpha Beta Pruning 制作了一款井字游戏。我想为 Tic Tac Toe (10x10) 游戏制作计算机 AI，但它的游戏树大得离谱。

我的代码是这样的，我只需要更改两个变量来更改连续获胜所需的棋盘大小 + 单元格。 示例:

boardSize = 3//这是 3x3 井字游戏

boardSize = 4//这是 4x4 井字游戏

boardSize = 10//这是 10x10 tic tac toe

和

winStreak = 3//需要连续 3 个单元格才能获胜

winStreak = 4//需要连续 4 个单元格才能获胜

我希望你明白了。

因此，我改变了制作 Tic Tac Toe 的计划，从 10x10 改为 3x3，而且效果很好。

然后我更改 boardSize = 4 和 winStreak = 3 使其成为 (4x4) 井字游戏。

现在，我认为带有 Alpha Beta 剪枝的 Minimax 足以解决 4x4 问题，但惊讶地发现，事实并非如此。

当我迈出第一步(人类)时，minimax 算法搜索了 5-10 分钟，然后浏览器选项卡就崩溃了。它甚至无法迈出第一步。

如何提高它的速度？人们甚至可以使用 Minimax + Alpha Beta Pruning 解决国际象棋问题，但我的代码有什么问题？

我的完整代码大约有 200-300 行，所以我只写伪代码。

humanMakeMove();

Minimax(); // Bot calls Minimax function to make a move

function Minimax(board, player) {
if (checkResult() != 0) // 0 = Game is on
   return checkResult(); // 1 = Win, 0.5 = Draw, -1 = Lose   

   availableMoves = getAvailableMoves();

   for(i = 0; i < availableMoves.length;i++)
   {
        move = availableMoves[i]; 
        removeMoveFromAvailableMovesArray(move);
        if (player == "X")
            score = Minimax(board, "O");
        else
            score = Minimax(board, "X");
        board[i] = "-"; // "-" means empty space


        if (depth of tree is on first level && score == 1)
                return maxScore; //Alpha Beta Pruning is applied here, if we get score of 1, then we don't need to search more. 


   }
}

我还可以应用哪些优化来使代码运行得更快？

Answer 1

提高程序性能的可能性有多种。

1. 评估功能。 目前看来您仅在到达终端游戏节点时才应用评估功能。在像 3x3 tic-tac-toe 这样的游戏中，这是一种合理的方法，因为搜索树很小，叶节点可以在短时间内从起始位置到达。但是对于在较大棋盘上玩的游戏(如国际象棋、围棋等)，在到达终端节点之前不能递归(这会花费太多时间)。因此，您需要决定停止哪个递归深度，并尝试根据游戏的战术/战略原则评估当前位置。为了做到这一点，您需要编写一个启发式评估函数，它将为您提供头寸的值(value)。然后，您可以将该值向上传播到搜索树以确定最佳着法。整个程序的质量在很大程度上取决于 eval 函数的质量。
2. 着法排序。生成所有有效着法的列表后，根据评估函数对它们进行降序排序。这样，该算法将首先考虑更有可能产生高 alpha-beta 截止值的好的移动，从而导致更多节点被 trim 。
3. 通过主要变体搜索进行迭代加深。不要以某个固定深度对 minimax 函数进行初始调用，而是尝试先以深度 1 调用它，然后是 2、3、...(当停止时达到每次移动截止时间)。存储使用深度 k 的 minimax 找到的最佳移动，并将其用作深度 k + 1 的 minimax 中的第一个候选。此外，您不仅可以存储最佳着法，还可以存储最佳着法的整个序列，这称为主要变化。因此，在找到深度 k 的主要变化后，将其提供给深度 k + 1 的 minimax 调用，它通常会产生很多好的 alpha-beta 截止值。
4. 开卷。如果您知道前几个(或什至几十个)回合的好 Action 是什么，您可以将它们硬编码到开卷中。因此，当您的程序面临开卷中的一个位置时，它会立即检索最佳答案。开局书的一个简单示例是硬编码 3×3 井字游戏的第一步到中心广场。这样您的程序将花费零秒来找到第一步。
5. 换位表。尝试重新使用在位置 X 的极小极大搜索过程中找到的最佳着法，以确定与 X 对称的另一个位置 Y 的最佳着法(意味着可以得到 Y从 X 通过旋转/反射)。在棋盘游戏编程中实现换位表的一种常见高级技术称为 Zobrist 哈希。
6. 并行算法。尝试并行化您的算法，使其在多核机器上运行得更快。
7. 编程语言。由于您的问题标有Javascript 标记，因此我假设您正在使用这种语言来实现算法。就性能而言，Javascript 不被认为是最好的语言。因此，如果您熟悉 C、C++ 或 Java 等语言，使用其中一种语言重写程序可以显着提高性能。

最后，你的短语

People are even able to solve chess using Minimax + Alpha Beta Pruning

严格来说是不正确的，因为国际象棋还不是一个解决的游戏。但是存在可以轻松击败人类玩家的国际象棋程序(使用 minimax 和 alpha-beta 剪枝以及许多其他更高级的技术)。所以程序能打败高手和世界冠军，并不代表它就玩的完美。