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

Question

我使用 Minimax 和 Alpha Beta Pruning 制作了一个 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

我希望你明白了。

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

最后，你的词

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

严格来说不是真的，因为国际象棋还不是一个已解决的游戏。但是存在可以轻松击败人类棋手的国际象棋程序（使用极小极大与 alpha-beta 剪枝和许多其他更高级的技术）。因此，程序可以击败专家级选手和世界冠军的事实并不意味着它玩得很完美。