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

我使用了带有Alpha-Beta剪枝的最小最大算法来解决这两个游戏。在3×3的游戏中，游戏树非常小，算法运行得很好。

但在10×10的游戏中，耗时过长。代码在10分钟内甚至无法做出一个动作。我运行了算法，等了10分钟，仍然在计算，然后我只是关闭了浏览器标签页。（如果我让代码继续运行，可能会花费数小时、数天甚至数周的时间，哈哈）

我在几篇文章中读到，使用Alpha-Beta剪枝的最小最大算法可以轻松解决10×10或更大的井字游戏。这是否是错误的，还是我的代码有问题？

这是我的代码，但我认为理解它会很困难。但我觉得代码并不重要。我已经应用了最小最大算法和Alpha-Beta剪枝。还有什么我可以做的吗？

function makeBotMove(newBoard, availMoves, XorO, firstCall) { // newBoard存储棋盘状态在一个数组中。availMoves存储可用的移动在一个数组中（0-99）。XorO存储“X”或“O”，取决于谁的回合。firstCall用于判断调用是否在函数内部进行。我需要它来进行Alpha-Beta剪枝。它有助于在调用时存储总可用移动的长度。
    if (firstCall)
    {
        var originalAvailMovesLength = availMoves.length;
        if (originalAvailMovesLength == board.length)
            var maxPossibleResult = 0.5; // 如果originalAvailMoves只有100，说明这是第一步。如果是第一步，获得1的奖励是不可能的。计算机能做的最好结果是平局（0.5的奖励）。
        else
            var maxPossibleResult = 1;
    }
    availMoves = getAvailableMoves(newBoard);
    var result = checkResult(newBoard, false); // 它可以返回4个值。1 = 赢，0.5 = 平局，0 = 游戏继续，-1 = 输。
    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.) 是
            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;
}

如果最小最大算法无法完成任务，你们推荐使用哪种算法？它必须不太复杂，因为我目前的编程水平还不够高。

编辑：在10×10的游戏中，玩家需要连续放置5个棋子才能获胜，而不是3个。

回答：

你的代码显示，你会继续进行递归调用，直到有赢/输结果或者棋盘已满。由于在专家之间的游戏中，连续五子成行并不容易，这种搜索可能会访问到大部分平局位置，我估计在10×10的棋盘上，这将涉及到大约10¹⁰⁰个位置，因为100!接近10¹⁵⁸（但我们需要从中减去所有赢和输的情况）。无论如何，这样的棋盘数量是不现实的，因为可见宇宙中的原子数量都少于这个数。所以不要指望你的代码能完成。在你有生之年它是不会完成的。

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

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

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

对于第二种方法，你应该限制你将进一步调查的移动数量。候选移动可以是那些离已经下过的方块相对较远的移动。

此外，你可以创建一个哈希表（每次真正移动后重新创建），存储你已经评估过的棋盘，这样在你的搜索树中通过玩家移动的交换到达那里时，你就不需要再次进行这项工作。确保哈希表也能捕捉到镜像或旋转的棋盘，这将在游戏的前几步中减少搜索量。

还有许多其他技术，比如在搜索过程中跟踪“杀手”移动。如果在搜索树的一个分支中发现有一个移动可以带来胜利或避免失败，那么在其他分支中也首先尝试这个移动。这可能会导致Alpha-Beta机制快速剪枝。从更一般的角度来说，按“质量”降序访问你的移动非常重要。当然，你在分析之前并不知道一个移动有多好，但同样，你可以注意到一些关于移动的静态事情。棋盘角落的移动肯定不如中心的移动好，…等等。

一些搜索变体首先进行1深度的搜索，并使用该结果按评估结果对移动进行排序。然后进行2深度的搜索，再次按那个（更准确的）结果对移动进行排序，…等等，直到达到最终深度。这看起来像是很多工作，但当移动按最优顺序排列时，Alpha-Beta剪枝将带来最大的好处，而这将是整体效率的决定性因素。