c# - 关于 AlphaBeta 算法

Question

我用自己的旧国际象棋引擎体验过 AlphaBeta 算法，现在我正在尝试编写新引擎，我看到该算法遇到 beta 截止，但在我看来，如果我不使用 narrowed，这永远不会发生 window 。我错了吗 ？我将 int.MaxValue 用于 beta，将 -int.MaxValue 用于 alpha 那么什么会导致 beta 截止？

编辑:

完整代码在这里。

    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)
   {
   }

您正在测试 >对于这两个限制，这似乎都不对。

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

i see that algorithim encounter beta cut-offs but in my opinion, this should never occur

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

if i don't use narrowed window.

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

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