Razoring

[bob]

So then, what is razoring?

If you read the prior posts you'll see that your question has already been answered multiple times. The thread is about razoring as implemented by Stockfish (as introduced by Tord). Not about razoring as introduced by Heinz.

But the current subthread is also about Bob's claim that both were essentially the same, which both Ed and myself doubt, and presumably also Marco and you.

Sven

What I said was this:

If you search to (say) ply 10, and generate all the moves there. You can, after making each move, make a decision to go directly to q-search for any that meet whatever criteria you use.

OR

You can search to ply 10, generate all the moves there, and make them one at a time. When you get to ply 11, you can do the "node razoring" at the top of search and make the decision to go directly to q-search, or continue the normal search.

They are exactly the same thing.

Does it matter whether you extend when you give check, or when you get out of check? There is one subtle difference, but if you ignore that tiny difference (which doesn't apply to the razoring idea above) on one of these,you extend the MOVE. On the other you extend the resulting POSITION. Exactly the same thing.

I like the former as it is slightly more efficient than the latter, because with the former your call graph goes like this:

Search(10) -> Quiesce(11)

With the latter you get this:

Search(10) -> Search(11) -> Quiesce(11)

where the numbers in parentheses is the ply for that instance of the procedure call.

[bob]

At ply=10 I can make a "razoring decision" move by move, by either searching a move normally, or going directly to q-search. OR, at ply=11, I can razor the entire node produced by one or more of the moves at the previous ply by dropping directly to q-search. Those are identical. Only difference is, the former did not do the unnecessary call to search, only to have it immediately call q-search.

Those are not identical, Bob.

Whatever you do with one of the moves at ply=10: pruning, reducing, dropping into q-search, you name it, is some kind of reducing the subtree size of a presumably bad move. If you instead call search() on that move then the resulting node at ply=11 is not one that you would razor, prune or whatever, since that node is now presumably going to produce a fail HIGH from the opponent's viewpoint, by one of his moves producing a beta cutoff. (That is also the reason why your point about dropping into q-search on a move-by-move basis at ply=10 is completely wrong: a q-search for a bad move can only confirm, from the opponent's viewpoint, that it was bad since the opponent can presumably win material, but at least does not lose material as a result of the q-search due to "stand pat". The "dropping into q-search" as introduced by Tord is applied to bad positions, i.e. at the node level, not to "bad moves" which would be useless.)

The razoring, pruning, or other kind of subtree size reduction of a move at ply=10 is therefore based on the prediction that the corresponding child node will fail high anyway.

Now that subtree size reduction for some moves at ply=10 typically appears if the position itself at ply=10 is already quite bad so that many moves will be affected. Razoring according to Heinz, combined with his extended futility pruning, does this:

Thence, the overall effect of limited razoring at pre-pre-frontier nodes is to cut off quiet moves and non-checking captures with insufficient material gains and a remaining depth of 3 plies while reducing the search depth of all other moves by 1 ply if the side-to-move suffers from a severe disadvantage.

I can imagine that the basic idea of razoring as introduced by Tord (Glaurung/Stockfish) could be to replace the Heinz-like "reduction by 1 ply" for all checks and all non-checking captures with *sufficient* material gains by even more of a reduction through dropping into q-search for the whole node, which covers almost exactly to search only those moves (checks + good captures) but with a much smaller tree size. By doing so you try to verify that the moving side which is in a bad situation has no obvious tactical shot. But this is an entirely different idea than the Heinz-like razoring + extended futility pruning, and may include more of a risk.

I hope that we can agree on that so far.

Sven

I don't follow that at all.

At ply=10 I can make a decision to go directly to q-search. Which means 10 full plies of normal search and then we drop into q-search.

At ply=10 I call Search() for ply 11 and at ply 11, I decide to go directly to q-search.

Now if you are talking about "OK, what happens if you do that razoring at the beginning of ply 11, but then you decide to ignore the results you get and do a normal search instead?" then that is different. But that is not razoring as it has been defined in the literature to date. And it should be called something else, because ambiguity in terms has to be avoided, perhaps as in this example discussion...

[Sven]

So then, what is razoring?

If you read the prior posts you'll see that your question has already been answered multiple times. The thread is about razoring as implemented by Stockfish (as introduced by Tord). Not about razoring as introduced by Heinz.

But the current subthread is also about Bob's claim that both were essentially the same, which both Ed and myself doubt, and presumably also Marco and you.

Sven

What I said was this:

If you search to (say) ply 10, and generate all the moves there. You can, after making each move, make a decision to go directly to q-search for any that meet whatever criteria you use.

OR

You can search to ply 10, generate all the moves there, and make them one at a time. When you get to ply 11, you can do the "node razoring" at the top of search and make the decision to go directly to q-search, or continue the normal search.

They are exactly the same thing.

Does it matter whether you extend when you give check, or when you get out of check? There is one subtle difference, but if you ignore that tiny difference (which doesn't apply to the razoring idea above) on one of these,you extend the MOVE. On the other you extend the resulting POSITION. Exactly the same thing.

I like the former as it is slightly more efficient than the latter, because with the former your call graph goes like this:

Search(10) -> Quiesce(11)

With the latter you get this:

Search(10) -> Search(11) -> Quiesce(11)

where the numbers in parentheses is the ply for that instance of the procedure call.

So your model is different from what it looked like to me initially, perhaps since you did not explain it like that in the beginning. That does not change very much regarding the two different razoring approaches but let's be more precise. I understand your model as follows:

At ply=10 the opponent has several moves which put me into a bad position. The razoring method discussed in the beginning of this thread implies to call search() for each of these moves, and at ply=11 the razoring condition is checked from "my" viewpoint, eventually causing the search to drop into q-search.

Your proposal to improve its performance is to perform that checking of the razoring condition before (and therefore possibly without) doing the recursive search() call. That is plausible, so indeed I can't call it "completely wrong" any longer. But it implies to transform the razoring condition from ply=11 ("my" viewpoint) into an equivalent condition at ply=10, after makeMove() but before search(), and therefore from "his" viewpoint. Since at ply=11 ("my" bad position) the razoring condition is basically something like

Code: Select all

eval() + razorMargin <= alpha11

and alpha11 (i.e. alpha at ply=11) corresponds to -(alpha10 + 1) if we restrict razoring to non-PV nodes where the zero-window search is applied (=> alpha == beta - 1) then we get this transformed condition at ply 10, after makeMove() but before search():

Code: Select all

eval() + razorMargin <= -(alpha10 + 1)

This could work.

But now you also say, if I understood you correctly, that this were identical to the Heinz-like razoring. And this is were I still have to disagree. It is obviously something else. After my correction above that follows your performance-improved model while keeping your ply=10/ply=11 example I would say that the Heinz method is always applied at ply=11 and (in conjunction with extended FP) reduces/prunes some ply=11 moves that are assumed to be bad. One can immediately see that applying Heinz-like razoring at ply=10 would not match the given scenario since the transformed razoring condition is completely different, it is derived from the bounds at the next ply.

Sven

[bob]

So then, what is razoring?

If you read the prior posts you'll see that your question has already been answered multiple times. The thread is about razoring as implemented by Stockfish (as introduced by Tord). Not about razoring as introduced by Heinz.

But the current subthread is also about Bob's claim that both were essentially the same, which both Ed and myself doubt, and presumably also Marco and you.

Sven

What I said was this:

If you search to (say) ply 10, and generate all the moves there. You can, after making each move, make a decision to go directly to q-search for any that meet whatever criteria you use.

OR

You can search to ply 10, generate all the moves there, and make them one at a time. When you get to ply 11, you can do the "node razoring" at the top of search and make the decision to go directly to q-search, or continue the normal search.

They are exactly the same thing.

Does it matter whether you extend when you give check, or when you get out of check? There is one subtle difference, but if you ignore that tiny difference (which doesn't apply to the razoring idea above) on one of these,you extend the MOVE. On the other you extend the resulting POSITION. Exactly the same thing.

I like the former as it is slightly more efficient than the latter, because with the former your call graph goes like this:

Search(10) -> Quiesce(11)

With the latter you get this:

Search(10) -> Search(11) -> Quiesce(11)

where the numbers in parentheses is the ply for that instance of the procedure call.

So your model is different from what it looked like to me initially, perhaps since you did not explain it like that in the beginning. That does not change very much regarding the two different razoring approaches but let's be more precise. I understand your model as follows:

At ply=10 the opponent has several moves which put me into a bad position. The razoring method discussed in the beginning of this thread implies to call search() for each of these moves, and at ply=11 the razoring condition is checked from "my" viewpoint, eventually causing the search to drop into q-search.

Your proposal to improve its performance is to perform that checking of the razoring condition before (and therefore possibly without) doing the recursive search() call. That is plausible, so indeed I can't call it "completely wrong" any longer. But it implies to transform the razoring condition from ply=11 ("my" viewpoint) into an equivalent condition at ply=10, after makeMove() but before search(), and therefore from "his" viewpoint. Since at ply=11 ("my" bad position) the razoring condition is basically something like

Code: Select all

eval() + razorMargin <= alpha11

and alpha11 (i.e. alpha at ply=11) corresponds to -(alpha10 + 1) if we restrict razoring to non-PV nodes where the zero-window search is applied (=> alpha == beta - 1) then we get this transformed condition at ply 10, after makeMove() but before search():

Code: Select all

eval() + razorMargin <= -(alpha10 + 1)

This could work.

But now you also say, if I understood you correctly, that this were identical to the Heinz-like razoring. And this is were I still have to disagree. It is obviously something else. After my correction above that follows your performance-improved model while keeping your ply=10/ply=11 example I would say that the Heinz method is always applied at ply=11 and (in conjunction with extended FP) reduces/prunes some ply=11 moves that are assumed to be bad. One can immediately see that applying Heinz-like razoring at ply=10 would not match the given scenario since the transformed razoring condition is completely different, it is derived from the bounds at the next ply.

Sven

I still think either is identical in result. But it caused me some issues because when you think about it, when Heinz says depth=2, that id depth=3 to me because of how his search is written. That's how I found that actual pruning in the last 4 plies worked. I thought I was doing what he said and used the value that was off by one because of the difference in how we count plies...

In any case, I don't razor at all any longer, so it doesn't make much difference. I think LMR subsumes all of that concept nicely...

[Rebel]

I can read, the question was to Bob.

But even so it is clear from his postings that Bob uses the term in the sense of Heinz. So there is no ambiguity there either.

Once again, I can read

I still think for clarity reasons to drop the term razoring and replace it as follows:

move_futility (Heinz)
node_futility (Tord)

[bob]

I can read, the question was to Bob.

But even so it is clear from his postings that Bob uses the term in the sense of Heinz. So there is no ambiguity there either.

Once again, I can read

I still think for clarity reasons to drop the term razoring and replace it as follows:

move_futility (Heinz)
node_futility (Tord)

I certainly think those are wrong.

This is not "futility" which has been "futility pruning" forever. I used a variable "delta" in Crafty's q-search to implement this idea, and some mistakenly started to refer to "delta pruning" and attributed it to me. I used a variable "delta" that basically "alpha - material_balance" which told me how much material I needed to gain to get the score back to within the window. It was a simple idea that says "if you are a queen down, then even a safe pawn capture is a waste of time to search". Classic futility pruning (in the q-search only) that I did not invent, so far as I know. I was doing this q-search trick in the 70's in Blitz and then Cray Blitz. Whether that was the first "q-search futility pruning" or not I have no idea... Slate did not do it, however, as I did at one time have chess 4.x source.

Reductions are in the same "family" as rather than just pruning a move and tossing it out forever, you search it to reduced depth. One can do this right after making a move as I do, or one could do it at the top of search at the next ply, if you prefer.

Hopefully we retain the accepted definitions for pruning vs reductions/extensions. And I suppose one could use the terms "futility pruning" (futility means hopeless, so this is pruning moves that have no hope of helping us improve things) or "futility reductions" where one reduces the tree for the same reason. I've always associated "futility" with pruning and "razoring" with reductions. Except that razoring went by the wayside since we now know it is safe to reduce throughout the tree, not just in the last 2-3 plies as the original razoring papers described.

[Eelco de Groot]

Code: Select all

    // Step 6. Razoring (is omitted in PV nodes)
    if (   !PvNode
        &&  depth < RazorDepth
        && !inCheck
        &&  refinedValue + razor_margin(depth) < beta
        &&  !(tte && tte->type() == VALUE_TYPE_UPPER) //[condition was: ttMove == MOVE_NONE]

A bit off topic but in case Marco or Joona or Tord are reading, for Stockfish maybe it is an idea to add an assert, for instance in the singular extension code, that SingularExtensionDepth should be >= 2 * RazorDepth.

Otherwise there is a risk that with depth/2 as the search depth, the search might start razoring and fall into qsearch(). And as far as I can see there is no code in qsearch() yet that will omit a move if it is set as the excluded move. I have not checked movepick.cpp yet but anyway, an assert or comment would not hurt in search. For now I think all is well because the SingularExtensionDepth is 8*ONE_PLY and RazorDepth 4*ONE_PLY but if you change that, I think it is a bit inconsistent to allow the excluded move again in qsearch.

At present I added for Rainbow Serpent in the razoring code the condition that && excludedMove == MOVE_NONE should be true for razoring to be allowed, but I think that certainly if you add no warning or an assert, the code would be safer if in qsearch() there is a check for an excluded move and not try that move. I know that it is important also to speed optimize qsearch but I don't think it will slow qsearch down much. It would theoretically allow razoring again in the exclusion search which might help a little, of course only if you start singular extensions at smaller depths than 8*One_PLY in Non PV nodes or if you would want to increase the RazorDepth (I don't think that works very well particularly, larger RazorDepths, but I did try smaller depths for the exclusion search in the past).

As the topic is razoring, this is still related to the razoring code I think.
I wanted to say a bit more about the codechanges above in Rainbow Serpent - and the feedback I received was appreciated Marco and Robert -, but that can wait, the thread is already getting rather large

Regards, Eelco