Smooth scaling -- an explanation

[bob]

Consider the following:
#ifdef SMOOTH_REDUCTION
double delta = approximateEval - beta;
delta = max(delta, 1.0);
double ddepth = double(depth);
double r = 0.18 * ddepth + 3.1 + log(delta)/5.0;
r = r > ddepth ? ddepth : r;
int R = int(r);
#else
// Null move dynamic reduction based on depth
int R = (depth >= 5 * OnePly ? 4 : 3);

// Null move dynamic reduction based on value
if (approximateEval - beta > PawnValueMidgame)
R++;
#endif

If depth = 5, then 0.18 * 5 = 0.9
So 0.9 + 3.1 gives 4.0 which is the same as the original formula.
In value.h, we find this:
const Value PawnValueMidgame = Value(0x0C6);
In decimal, C6 is 198.
log (base e) of 198 is 5.288
dividing 5.288 by 5 gives 1 (approximately).

So, for the points at the boundary conditions of the old formula, my curve gives the same answers (or answers pretty nearly). When you fit this idea to your code, I suggest that you calibrate the curve accordingly, especially if you have carefully weighed out your null move reduction constants by experiment.

The difference is that when we bend away from these answers the solution I propose slowly changes so that instead of slamming the door, we are slowly closing it.

The reason I came up with smooth scaling is that null move's abrupt nature really bothered me. Why do we reduce the same in a 30 ply search as we do in a 12 ply search? That does not make sense. Why do we reduce the same with a full queen advantage as with a knight advantage? That also seemed very strange. So I just did a simple extrapolation to smooth out the reductions in order that they made sense to me.

First, for the last two questions, the answer is because null-move is not doing exactly what you appear to think it is doing. It is a quick way to bail out of positions where you are so far ahead, if you give your opponent the ability to make two moves in a row, he can't catch up. This idea is unrelated to the actual material balance. Null-move helps when you start off a queen ahead, because it will only cause cutoffs if you get way _more_ than a queen ahead, so it is a relative algorithm, that is not dependent on the initial position's material balance. Most of us are not really doing null-move on a 30 ply search as that is usually a pawn ending where null-move is not so safe unless you resort to the verification search. And since testing has shown that idea to not be useful (it loses a couple of elo, in fact)

As far as deeper reductions (beyond R=3 go), I have not had any success with that, and I tested it an absolute ton before 23.0 was released. I tried linear interpolation, and exponential in both directions (tapers off rapidly or tapers off very slowly. Once I have a chance to test the old/new stockfish on the cluster, that will quickly show whether this idea is a good one or not. But it certainly isn't +150. And I'd have a hard time imagining it even being possible to reach +50 with this kind of change, since basic null-move doesn't give that big a boost by itself, and this is just an enhancement.

More when we get our A/C up so the cluster can wake up.

[bob]

Consider the following:
#ifdef SMOOTH_REDUCTION
double delta = approximateEval - beta;
delta = max(delta, 1.0);
double ddepth = double(depth);
double r = 0.18 * ddepth + 3.1 + log(delta)/5.0;
r = r > ddepth ? ddepth : r;
int R = int(r);
#else
// Null move dynamic reduction based on depth
int R = (depth >= 5 * OnePly ? 4 : 3);

// Null move dynamic reduction based on value
if (approximateEval - beta > PawnValueMidgame)
R++;
#endif

If depth = 5, then 0.18 * 5 = 0.9
So 0.9 + 3.1 gives 4.0 which is the same as the original formula.
In value.h, we find this:
const Value PawnValueMidgame = Value(0x0C6);
In decimal, C6 is 198.
log (base e) of 198 is 5.288
dividing 5.288 by 5 gives 1 (approximately).

So, for the points at the boundary conditions of the old formula, my curve gives the same answers (or answers pretty nearly). When you fit this idea to your code, I suggest that you calibrate the curve accordingly, especially if you have carefully weighed out your null move reduction constants by experiment.

The difference is that when we bend away from these answers the solution I propose slowly changes so that instead of slamming the door, we are slowly closing it.

The reason I came up with smooth scaling is that null move's abrupt nature really bothered me. Why do we reduce the same in a 30 ply search as we do in a 12 ply search? That does not make sense. Why do we reduce the same with a full queen advantage as with a knight advantage? That also seemed very strange. So I just did a simple extrapolation to smooth out the reductions in order that they made sense to me.

This is for the non-believers and deniers

First of all, it needs to be tested, but some indicated that it should not work (based on intuition and/or theoretical issues). I disagree. It is wrong to say that if null move alone gives you 80 points, tweaking null move cannot give you more than, say, 20 points. It is possible to tweak nullmove and obtain a bigger boost than the addition of the technique itself... at least in theory...

Lets say that nullmove allows you to search 3 plies deeper. 3 plies deeper may mean 300 ELO points. Why do you see an increase of only 100 points? Because the search is full of holes. So, in this case, there is 200 points to be gained by avoiding the holes. It is as important to know WHEN to do cut off by nullmove as to the reduction you get. It is possible that Dann's adjustment may cause a more careful decision making at the level of nullmove for certain engines. I could see that this could be completely dependent on the engine.

That's simply wrong, and here's why. Just report your depth as 2 plies deeper. Are you any stronger? Null-move easily increased the typical search depth by more than 3 plies, but gets _nowhere_ near +300. I ran the test and reported these results earlier this year. NM is worth about +120 if you do not also do LMR. If you are doing LMR, NM will only add +80. Even with those extra plies.

You are treating all plies as "equal" but they are not when there is selective pruning involved, and with NM that is exactly what is happening.

and BTW, this is not adaptive null move, it has nothing to do with the snippet from Robbert Litto, and who the heck cares whether someone whisper a similar thought about this 5 years ago. Drop y'all EGO points and test to see whether it gives ELO points.

No Ego here. You can look back to when we were working on 23.0 and find posts where I tried a ton of different approaches to the adaptive null-move idea. And this _is_ about adaptive null-move, not sure why you think it is not. The idea of a non-constant R value is, by definition, adaptive null-move. How the value is altered is wide-open to variations, of course, but it is still the same _idea_.

In experimental science you learn that ideas are meaningless. My former PhD's advisor said to me, everybody has plenty, an most likely, yours is not original. Someone else is thinking about it or already did . What matters is the execution and who finally did it. What my PhD advisor was trying to say was (he was too polite to say it directly), "get your ass to the bench and start doing the experiment"

Miguel

Couldn't agree more. That's exactly why I test _every_ idea I come up with, and most that others suggest as well... My answers are almost always based on test results, not guesswork. If I give an opinion, I make it clear it is an opinion. If I give results, they are what they are.

[BubbaTough]

First, for the last two questions, the answer is because null-move is not doing exactly what you appear to think it is doing. It is a quick way to bail out of positions where you are so far ahead, if you give your opponent the ability to make two moves in a row, he can't catch up. This idea is unrelated to the actual material balance. Null-move helps when you start off a queen ahead, because it will only cause cutoffs if you get way _more_ than a queen ahead, so it is a relative algorithm, that is not dependent on the initial position's material balance. Most of us are not really doing null-move on a 30 ply search as that is usually a pawn ending where null-move is not so safe unless you resort to the verification search. And since testing has shown that idea to not be useful (it loses a couple of elo, in fact)

As far as deeper reductions (beyond R=3 go), I have not had any success with that, and I tested it an absolute ton before 23.0 was released. I tried linear interpolation, and exponential in both directions (tapers off rapidly or tapers off very slowly. Once I have a chance to test the old/new stockfish on the cluster, that will quickly show whether this idea is a good one or not. But it certainly isn't +150. And I'd have a hard time imagining it even being possible to reach +50 with this kind of change, since basic null-move doesn't give that big a boost by itself, and this is just an enhancement.

More when we get our A/C up so the cluster can wake up.

Just out of curiosity, what kind of time control do you do your testing of this kind of thing on? That is what always bothered me with fooling around with these kinds of things. Its not feasible for me to really explore the effect in long games, but the effects of this genre of change might be quite different at high depths than lower depths. Thus, I have always been a little suspicious of my results.

-Sam

[Dann Corbit]

Consider the following:
#ifdef SMOOTH_REDUCTION
double delta = approximateEval - beta;
delta = max(delta, 1.0);
double ddepth = double(depth);
double r = 0.18 * ddepth + 3.1 + log(delta)/5.0;
r = r > ddepth ? ddepth : r;
int R = int(r);
#else
// Null move dynamic reduction based on depth
int R = (depth >= 5 * OnePly ? 4 : 3);

// Null move dynamic reduction based on value
if (approximateEval - beta > PawnValueMidgame)
R++;
#endif

If depth = 5, then 0.18 * 5 = 0.9
So 0.9 + 3.1 gives 4.0 which is the same as the original formula.
In value.h, we find this:
const Value PawnValueMidgame = Value(0x0C6);
In decimal, C6 is 198.
log (base e) of 198 is 5.288
dividing 5.288 by 5 gives 1 (approximately).

So, for the points at the boundary conditions of the old formula, my curve gives the same answers (or answers pretty nearly). When you fit this idea to your code, I suggest that you calibrate the curve accordingly, especially if you have carefully weighed out your null move reduction constants by experiment.

The difference is that when we bend away from these answers the solution I propose slowly changes so that instead of slamming the door, we are slowly closing it.

The reason I came up with smooth scaling is that null move's abrupt nature really bothered me. Why do we reduce the same in a 30 ply search as we do in a 12 ply search? That does not make sense. Why do we reduce the same with a full queen advantage as with a knight advantage? That also seemed very strange. So I just did a simple extrapolation to smooth out the reductions in order that they made sense to me.

First, for the last two questions, the answer is because null-move is not doing exactly what you appear to think it is doing. It is a quick way to bail out of positions where you are so far ahead, if you give your opponent the ability to make two moves in a row, he can't catch up. This idea is unrelated to the actual material balance. Null-move helps when you start off a queen ahead, because it will only cause cutoffs if you get way _more_ than a queen ahead, so it is a relative algorithm, that is not dependent on the initial position's material balance. Most of us are not really doing null-move on a 30 ply search as that is usually a pawn ending where null-move is not so safe unless you resort to the verification search. And since testing has shown that idea to not be useful (it loses a couple of elo, in fact)

As far as deeper reductions (beyond R=3 go), I have not had any success with that, and I tested it an absolute ton before 23.0 was released. I tried linear interpolation, and exponential in both directions (tapers off rapidly or tapers off very slowly. Once I have a chance to test the old/new stockfish on the cluster, that will quickly show whether this idea is a good one or not. But it certainly isn't +150. And I'd have a hard time imagining it even being possible to reach +50 with this kind of change, since basic null-move doesn't give that big a boost by itself, and this is just an enhancement.

More when we get our A/C up so the cluster can wake up.

I am not using material balance. I am using previous search (if any) and in those cases where no search has ever been performed, it gets estimated though evaluation. The centipawn evaluations are returned through the hash table, and I only use eval if there is nothing else available.

I do not know where the idea will lead. It would not surprise me even if the sign of one or more of my coefficients were wrong. But if that is the case, then we will see even bigger improvements when it gets corrected.

By the way, I think that it is not just huge leads that need less effort but also huge deficits.

It is the positions where things are very close that we have to analyze way out to the fingertips.

[michiguel]

Consider the following:
#ifdef SMOOTH_REDUCTION
double delta = approximateEval - beta;
delta = max(delta, 1.0);
double ddepth = double(depth);
double r = 0.18 * ddepth + 3.1 + log(delta)/5.0;
r = r > ddepth ? ddepth : r;
int R = int(r);
#else
// Null move dynamic reduction based on depth
int R = (depth >= 5 * OnePly ? 4 : 3);

// Null move dynamic reduction based on value
if (approximateEval - beta > PawnValueMidgame)
R++;
#endif

If depth = 5, then 0.18 * 5 = 0.9
So 0.9 + 3.1 gives 4.0 which is the same as the original formula.
In value.h, we find this:
const Value PawnValueMidgame = Value(0x0C6);
In decimal, C6 is 198.
log (base e) of 198 is 5.288
dividing 5.288 by 5 gives 1 (approximately).

So, for the points at the boundary conditions of the old formula, my curve gives the same answers (or answers pretty nearly). When you fit this idea to your code, I suggest that you calibrate the curve accordingly, especially if you have carefully weighed out your null move reduction constants by experiment.

The difference is that when we bend away from these answers the solution I propose slowly changes so that instead of slamming the door, we are slowly closing it.

The reason I came up with smooth scaling is that null move's abrupt nature really bothered me. Why do we reduce the same in a 30 ply search as we do in a 12 ply search? That does not make sense. Why do we reduce the same with a full queen advantage as with a knight advantage? That also seemed very strange. So I just did a simple extrapolation to smooth out the reductions in order that they made sense to me.

This is for the non-believers and deniers

First of all, it needs to be tested, but some indicated that it should not work (based on intuition and/or theoretical issues). I disagree. It is wrong to say that if null move alone gives you 80 points, tweaking null move cannot give you more than, say, 20 points. It is possible to tweak nullmove and obtain a bigger boost than the addition of the technique itself... at least in theory...

Lets say that nullmove allows you to search 3 plies deeper. 3 plies deeper may mean 300 ELO points. Why do you see an increase of only 100 points? Because the search is full of holes. So, in this case, there is 200 points to be gained by avoiding the holes. It is as important to know WHEN to do cut off by nullmove as to the reduction you get. It is possible that Dann's adjustment may cause a more careful decision making at the level of nullmove for certain engines. I could see that this could be completely dependent on the engine.

That's simply wrong, and here's why.

I am not wrong, and this is why: I am saying exactly the same thing as you say

Just report your depth as 2 plies deeper. Are you any stronger? Null-move easily increased the typical search depth by more than 3 plies, but gets _nowhere_ near +300. I ran the test and reported these results earlier this year. NM is worth about +120 if you do not also do LMR. If you are doing LMR, NM will only add +80. Even with those extra plies.

Exactly my point. Why you get 120 and not 300? you should get 300 (ish, let's not fight for accuracy) if you magically reach 3 more plies WITHOUT nullmove, just by magically increasing your nps or whatever. That means you have 300 for reaching deeper - 180 for all the holes in the search. We can debate that this 180 I estimate here is not 180, but you may agree that it is a big number.

You are treating all plies as "equal" but they are not when there is selective pruning involved, and with NM that is exactly what is happening.

and BTW, this is not adaptive null move, it has nothing to do with the snippet from Robbert Litto, and who the heck cares whether someone whisper a similar thought about this 5 years ago. Drop y'all EGO points and test to see whether it gives ELO points.

No Ego here. You can look back to when we were working on 23.0 and find posts where I tried a ton of different approaches to the adaptive null-move idea. And this _is_ about adaptive null-move, not sure why you think it is not. The idea of a non-constant R value is, by definition, adaptive null-move. How the value is altered is wide-open to variations, of course, but it is still the same _idea_.

Let me rephrase: it is not the classical Heinz's implementation.

Miguel

In experimental science you learn that ideas are meaningless. My former PhD's advisor said to me, everybody has plenty, an most likely, yours is not original. Someone else is thinking about it or already did . What matters is the execution and who finally did it. What my PhD advisor was trying to say was (he was too polite to say it directly), "get your ass to the bench and start doing the experiment"

Miguel

Couldn't agree more. That's exactly why I test _every_ idea I come up with, and most that others suggest as well... My answers are almost always based on test results, not guesswork. If I give an opinion, I make it clear it is an opinion. If I give results, they are what they are.

[Dann Corbit]

And I agree fully with both of you.

I think that the idea should be investigated heuristically. The proof of the pudding is in the eating.

I think that the constants I chose should be ignored and replaced by sensible values.

I think that the natural logarithm function should be tossed and other distance compression ideas tried. Maybe we should even expand it (just kidding).

At any rate, I think that the right way to explore the idea is to test it out and also to systematically go through different combinations of coefficients and algorithms until a superior one is found or the entire idea is tossed into the trash bin.

[Milos]

Regarding your explanation I was just saying that when you write in your example depth = 5, actually it is depth = 2,5*OnePly so that when you say that with depth = 5 you have the same reduction by 4 of the original, this is not correct because the original with a depth = 5 (aka 2,5*OnePly) gets a reduction of 3 not 4.

Marco you are right, except for depth=5*OnePly, but just because of coincidence.
For depth=5*OnePly, r=0.18*10+3.1=4.9, R=(int)4.9=4.
However, already for depth=6*OnePly, r=0.18*12+3.1=5.26, R=(int)5.26=5.

On the other hand Robbo uses always R>=4, and it works quite well, so I'm starting to doubt seriously that R=3 is really optimal, despite huge respect for what Bob says.

[Dann Corbit]

Regarding your explanation I was just saying that when you write in your example depth = 5, actually it is depth = 2,5*OnePly so that when you say that with depth = 5 you have the same reduction by 4 of the original, this is not correct because the original with a depth = 5 (aka 2,5*OnePly) gets a reduction of 3 not 4.

Marco you are right, except for depth=5*OnePly, but just because of coincidence.
For depth=5*OnePly, r=0.18*10+3.1=4.9, R=(int)4.9=4.
However, already for depth=6*OnePly, r=0.18*12+3.1=5.26, R=(int)5.26=5.

On the other hand Robbo uses always R>=4, and it works quite well, so I'm starting to doubt seriously that R=3 is really optimal, despite huge respect for what Bob says.

I guess that each and every program will have its own optimal R factor, and also that the factor will change if they add LMR and it will change if they add other reductions.

When we decide what to examine less deeply, it will depend greatly on what the program is already doing in terms of reductions.

I think that a long and careful experiment with engine "X" to determine the optimal value for R cannot simply be translated to program "Y" and then we assume that it is best. I doubt it will work like that.

[Michael Sherwin]

And I agree fully with both of you.

I think that the idea should be investigated heuristically. The proof of the pudding is in the eating.

I think that the constants I chose should be ignored and replaced by sensible values.

I think that the natural logarithm function should be tossed and other distance compression ideas tried. Maybe we should even expand it (just kidding).

At any rate, I think that the right way to explore the idea is to test it out and also to systematically go through different combinations of coefficients and algorithms until a superior one is found or the entire idea is tossed into the trash bin.

If in Stockfish the elo gain is 150 points or even half of that then your formula may be covering up a flaw in Stockfish. I however, think that an aggressive reduction that is intelligent enough can lead to a big improvement. Adding delta is increasing the intelligence of Null Move.

[Milos]

I guess that each and every program will have its own optimal R factor, and also that the factor will change if they add LMR and it will change if they add other reductions.

This is exactly the point. Neither, 2 nor 3 nor 4 is carved in stone.
It has to be determined for each program what is the optimal value, and even though 3 might be the most optimal for Crafty, for SF it might be even 5, or some gradual change between 3 and 5.