Can someone spot the issue with my search + evaluation?

Question

I am working on a chess engine and believe I'm using my evaluation function in Negamax and Minimax with alpha beta pruning wrong. A couple days ago, I implemented Negamax with alpha beta pruning and noticed a large performance hit compared to the other aspects of my code like move generation. I originally thought the evaluation function was the issue but now believe it is because of my search/evaluation.

I implemented Minimax with alpha beta pruning to compare the two algorithms as their results should be the same. What I found was that at an odd depth both algorithms search the same number of nodes, but they are searching more than I believe they should (e.g. depth 3 on the starting position searches 4,314 nodes, when I have seen it should be closer to 500). When the depth is even, Minimax outperforms Negamax (e.g. depth of 4 on the starting position searches 52,452 nodes in Negamax and 17,899 in Minimax), but even these seem higher than they should be as I've seen they should be closer to 1,500. Also, these algorithms are using the same evaluation function but are returning different best moves and corresponding evaluations.

More than likely I'm using the result from the evaluation function wrong, or my evaluation function is not performing the correct relative evaluation.

If it helps anyone understand my code better, the board.clone_with_move() function, clones the board state, applies the move to the new board, and returns the new board. Applying the move also changes the new board's active color.

Negamax Code:

const INITIAL_ALPHA: i32 = std::i32::MIN + 1;
const INITIAL_BETA: i32 = std::i32::MAX - 1;

pub fn best_move_negamax_ab(&self, board: &Board, depth: u8) -> (i32, Option<Move>) {
    let moves = self.move_gen.generate_moves(board);
    let mut best_move = None;
    let mut best_score = std::i32::MIN + 1;

    for mv in moves {
        let new_board = board.clone_with_move(&mv);
        let score = -self.negamax_alpha_beta(&new_board, INITIAL_ALPHA, INITIAL_BETA, depth - 1);
        if score > best_score {
            best_move = Some(mv);
            best_score = score;
        }
    }

    (best_score, best_move)
}

fn negamax_alpha_beta(&self, board: &Board, alpha: i32, beta: i32, depth: u8) -> i32 {
    if depth == 0 {
        return evaluate(board) as i32;
    }

    let moves = self.move_gen.generate_moves(board);
    let mut alpha = alpha;

    for mv in moves {
        let new_board = board.clone_with_move(&mv);
        let score = -self.negamax_alpha_beta(&new_board, -beta, -alpha, depth - 1);
        if score >= beta {
            return beta;
        }
        if score > alpha {
            alpha = score;
        }
    }
    return alpha;
}

Minimax Code:

const INITIAL_ALPHA: i32 = std::i32::MIN + 1;
const INITIAL_BETA: i32 = std::i32::MAX - 1;

pub fn best_move_minimax_ab(&self, board: &Board, depth: u8) -> (i32, Option<Move>) {
    let moves = self.move_gen.generate_moves(board);
    let mut best_move = None;
    let mut best_score = std::i32::MIN + 1;

    for mv in moves {
        let new_board = board.clone_with_move(&mv);
        let score = self.alpha_beta_max(&new_board, INITIAL_ALPHA, INITIAL_BETA, depth - 1);
        if score > best_score {
            best_move = Some(mv);
            best_score = score;
        }
    }

    (best_score, best_move)
}

fn alpha_beta_max(&self, board: &Board, alpha: i32, beta: i32, depth: u8) -> i32 {
    if depth == 0 {
        return evaluate(board) as i32;
    }
    let moves = self.move_gen.generate_moves(board);
    let mut alpha = alpha;

    for mv in moves {
        let new_board = board.clone_with_move(&mv);
        let score = self.alpha_beta_min(&new_board, alpha, beta, depth-1);
        if score >= beta {
            return beta;
        }
        if score > alpha {
            alpha = score;
        }
    }
    return alpha;

}
fn alpha_beta_min(&self, board: &Board, alpha: i32, beta: i32, depth: u8) -> i32 {
    if depth == 0 {
        return evaluate(board) as i32;
    }
    let moves = self.move_gen.generate_moves(board);
    let mut beta = beta;

    for mv in moves {
        let new_board = board.clone_with_move(&mv);
        let score = self.alpha_beta_max(&new_board, alpha, beta, depth - 1);
        if score <= alpha {
            return alpha;
        }
        if score < beta {
            beta = score;
        }
    }
    return beta;
}

Evaluation function code:

use crate::board::Board;
use crate::pieces::{Piece, Color};
use crate::bitboard::BitboardIterator;

pub static PAWN_PIECE_SQUARE_TABLE: [i16; 64] = [
    100, 100, 100, 100, 100, 100, 100, 100,
    150, 150, 150, 150, 150, 150, 150, 150,
    110, 110, 120, 130, 130, 120, 110, 110,
    105, 105, 110, 125, 125, 110, 105, 105,
    100, 100, 100, 120, 120, 100, 100, 100,
    105,  95,  90, 100, 100,  90,  95, 105,
    105, 110, 110,  80,  80, 110, 110, 105,
    100, 100, 100, 100, 100, 100, 100, 100, 
];

pub static KNIGHT_PIECE_SQUARE_TABLE: [i16; 64] = [
    270, 280, 290, 290, 290, 290, 280, 270,
    280, 300, 320, 320, 320, 320, 300, 280,
    290, 320, 330, 335, 335, 330, 320, 290,
    290, 325, 335, 340, 340, 335, 325, 290,
    290, 320, 335, 340, 340, 335, 320, 290,
    290, 325, 330, 335, 335, 330, 325, 290,
    280, 300, 320, 325, 325, 320, 300, 280,
    270, 280, 290, 290, 290, 290, 280, 270,    
];

pub static BISHOP_PIECE_SQUARE_TABLE: [i16; 64] = [
    310, 320, 320, 320, 320, 320, 320, 310,
    320, 330, 330, 330, 330, 330, 330, 320,
    320, 330, 335, 340, 340, 335, 330, 320,
    320, 335, 335, 340, 340, 335, 335, 320,
    320, 330, 340, 340, 340, 340, 330, 320,
    320, 340, 340, 340, 340, 340, 340, 320,
    320, 335, 330, 330, 330, 330, 335, 320,
    310, 320, 320, 320, 320, 320, 320, 310,    
];

pub static ROOK_PIECE_SQUARE_TABLE: [i16; 64] = [
    500, 500, 500, 500, 500, 500, 500, 500,
    505, 510, 510, 510, 510, 510, 510, 505,
    495, 500, 500, 500, 500, 500, 500, 495,
    495, 500, 500, 500, 500, 500, 500, 495,
    495, 500, 500, 500, 500, 500, 500, 495,
    495, 500, 500, 500, 500, 500, 500, 495,
    495, 500, 500, 500, 500, 500, 500, 495,
    500, 500, 500, 505, 505, 500, 500, 500,    
];

pub static QUEEN_PIECE_SQUARE_TABLE: [i16; 64] = [
    880, 890, 890, 895, 895, 890, 890, 880,
    890, 900, 900, 900, 900, 900, 900, 890,
    890, 900, 905, 905, 905, 905, 900, 890,
    895, 900, 905, 905, 905, 905, 900, 895,
    900, 900, 905, 905, 905, 905, 900, 895,
    890, 905, 905, 905, 905, 905, 900, 890,
    890, 900, 905, 900, 900, 900, 900, 890,
    880, 890, 890, 895, 895, 890, 890, 880,
];

pub static KING_OPENING_PIECE_SQUARE_TABLE: [i16; 64] = [
    19970, 19960, 19960, 19950, 19950, 19960, 19960, 19970,
    19970, 19960, 19960, 19950, 19950, 19960, 19960, 19970,
    19970, 19960, 19960, 19950, 19950, 19960, 19960, 19970,
    19970, 19960, 19960, 19950, 19950, 19960, 19960, 19970,
    19980, 19970, 19970, 19960, 19960, 19970, 19970, 19980,
    19990, 19980, 19980, 19980, 19980, 19980, 19980, 19990,
    20020, 20020, 20000, 20000, 20000, 20000, 20020, 20020,
    20020, 20030, 20010, 20000, 20000, 20010, 20030, 20020,
];

pub static KING_ENDGAME_PIECE_SQUARE_TABLE: [i16; 64] = [
    19950, 19960, 19970, 19980, 19980, 19970, 19960, 19950,
    19970, 19980, 19990, 20000, 20000, 19990, 19980, 19970,
    19970, 19990, 20020, 20030, 20030, 20020, 19990, 19970,
    19970, 19990, 20030, 20040, 20040, 20030, 19990, 19970,
    19970, 19990, 20030, 20040, 20040, 20030, 19990, 19970,
    19970, 19990, 20020, 20030, 20030, 20020, 19990, 19970,
    19970, 19970, 20000, 20000, 20000, 20000, 19970, 19970,
    19950, 19970, 19970, 19970, 19970, 19970, 19970, 19950,
];

pub fn is_endgame(board: &Board) -> bool {
    no_queens(board) || (has_queen_with_most_one_minor_piece(Color::White, board) && has_queen_with_most_one_minor_piece(Color::Black, board))
}

fn no_queens(board: &Board) -> bool {
    board.bb_piece(Piece::Queen) == 0
}

fn has_queen_with_most_one_minor_piece(color: Color, board: &Board) -> bool {
    let has_queen = board.bb(color, Piece::Queen) != 0;

    if has_queen {
        let pieces = board.bb(color, Piece::Knight) | board.bb(color, Piece::Bishop) | board.bb(color, Piece::Rook);
        let has_no_other_pieces = pieces == 0;
        let has_one_minor_piece = (pieces & !board.bb(color, Piece::Rook)).count_ones() <= 1;

        return has_no_other_pieces || has_one_minor_piece;
    }
    true
}

pub fn evaluate(board: &Board) -> i16 {
    let color = board.active_color();

    let pawn_eval = eval_piece_position(color, Piece::Pawn, &PAWN_PIECE_SQUARE_TABLE, board) - eval_piece_position(!color, Piece::Pawn, &PAWN_PIECE_SQUARE_TABLE, board);
    let knight_eval = eval_piece_position(color, Piece::Knight, &KNIGHT_PIECE_SQUARE_TABLE, board) - eval_piece_position(!color, Piece::Knight, &KNIGHT_PIECE_SQUARE_TABLE, board);
    let bishop_eval = eval_piece_position(color, Piece::Bishop, &BISHOP_PIECE_SQUARE_TABLE, board) - eval_piece_position(!color, Piece::Bishop, &BISHOP_PIECE_SQUARE_TABLE, board);
    let rook_eval = eval_piece_position(color, Piece::Rook, &ROOK_PIECE_SQUARE_TABLE, board) - eval_piece_position(!color, Piece::Rook, &ROOK_PIECE_SQUARE_TABLE, board);
    let queen_eval = eval_piece_position(color, Piece::Queen, &QUEEN_PIECE_SQUARE_TABLE, board) - eval_piece_position(!color, Piece::Queen, &QUEEN_PIECE_SQUARE_TABLE, board);
    
    let king_eval = if is_endgame(board) {
        eval_piece_position(color, Piece::King, &KING_ENDGAME_PIECE_SQUARE_TABLE, board) - eval_piece_position(!color, Piece::King, &KING_ENDGAME_PIECE_SQUARE_TABLE, board)
    } else {
        eval_piece_position(color, Piece::King, &KING_OPENING_PIECE_SQUARE_TABLE, board) - eval_piece_position(!color, Piece::King, &KING_OPENING_PIECE_SQUARE_TABLE, board)
    };

    pawn_eval + knight_eval + bishop_eval + rook_eval + queen_eval + king_eval
}

fn eval_piece_position(color:Color, piece: Piece, piece_square_table: &[i16; 64], board: &Board) -> i16 {
    let pieces = board.bb(color, piece);

    let mut score = 0;
    let iter = BitboardIterator::new(pieces);
    for square in iter {
        match color {
            Color::White => {
                let index = (7 - square / 8) * 8 + square % 8;
                score += piece_square_table[index as usize];
            }
            Color::Black => {
                score += piece_square_table[square as usize];
            }
        }
    }
    score
}

Answer 1

The primary issue you have is with the evaluation function. For a standard minimax implementation, it is supposed to be implemented such that the result is an absolute evaluation. I.e. a positive score means the position favors white, and negative meaning the position favors black. However, this is not the case for Negamax. When implementing the Negamax algorithm, the evaluation must return a score relative to the side to move (i.e. if it is Black-to-Move, a positive score indicates that the position favors black). This would explain why the results have an odd-even effect. The evaluation function is wrong for either Minimax or Negamax when it is Black-To-Move during the evaluate call, but it is correct when it is White-To-Move during the evalutate call.

It looks like the evaluation is wrong for Minimax. Does the returned best move make sense when you run the search, or does it seem to be unstable?

Another issue that might not be problematic, is that your initial Alpha and Beta values are not quite right. Since Max Int32 is 2,147,483,647 and Min Int32 is -2,147,483,648, your intial alpha and beta values are not the negative versions of each other, so the values do not stay constant as they go down the recursive Negamax calls. I'm not sure if this is actually going to cause problems, but I think you should set INITIAL_BETA = -INITIAL_ALPHA at the top.