Is there a problem with my Negamax implementation?

Question

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).

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

Answer 1

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:

• You don't detect stalemate. Currently when there are no legal moves you return -9999 (assuming you make the fix above first), which can indicate that the current player was checkmated. But another possibility is stalemate which should have a score of 0.
• All "mate in N" positions will have the same score of 9999, which means the AI will be in no rush to mate and may just make repeating moves. One way to solve this is to give "mate in N" a score of 9999-N.