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

Question

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

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

boardSize = 3 // This is for 3x3 tic tac toe

boardSize = 4 // This is for 4x4 tic tac toe

boardSize = 10 // This is for 10x10 tic tac toe

和

winStreak = 3 // Need to make 3 cells in a row to win

winStreak = 4 // Need to make 4 cells in a row to win

希望你明白了。

所以，我改变了我的计划，将 Tic Tac Toe 从 10x10 改为 3x3，并且效果很好。

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

现在，我认为带有 Alpha Beta P运行ing 的 Minimax 足以解决 4x4，但惊讶地发现，事实并非如此。

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

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

我的完整代码大约有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

有几种方法可以提高程序的性能。

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

最后，你的短语

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

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

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

How to solve Tic Tac Toe 4x4 game using Minimax Algorithem.and Alpha Beta Pruning

javascript

machine-learning

tic-tac-toe

minimax

alpha-beta-pruning