3

私は自分の古いチェスエンジンでAlphaBetaアルゴリズムを経験しましたが、今は新しいエンジンを書き込もうとしています。algorithimはベータカットオフに遭遇しますが、私の意見では、狭いウィンドウを使用しない場合、これは発生しないはずです。私が間違っている ？私はint.MaxValueベータ版と-int.MaxValueアルファ版を使用していますが、ベータ版のカットオフを引き起こす可能性があるのは何ですか？

編集：

完全なコードはここにあります。

    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

OK、あなたは MinValue/MaxValue について正しいです。

NegaMax と AlphaBeta については少しさびていますが、

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

両方の制限をテスト>していますが、正しくないようです。

編集：それは、ある種の命名/理解の問題のようです。メソッドのAlphaBeta()名前をより正確に指定できますNegaMaxWithAlphaBeta()。NegaMax ではアルファとベータの役割が交互に変わるため、これらのパラメータの名前は MiniMax と完全に一致しません。

アルゴリズムがベータ カットオフに遭遇することがわかりますが、私の意見では、これは決して起こらないはずです

はい、発生するはずです。そして、それは偶数層レベルでのベータカットオフにすぎません. 奇数レベルでif (eval >= 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)

そのため、プライごとに役割が変わります。アルファは更新できます。これは、ツリーのより深いレベルでのベータの削減に相当します。

私には、これはアルファ/ベータとネガマックスの奇妙な組み合わせのように見えます。なぜなら、両方のプレイヤーが各レベルで無効になるスコアを減らそうとしているためです.

于 2010-07-28T17:06:57.303 に答える