关于AlphaBeta算法

Question

我用我自己的旧国际象棋引擎体验过 AlphaBeta 算法，现在我正在尝试编写新引擎，我看到算法遇到了 beta 截止，但在我看来，如果我不使用缩小的窗口，这种情况永远不会发生。我错了吗？我使用 int.MaxValue 作为 beta 版本，使用 -int.MaxValue 作为 alpha 版本，那么什么会导致 beta 截止呢？

编辑：

Full code is here.

    public Result Search(int maxDepth)
    {
        int alpha = -int.MaxValue, beta = int.MaxValue, ply = maxDepth;
        var bestLine = new Stack<Move>();

        var score = AlphaBeta(alpha, beta, ply, bestLine);

        return new Result(score, bestLine);
    }
    int AlphaBeta(int alpha, int beta, int ply, Stack<Move> bestLine)
    {
        if (ply <= 0) return Evaluation.Evaluate(Board);
        var moves = Board.GenerateMoves();
        foreach (var move in moves)
        {
            Board.MakeMove(move);

            eval = -AlphaBeta(-beta, -alpha, ply - 1, bestLine);

            Board.TakeBackMove(move);

            if (eval >= beta)
            {
                return beta;
            }
            if (eval > alpha)
            {
                alpha = eval;
                if (ply == 1) bestLine.Clear();

                bestLine.Push(move);
            }
        }
        return alpha;
    }
}

Answer 1

好的，您对 MinValue/MaxValue 的看法是正确的。

<罢工>
我对 NegaMax 和 AlphaBeta 有点生疏，但是当我看到

   if (eval >= beta)
   {
       return beta;
   }
   if (eval > alpha)
   {
   }

You're test >这两个限制时，这似乎不对。
编辑

：这似乎只是一个命名/理解问题。您的 AlphaBeta() 方法可以更准确地命名为 NegaMaxWithAlphaBeta()。由于 NegaMax 中 alpha 和 beta 的角色交替，这些参数的命名与 MiniMax 并不完全匹配。

我发现算法遇到了 beta 截止，但在我看来，这种情况永远不应该发生

，是的，它应该发生。这只是偶数层的贝塔截止值。在奇数级别，if (eval >= beta) 测试 alpha 截止值。

如果我不使用缩小的窗口。

我认为您正在使用缩小的 alpha/beta 窗口。

但也许这个答案可以帮助您更好地解释您的问题。

Answer 2

请注意，在递归中，您以相反的顺序传递参数：

eval = -AlphaBeta(-beta, -alpha, ply - 1, bestLine);

与声明它们的方式相反：

int AlphaBeta(int alpha, int beta, int ply, Stack bestLine)

因此它们在每一层都会改变角色。 Alpha 可以更新，这相当于在树的更深层次上减少 beta。

对我来说，这看起来像是 Alpha/Beta 和 Negamax 的奇怪组合，因为两个玩家都试图降低分数，而分数在每个级别都会被否定。