about AlphaBeta algorithm

Question

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 ?

Edit:

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

OK, you are right on the MinValue/MaxValue thing.

I'm a bit rusty about NegaMax and AlphaBeta but when I see

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

You're testing > for both limits, that doesn't seem right.

Edit: It seems just a naming/understanding issue of sorts. Your AlphaBeta() method could be named more accurately NegaMaxWithAlphaBeta(). Because of the alternating roles of alpha and beta in NegaMax the naming of those parameters is not an exact match with MiniMax.

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

Yes it should occur. And it's only a beta-cutoff at the even ply-levels. At the odd levels, if (eval >= beta) tests for an alpha-cutoff.

if i don't use narrowed window.

I think you are using a narrowing alpha/beta window.

But maybe this answer can help you explain your problem better.

Answer 2

Notice that in your recursion you pass the parameters in reverse order:

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

Reversed from the way they are declared:

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

So they change roles at each ply. Alpha can be updated, and that's equivalent to a reduction in beta on deeper levels of the tree.

To me this looks like an odd mix of Alpha/Beta and Negamax since both players are trying to reduce the score, which is negated at each level.