rustchessnegamax

Is there a problem with my Negamax implementation?

I'm trying to write a simple negamax algorithm in Rust for my Chess engine. I have a very simple evaluation function:

pub fn evaluate(&self) -> i32 {
    let mut eval: i32 = 0;

    for piece_type in PType::PIECE_TYPES {
        eval += (
            self.bitboards[piece_type, Col::White].count_ones() as i32 - 
            self.bitboards[piece_type, Col::Black].count_ones() as i32
        ) * piece_type.value();
    }

    eval
}

And here's my negamax implementation:

fn negamax(pos: &mut Position, depth: u32, piece_colour: Col) -> i32 {
    let mult = match piece_colour {
        Col::Black => -1,
        Col::White => 1
    };

    if depth == 0 {
        return pos.evaluate() * mult
    }

    let mut best_so_far = -9999;

    let legal_moves = movegen::legal_moves(pos, piece_colour);

    for child in legal_moves {
        pos.make_move(child);
        best_so_far = std::cmp::max(best_so_far, negamax(pos, depth - 1, piece_colour.inverse()));
        pos.unmake_move(child);
    }

    -best_so_far
}

A lot of this is derived from the Wikipedia pseudocode for the Negamax algorithm. However, in the following position on depth 5, the best move generated for white is Nxd3 when it should be Nb7 to fork the queen and king, then capture the queen on the next move (yes, my move generator does account for forks).

The position in question

I have a feeling my Negamax implementation is at fault, however I can't figure out where.

Solution

  • The pseudocode given in the Wikipedia article which you followed is wrong: There is a discrepancy between depth == 0 and depth > 0. In the depth == 0 case, it returns the evaluation from the point of view of the current player. But for depth > 0, it returns the evaluation from the point of view of the other player due to the negation at the end. This causes incorrect results when going from depth 1 to 0.

    To fix this, the negation should be done right after the recursive call instead of when returning. Note that this is the way it's done in the pseudocode for the alpha-beta pruning variant which seems correct.

    There are also some additional issues in your code: