如何用极小极大算法解决Tic-Tac-Toe 4x4游戏。α-β修剪

Question

我做了一个Tic-Tac-Toe游戏，使用Minimax和Alpha-Beta修剪。我想为Tic-Tac-Toe（10x10）游戏制作一个计算机AI，但它的游戏树大得离谱。

我的代码是这样的，我只需要更改两个变量就可以更改一行中所需的板大小单元格。例子：

boardSize=3//这是用于3x3 tic tac toe的

boardSize=4//这是用于4x4 tic tac-toe的

boardSize=10//这是用于10x10 tic tac-toe的

和

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

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

我希望你明白了。

所以，我把我的计划从10x10改为3x3，效果很好。

然后我改变boardsize=4和winStreak=3，使其成为（4x4）井字游戏。

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

当我第一次移动（人类）时，minimax算法搜索5-10分钟，然后浏览器选项卡就崩溃了。它连第一步都做不到。

我怎样才能提高它的速度？人们甚至能够使用极小值阿尔法贝塔修剪解决国际象棋，但是我的代码有什么问题？

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

最后，你的短语

人们甚至可以使用极小极大阿尔法-贝塔修剪来解国际象棋

严格地说，这不是真的，因为国际象棋还不是一个已解决的游戏。但也有一些国际象棋程序可以轻松击败人类玩家（使用minimax和alpha-beta修剪以及许多其他更先进的技术）。所以，该程序能够击败专家选手和世界冠军的事实并不意味着它玩得很完美。