AlphaBeta should not exceed beta in full window ?

[Freshblood]

Hello everybody.

I have experienced AlphaBeta algorithm with my own old chess engine and now i am trying to write new engine and i see that algorithim encounter beta cut-offs but in my opinion, this should never be occur if i don't use narrowed window. Am i wrong ? I am using int.MaxValue for beta and -int.MaxValue for alpha so what can cause a beta cut-offs ?

Here is c# codes.

Code: Select all

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

        var score = AlphaBeta&#40;alpha, beta, ply, bestLine&#41;;

        return new Result&#40;score, bestLine&#41;;
    &#125;
    int AlphaBeta&#40;int alpha, int beta, int ply, Stack<Move> bestLine&#41;
    &#123;
        if &#40;ply <= 0&#41; return Evaluation.Evaluate&#40;Board&#41;;
        var moves = Board.GenerateMoves&#40;);
        foreach &#40;var move in moves&#41;
        &#123;
            Board.MakeMove&#40;move&#41;;

            eval = -AlphaBeta&#40;-beta, -alpha, ply - 1, bestLine&#41;;

            Board.TakeBackMove&#40;move&#41;;

            if &#40;eval >= beta&#41;
            &#123;
                return beta;
            &#125;
            if &#40;eval > alpha&#41;
            &#123;
                alpha = eval;
                if &#40;ply == 1&#41; bestLine.Clear&#40;);

                bestLine.Push&#40;move&#41;;
            &#125;
        &#125;
        return alpha;
    &#125;
&#125;

[Mangar]

Hi,

I am not sure, if I got what you mean. But you do change alpha if Eval > alpha. In next iteration you call AlphaBeta with beta = -alpha; thus beta is no longer maxval at ply > 0 and may cause a cuttoff.

Greetings Volker

[hgm]

Hello everybody.

I have experienced AlphaBeta algorithm with my own old chess engine and now i am trying to write new engine and i see that algorithim encounter beta cut-offs but in my opinion, this should never be occur if i don't use narrowed window. Am i wrong ? I am using int.MaxValue for beta and -int.MaxValue for alpha so what can cause a beta cut-offs ?

The whole idea of alpha-beta is that you narrow the window as you search. Aspiration of the root window just tries to improve on that a little, by already starting with a limited window.

[Freshblood]

Can u just tell me, eval >= beta can be happen any in full window search ?

[hgm]

It cannot happen in the root. But, as Volker already mentioned, there are recursive calls to AlphaBeta(-beta, -alpha, ...) which do have a value -alpha which is different from int.MaxValue. So the window does not stay open in the deeper nodes.

[bob]

Can u just tell me, eval >= beta can be happen any in full window search ?

Got to, unless beta = +infinity. If by full-window you mean -inf, +inf, then no. If you just mean any window where alpha += beta - 1, then yes, you can always get scores > beta (or < alpha).

[Freshblood]

I was trying to say that i enter AlphaBeta algorithm with alpha=-infinity and beta=+infinity. So i understand from your answer that never score>=beta in algorithm. This is what i wanted to be sure. But still can't understand what can cause this.

[hgm]

You enter it with alpha=-infinity and beta=+infinity only in the root, and every first child of the root and its first (great-grand-)children. All younger brothers will NOT be entered with beta=+infinity.

If you want beta to be always +infinity, to prevent beta cutoffs,
you should change your code to recursively call

eval = Search(-beta, +int.MaxValue, ...)

[AlvaroBegue]

If you want beta to be always +infinity, to prevent beta cutoffs, you should change your code to recursively call

eval = Search(-beta, +int.MaxValue, ...)

But what's the point of implementing alpha-beta if you are going to examine the whole tree anyway? You may as well use plain minimax and not pass around bounds that you are not going to use.

[bob]

I was trying to say that i enter AlphaBeta algorithm with alpha=-infinity and beta=+infinity. So i understand from your answer that never score>=beta in algorithm. This is what i wanted to be sure. But still can't understand what can cause this.

A bug. I see this occasionally when I make a bad change. In Crafty, inf = 32767. No number of queens can make the score larger than that, since at most you can have 9, which is a score of 8100 in centipawns. But a bad array reference can pull up a score that is anywhere in the 64 bit range, which will blow that right out of the water.