negamax alpha beta search doesn't always return mating score

[maksimKorzh]

Dear community

I have a humble help request of more like showing me a path rather than a concrete solution, but still I'll describe the issue.
I've created 30+ youtube video series on creating a simple chess engine from scratch.
I thought I'm so cool... until reached the negamax alphabeta search...
While understanding move generation process really clear (as series shows) I've horribly realized that when it came to the search I always copypasted it...
I know it's a shame... So from now on I really really want to master it and looking for a guidance at this point.

Particular technical issue I encounter: mating score and associated move are not always returned correclty, it seems like it depends on search depth somehow, e.g. at depth 5 it doesn't find mate in 1 while at depth 2 it does.

I have a very very basic negamax failhard framework (copypasted numerous times(((( ):

Code: Select all

// search position
int search_position(int alpha, int beta, int depth)
{
    // legal moves
    int legal_moves = 0;
    
    // best move
    int best_so_far = 0;
    
    // old alpha
    int old_alpha = alpha;

    // escape condition
    if  (!depth)
        // search for calm position before evaluation
        return quiescence_search(alpha, beta);

    // create move list variable
    moves move_list[1];
    
    // generate moves
    generate_moves(move_list);
    
    // loop over the generated moves
    for (int move_count = 0; move_count < move_list->count; move_count++)
    {
        // define board state variable copies
        int board_copy[128], king_square_copy[2];
        int side_copy, enpassant_copy, castle_copy;
        
        // copy board state
        memcpy(board_copy, board, 512);
        side_copy = side;
        enpassant_copy = enpassant;
        castle_copy = castle;
        memcpy(king_square_copy, king_square,8);
        
        // make only legal moves
        if (!make_move(move_list->moves[move_count], all_moves))
            // skip illegal move
            continue;
        
        // increment legal moves
        legal_moves++;
        
        // recursive call
        int score = -search_position(-beta, -alpha, depth - 1);
        
        // restore board position
        memcpy(board, board_copy, 512);
        side = side_copy;
        enpassant = enpassant_copy;
        castle = castle_copy;
        memcpy(king_square, king_square_copy,8);
        
        //  fail hard beta-cutoff
        if (score >= beta)
             return beta;
        
        // alpha acts like max in MiniMax
        if (score > alpha)
        {
            // set alpha score
            alpha = score;
            
            // store current best move
            best_so_far = move_list->moves[move_count];
        }
    }
    
    // if no legal moves
    if (!legal_moves)
    {
        // check mate detection
        if (is_square_attacked(king_square[side], side ^ 1))
            return -49000;
        
        // stalemate detection
        else
            return 0;
    }
    
    // associate best score with best move
    if (alpha != old_alpha)
        best_move = best_so_far;
    
    // return alpha score
    return alpha;
}

Finally, to get an idea of how it behaves you can watch this video:

it has timestamps in the description pointing out where the issue occurs.

I'm not asking for a working solution but I would be very very grateful if you guys kindly point me the right direction. Thanks in advance!

[Joost Buijs]

Dear community

I have a humble help request of more like showing me a path rather than a concrete solution, but still I'll describe the issue.
I've created 30+ youtube video series on creating a simple chess engine from scratch.
I thought I'm so cool... until reached the negamax alphabeta search...
While understanding move generation process really clear (as series shows) I've horribly realized that when it came to the search I always copypasted it...
I know it's a shame... So from now on I really really want to master it and looking for a guidance at this point.

Particular technical issue I encounter: mating score and associated move are not always returned correclty, it seems like it depends on search depth somehow, e.g. at depth 5 it doesn't find mate in 1 while at depth 2 it does.

I have a very very basic negamax failhard framework (copypasted numerous times(((( ):

Code: Select all

// search position
int search_position(int alpha, int beta, int depth)
{
    // legal moves
    int legal_moves = 0;
    
    // best move
    int best_so_far = 0;
    
    // old alpha
    int old_alpha = alpha;

    // escape condition
    if  (!depth)
        // search for calm position before evaluation
        return quiescence_search(alpha, beta);

    // create move list variable
    moves move_list[1];
    
    // generate moves
    generate_moves(move_list);
    
    // loop over the generated moves
    for (int move_count = 0; move_count < move_list->count; move_count++)
    {
        // define board state variable copies
        int board_copy[128], king_square_copy[2];
        int side_copy, enpassant_copy, castle_copy;
        
        // copy board state
        memcpy(board_copy, board, 512);
        side_copy = side;
        enpassant_copy = enpassant;
        castle_copy = castle;
        memcpy(king_square_copy, king_square,8);
        
        // make only legal moves
        if (!make_move(move_list->moves[move_count], all_moves))
            // skip illegal move
            continue;
        
        // increment legal moves
        legal_moves++;
        
        // recursive call
        int score = -search_position(-beta, -alpha, depth - 1);
        
        // restore board position
        memcpy(board, board_copy, 512);
        side = side_copy;
        enpassant = enpassant_copy;
        castle = castle_copy;
        memcpy(king_square, king_square_copy,8);
        
        //  fail hard beta-cutoff
        if (score >= beta)
             return beta;
        
        // alpha acts like max in MiniMax
        if (score > alpha)
        {
            // set alpha score
            alpha = score;
            
            // store current best move
            best_so_far = move_list->moves[move_count];
        }
    }
    
    // if no legal moves
    if (!legal_moves)
    {
        // check mate detection
        if (is_square_attacked(king_square[side], side ^ 1))
            return -49000;
        
        // stalemate detection
        else
            return 0;
    }
    
    // associate best score with best move
    if (alpha != old_alpha)
        best_move = best_so_far;
    
    // return alpha score
    return alpha;
}

Finally, to get an idea of how it behaves you can watch this video:

it has timestamps in the description pointing out where the issue occurs.

I'm not asking for a working solution but I would be very very grateful if you guys kindly point me the right direction. Thanks in advance!

One of the things I notice is that you don't update the best move when there is a beta cut-off, but if everything else is right it should still return the mate score.

Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?

[maksimKorzh]

Dear community

I have a humble help request of more like showing me a path rather than a concrete solution, but still I'll describe the issue.
I've created 30+ youtube video series on creating a simple chess engine from scratch.
I thought I'm so cool... until reached the negamax alphabeta search...
While understanding move generation process really clear (as series shows) I've horribly realized that when it came to the search I always copypasted it...
I know it's a shame... So from now on I really really want to master it and looking for a guidance at this point.

Particular technical issue I encounter: mating score and associated move are not always returned correclty, it seems like it depends on search depth somehow, e.g. at depth 5 it doesn't find mate in 1 while at depth 2 it does.

I have a very very basic negamax failhard framework (copypasted numerous times(((( ):

Code: Select all

// search position
int search_position(int alpha, int beta, int depth)
{
    // legal moves
    int legal_moves = 0;
    
    // best move
    int best_so_far = 0;
    
    // old alpha
    int old_alpha = alpha;

    // escape condition
    if  (!depth)
        // search for calm position before evaluation
        return quiescence_search(alpha, beta);

    // create move list variable
    moves move_list[1];
    
    // generate moves
    generate_moves(move_list);
    
    // loop over the generated moves
    for (int move_count = 0; move_count < move_list->count; move_count++)
    {
        // define board state variable copies
        int board_copy[128], king_square_copy[2];
        int side_copy, enpassant_copy, castle_copy;
        
        // copy board state
        memcpy(board_copy, board, 512);
        side_copy = side;
        enpassant_copy = enpassant;
        castle_copy = castle;
        memcpy(king_square_copy, king_square,8);
        
        // make only legal moves
        if (!make_move(move_list->moves[move_count], all_moves))
            // skip illegal move
            continue;
        
        // increment legal moves
        legal_moves++;
        
        // recursive call
        int score = -search_position(-beta, -alpha, depth - 1);
        
        // restore board position
        memcpy(board, board_copy, 512);
        side = side_copy;
        enpassant = enpassant_copy;
        castle = castle_copy;
        memcpy(king_square, king_square_copy,8);
        
        //  fail hard beta-cutoff
        if (score >= beta)
             return beta;
        
        // alpha acts like max in MiniMax
        if (score > alpha)
        {
            // set alpha score
            alpha = score;
            
            // store current best move
            best_so_far = move_list->moves[move_count];
        }
    }
    
    // if no legal moves
    if (!legal_moves)
    {
        // check mate detection
        if (is_square_attacked(king_square[side], side ^ 1))
            return -49000;
        
        // stalemate detection
        else
            return 0;
    }
    
    // associate best score with best move
    if (alpha != old_alpha)
        best_move = best_so_far;
    
    // return alpha score
    return alpha;
}

Finally, to get an idea of how it behaves you can watch this video:

it has timestamps in the description pointing out where the issue occurs.

I'm not asking for a working solution but I would be very very grateful if you guys kindly point me the right direction. Thanks in advance!

One of the things I notice is that you don't update the best move when there is a beta cut-off, but if everything else is right it should still return the mate score.

Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?

re: Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?
Yes, absolutely because I've passed the perft test.

re: One of the things I notice is that you don't update the best move when there is a beta cut-off
- Should I? Sorry for a dumb question, but my understanding of beta cutoffs is limited like... skip calculating the branch because it gives a loosing score. So I'm not sure what exactly it returns.

so you mean something like:

Code: Select all

//  fail hard beta-cutoff
if (score >= beta)
{
    best_move = best_so_far;
    return beta;
}

So can I say that the current version would work in brute force negamax when we associate bestscore (alpha equivalent) with best move?

[odomobo]

Code: Select all

    // associate best score with best move
    if (alpha != old_alpha)
        best_move = best_so_far;

Is best_move a global? If yes, then shouldn't we only be setting this at the root of the search? Otherwise this might get set on moves at nearly the leaf of the tree, and should often be suggesting illegal moves.

[Sven]

Main issues are:

1) "best_move" is a global variable which you seem to overwrite from everywhere in the tree. This can often lead to random results, not limited to mate scores. So you'd better make "best_move" an output parameter (in C++ "int & best_move" or in C/C++ "int * best_move"). It will be redundant for all depths except the root, though, since you normally only consume the score of the subtree. There are at least two solutions to avoid this redundancy: either have a separate search function for the root (and maintain "best_move" only there), or track the whole principal variation (PV) as a result parameter at each depth. The former is easy to quickly get a working search (if you do not accept the redundancy I mentioned), the latter is the future way to go since you will certainly want to be able to let your search report its progress somehow. Whenever you get a new best score within the alpha-beta window (so > alpha and < beta), you update the PV of the current node by concatenating the current move with the PV that was returned from its subtree.

2) Distance to mate is unknown for your search since you always return "-49000" whenever you detect that the side to move is mated. A typical solution is to simply return "-(49000 - distance_to_root)" instead. This ensures that the moving side will always favor moves leading to a shorter mate, if there is any forced mate available at all. The "distance_to_root" value (often simply called "ply") is an additional parameter of your search_position() function. Obviously you call search_position() with ply=0 at the root, and with ply+1 in the recursive call.

There are some more points to comment on, where none of them is really critical, nor related to your main goal of getting correct mate scores.

- Improve your make/unmake code: Your copy&make approach is fine in general. But I would change two things to improve it:
a) put all board-related variables into one struct (or class) - to get source code that is easier to read,
b) think about saving all board copies on a stack that is maintained outside of "search_position()" and passed in as a parameter, and then simply moving the stack pointer back one level when doing the "unmake" - to avoid a second copying action.

- Avoid redundancy of "best_so_far" and "old_alpha": both variables are not really necessary in this simple implementation of a full-widh fail-hard alpha-beta search. If your move loop terminates then "best_so_far" is already the best move of the current node, the condition "alpha != old_alpha" which you use for assigning "best_move = best_so_far" is always false if no subtree score was sufficient to improve alpha. So in conjunction with my point 1) above you could think about removing "old_alpha" and about melting "best_so_far" and "best_move" into just one variable.

[Sven]

One of the things I notice is that you don't update the best move when there is a beta cut-off, but if everything else is right it should still return the mate score.

Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?

re: Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?
Yes, absolutely because I've passed the perft test.

re: One of the things I notice is that you don't update the best move when there is a beta cut-off
- Should I? Sorry for a dumb question, but my understanding of beta cutoffs is limited like... skip calculating the branch because it gives a loosing score. So I'm not sure what exactly it returns.

so you mean something like:

Code: Select all

//  fail hard beta-cutoff
if (score >= beta)
{
    best_move = best_so_far;
    return beta;
}

So can I say that the current version would work in brute force negamax when we associate bestscore (alpha equivalent) with best move?

"best_move" does not need to be updated on a beta cutoff since the parent node will discard the move leading to this subtree (that is the subject of a cutoff) so our "best_move" would not be propagated towards the root, it will never be part of the PV.

[Joost Buijs]

One of the things I notice is that you don't update the best move when there is a beta cut-off, but if everything else is right it should still return the mate score.

Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?

re: Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?
Yes, absolutely because I've passed the perft test.

re: One of the things I notice is that you don't update the best move when there is a beta cut-off
- Should I? Sorry for a dumb question, but my understanding of beta cutoffs is limited like... skip calculating the branch because it gives a loosing score. So I'm not sure what exactly it returns.

so you mean something like:

Code: Select all

//  fail hard beta-cutoff
if (score >= beta)
{
    best_move = best_so_far;
    return beta;
}

So can I say that the current version would work in brute force negamax when we associate bestscore (alpha equivalent) with best move?

"best_move" does not need to be updated on a beta cutoff since the parent node will discard the move leading to this subtree (that is the subject of a cutoff) so our "best_move" would not be propagated towards the root, it will never be part of the PV.

[Joost Buijs]

One of the things I notice is that you don't update the best move when there is a beta cut-off, but if everything else is right it should still return the mate score.

Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?

re: Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?
Yes, absolutely because I've passed the perft test.

re: One of the things I notice is that you don't update the best move when there is a beta cut-off
- Should I? Sorry for a dumb question, but my understanding of beta cutoffs is limited like... skip calculating the branch because it gives a loosing score. So I'm not sure what exactly it returns.

so you mean something like:

Code: Select all

//  fail hard beta-cutoff
if (score >= beta)
{
    best_move = best_so_far;
    return beta;
}

So can I say that the current version would work in brute force negamax when we associate bestscore (alpha equivalent) with best move?

"best_move" does not need to be updated on a beta cutoff since the parent node will discard the move leading to this subtree (that is the subject of a cutoff) so our "best_move" would not be propagated towards the root, it will never be part of the PV.

This might be so, but you'll need it if this is the root-node and there is no parent node, which is absolutely not clear from this example.
You can argue that there will never be a beta cutoff at the root, but it solely depends upon how you handle the root.

[Joost Buijs]

Dear community

I have a humble help request of more like showing me a path rather than a concrete solution, but still I'll describe the issue.
I've created 30+ youtube video series on creating a simple chess engine from scratch.
I thought I'm so cool... until reached the negamax alphabeta search...
While understanding move generation process really clear (as series shows) I've horribly realized that when it came to the search I always copypasted it...
I know it's a shame... So from now on I really really want to master it and looking for a guidance at this point.

Particular technical issue I encounter: mating score and associated move are not always returned correclty, it seems like it depends on search depth somehow, e.g. at depth 5 it doesn't find mate in 1 while at depth 2 it does.

I have a very very basic negamax failhard framework (copypasted numerous times(((( ):

Code: Select all

// search position
int search_position(int alpha, int beta, int depth)
{
    // legal moves
    int legal_moves = 0;
    
    // best move
    int best_so_far = 0;
    
    // old alpha
    int old_alpha = alpha;

    // escape condition
    if  (!depth)
        // search for calm position before evaluation
        return quiescence_search(alpha, beta);

    // create move list variable
    moves move_list[1];
    
    // generate moves
    generate_moves(move_list);
    
    // loop over the generated moves
    for (int move_count = 0; move_count < move_list->count; move_count++)
    {
        // define board state variable copies
        int board_copy[128], king_square_copy[2];
        int side_copy, enpassant_copy, castle_copy;
        
        // copy board state
        memcpy(board_copy, board, 512);
        side_copy = side;
        enpassant_copy = enpassant;
        castle_copy = castle;
        memcpy(king_square_copy, king_square,8);
        
        // make only legal moves
        if (!make_move(move_list->moves[move_count], all_moves))
            // skip illegal move
            continue;
        
        // increment legal moves
        legal_moves++;
        
        // recursive call
        int score = -search_position(-beta, -alpha, depth - 1);
        
        // restore board position
        memcpy(board, board_copy, 512);
        side = side_copy;
        enpassant = enpassant_copy;
        castle = castle_copy;
        memcpy(king_square, king_square_copy,8);
        
        //  fail hard beta-cutoff
        if (score >= beta)
             return beta;
        
        // alpha acts like max in MiniMax
        if (score > alpha)
        {
            // set alpha score
            alpha = score;
            
            // store current best move
            best_so_far = move_list->moves[move_count];
        }
    }
    
    // if no legal moves
    if (!legal_moves)
    {
        // check mate detection
        if (is_square_attacked(king_square[side], side ^ 1))
            return -49000;
        
        // stalemate detection
        else
            return 0;
    }
    
    // associate best score with best move
    if (alpha != old_alpha)
        best_move = best_so_far;
    
    // return alpha score
    return alpha;
}

Finally, to get an idea of how it behaves you can watch this video:

it has timestamps in the description pointing out where the issue occurs.

I'm not asking for a working solution but I would be very very grateful if you guys kindly point me the right direction. Thanks in advance!

One of the things I notice is that you don't update the best move when there is a beta cut-off, but if everything else is right it should still return the mate score.

Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?

re: Are you sure that the move-generator, the check for illegal moves and the is_square_attacked function are working in the way they should?
Yes, absolutely because I've passed the perft test.

re: One of the things I notice is that you don't update the best move when there is a beta cut-off
- Should I? Sorry for a dumb question, but my understanding of beta cutoffs is limited like... skip calculating the branch because it gives a loosing score. So I'm not sure what exactly it returns.

so you mean something like:

Code: Select all

//  fail hard beta-cutoff
if (score >= beta)
{
    best_move = best_so_far;
    return beta;
}

So can I say that the current version would work in brute force negamax when we associate bestscore (alpha equivalent) with best move?

At fist glance I would say it should work if everything else is correct, and I would update best_sofar also when there is a beta cutoff if you want to store it in a transposition-table in the future.

[Joost Buijs]

I would say something like:

Code: Select all

if (score > alpha)
{
	best_sofar = xxx;
	if (score >= beta) return score; // or return beta for fail hard
	alpha = score;
}

Probably better to introduce a ply counter as well, since you only have to update the best_move at ply 0, I assume best_move is the move that you want to play eventually.

Code: Select all

if (score > alpha)
{
	best_sofar = xxx;
	if (ply == 0) best_move = best_sofar;
	if (score >= beta) return score; // or return beta for fail hard
	alpha = score;
}