Alpha/beta: can beta ever equal alpha?

[benvining]

My alpha/beta function looks like this:

Code: Select all

Eval alpha_beta(
        Eval alpha, const Eval beta,
        const Position& currentPosition,
        const size_t    depth)
    {
        // assert(beta > alpha);

        auto moves = moves::generate(currentPosition);

        order_moves_for_search(currentPosition, moves);

        for (const auto& move : moves) {
            const auto newPosition = game::after_move(currentPosition, move);

            const auto evaluation = depth > 1uz
                                      ? -alpha_beta(-beta, -alpha, newPosition, depth - 1uz)
                                      : -quiescence(-beta, -alpha, newPosition);

            if (evaluation >= beta)
                return beta;

            alpha = std::max(alpha, evaluation);
        }

        return alpha;
    }

The commented-out assertion was firing in situations where a capture that leads to mate was searched before mate-in-one due to my move ordering. Is this a bug in my code, should that assertion always hold?

[syzygy]

I guess the bug is in how you handle mates, which isn't shown in the quoted part of your code.

[benvining]

My evaluation function returns -INF if the side to move got checkmated (I'm in C++, so technically it's a bit of code like:

Code: Select all

using Eval = double;

static constexpr auto MIN = std::numeric_limits<Eval>::min();

Eval evaluate(const Position& pos)
{
  if (pos.is_checkmate())
    return MIN;
    
    // ...
}

And then in the alpha/beta, alpha begins as `MIN` and beta begins as `MAX` (which is `std::numeric_limits<Eval>::max()`).

Should the mate score be smaller than the absolute max of the Eval data type?

[Golden]

Ideally you probably don't want to have the checkmate score be the same as the INF bounds in alpha beta, the score should be strictly greater than alpha and strictly lower than beta. To see why, if you are using aspiration windows and you predict that the true score of the next search will be in the range 150-175 centipawns (alpha == 150 and beta == 175), if the search comes back and says 150 or 175, you can't be sure that the search came back with a true 150/175 since more than likely the true score was somewhere outside the bounds.

Also, is there a reason you are using double for eval? I'd wager that a lot could be going wrong there especially if you are compiling with -Ofast

[Ras]

Should the mate score be smaller than the absolute max of the Eval data type?

Typically, your range would look like this - only shown for the positive range here:
0 ... EVAL_MAX ... MAX
The range 0-EVAL_MAX is what you can get in game play, assuming weird things like all base pieces plus eight queen promoted pawns against a king and a shielding pawn. What I mean is the static evaluation of that position, not the mate related one.
[d]k2qqrrq/4bbnn/6qq/6qq/6qq/8/7P/7K w - - 0 1

And then you'd score a mate position (i.e. a mate in 0) with MAX. For each ply to get to that position, you subtract the ply count so that a mate in 1 would be MAX-1, mate in 2 MAX-3 and so on. This way, you make sure that your engine actually goes for a mate instead of merely detecting it and then shuffling around.

Now, a GUI shouldn't transmit a mate position (i.e. mate in 0) because there are no legal moves, that's the definition of a mate. But you can easily sort that out before starting the search if you want. The kicker is that even if the best move does deliver mate, that'll be scored as MAX-1. Your initial window, however, starts with MAX.

Note that you'll also need to take care of mate scores in your transposition table with translating back and forth betwen root-relative and node-relative mate scores. Because what was, say, a mate-in-2 in this move becomes a mate-in-1 in the next move from the GUI.

Also, you'd transmit scores differently depending on the range. In UCI, you'd use "score cp" in the 0 ... EVAL_MAX range, but "score mate" in the EVAL_MAX ... MAX range - properly adjusted, of course.

[syzygy]

My evaluation function returns -INF if the side to move got checkmated (I'm in C++, so technically it's a bit of code like:

But the node you are giving to alpha_beta() can already be a mate position.
Basically you should never call evaluate() on a mate position. Your search needs to know, i.e. figure out itself, that it is a checkmate.
You should also test for stalemate (and for draw by repetition, although this does not seem critical for the present discussion).

Code: Select all

using Eval = double;

static constexpr auto MIN = std::numeric_limits<Eval>::min();

Eval evaluate(const Position& pos)
{
  if (pos.is_checkmate())
    return MIN;
    
    // ...
}

And then in the alpha/beta, alpha begins as `MIN` and beta begins as `MAX` (which is `std::numeric_limits<Eval>::max()`).

You need to adjust the mate score by the distance to the root. Otherwise you cannot distinguish between longer and shorter mates.

[syzygy]

Also, is there a reason you are using double for eval? I'd wager that a lot could be going wrong there especially if you are compiling with -Ofast

And switching the sign of the minimum value of a double is probably not going to end well!!
I suppose this explains the failure of the assert. The mate value's sign is messed up.

The OP should switch to using ints (and avoid the limits of the type's range).

[benvining]

Thanks for the input everyone. I've switched to using ints for evaluation values, and I'm now scoring mate positions as

Code: Select all

(MAX - plyFromRoot) * -1

, and now that assertion passes.

[hgm]

My alpha/beta function looks like this:

Code: Select all

Eval alpha_beta(
        Eval alpha, const Eval beta,
        const Position& currentPosition,
        const size_t    depth)
    {
        // assert(beta > alpha);

        auto moves = moves::generate(currentPosition);

        order_moves_for_search(currentPosition, moves);

        for (const auto& move : moves) {
            const auto newPosition = game::after_move(currentPosition, move);

            const auto evaluation = depth > 1uz
                                      ? -alpha_beta(-beta, -alpha, newPosition, depth - 1uz)
                                      : -quiescence(-beta, -alpha, newPosition);

            if (evaluation >= beta)
                return beta;

            alpha = std::max(alpha, evaluation);
        }

        return alpha;
    }

The commented-out assertion was firing in situations where a capture that leads to mate was searched before mate-in-one due to my move ordering. Is this a bug in my code, should that assertion always hold?

If alpha >= beta you take a beta cutoff. Which means that you would not make any recursive call to a search routine that would pass these alpha and beta.

So yes, you have a bug, and fail to execute a beta cutoff when you should. What your mate score is has nothing to do with this. Whenever you increase alpha, you should test to make sure it remained below beta, or take a cutoff.

[syzygy]

My alpha/beta function looks like this:

Code: Select all

            if (evaluation >= beta)
                return beta;

            alpha = std::max(alpha, evaluation);

If alpha >= beta you take a beta cutoff. Which means that you would not make any recursive call to a search routine that would pass these alpha and beta.

So yes, you have a bug, and fail to execute a beta cutoff when you should. What your mate score is has nothing to do with this. Whenever you increase alpha, you should test to make sure it remained below beta, or take a cutoff.

He takes the beta cutoff.