Null Move Pruning gives little/no elo gain

[AAce3]

Hi all,
I have been testing NMP with Shen Yu. Currently, my implementation looks something like this:

Code: Select all

if !in_check && !is_pv && eval >= beta && !IS_ROOT && !self.board.is_kp() {
            self.board.make_nullmove();
            let reduction = 3 + depth / 6;
            let score = if depth > reduction {
                let mut new_pvline = PVLine::new();
                self.alphabeta::<false>(
                    depth - 1 - reduction,
                    ply + 1,
                    -beta,
                    -beta + 1,
                    &mut new_pvline,
                )
            } else {
                self.quiesce(0, -beta, -beta + 1)
            };

            self.board.unmake_nullmove();

            if self.timer.stopped {
                return 0;
            }

            if score >= beta {
                return beta;
            }
}
 

make_nullmove swaps sides, resets the en passant square, resets the fifty move counter, and changes the zobrist key accordingly. However, when testing against the version with no null move, the adoption of null move pruning gives -16.0 (+/- 30.3) elo at 10+0.1 tc. Many other authors have reported 100+ elo gains with the addition of null move pruning, so I suspect there is something wrong with my implementation. Does anyone have any experience with this?

Additional information:
I have not implemented any other forms of pruning, other than SEE pruning in QSearch. Currently, I have staged move generation implemented as such:

1. Test the TT move for legality, then play it
2. Generate captures. Sort them using MVV-LVA, and use SEE to filter out "losing captures," which are tested in stage 4. Winning captures are played.
3. Test Killer moves for legality
4. Play all losing captures
5. Generate quiet moves, then sort them by history heuristic.

Since switching to make/unmake board representation and legal move generation, I have incurred a small speed hit (ShenYu 1.0.0 searches at about 5.4 MNps, whereas the newer version usually hits about 4.8 MNps), possibly due to inefficient implementation. For now, this is not particularly problematic for me because the code is cleaner, and my eventual goal is to switch to a (self-trained) NNUE for evaluation, so the small inefficiencies that I am currently seeing are probably not too much to worry about.

[Mike Sherwin]

What language has the syntax "let score = if depth > reduction"? Is this Rust? Why not put score = in front of the function that returns score? Most null move implementations that I have seen don't have the restriction, if depth > reduction. I've seen, if depth > some_number. I use some_number = 1. And I have not seen quiesce called directly from the null move code. Just let search handle that (as in if depth < 1)?

if self.timer.stopped {
return 0;
}

Why return what may be a bogus score just because time ran out?

I don't know if any of this is wrong. It just looks suspect.

[AAce3]

What language has the syntax "let score = if depth > reduction"? Is this Rust? Why not put score = in front of the function that returns score? Most null move implementations that I have seen don't have the restriction, if depth > reduction. I've seen, if depth > some_number. I use some_number = 1. And I have not seen quiesce called directly from the null move code. Just let search handle that (as in if depth < 1)?

if self.timer.stopped {
return 0;
}

Why return what may be a bogus score just because time ran out?

I don't know if any of this is wrong. It just looks suspect.

Hi Mike! Thanks for your response.
Yes, this is rust. The syntax looks a little weird if you're used to C++, but it's pretty similar to a ternary operator (although much more versatile).

The reason why I have that "if" there is because if I just subtract the reduction directly, the depth value will overflow, because I use unsigned integers for depth.

When time runs out, that means that the search didn't finish. So, I return zero because the result from search isn't going to be used anyways -- instead, we're just going to return the result from the previous search.

[alvinypeng]

Hi all,
I have been testing NMP with Shen Yu. Currently, my implementation looks something like this:

Code: Select all

if !in_check && !is_pv && eval >= beta && !IS_ROOT && !self.board.is_kp() {
            self.board.make_nullmove();
            let reduction = 3 + depth / 6;
            let score = if depth > reduction {
                let mut new_pvline = PVLine::new();
                self.alphabeta::<false>(
                    depth - 1 - reduction,
                    ply + 1,
                    -beta,
                    -beta + 1,
                    &mut new_pvline,
                )
            } else {
                self.quiesce(0, -beta, -beta + 1)
            };

            self.board.unmake_nullmove();

            if self.timer.stopped {
                return 0;
            }

            if score >= beta {
                return beta;
            }
}
 

make_nullmove swaps sides, resets the en passant square, resets the fifty move counter, and changes the zobrist key accordingly. However, when testing against the version with no null move, the adoption of null move pruning gives -16.0 (+/- 30.3) elo at 10+0.1 tc. Many other authors have reported 100+ elo gains with the addition of null move pruning, so I suspect there is something wrong with my implementation. Does anyone have any experience with this?

Additional information:
I have not implemented any other forms of pruning, other than SEE pruning in QSearch. Currently, I have staged move generation implemented as such:

1. Test the TT move for legality, then play it
2. Generate captures. Sort them using MVV-LVA, and use SEE to filter out "losing captures," which are tested in stage 4. Winning captures are played.
3. Test Killer moves for legality
4. Play all losing captures
5. Generate quiet moves, then sort them by history heuristic.

Since switching to make/unmake board representation and legal move generation, I have incurred a small speed hit (ShenYu 1.0.0 searches at about 5.4 MNps, whereas the newer version usually hits about 4.8 MNps), possibly due to inefficient implementation. For now, this is not particularly problematic for me because the code is cleaner, and my eventual goal is to switch to a (self-trained) NNUE for evaluation, so the small inefficiencies that I am currently seeing are probably not too much to worry about.

I think you forgot a negative sign in front of self.alphabeta and self.quiesce.

[Mike Sherwin]

Hi all,
I have been testing NMP with Shen Yu. Currently, my implementation looks something like this:

Code: Select all

if !in_check && !is_pv && eval >= beta && !IS_ROOT && !self.board.is_kp() {
            self.board.make_nullmove();
            let reduction = 3 + depth / 6;
            let score = if depth > reduction {
                let mut new_pvline = PVLine::new();
                self.alphabeta::<false>(
                    depth - 1 - reduction,
                    ply + 1,
                    -beta,
                    -beta + 1,
                    &mut new_pvline,
                )
            } else {
                self.quiesce(0, -beta, -beta + 1)
            };

            self.board.unmake_nullmove();

            if self.timer.stopped {
                return 0;
            }

            if score >= beta {
                return beta;
            }
}
 

make_nullmove swaps sides, resets the en passant square, resets the fifty move counter, and changes the zobrist key accordingly. However, when testing against the version with no null move, the adoption of null move pruning gives -16.0 (+/- 30.3) elo at 10+0.1 tc. Many other authors have reported 100+ elo gains with the addition of null move pruning, so I suspect there is something wrong with my implementation. Does anyone have any experience with this?

Additional information:
I have not implemented any other forms of pruning, other than SEE pruning in QSearch. Currently, I have staged move generation implemented as such:

1. Test the TT move for legality, then play it
2. Generate captures. Sort them using MVV-LVA, and use SEE to filter out "losing captures," which are tested in stage 4. Winning captures are played.
3. Test Killer moves for legality
4. Play all losing captures
5. Generate quiet moves, then sort them by history heuristic.

Since switching to make/unmake board representation and legal move generation, I have incurred a small speed hit (ShenYu 1.0.0 searches at about 5.4 MNps, whereas the newer version usually hits about 4.8 MNps), possibly due to inefficient implementation. For now, this is not particularly problematic for me because the code is cleaner, and my eventual goal is to switch to a (self-trained) NNUE for evaluation, so the small inefficiencies that I am currently seeing are probably not too much to worry about.

I think you forgot a negative sign in front of self.alphabeta and self.quiesce.

Correct! I can't believe that I missed that.

There is possibly a better formula for r.

Code: Select all

    double delta = max(h->eval - beta, 1.0); 
    double ddepth = (double)depth; 
    int r = (int)(0.25 * ddepth + 2.5 + log(delta)/5.0);

[AAce3]

Hi all,
I have been testing NMP with Shen Yu. Currently, my implementation looks something like this:

Code: Select all

if !in_check && !is_pv && eval >= beta && !IS_ROOT && !self.board.is_kp() {
            self.board.make_nullmove();
            let reduction = 3 + depth / 6;
            let score = if depth > reduction {
                let mut new_pvline = PVLine::new();
                self.alphabeta::<false>(
                    depth - 1 - reduction,
                    ply + 1,
                    -beta,
                    -beta + 1,
                    &mut new_pvline,
                )
            } else {
                self.quiesce(0, -beta, -beta + 1)
            };

            self.board.unmake_nullmove();

            if self.timer.stopped {
                return 0;
            }

            if score >= beta {
                return beta;
            }
}
 

make_nullmove swaps sides, resets the en passant square, resets the fifty move counter, and changes the zobrist key accordingly. However, when testing against the version with no null move, the adoption of null move pruning gives -16.0 (+/- 30.3) elo at 10+0.1 tc. Many other authors have reported 100+ elo gains with the addition of null move pruning, so I suspect there is something wrong with my implementation. Does anyone have any experience with this?

Additional information:
I have not implemented any other forms of pruning, other than SEE pruning in QSearch. Currently, I have staged move generation implemented as such:

1. Test the TT move for legality, then play it
2. Generate captures. Sort them using MVV-LVA, and use SEE to filter out "losing captures," which are tested in stage 4. Winning captures are played.
3. Test Killer moves for legality
4. Play all losing captures
5. Generate quiet moves, then sort them by history heuristic.

Since switching to make/unmake board representation and legal move generation, I have incurred a small speed hit (ShenYu 1.0.0 searches at about 5.4 MNps, whereas the newer version usually hits about 4.8 MNps), possibly due to inefficient implementation. For now, this is not particularly problematic for me because the code is cleaner, and my eventual goal is to switch to a (self-trained) NNUE for evaluation, so the small inefficiencies that I am currently seeing are probably not too much to worry about.

I think you forgot a negative sign in front of self.alphabeta and self.quiesce.

That's honestly hilarious. I can't believe I missed that. Thank you so much.

[AAce3]

Hi all,
I have been testing NMP with Shen Yu. Currently, my implementation looks something like this:

Code: Select all

if !in_check && !is_pv && eval >= beta && !IS_ROOT && !self.board.is_kp() {
            self.board.make_nullmove();
            let reduction = 3 + depth / 6;
            let score = if depth > reduction {
                let mut new_pvline = PVLine::new();
                self.alphabeta::<false>(
                    depth - 1 - reduction,
                    ply + 1,
                    -beta,
                    -beta + 1,
                    &mut new_pvline,
                )
            } else {
                self.quiesce(0, -beta, -beta + 1)
            };

            self.board.unmake_nullmove();

            if self.timer.stopped {
                return 0;
            }

            if score >= beta {
                return beta;
            }
}
 

make_nullmove swaps sides, resets the en passant square, resets the fifty move counter, and changes the zobrist key accordingly. However, when testing against the version with no null move, the adoption of null move pruning gives -16.0 (+/- 30.3) elo at 10+0.1 tc. Many other authors have reported 100+ elo gains with the addition of null move pruning, so I suspect there is something wrong with my implementation. Does anyone have any experience with this?

Additional information:
I have not implemented any other forms of pruning, other than SEE pruning in QSearch. Currently, I have staged move generation implemented as such:

1. Test the TT move for legality, then play it
2. Generate captures. Sort them using MVV-LVA, and use SEE to filter out "losing captures," which are tested in stage 4. Winning captures are played.
3. Test Killer moves for legality
4. Play all losing captures
5. Generate quiet moves, then sort them by history heuristic.

Since switching to make/unmake board representation and legal move generation, I have incurred a small speed hit (ShenYu 1.0.0 searches at about 5.4 MNps, whereas the newer version usually hits about 4.8 MNps), possibly due to inefficient implementation. For now, this is not particularly problematic for me because the code is cleaner, and my eventual goal is to switch to a (self-trained) NNUE for evaluation, so the small inefficiencies that I am currently seeing are probably not too much to worry about.

I think you forgot a negative sign in front of self.alphabeta and self.quiesce.

That's honestly hilarious. I can't believe I missed that. Thank you so much.

Super quick initial test

Code: Select all

Elo difference: 144.1 +/- 64.5, LOS: 100.0 %, DrawRatio: 35.4 %
SPRT: llr 2.9 (100.4%), lbound -2.25, ubound 2.89 - H1 was accepted