javascript - Minimax Alpha Beta Pruning Algorithm 解决 Tic Tac Toe(10x10 棋盘)需要花费太多时间

Question

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

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

但是在 10x10 中，它需要太多时间。该代码甚至无法在 10 分钟内完成一步操作。我运行了算法，等了 10 分钟，仍然在计算，然后我就关闭了浏览器选项卡。 (如果我让代码运行，可能需要数小时、数天、数周的时间，哈哈)

我在几篇文章中读到，带 Alpha Beta 剪枝的 Minimax 可以轻松解决 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 行不是微不足道的，此搜索可能必须访问大部分绘图位置，我估计这将达到大约 10¹⁰⁰ 个位置10x10 板，给定 100!几乎是 10¹⁵⁸(但我们需要从这些中减去所有的输赢)。无论如何，这样多的板子要搜索起来是不现实的，因为可见宇宙中的原子数比这个少。所以不要等待你的代码完成。它不会在你的一生中。

有两种通用方法可以减少花在计算好着法上的时间:

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

对于第一个操作，您可以定义递归搜索的硬编码最大深度。如果你到达那个深度并且游戏还没有结束，那么调用一个应该给当前棋盘打分的评估函数，而不需要下更多的棋子。因此，它应该查看一些简单的模式，例如连续 3 次，并让这些对最终得分有所贡献。这是一种启发式方法，意味着它是一个(希望如此)好的猜测:该值应该介于赢和输的两个极端之间。

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

此外，您可以制作一个哈希表(在每次真正下完棋后新建)，用于存储您已经评估过的棋盘，这样您就不必再做这项工作，以防您通过一个玩家的棋步交换到达那里你的搜索树。确保哈希表也捕获镜像或翻转的棋盘，这将减少游戏的前几步。

还有许多其他技术，例如在搜索过程中跟踪“ killer ” Action 。如果在搜索树的一个分支中发现有一个可以带来胜利或避免损失的着法，那么也首先在其他分支中尝试这个着法。它可能导致 alpha-beta 机制的快速 trim 。更一般地说，按“质量”的降序访问您的 Action 很重要。当然，在你分析之前你不知道一个 Action 有多好，但是同样，你可以注意到一些关于 Action 的静态事情。在棋盘 Angular 落的一步肯定不如在中心的一步，等等。

搜索的某些变体首先进行 1 深度搜索，然后使用结果根据该评估结果对移动进行排序。然后进行 2 深度搜索，并再次根据该(更准确的)结果对移动进行排序，...等，直到达到最终深度。这可能看起来像很多工作，但 alpha-beta 剪枝将在移动以最佳顺序排列时提供最大的好处，这将成为整体效率的更具决定性的因素。