Another null move condition

[jwes]

I did an experiment to see how often null moves gave cutoffs dependent on the difference between the material score and alpha. What I found surprised me. There is a dramatic difference in the success rates depending on whether the last move was a capture or not.Here is what I found: The first three columns show how far ahead or behind in material you have to be to have a 1, 5, or 10 percent chance of having a null-move cutoff, e.g. you need to have 2.57 pawns above alpha to have a 10% chance of a nullmove cutoff if the last move was a winning capture, while you could be 2.18 pawns below alpha and have a 10% chance of a nullmove capture if the last move was a non-capture other move. The last column shows the overall probability of a nullmove cutoff for the 4 types of moves. Note that 71% of other moves give a nullmove cutoff which suggests that pruning these moves is not unreasonable.

Code: Select all

Material-alpha            Probability of nullmove cutoff  Probability of 
in centipawns                <1%    <5%    <10%           nullmove cutoff

Non-capture hash or killer   -309   -209   -55               45.17%
Non-capture other            -321   -302   -218              71.08%
Winning capture              -42     88     257              18.68%
Losing capture               -116    64     197              23.21%

The point of all this is to say that it is a waste of time to try nullmove after a capture unless you are well ahead in material. One unanswered question is what percentage of nullmove searches need to give cutoffs to make nullmove worthwhile.

[bob]

I did an experiment to see how often null moves gave cutoffs dependent on the difference between the material score and alpha. What I found surprised me. There is a dramatic difference in the success rates depending on whether the last move was a capture or not.Here is what I found: The first three columns show how far ahead or behind in material you have to be to have a 1, 5, or 10 percent chance of having a null-move cutoff, e.g. you need to have 2.57 pawns above alpha to have a 10% chance of a nullmove cutoff if the last move was a winning capture, while you could be 2.18 pawns below alpha and have a 10% chance of a nullmove capture if the last move was a non-capture other move. The last column shows the overall probability of a nullmove cutoff for the 4 types of moves. Note that 71% of other moves give a nullmove cutoff which suggests that pruning these moves is not unreasonable.

Code: Select all

Material-alpha            Probability of nullmove cutoff  Probability of 
in centipawns                <1%    <5%    <10%           nullmove cutoff

Non-capture hash or killer   -309   -209   -55               45.17%
Non-capture other            -321   -302   -218              71.08%
Winning capture              -42     88     257              18.68%
Losing capture               -116    64     197              23.21%

The point of all this is to say that it is a waste of time to try nullmove after a capture unless you are well ahead in material. One unanswered question is what percentage of nullmove searches need to give cutoffs to make nullmove worthwhile.

Would seem to me this is an issue similar to things Beal discussed. If the move at ply N is a capture (it might be an even exchange in fact), then trying the null move will fail low because the opponent just retreats the piece and is a piece ahead. But if the capture is not the initial capture of a capture/re-capture pair, then this is not true as often. I worked on that for quite a while, but recognizing a capture/re-capture pair is a pain at times. Overall I found it better to try null-moves everywhere and occasionally waste one, rather than eliminating them in incorrect situations and missing a quick cutoff...

[Chan Rasjid]

...,but recognizing a capture/re-capture pair is a pain at times.
...

I am not sure my way is correct. I keep extra 2 global variables int neutral_mat[2] for 2 colors. After make() of every game move and if it is a non_qs move, they are updated:

Code: Select all

makemove(game_move);
if (game_move_is_non_qs){
neutral_mat[0] = mat[0]; 
neutral_mat[1] = mat[1];
}
... 

This way we might be able to figure out a capture/recapture pair. It could also be used for recapture extension, etc.

Rasjid.

[bob]

...,but recognizing a capture/re-capture pair is a pain at times.
...

I am not sure my way is correct. I keep extra 2 global variables int neutral_mat[2] for 2 colors. After make() of every game move and if it is a non_qs move, they are updated:

Code: Select all

makemove(game_move);
if (game_move_is_non_qs){
neutral_mat[0] = mat[0]; 
neutral_mat[1] = mat[1];
}
... 

This way we might be able to figure out a capture/recapture pair. It could also be used for recapture extension, etc.

Rasjid.

I found so many exceptions I gave up. For example, you can play capture-recapture, or you can play capture-check-escapecheck-recapture. This latter one is a bit tougher to see. Berliner suggested moves that return to material equality, but then you get into the 4-capture sequences where material balance is not restored until the 4th capture is played. In my old recapture extension, I was pretty draconian. Captures on the same square (all exchanges do not meed this, Bxf6, Rxc2 for example, where both captures are removing a knight) with same piece material values, two consecutive plies, plus a couple of tricks dealing with a 4-ply sequence (or a 3-ply sequence). It was pretty problematic, overall.

[Ferdy]

I did an experiment to see how often null moves gave cutoffs dependent on the difference between the material score and alpha. What I found surprised me. There is a dramatic difference in the success rates depending on whether the last move was a capture or not.Here is what I found: The first three columns show how far ahead or behind in material you have to be to have a 1, 5, or 10 percent chance of having a null-move cutoff, e.g. you need to have 2.57 pawns above alpha to have a 10% chance of a nullmove cutoff if the last move was a winning capture, while you could be 2.18 pawns below alpha and have a 10% chance of a nullmove capture if the last move was a non-capture other move. The last column shows the overall probability of a nullmove cutoff for the 4 types of moves. Note that 71% of other moves give a nullmove cutoff which suggests that pruning these moves is not unreasonable.

Code: Select all

Material-alpha            Probability of nullmove cutoff  Probability of 
in centipawns                <1%    <5%    <10%           nullmove cutoff

Non-capture hash or killer   -309   -209   -55               45.17%
Non-capture other            -321   -302   -218              71.08%
Winning capture              -42     88     257              18.68%
Losing capture               -116    64     197              23.21%

The point of all this is to say that it is a waste of time to try nullmove after a capture unless you are well ahead in material. One unanswered question is what percentage of nullmove searches need to give cutoffs to make nullmove worthwhile.

I have tried your idea, but I practically disabled null move if last move (move before null move) belongs to top 2 moves or if it is a hash move. I also include promote moves to the winning and losing capture theme and use a margin of 200 for this type of moves. And instead of material eval, I use position and material scores. On the first try, I got a promising result of +10 elo after 1600 games (not enough games) out of 8 different opponents run at tc=40moves/10sec.

I think this concept has a lot of potential. we can also use this to adjust R values, or even adjust other depth reductions schemes and even pruning strategies.

The idea is very practical, in chess it was actually the last move of opponent that determines how we chose and prioritize our moves. If he captured then we try to prioritize capture moves. if he is threatening our piece, then we try to move that threatened piece or make a more lethal threat than his threat. If he pins our piece then we try moves that unpins or prevent more pressure to the pinned piece, etc.

Thanks for sharing.

[jwes]

I did an experiment to see how often null moves gave cutoffs dependent on the difference between the material score and alpha. What I found surprised me. There is a dramatic difference in the success rates depending on whether the last move was a capture or not.Here is what I found: The first three columns show how far ahead or behind in material you have to be to have a 1, 5, or 10 percent chance of having a null-move cutoff, e.g. you need to have 2.57 pawns above alpha to have a 10% chance of a nullmove cutoff if the last move was a winning capture, while you could be 2.18 pawns below alpha and have a 10% chance of a nullmove capture if the last move was a non-capture other move. The last column shows the overall probability of a nullmove cutoff for the 4 types of moves. Note that 71% of other moves give a nullmove cutoff which suggests that pruning these moves is not unreasonable.

Code: Select all

Material-alpha            Probability of nullmove cutoff  Probability of 
in centipawns                <1%    <5%    <10%           nullmove cutoff

Non-capture hash or killer   -309   -209   -55               45.17%
Non-capture other            -321   -302   -218              71.08%
Winning capture              -42     88     257              18.68%
Losing capture               -116    64     197              23.21%

The point of all this is to say that it is a waste of time to try nullmove after a capture unless you are well ahead in material. One unanswered question is what percentage of nullmove searches need to give cutoffs to make nullmove worthwhile.

Would seem to me this is an issue similar to things Beal discussed. If the move at ply N is a capture (it might be an even exchange in fact), then trying the null move will fail low because the opponent just retreats the piece and is a piece ahead. But if the capture is not the initial capture of a capture/re-capture pair, then this is not true as often. I worked on that for quite a while, but recognizing a capture/re-capture pair is a pain at times. Overall I found it better to try null-moves everywhere and occasionally waste one, rather than eliminating them in incorrect situations and missing a quick cutoff...

The logic seems pretty compelling to me. You only want to do nullmove to make your search faster. Your search is faster if and only if the average number of nodes saved by a nullmove cutoff times the probability of a nullmove cutoff is greater than the average cost of a nullmove search. Therefore, if the probability of a nullmove cutoff in some situations is too low, your search will be slower if you do null move in those situations. I am having trouble measuring the cost and gain of nullmove searches, but I believe that break-even percentage is about 10%. Since the probability of a nullmove cutoff is less than 3% when the last move was a capture and the material balance is below alpha, I am confident that not doing nullmove in this situation will be a net gain.