3

我用自己的旧国际象棋引擎体验过 AlphaBeta 算法，现在我正在尝试编写新引擎，我看到算法遇到了 beta 截止，但我认为，如果我不使用窄窗口，这永远不会发生。我错了吗 ？我正在使用int.MaxValuebeta 和-int.MaxValuealpha 那么什么会导致 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;
    }
}
4

2 回答 2

1

好的，你在 MinValue/MaxValue 上是对的。

我对 NegaMax 和 AlphaBeta 有点生疏，但是当我看到

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

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

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

我看到算法遇到 beta 截止，但在我看来，这不应该发生

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

如果我不使用窄窗。

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

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

于 2010-07-28T12:37:45.430 回答
1

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

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

与它们的声明方式相反：

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

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

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

于 2010-07-28T17:06:57.303 回答