Questions on Razoring and Code Structure for Pruning

[Cheney]

Hi,

I have recently added in extended futility pruning (up to 3 plys) and am having some positive success.

I am reading about Razoring, have tried laying in some flavors of code, tests are not positive. I also decided to look at some other code and now wonder about more than razoring but also code structure.

In reading about Razoring on CPW (https://www.chessprogramming.org/Razoring), the original proposal discusses obtaining the evaluation for each move, sorting that list of moves in decreasing order, and once a move's eval score cannot beat alpha, prune that move and all following moves. I imagine this can happen during/after move generation and the decision to prune happens within the move playing loop.

However, the approaches discussed further down on the page discuss either reducing the depth by 1 or dropping into qsearch. It also appears to be that this is happening before the loop to iterate and play moves.

My first question here is how are the two models the same? What is the true definition of razoring?

The next thought I have on this is how it works with futility pruning (FP). Before my move loop, I set a futile flag for the node I am in (if the static eval score + margin < alpha). Then, within the move loop for that node, certain moves can be pruned. These moves might be moves with or without a history value used for move ordering. But when I think about it, a lot of moves are potentially pruned at any given node. So when I think of razoring, I have to imagine it needs to follow the same rules as FP - do not razor when: in check, delivering check, alpha is near mate, etc.

My question here is about the implementation. If FP is pruning all those moves at depth <=3 then why would I want to run a qsearch on each move or "sort and prune" a contiguous set of ordered moves? Is it maybe I look to do razoring if a node is not flagged for pruning and maybe make the razoring marine less than the futility margin?

Last is when I review other code from other engines, I see razoring and futility pruning performed when entering a node to search (before generating and looping moves) and I will also see futility pruning pre-move-make (within the move loop).

What is the advantage here? I believe performing the pruning method in the top of the node is the same as performing it after making the move where the catch is if I do this in the top of the node, I have to return a score. Is this accurate? Is doing this more efficient?

Thank you

[hgm]

Normally the margin for futility pruning is so large that you don't distinguish moves by anything other than the value of the captured piece. So either all non-captures are futile, or none is. If all are futile, it is a bit of a waste of time to loop through all of them, to conclude it one by one.

The normal move ordering, where you sort the captures by MVV, would already be what you need. As soon as you get to victims whose capture does not bring you above alpha - MARGIN, ging on is pointless. If you do staged move generation, there isn't even any need to generate the remaining moves.

When you want to exempt checks from pruning, it depends on how you detect that moves are checks. If you can only test that on move by move basis, you will have to loop through all moves. OTOH, you might have a special move generator that selectively generates checks.

At d=1 (after a possible extension) there is no need to exempt check evasions. If these are futile, they are guaranteed to fail low.

[brianr]

Just mentioning that Crafty "has it all" (razoring and many other things, IIRC), and is reasonably well documented.
Many comments in main.c so look there too.
Whether or not they work for you is unknown.
Experiment and have fun.

[Cheney]

Ty

The easy answer - I have reviewed the Crafty code and did not see razoring. I believe Dr. Hyatt removed that; I have seen comments on other posts where it was removed. I forgot about main.c and all the details there, going to read it, thanks.

Normally the margin for futility pruning is so large that you don't distinguish moves by anything other than the value of the captured piece. So either all non-captures are futile, or none is. If all are futile, it is a bit of a waste of time to loop through all of them, to conclude it one by one.

The margin I have for futility pruning is rather low {100, 150, 300} and works rather well. On another post you recently helped me with regarding this, I was using 650 at one point . Are you possibly referring to the margin for razoring is large or am I missing the point?

During move generation, I performed a phased generation - the hash, then all captures using MVV, then all non-capture (silent), and when needed, I have an evasion generator. During move generation, any move that delivers or discovers check will have a bit set to flag that move to not prune. Thus, when using Futility Pruning and all silent moves have been generated, all checking moves will be searched. In regards to the quote above, are you saying, from a Razoring perspective, once I play those captures, I can consider all following moves futile and just not search them?

I am still testing a few models out, but I feel, in the end, I need help understanding exactly what Razoring is. Per CPW's reference, the first definition sounds like a pruning technique while the references on the page seem more like a late reduction.

I appreciate your time with this

[jdart]

Last is when I review other code from other engines, I see razoring and futility pruning performed when entering a node to search (before generating and looping moves) and I will also see futility pruning pre-move-make (within the move loop).

Razoring as the term is commonly used is a pre-search pruning step. As implemented in Stockfish, if the eval is very bad, then you basically drop into the q-search early. Stockfish now does this only at depth==1 and with a very large margin.

Futility pruning is performed on a per-move basis during the search loop. It compares the eval + max possible gain from a move + a margin to the current window. If the move is likely to fail low, it will be skipped.

These are different techniques and can be used together.

--Jon

[Cheney]

OK, thanks! I did attempt that before the search and when it failed miserably (getting deeper but playing crazy lines) I figured I was not understanding the process.

I tried various options, like trying it only when futility pruning was not allowed, static depths, smaller margins, etc. I did not increase the margins.

I cannot recall the last time I looked at StockFish but maybe I will after I go a few more rounds with this. Ty

[brianr]

The easy answer - I have reviewed the Crafty code and did not see razoring. I believe Dr. Hyatt removed that; I have seen comments on other posts where it was removed. I forgot about main.c and all the details there, going to read it, thanks.

Yes, I forgot that a LOT of code has been removed from Crafty after exhaustive testing (30,000 games at a time on a large cluster, IIRC to measure small Elo changes). However, it is still "out there" in the older versions, of which I happen to have quite a few. I think there are sites where someone was collecting them also, so you could dig a bit if you feel it is worthwhile.

[hgm]

The margin I have for futility pruning is rather low {100, 150, 300} and works rather well. On another post you recently helped me with regarding this, I was using 650 at one point . Are you possibly referring to the margin for razoring is large or am I missing the point?

I just meant to say that looping through 30 non-captures to test each of them for futility, when it is guaranteed in advance that every single one of those will be futile is sort of a waste of time.

As implemented in Stockfish, if the eval is very bad, then you basically drop into the q-search early. Stockfish now does this only at depth==1 and with a very large margin.

I don't get that. 'Very bad' here means below alpha minus a rather small margin? Because that is what it automatically boils down to: if only captures stand a chance to raise the score above alpha, you will only search captures, and prune all non-captures.

[jdart]

I don't get that. 'Very bad' here means below alpha minus a rather small margin? Because that is what it automatically boils down to: if only captures stand a chance to raise the score above alpha, you will only search captures, and prune all non-captures.

No, there is an eval test, and the margin is about 5 pawns IIRC.
The code is:

Code: Select all

if (   !rootNode // The required rootNode PV handling is not available in qsearch
        &&  depth == 1
        &&  eval <= alpha - RazorMargin)
        return qsearch<NT>(pos, ss, alpha, beta);

So if the eval is considerably below alpha, you can probably prune the node. But the qsearch is called in case there is some capture or promotion that would bring the eval above alpha. This however is not a big winner ELO wise. Other techniques like late move pruning are more significant.

[hgm]

This just seems extra code for no purpose. All non-captures and captures of Pawns, minors and Rooks would have been pruned because of futility anyway, if you are that much below alpha, and only promotion to Queen or Queen capture would not have been futile. So the node would have done nothing different from QS anyway.