negamax alpha beta search doesn't always return mating score

[maksimKorzh]

Mate distance solution actually solved my issue! Thank you so much!

I understand that global variables are bad idea, but let's say we drop alpha beta and leave the brute force negamax (this time I wrote it myself, no copypaste):

Code: Select all

int search(int depth)
{

    if (!depth)
        return evaluate_position();

    int best_score = -50000;
    int best_so_far;
    int legal_moves = 0;
    
    moves move_list[1];
    generate_moves(move_list);
    
    for (int count = 0; count < move_list->count; count++)  {
        
        copy_board();
        ply++;
        if(!make_move(move_list->moves[count], all_moves))
        {
            ply--;
            continue;
        }
        
        
        legal_moves++;
        int score = -search(depth - 1);
        take_back();
        
        if (score > best_score)
        {
            best_so_far = move_list->moves[count];
            best_score = score;
            printf("best so far: %s%s  score: %d  ply: %d\n", square_to_coords[get_move_source(move_list->moves[count])],
                                          square_to_coords[get_move_target(move_list->moves[count])],
                                          best_score, ply);
        }
        
        ply--;
    }
    
    best_move = best_so_far;
    
    if (!legal_moves)
    {
        if (is_square_attacked(king_square[side], side ^ 1))
            return -49000 + ply;

        else
            return 0;
    }
    
    return best_score;
}

at least this solution ALWAYS returns mate regardless of search depth.

In your last example and the one I just showed the evaluation function is called at depth 0 instead of quiescence.
If you want to have it working properly you also have to check for a mate/stalemate condition in the evaluation/quiescence, which is omitted now.

Obviously I'm aware the quiescence search is absolutely essential.
But I'm just wondering - how to implement quiescence search for bruteforce negamax?
I mean when we work inside alpha beta framework we can simply forward alpha and beta scores from negamax to quiescence, but how we can implement it without alpha beta?
Should we assume that best score works as alpha and pass it to quiescence and limit the quiescence depth by ply instead of a beta cutoff since beta is not available in non alha beta implementations?

[maksimKorzh]

I mean something like:

Code: Select all

int quiescence()
{
    if (ply > 3)
        return evaluate_position();
    
    int best_score = -50000;
    
    int eval = evaluate_position();
    
    if (best_score < eval)
        best_score = eval;
    
    // create move list
    moves movelist[1];
    
    // generate moves for given side to move
    generate_moves(movelist);
    
    // loop over generated moves
    for (int count = 0; count < movelist->count; count++)
    {
        // snapshote current board position
        copy_board();
        
        // init move
        int move = movelist->moves[count];
        
        // increment ply
        ply++;
        
        // make only legal moves
        if (!make_move(move, only_captures))
        {
            // decrement ply
            ply--;
            continue;
        }
        
        // recursive negamax call
        int score = -quiescence();
        
        // take move back
        take_back();
        
        // decrement ply
        ply--;
        
        // found better move
        if (score > best_score)
            // update the score
            best_score = score;
    }
    
    // return best score
    return best_score;
}

Makes it play reasonable chess (I mean does not give pieces away) in 1ply depth

[Joost Buijs]

Mate distance solution actually solved my issue! Thank you so much!

I understand that global variables are bad idea, but let's say we drop alpha beta and leave the brute force negamax (this time I wrote it myself, no copypaste):

Code: Select all

int search(int depth)
{

    if (!depth)
        return evaluate_position();

    int best_score = -50000;
    int best_so_far;
    int legal_moves = 0;
    
    moves move_list[1];
    generate_moves(move_list);
    
    for (int count = 0; count < move_list->count; count++)  {
        
        copy_board();
        ply++;
        if(!make_move(move_list->moves[count], all_moves))
        {
            ply--;
            continue;
        }
        
        
        legal_moves++;
        int score = -search(depth - 1);
        take_back();
        
        if (score > best_score)
        {
            best_so_far = move_list->moves[count];
            best_score = score;
            printf("best so far: %s%s  score: %d  ply: %d\n", square_to_coords[get_move_source(move_list->moves[count])],
                                          square_to_coords[get_move_target(move_list->moves[count])],
                                          best_score, ply);
        }
        
        ply--;
    }
    
    best_move = best_so_far;
    
    if (!legal_moves)
    {
        if (is_square_attacked(king_square[side], side ^ 1))
            return -49000 + ply;

        else
            return 0;
    }
    
    return best_score;
}

at least this solution ALWAYS returns mate regardless of search depth.

In your last example and the one I just showed the evaluation function is called at depth 0 instead of quiescence.
If you want to have it working properly you also have to check for a mate/stalemate condition in the evaluation/quiescence, which is omitted now.

Obviously I'm aware the quiescence search is absolutely essential.
But I'm just wondering - how to implement quiescence search for bruteforce negamax?
I mean when we work inside alpha beta framework we can simply forward alpha and beta scores from negamax to quiescence, but how we can implement it without alpha beta?
Should we assume that best score works as alpha and pass it to quiescence and limit the quiescence depth by ply instead of a beta cutoff since beta is not available in non alha beta implementations?

Yes, you may assume that best_score works as alpha, completely remove beta and the (score >= beta) cut_off condition.

Limiting the quiescence depth by ply is not a good idea because you want to evaluate at the point where all captures are exhausted and the position is quiet.

Removing a-b pruning will make the search horribly inefficient, I don't know why you want to do that.

[maksimKorzh]

Mate distance solution actually solved my issue! Thank you so much!

I understand that global variables are bad idea, but let's say we drop alpha beta and leave the brute force negamax (this time I wrote it myself, no copypaste):

Code: Select all

int search(int depth)
{

    if (!depth)
        return evaluate_position();

    int best_score = -50000;
    int best_so_far;
    int legal_moves = 0;
    
    moves move_list[1];
    generate_moves(move_list);
    
    for (int count = 0; count < move_list->count; count++)  {
        
        copy_board();
        ply++;
        if(!make_move(move_list->moves[count], all_moves))
        {
            ply--;
            continue;
        }
        
        
        legal_moves++;
        int score = -search(depth - 1);
        take_back();
        
        if (score > best_score)
        {
            best_so_far = move_list->moves[count];
            best_score = score;
            printf("best so far: %s%s  score: %d  ply: %d\n", square_to_coords[get_move_source(move_list->moves[count])],
                                          square_to_coords[get_move_target(move_list->moves[count])],
                                          best_score, ply);
        }
        
        ply--;
    }
    
    best_move = best_so_far;
    
    if (!legal_moves)
    {
        if (is_square_attacked(king_square[side], side ^ 1))
            return -49000 + ply;

        else
            return 0;
    }
    
    return best_score;
}

at least this solution ALWAYS returns mate regardless of search depth.

In your last example and the one I just showed the evaluation function is called at depth 0 instead of quiescence.
If you want to have it working properly you also have to check for a mate/stalemate condition in the evaluation/quiescence, which is omitted now.

Obviously I'm aware the quiescence search is absolutely essential.
But I'm just wondering - how to implement quiescence search for bruteforce negamax?
I mean when we work inside alpha beta framework we can simply forward alpha and beta scores from negamax to quiescence, but how we can implement it without alpha beta?
Should we assume that best score works as alpha and pass it to quiescence and limit the quiescence depth by ply instead of a beta cutoff since beta is not available in non alha beta implementations?

Yes, you may assume that best_score works as alpha, completely remove beta and the (score >= beta) cut_off condition.

Limiting the quiescence depth by ply is not a good idea, because you want to evaluate at the point where all captures are exhausted and the position is quiet.

Removing a-b pruning will make the search horribly inefficient, I don't know why you want to do that.

Haha))) I don't want to do that))) I'm just building my own understanding of the basic concepts being involved it the search process. And you current expert evaluation satisfies me completely). After finally realizing the importance of using plies within the search and calculating distance of the mating score I can now move from brute force back to alpha beta. Understanding best score working like alpha is important for me. Probably my understanding and approach is weird but at least I've written a couple of searches completely on my own instead of copypasting. So I really really appreciate your help!

[hgm]

But I'm just wondering - how to implement quiescence search for bruteforce negamax?

Like always: search only captures, and assume all non-captures return the current evaluation as score.

But this tends to explode; capture-only searches in middle-game positions will have huge minimax trees, because their depth is practically unlimited (i.e. as many ply as there are pieces on the board to capture). You really need alpha-beta there to save the day.

A more robust algorithm is search recapture only (i.e. to same square, efectively making it a SEE). A compromise is to do a fixed number of all-captures ply, and beyond that recapture only.

[maksimKorzh]

But I'm just wondering - how to implement quiescence search for bruteforce negamax?

Like always: search only captures, and assume all non-captures return the current evaluation as score.

But this tends to explode; capture-only searches in middle-game positions will have huge minimax trees, because their depth is practically unlimited (i.e. as many ply as there are pieces on the board to capture). You really need alpha-beta there to save the day.

A more robust algorithm is search recapture only (i.e. to same square, efectively making it a SEE). A compromise is to do a fixed number of all-captures ply, and beyond that recapture only.

Oh! Maestro here! Thanks for taking your time to to have a look at this!