How do you prevent "easy" mates from being missed when using null move pruning?

[clayt]

I'm currently implementing null-move pruning on my chess engine. Currently, I have a gain of about 50 Elo, but I found that after implementing it, my engine fails to catch easy mates, most likely assuming that playing a null move is an easy escape from a forced mate.

Right now, the null-move pruning step in my search function looks like this:

Code: Select all

// Use null-move pruning to construct a best-guess lower bound on the position.
// Do not prune in principal variation nodes or if the previous move was a null-move.
// (~45 Elo)
if !PV // do not prune in PV lines
    && depth >= 4 // must have some amount of depth left to search
    && beta < Eval::MAX // must be possible to cause a cutoff
    && self.game.meta().checkers.is_empty() // cannot nullmove out of check
    && !matches!( // play NMs once
        self.game.moves.last(), 
        Some((Move::BAD_MOVE, _))) 
{
    self.game.null_move();

    let null_depth = depth - 4;
    
    // bookkeeping on state informaton
    let mut child_line = Vec::new();
    let mut null_state = NodeState {
        depth_since_root: state.depth_since_root + 1,
        cumulative_score: -state.cumulative_score,
        mg_npm: state.mg_npm,
        phase: state.phase,
        line: &mut child_line,
    };

    // perform a search
    let null_score = -self.pvs::<false, false, REDUCE>(null_depth, -beta, -beta + Eval::centipawns(1), &mut null_state)?;

    self.game.undo_null();

    if null_score >= beta {
        return Ok(null_score);
    }
}

Are there other conditions I can add to help the search function catch those easy checks?

[Mike Sherwin]

I don't know the answer. What I would suggest though is testing 'it'. Do a full search after a null move returns >= beta and count the mate scores against the side doing the null move.

[hgm]

I suppose the 'moral lesson' here is that detecting easy mates doesn't bring you any Elo...

[Ras]

my engine fails to catch easy mates

What does "easy mate" exactly mean? Something like K+R vs K? That relies on zugzwang for the losing side. You should disable null move in the endgame anyway.

[lithander]

Can you give a few FENs where the engine is struggling now that were obvious mates earlier?

[clayt]

Here's a relatively simple position where the engine fails:

[fen]3k4/R7/8/5K2/3R4/8/8/8 b - - 0 1[/fen]

This position is nominally mate in 4 ply, but my engine doesn't catch it until searching to a depth of 10 ply.

[Ras]

If Black moves Kd8-c8, the shortest mate is Rd4-b4 Kc8-d8 Rb4-b8# (mate in 4 plies). However, Kc8-d8 is zugzwang. If you allow a nullmove here, Rb4-b8 does not work so that Black escapes from that mate. So instead after Kd8-c8, the next shortest line without zugzwang is Rd4-h4 Kc8-b8 Rb7-g7 Kb8-c8 Rh4-h8# (mate in 6 plies - still less than 10).

I only enable nullmove if the moving side has at least one slider or two knights. Maybe you try that additional condition?

[lithander]

If Black moves Kd8-c8, the shortest mate is Rd4-b4 Kc8-d8 Rb4-b8# (mate in 4 plies). However, Kc8-d8 is zugzwang. If you allow a nullmove here, Rb4-b8 does not work so that Black escapes from that mate. So instead after Kd8-c8, the next shortest line without zugzwang is Rd4-h4 Kc8-b8 Rb7-g7 Kb8-c8 Rh4-h8# (mate in 6 plies - still less than 10).

I think what Clayton maybe means that his engine takes a 10 ply deep search to finally catch the mate in 4 plys? I find it hard to imagine how it would miss the mate in 6 as long as null-move is not playable when STM is in check. (which should be obvious)

With all safeguards removed Leorik would never find the mate in 4 because he'd miss the Zugzwang entirely but finds the mate in 6 plies at depth 6.

Code: Select all

if (!inCheck) DoNullmovePruning()

Code: Select all

info depth 1 score cp -2122 nodes 3 nps 600 time 5 pv d8c8
info depth 2 score cp -2172 nodes 49 nps 2578 time 19 pv d8c8 f5e6
info depth 3 score cp -2181 nodes 199 nps 10473 time 19 pv d8e8 d4d7 e8f8
info depth 4 score cp -2283 nodes 649 nps 32450 time 20 pv d8c8 f5e6 c8b8 d4d7
info depth 5 score cp -2246 nodes 1003 nps 50150 time 20 pv d8c8 f5e6 c8b8 d4d7 b8c8
info depth 6 score mate -3 nodes 1707 nps 85350 time 20 pv d8c8 f5e6 c8b8 d4d7 b8c8 a7a8
info depth 7 score mate -3 nodes 2377 nps 118850 time 20 pv d8c8 f5e6 c8b8 d4d7 b8c8 a7a8
info depth 8 score mate -3 nodes 3558 nps 169428 time 21 pv d8c8 f5e6 c8b8 d4d7 b8c8 a7a8
info depth 9 score mate -3 nodes 4377 nps 208428 time 21 pv d8c8 f5e6 c8b8 d4d7 b8c8 a7a8
info depth 10 score mate -3 nodes 7454 nps 354952 time 21 pv d8c8 f5e6 c8b8 d4d7 b8c8 a7a8
info depth 11 score mate -3 nodes 10307 nps 468500 time 22 pv d8c8 f5e6 c8b8 d4d7 b8c8 a7a8
info depth 12 score mate -3 nodes 18661 nps 811347 time 23 pv d8c8 f5e6 c8b8 d4d7 b8c8 a7a8

The important safeguard to add is to not do NullMovePruning in "endgames" which I define as the side to move having only Kings & Pawns. (Ras definition was more inclusive)

Code: Select all

if (!inCheck && !current.IsEndgame()) DoNullmovePruning()

Code: Select all

info depth 1 score cp -2122 nodes 3 nps 600 time 5 pv d8c8
info depth 2 score cp -2172 nodes 49 nps 2578 time 19 pv d8c8 f5e6
info depth 3 score cp -2181 nodes 192 nps 9600 time 20 pv d8e8 d4d7 e8f8
info depth 4 score cp -2283 nodes 895 nps 44750 time 20 pv d8c8 f5e6 c8b8 d4d7
info depth 5 score cp -2246 nodes 1134 nps 56700 time 20 pv d8c8 f5e6 c8b8 d4d7 b8c8
info depth 6 score mate -2 nodes 2834 nps 141700 time 20 pv d8c8 d4b4 c8d8 b4b8

Now the mate exploiting Zugzwang is found quickly enough.

Another safeguard I usually add is that when the previous iteration found a mate then I disable null-moves entirely to try and find a shorter mate involving zugzwang. (The game is won already, but now let's try to win it as quickly as possible)

And last but not least I usually also don't do null-moves the first few plies e.g. not when current ply <= searchdepth / 4

[KhepriChess]

I know null move isn't supposed to be done in endgame, but I haven't seen much gain limiting it on that point.

With:

Code: Select all

if (!inCheck && !isPVNode && nullAllowed && staticEval >= beta) { ... }

Khepri finds the mate in 3 at depth 6 and mate in 2 at depth 14.

If I add a "!endgame" condition to the if statement above, Khepri finds the mate in 2 at depth 5.

I'm also testing a separate eval function for when there's no pawns, something akin to a mop-op function. Currently, it seems like Khepri is actually a bit stronger without the endgame condition but with the mop-up eval.

Ultimately, does it actually matter if you don't find the faster mate? Especially if it doesn't actually contribute any strength (or even the opposite)?

[Ras]

Ultimately, does it actually matter if you don't find the faster mate?

That's just a symptom - the underlying problem is misevaluating zugzwang positions, especially in the endgame.