0

I'm creating my own chess engine and noticed a significant time difference between running perft and the search + evaluation. At depth 5, perft on the initial position searches 4,865,609 nodes in about 1 second. Searching for the best move at depth 5 only searches 514,699 nodes but takes around 10 seconds.

I'm using negamax with alpha-beta pruning for searching and the simplified evaluation function for evaluation. I get that evaluating the position takes time, but I thought searching much fewer nodes would make up for it.

Is it normal to see such a large time difference between perft and searching for the best move?

Search Code:

const INITIAL_ALPHA: isize = (std::i32::MIN) as isize + 1;
const INITIAL_BETA: isize = (std::i32::MAX) as isize - 1;
const MATE_VALUE: isize = std::isize::MIN + 1;

pub fn best_move(&self, board: &Board, depth: usize) -> (isize, Option<Move>) {
    let moves = self.move_gen.generate_moves(board);
    let mut best_move = None;
    let mut best_score = std::isize::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);
        if score > best_score {
            best_move = Some(mv);
            best_score = score;
        }
    }

    (best_score, best_move)
}

fn negamax_alpha_beta(&self, board: &Board, mut alpha: isize, beta: isize, depth: usize) -> isize {
    if depth == 0 {
        return evaluate(board);
    }

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

    if moves.len() == 0 {
        if self.move_gen.attacks_to(board, self.move_gen.king_square(board)) != 0 {
            return MATE_VALUE;
        } else {
            return 0;
        }
    }

    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;
        }
    }
    alpha
}

Evaluation Code:

pub const PAWN_VALUE: isize = 100;
pub const KNIGHT_VALUE: isize = 320;
pub const BISHOP_VALUE: isize = 330;
pub const ROOK_VALUE: isize = 500;
pub const QUEEN_VALUE: isize = 900;
pub const KING_VALUE: isize = 20000;

pub const PAWN_PIECE_SQUARE_TABLE: [isize; 64] = [
    0,  0,  0,  0,  0,  0,  0,  0,
    50, 50, 50, 50, 50, 50, 50, 50,
    10, 10, 20, 30, 30, 20, 10, 10,
     5,  5, 10, 25, 25, 10,  5,  5,
     0,  0,  0, 20, 20,  0,  0,  0,
     5, -5,-10,  0,  0,-10, -5,  5,
     5, 10, 10,-20,-20, 10, 10,  5,
     0,  0,  0,  0,  0,  0,  0,  0
];

pub const KNIGHT_PIECE_SQUARE_TABLE: [isize; 64] = [
    -50,-40,-30,-30,-30,-30,-40,-50,
    -40,-20,  0,  0,  0,  0,-20,-40,
    -30,  0, 10, 15, 15, 10,  0,-30,
    -30,  5, 15, 20, 20, 15,  5,-30,
    -30,  0, 15, 20, 20, 15,  0,-30,
    -30,  5, 10, 15, 15, 10,  5,-30,
    -40,-20,  0,  5,  5,  0,-20,-40,
    -50,-40,-30,-30,-30,-30,-40,-50,
];

pub const BISHOP_PIECE_SQUARE_TABLE: [isize; 64] = [
    -20,-10,-10,-10,-10,-10,-10,-20,
    -10,  0,  0,  0,  0,  0,  0,-10,
    -10,  0,  5, 10, 10,  5,  0,-10,
    -10,  5,  5, 10, 10,  5,  5,-10,
    -10,  0, 10, 10, 10, 10,  0,-10,
    -10, 10, 10, 10, 10, 10, 10,-10,
    -10,  5,  0,  0,  0,  0,  5,-10,
    -20,-10,-10,-10,-10,-10,-10,-20,
];

pub const ROOK_PIECE_SQUARE_TABLE: [isize; 64] = [
    0,  0,  0,  0,  0,  0,  0,  0,
    5, 10, 10, 10, 10, 10, 10,  5,
   -5,  0,  0,  0,  0,  0,  0, -5,
   -5,  0,  0,  0,  0,  0,  0, -5,
   -5,  0,  0,  0,  0,  0,  0, -5,
   -5,  0,  0,  0,  0,  0,  0, -5,
   -5,  0,  0,  0,  0,  0,  0, -5,
    0,  0,  0,  5,  5,  0,  0,  0
];

pub const QUEEN_PIECE_SQUARE_TABLE: [isize; 64] = [
    -20,-10,-10, -5, -5,-10,-10,-20,
    -10,  0,  0,  0,  0,  0,  0,-10,
    -10,  0,  5,  5,  5,  5,  0,-10,
     -5,  0,  5,  5,  5,  5,  0, -5,
      0,  0,  5,  5,  5,  5,  0, -5,
    -10,  5,  5,  5,  5,  5,  0,-10,
    -10,  0,  5,  0,  0,  0,  0,-10,
    -20,-10,-10, -5, -5,-10,-10,-20
];

pub const KING_OPENING_PIECE_SQUARE_TABLE: [isize; 64] = [
    -30,-40,-40,-50,-50,-40,-40,-30,
    -30,-40,-40,-50,-50,-40,-40,-30,
    -30,-40,-40,-50,-50,-40,-40,-30,
    -30,-40,-40,-50,-50,-40,-40,-30,
    -20,-30,-30,-40,-40,-30,-30,-20,
    -10,-20,-20,-20,-20,-20,-20,-10,
     20, 20,  0,  0,  0,  0, 20, 20,
     20, 30, 10,  0,  0, 10, 30, 20
];

pub const KING_ENDGAME_PIECE_SQUARE_TABLE: [isize; 64] = [
    -50,-40,-30,-20,-20,-30,-40,-50,
    -30,-20,-10,  0,  0,-10,-20,-30,
    -30,-10, 20, 30, 30, 20,-10,-30,
    -30,-10, 30, 40, 40, 30,-10,-30,
    -30,-10, 30, 40, 40, 30,-10,-30,
    -30,-10, 20, 30, 30, 20,-10,-30,
    -30,-30,  0,  0,  0,  0,-30,-30,
    -50,-30,-30,-30,-30,-30,-30,-50
];

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).count_ones() == 0
}

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

    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.count_ones() == 0;
        let has_one_minor_piece = (pieces & !board.bb(color, Piece::Rook)).count_ones() <= 1;

        result = has_no_other_pieces || has_one_minor_piece;
    }

    !has_queen || result
}

pub fn evaluate(board: &Board) -> isize {
    eval_material(board) + eval_position(board)
}

fn eval_material(board: &Board) -> isize {
    let color = board.active_color();

    let pawn_eval = piece_difference(color, Piece::Pawn, board) * PAWN_VALUE;
    let knight_eval = piece_difference(color, Piece::Knight, board) * KNIGHT_VALUE;
    let bishop_eval = piece_difference(color, Piece::Bishop, board) * BISHOP_VALUE;
    let rook_eval = piece_difference(color, Piece::Rook, board) * ROOK_VALUE;
    let queen_eval = piece_difference(color, Piece::Queen, board) * QUEEN_VALUE;
    let king_eval = piece_difference(color, Piece::King, board) * KING_VALUE;

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

fn piece_difference(color: Color, piece: Piece, board: &Board) -> isize {
    board.bb(color, piece).count_ones() as isize - board.bb(!color, piece).count_ones() as isize
}

fn eval_position(board: &Board) -> isize {
    let color = board.active_color();

    let pawn_eval = eval_piece_position(color, Piece::Pawn, board) - eval_piece_position(!color, Piece::Pawn, board);
    let knight_eval = eval_piece_position(color, Piece::Knight, board) - eval_piece_position(!color, Piece::Knight, board);
    let bishop_eval = eval_piece_position(color, Piece::Bishop, board) - eval_piece_position(!color, Piece::Bishop, board);
    let rook_eval = eval_piece_position(color, Piece::Rook, board) - eval_piece_position(!color, Piece::Rook, board);
    let queen_eval = eval_piece_position(color, Piece::Queen, board) - eval_piece_position(!color, Piece::Queen, board);
    let king_eval = eval_piece_position(color, Piece::King, board) - eval_piece_position(!color, Piece::King, board);

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

fn eval_piece_position(color:Color, piece: Piece, board: &Board) -> isize {
    let pieces = board.bb(color, piece);

    let piece_square_table = match piece {
        Piece::Pawn => PAWN_PIECE_SQUARE_TABLE,
        Piece::Knight => KNIGHT_PIECE_SQUARE_TABLE,
        Piece::Bishop => BISHOP_PIECE_SQUARE_TABLE,
        Piece::Rook => ROOK_PIECE_SQUARE_TABLE,
        Piece::Queen => QUEEN_PIECE_SQUARE_TABLE,
        Piece::King => {
            if is_endgame(board) {
                KING_ENDGAME_PIECE_SQUARE_TABLE
            } else {
                KING_OPENING_PIECE_SQUARE_TABLE
            }
        },
    };

    let mut score = 0;
    let iter = BitboardIterator::new(pieces);
    for square in iter {
        match color {
            Color::White => score += piece_square_table[63 - square as usize],
            Color::Black => score += piece_square_table[square as usize],
        }
    }
    score
}
Improve this question
1
  • Koedem has already raised some valid points. However, there's a small addition you can make by incorporating the piece values into the piece-square table. This modification allows you to eliminate the need for the eval_material function entirely. Simply put, you would increase the value of each square in the specific piece-square table by the corresponding material value for the piece. Note: In combination with the Koedem points you will get a significant speedup.
    – Sheyteo
    Nov 13 at 17:00

1 Answer 1

Reset to default
0

Without seeing your code, I would guess that your evaluation function is implemented inefficiently. I once wrote a search + PST engine and I got around 10 MN/s on one core.

What you want to do with PST is to update it incrementally throughout search. So rather than iterating over the entire board at each leaf node, which will take quite a while (though even that shouldn't be so slow), keep the current evaluation updated through make and unmake move operations. So in the start position the evaluation would be 0. Then if you do a search and in search make the move e2-e4 you update the score by subtracting the Pe2 PST-score and adding the Pe4 PST-score. When you end at a leaf your evaluation is already computed and you can just use it. Then, when you back up from search and unmake e2-e4 you simply subtract the Pe4 PST-score and add the Pe2 one.

Improve this answer
4
  • Thanks for your response! I added the code for my search and evaluation, so if you have free time and are willing to take a look to see if you notice any glaring flaws I'd appreciate it! Regarding your suggestion, at the moment I'm working on creating a baseline engine that I can build upon, and iterating over the entire board for each leaf node was the simplest. When I work to optimize it later on I will for sure add the incremental evaluation update!
    – guest1337
    May 31 at 15:50
  • @guest1337 I don't really know Rust, but looking at the search procedure, that looks ok to me. Cloning the board for each node is not ideal of course, but I assume you do the same in perft too? So that wouldn't explain the big performance difference. (and with the Rust borrow checker, I wouldn't know how easy or difficult it would be to get rid of it) One experiment you can do is to have a trivial evaluation function (e.g. constant 0, or random or something) and see how fast that would be.
    – koedem
    Jun 1 at 14:38
  • As for the evaluation. Small detail, you can put the piece value scores into the PST scores to have it a bit cleaner and simpler. Assuming the bitboard operations (like count_ones()) are implemented efficiently (e.g. compiled down to the asm popcount instruction), I also don't see anything too wrong with the evaluation code. Have you profiled the code to see what exactly takes so much computing time?
    – koedem
    Jun 1 at 14:43
  • I do clone the board as well in perft, and I tried your suggestion on returning 0 for the eval function and that sped it up significantly (not sure why I didn't think to try this earlier). I profiled the code yesterday and found that the inclusive percentages were 42% for the eval function and 23% for move generation. Something that stuck out was a decent amount of time (~16%) was spent allocating, reallocating, and freeing items from the heap. The performance hit seems to be coming from my eval function, so I'll dig into it to find where the issue is. Thanks for all your help!
    – guest1337
    Jun 1 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.