Minimax Alpha Beta Pruning Algorithm 解决 Tic Tac Toe（10x10 棋盘）需要花费太多时间

Question

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

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

但是在 10x10 中，它需要太多时间。该代码甚至无法在 10 分钟内完成一步操作。我运行算法，等了10分钟，还在计算，然后我就关闭了浏览器标签。（如果我让代码运行大声笑）

可能甚至需要数小时、数天、数周

我在几篇文章中读到，带 Alpha Beta P运行ing 的 Minimax 可以轻松解决 10x10 或更大的 Tic Tac Toe。是假的，还是我的代码不好？

这是我的代码，但我认为，很难理解它。但代码并不重要，我猜。我应用了 Minimax + Alpha Beta P运行ing。我还可以做些什么？

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

您的代码显示您会继续进行递归调用，直到您有 win/loss 或棋盘已满。由于在专家之间的游戏中制作 5 行不是微不足道的，因此此搜索可能必须访问大部分绘图位置，我估计这将达到大约 10¹⁰⁰在 10x10 棋盘上的位置，给定 100！几乎是 10¹⁵⁸（但我们需要从这些中减去所有的输赢）。无论如何，这样多的板子要搜索起来是不现实的，因为可见宇宙中的原子数比这个少。所以不要等待你的代码完成。这辈子都不会。

有两种通用方法可以减少计算好着法所花费的时间：

减少搜索树的深度
减少搜索树的宽度

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

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

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

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

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

Minimax Alpha Beta Pruning Algorithm 解决 Tic Tac Toe（10x10 棋盘）需要花费太多时间

Minimax Alpha Beta Pruning Algorithm takes too much time to solve Tic Tac Toe (10x10 board)

javascript

algorithm

machine-learning

minimax

alpha-beta-pruning