Minimax Alpha-Beta修剪算法需要太多时间来解决Tic Tac Toe（10x10板）

Question

我用Javascript制作了一个两种类型的井字游戏。一个是3x3，另一个是10x10。

我正在使用带有Alpha-Beta修剪的Minimax算法来解决这两个游戏。在3x3中，博弈树非常小，算法运行良好。

但在10x10中，它需要太多的时间。代码甚至不能在10分钟内移动一步。我运行了算法，等了10分钟，仍然在计算，然后我关闭了浏览器选项卡。（如果我让代码运行lol，甚至可能需要几个小时、几天、几周）

我在几篇文章中读到，带有阿尔法贝塔修剪的极小值可以轻松解决井字游戏脚趾10x10或更大的问题。是错误的，还是我的代码不好？

这是我的代码，但我想，很难理解它。但我想代码并不重要。我应用了Minimax Alpha-Beta修剪。我还能做什么？

function makeBotMove(newBoard, availMoves, XorO, firstCall) { // newBoard stores board state in an array. availMoves stores Available moves in an array (0-99). XorO store either "X" or "O" depending on whoes turn it is. firstCall is used to find out If the call is made inside the function or not. I need it for Alpha Beta Pruning. It helps in storing the length of the total available moves when the call was made for
    if (firstCall)
    {
        var originalAvailMovesLength = availMoves.length;
        if (originalAvailMovesLength == board.length)
            var maxPossibleResult = 0.5; // OriginalAvailMoves will be only 100, if it is the first move. And if it is first move, it is impossible to get reward of 1. The best the computer can do is, draw (0.5 reward). 
        else
            var maxPossibleResult = 1;
    }

    availMoves = getAvailableMoves(newBoard);

    var result = checkResult(newBoard, false); // It can return 4 values. 1 = Win, 0.5 = Draw, 0 = Game is on, -1 = Lose.
    if (result != 0) 
        return [result];

    var movesIndex = []; 
    var movesScore = []; 
    for (var i = 0; i < availMoves.length; i++)
    {

        var move = availMoves[i];  
        newBoard[move] = XorO; 
        availMoves.splice(availMoves.indexOf(Number(move)),1); 
        if (XorO == "O") // 1.) Yes 
            var reward = makeBotMove(newBoard, availMoves, "X", false); 
        else 
            var reward = makeBotMove(newBoard, availMoves, "O", false); 

        newBoard[move] = "-"; 

        availMoves.push(move);
        availMoves.sort();


        movesIndex.push(move); 
        movesScore.push(reward[0]); 
        var bestMove = [];
        if (originalAvailMovesLength == availMoves.length && Math.max(...movesScore) == maxPossibleResult)
        {
            bestMove[0] = Math.max(...movesScore);
            bestMove[1] = movesScore.indexOf(bestMove[0]);
            bestMove[1] = movesIndex[bestMove[1]];
            return bestMove;
        }
    }


    if (XorO == "O") 
        bestMove[0] = Math.max(...movesScore);
    else 
        bestMove[0] = Math.min(...movesScore);

    bestMove[1] = movesScore.indexOf(bestMove[0]);
    bestMove[1] = movesIndex[bestMove[1]];

    return bestMove;

}

如果最小化，就不能做这项工作。你们推荐哪种算法？一定不是很复杂，我到现在也不是那么好的程序员。

编辑：在10x10中，玩家需要连续5步才能获胜，而不是3步。

Answer 1

您的代码表明，您将继续执行递归调用，直到您赢/输或电路板已满。由于在专家之间的游戏中，一行5个位置并非微不足道，因此此搜索可能必须访问大多数绘图位置，我估计在10x10板上大约有10个^{100个位置，假设是100个！几乎是10158（但我们需要从所有的赢和输中减去）。无论如何，这么多的板是不现实的搜索，因为在可见的宇宙中原子的数量比这少。因此，不要等待代码完成。在你的有生之年不会。}

有两种通用方法可以减少计算一个好移动的时间：

1. 减少搜索树的深度
2. 缩小搜索树的宽度

对于第一个操作，您可以定义递归搜索的硬编码最大深度。如果你到达了那个深度，游戏还没有结束，那么调用一个评估函数，给当前棋盘一个分数，而不玩更多的动作。因此，它应该考虑一些简单的模式，比如连续3次，并让这些模式为最终得分做出贡献。这是一个启发式，意味着这是一个（希望是）好的猜测：价值应该在输赢两个极端之间。

对于第二个动作，您应该限制将进一步调查的移动次数。离开未访问的候选移动是相对远离已玩方块的移动。

此外，您还可以创建一个哈希表（在每次真正玩过的移动之后都是新的），该哈希表存储您已经评估过的棋盘，因此，如果您通过搜索树中的一个玩家的移动交换到达该哈希表，您就不会再进行该操作。确保哈希表也捕捉镜像或翻转的棋盘，这将减少游戏的前几步。

还有很多其他技巧，比如在搜索过程中跟踪“杀手”的动作。如果在搜索树的一个分支中发现有一个移动可以带来胜利或避免损失，那么也可以先在其他分支中尝试此移动。它可能导致阿尔法-贝塔机制的快速修剪。更一般地说，重要的是按照“质量”的降序访问您的移动。当然，在你分析一个动作之前，你不知道它有多好，但同样的，关于这个动作，你可以注意到一些静态的东西。在董事会角落里的动作肯定不如在董事会中间的动作好。。。等

搜索的一些变体首先进行1深度搜索，并使用结果根据评估结果对移动进行排序。然后进行两个深度的搜索，再次按照（更准确的）结果对移动进行排序。。。等，直到达到最终深度。这看起来可能需要做很多工作，但alpha-beta修剪将在移动顺序最佳时提供最大的好处，这将是整体效率的一个更具决定性的因素。