如何使用 Minimax 算法和 Alpha Beta 剪枝解决 Tic Tac Toe 4x4 游戏

Question

我使用 Minimax 和 Alpha Beta 剪枝制作了一款 Tic Tac Toe 游戏。我想为 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

我希望你明白了。

所以，我改变了制作井字棋的计划，从 10x10 改为 3x3，效果很好。

然后我更改

boardSize = 4

和

winStreak = 3

使其成为 (4x4) 井字游戏。

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

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

如何提高其速度？人们甚至能够使用 Minimax + Alpha Beta 剪枝来解决国际象棋问题，但是我的代码有什么问题吗？

我的完整代码大约有 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 等游戏中，这是一种合理的方法，因为搜索树很小，并且可以在短时间内从起始位置到达叶节点。但是对于在较大棋盘上玩的游戏（例如国际象棋、围棋等），您无法递归，直到到达终端节点（这将花费太多时间）。因此，您需要决定停止哪个递归深度，并尝试根据游戏的战术/战略原则评估当前位置。为此，您需要编写一个启发式评估函数，该函数将为您提供该职位的价值。然后，您可以将该值沿搜索树向上传播以确定最佳移动。整个程序的质量在很大程度上取决于评估函数的质量。
2. 移动排序。生成所有有效移动的列表后，根据评估函数按降序对它们进行排序。这样，算法将首先考虑好的动作，这些动作更有可能产生高 alpha-beta 截止值，从而导致更多节点被修剪。
3. 使用主变分搜索进行迭代加深。不要对具有固定深度的 minimax 函数进行初始调用，而是尝试首先使用深度 1 调用它，然后调用 2、3，...（当达到每次移动时间截止时停止） ）。存储使用深度

   k

   找到的最佳移动，并将其用作深度

   k + 1

   的最小最大中的第一个候选。此外，您不仅可以存储最佳移动，还可以存储最佳移动的整个序列，这称为主变分。因此，在您找到深度

   k

   的主要变化之后，将其提供给深度

   k + 1

   上的极小极大调用，它通常会产生很多良好的 alpha-beta 截止值。
4. 开局书。如果您知道前几个（甚至可能是几十个）回合的好动作是什么，您可以将它们硬编码在开局书中。因此，当你的程序面临开卷中的位置时，它会立即检索最佳答案。开局书的一个简单例子是对 3×3 井字游戏的第一个移动到中心方块进行硬编码。这样你的程序将花费零秒来找到第一步。
5. 换位表。尝试重用在位置 X 的极小极大搜索期间找到的最佳移动，以确定与 X 对称的另一个位置 Y 的最佳移动（意味着可以通过旋转/反射从 X 获得 Y） 。在棋盘游戏编程中实现换位表的常见高级技术之一称为 Zobrist 哈希。
6. 并行算法。尝试并行化您的算法，使其在多核机器上运行得更快。
7. 编程语言。由于您的问题标有

   Javascript

   标签，我假设您正在使用这种语言来实现算法。就性能而言，Javascript 并不被认为是最好的语言。因此，如果您熟悉 C、C++ 或 Java 等语言，使用其中一种语言重写程序可以显着提高性能。

最后，你的那句话

人们甚至能够使用 Minimax + Alpha Beta 剪枝来解决国际象棋问题

严格来说并不正确，因为国际象棋还不是一个已解决的游戏。但是存在可以轻松击败人类玩家的国际象棋程序（使用带有 alpha-beta 剪枝的极小极大值以及许多其他更先进的技术）。因此，程序能够击败专家玩家和世界冠军并不意味着它运行完美。