Razoring...

[mcostalba]

How can you try razoring _before_ null-move? You do null move search first, before you generate moves or anything. Razoring is applied to each individual move near the tips. But this can only happen after null-search has been completed and you start to search real moves to normal depth.

??????


Razoring is applied at the same level of null move search, i.e. BEFORE the moves are generated.

If the (full or quick) evaluation of the position is very low and qsearch verification still keeps the low value node is completely razored away, this before to generate the moves and enter the moves loop for that position.

Am I missing something?

[bob]

How can you try razoring _before_ null-move? You do null move search first, before you generate moves or anything. Razoring is applied to each individual move near the tips. But this can only happen after null-search has been completed and you start to search real moves to normal depth.

??????


Razoring is applied at the same level of null move search, i.e. BEFORE the moves are generated.

If the (full or quick) evaluation of the position is very low and qsearch verification still keeps the low value node is completely razored away, this before to generate the moves and enter the moves loop for that position.

Am I missing something?

I am using razoring as explained in Heinz's book. This is applied two moves prior to the frontier and simply reduces the search by one ply if a specific move is not extended, we are not in check, the bound doesn't suggest mate has been found, and a quick eval + some margin is below alpha.

This is done in the body of the search, as each move is searched. Null-move is done at the top of search before any move is searched. If you use Heinz's somewhat twisted search algorithm, you might do things differently. Most of us have a loop in search where we select a move, make it, call search, unmake the move, and continue the loop. Heinz did the more unusual structure where you generate the moves, and in a loop pass each one to a recursive search call where they are made/unmade there...

But razoring applies to a specific move, where null-move applies to the beginning of a ply before a move is even made.

[mcostalba]

But razoring applies to a specific move, where null-move applies to the beginning of a ply before a move is even made.

mmmmmm....I would think a bit of clarification on naming standards would help. For what I have seen (and also from the Norman example above) we have:

Razoring: when if the evaluation is very low, we don't are in check and perhaps some other condition _on the position_ not on any move, we return with a fail low value if a quick qsearch does not rise the score enough.

If razoring is passed then we generate the moves and enter the moves loop (in any program that I have seen, also in crafty). Inside the loop we get a move and then:

Futility pruning based on value: if position has a low value and the _move_ is not interesting (capture, check, etc..) we discard without testing with do_move() / undo_move() and simply pass to the next move.

LMR: if we are at the end of the move list and move is not interesting, as example does not have a good history then we search the move with reduced depth or we discard (this is also called history pruning).


So the main difference between razoring and the other pruning techniques and a difference that is easily spottable is that:

If razoring succed we RETURN from search(), while in all the other cases we CONTINUE to the next move.

As said the above example of Norman is like this, and also all the implementations of razoring that I know, mainly Glaurung one.

Still missing something ?

Thanks
Marco

[bob]

But razoring applies to a specific move, where null-move applies to the beginning of a ply before a move is even made.

mmmmmm....I would think a bit of clarification on naming standards would help. For what I have seen (and also from the Norman example above) we have:

Razoring: when if the evaluation is very low, we don't are in check and perhaps some other condition _on the position_ not on any move, we return with a fail low value if a quick qsearch does not rise the score enough.

If razoring is passed then we generate the moves and enter the moves loop (in any program that I have seen, also in crafty). Inside the loop we get a move and then:

Futility pruning based on value: if position has a low value and the _move_ is not interesting (capture, check, etc..) we discard without testing with do_move() / undo_move() and simply pass to the next move.

LMR: if we are at the end of the move list and move is not interesting, as example does not have a good history then we search the move with reduced depth or we discard (this is also called history pruning).


So the main difference between razoring and the other pruning techniques and a difference that is easily spottable is that:

If razoring succed we RETURN from search(), while in all the other cases we CONTINUE to the next move.

As said the above example of Norman is like this, and also all the implementations of razoring that I know, mainly Glaurung one.

Still missing something ?

Thanks
Marco

I can only tell you that in the implementation I did from Heinz's paper, razoring is applied to a _move_. He explicitly mentioned never razoring a move that was a check, nor at a position where the alpha bound is close to MATE. Razoring just drops a ply and drops into the q-search. How can you do that without making a move first?

This might be semantical in nature since as I mentioned, Heinz uses a non-standard approach of choosing a move and recursively calling Search() with that move. That instance of search then makes the move, generates more moves for the other side, and sequentially passes those to yet another instance of Search.

Most seem to do it as I do it, which as Ken Thompson's simple negamax search pseudo-code did it, because it is more understandable. But in either approach, you apply razoring to a specific move. whether it be as I do, after I make a move and before calling search recursively, or whether it is as Heinz did and call search recursively to make the move in question.

As far as your "easily spotted difference" that is normal. We reduce a move and hope we don't need to re-search. With null-move we try for a quick cutoff. With LMR we reduce most moves and hope we don't get a fail-high. I don't find any significant use in razoring, but I have not removed it. Conceptually it is very close to LMR except that for LMR, we exclude certain moves but reduce everywhere in the tree. With razoring, we exclude fewer moves, but only apply it close to the "frontier" of the search.

We don't allow LMR to drop us right in to q-search, while razoring does exactly that.

[bob]

But razoring applies to a specific move, where null-move applies to the beginning of a ply before a move is even made.

mmmmmm....I would think a bit of clarification on naming standards would help. For what I have seen (and also from the Norman example above) we have:

Razoring: when if the evaluation is very low, we don't are in check and perhaps some other condition _on the position_ not on any move, we return with a fail low value if a quick qsearch does not rise the score enough.

If razoring is passed then we generate the moves and enter the moves loop (in any program that I have seen, also in crafty). Inside the loop we get a move and then:

Futility pruning based on value: if position has a low value and the _move_ is not interesting (capture, check, etc..) we discard without testing with do_move() / undo_move() and simply pass to the next move.

LMR: if we are at the end of the move list and move is not interesting, as example does not have a good history then we search the move with reduced depth or we discard (this is also called history pruning).


So the main difference between razoring and the other pruning techniques and a difference that is easily spottable is that:

If razoring succed we RETURN from search(), while in all the other cases we CONTINUE to the next move.

As said the above example of Norman is like this, and also all the implementations of razoring that I know, mainly Glaurung one.

Still missing something ?

Thanks
Marco

I can only tell you that in the implementation I did from Heinz's paper, razoring is applied to a _move_. He explicitly mentioned never razoring a move that was a check, nor at a position where the alpha bound is close to MATE. Razoring just drops a ply and drops into the q-search. How can you do that without making a move first?

This might be semantical in nature since as I mentioned, Heinz uses a non-standard approach of choosing a move and recursively calling Search() with that move. That instance of search then makes the move, generates more moves for the other side, and sequentially passes those to yet another instance of Search.

Most seem to do it as I do it, which as Ken Thompson's simple negamax search pseudo-code did it, because it is more understandable. But in either approach, you apply razoring to a specific move. whether it be as I do, after I make a move and before calling search recursively, or whether it is as Heinz did and call search recursively to make the move in question.

As far as your "easily spotted difference" that is normal. We reduce a move and hope we don't need to re-search. With null-move we try for a quick cutoff. With LMR we reduce most moves and hope we don't get a fail-high. I don't find any significant use in razoring, but I have not removed it. Conceptually it is very close to LMR except that for LMR, we exclude certain moves but reduce everywhere in the tree. With razoring, we exclude fewer moves, but only apply it close to the "frontier" of the search.

We don't allow LMR to drop us right in to q-search, while razoring does exactly that.

[wgarvin]

But razoring applies to a specific move, where null-move applies to the beginning of a ply before a move is even made.

mmmmmm....I would think a bit of clarification on naming standards would help. For what I have seen (and also from the Norman example above) we have:

Razoring: when if the evaluation is very low, we don't are in check and perhaps some other condition _on the position_ not on any move, we return with a fail low value if a quick qsearch does not rise the score enough.

If razoring is passed then we generate the moves and enter the moves loop (in any program that I have seen, also in crafty). Inside the loop we get a move and then:

Futility pruning based on value: if position has a low value and the _move_ is not interesting (capture, check, etc..) we discard without testing with do_move() / undo_move() and simply pass to the next move.

LMR: if we are at the end of the move list and move is not interesting, as example does not have a good history then we search the move with reduced depth or we discard (this is also called history pruning).


So the main difference between razoring and the other pruning techniques and a difference that is easily spottable is that:

If razoring succed we RETURN from search(), while in all the other cases we CONTINUE to the next move.

As said the above example of Norman is like this, and also all the implementations of razoring that I know, mainly Glaurung one.

Still missing something ?

Thanks
Marco

The wiki has a page about AEL Pruning, which is what Heinz called the combination of null move pruning with R=2~3, "Extended Futility Pruning" and "Limited Razoring".

The pseudo-code there should make it clear that "futility pruning", "extended futility pruning" and "limited razoring" are all pretty much the same thing, except with different depths and different "futility margin".

The greater the remaining depth, the more lousy the move needs to be before it can be safely pruned. So futility might use a margin of a couple pawns, extended futility a margin of a rook, and razoring a margin of a queen. Or something like that.

[bob]

But razoring applies to a specific move, where null-move applies to the beginning of a ply before a move is even made.

mmmmmm....I would think a bit of clarification on naming standards would help. For what I have seen (and also from the Norman example above) we have:

Razoring: when if the evaluation is very low, we don't are in check and perhaps some other condition _on the position_ not on any move, we return with a fail low value if a quick qsearch does not rise the score enough.

If razoring is passed then we generate the moves and enter the moves loop (in any program that I have seen, also in crafty). Inside the loop we get a move and then:

Futility pruning based on value: if position has a low value and the _move_ is not interesting (capture, check, etc..) we discard without testing with do_move() / undo_move() and simply pass to the next move.

LMR: if we are at the end of the move list and move is not interesting, as example does not have a good history then we search the move with reduced depth or we discard (this is also called history pruning).


So the main difference between razoring and the other pruning techniques and a difference that is easily spottable is that:

If razoring succed we RETURN from search(), while in all the other cases we CONTINUE to the next move.

As said the above example of Norman is like this, and also all the implementations of razoring that I know, mainly Glaurung one.

Still missing something ?

Thanks
Marco

The wiki has a page about AEL Pruning, which is what Heinz called the combination of null move pruning with R=2~3, "Extended Futility Pruning" and "Limited Razoring".

The pseudo-code there should make it clear that "futility pruning", "extended futility pruning" and "limited razoring" are all pretty much the same thing, except with different depths and different "futility margin".

The greater the remaining depth, the more lousy the move needs to be before it can be safely pruned. So futility might use a margin of a couple pawns, extended futility a margin of a rook, and razoring a margin of a queen. Or something like that.

That is included in Crafty's search. I found his margins to be way off when using cluster testing. You can see the numbers in Crafty. Those were chosen after varying the margin up and down and playing 32K game matches with each setting, to choose the best one.

[jdart]

It is one of the changes I put in rather recently (in my 11.3 release) and it seemed to help. I tried it before though and got bad results.

There are various guards you can use around this. My implementation looks like this:

else if (!node->PV() && (node-1)->extensions == 0 &&
Capture((node-1)->last_move) == Empty &&
depth <= 4*DEPTH_INCREMENT && depth>DEPTH_INCREMENT) {
int margin = depth <= 2*DEPTH_INCREMENT ? (3*PAWN_VALUE/2) : 3*PAWN_VALUE;
if (scoring.evalu8(board) < node->beta - margin) {
int v = quiesce(node->beta-1,node->beta,ply,0);
if(v < node->beta) {
#ifdef _TRACE
indent(ply); cout << "razored node, score=" << v << endl;
#endif
controller->stats->num_razored++;
return v;
}
}


So I don't razor on PV nodes, if the last move was a capture or if any extension was done in the previous node. The margin is variable based on depth.

My theory about not doing razoring after captures was that the static eval test isn't valuable at that point: your opponent just took something and if you can't retake you are hosed. So the first test in razoring (compare static eval) will pretty much always succeed. It doesn't tell you anything about positional "goodness" or "badness".

And I didn't want to do it after extensions because you if had a reason to extend the previous node, slicing off all moves once you get there seemed a bit extreme.

--Jon

[mcostalba]

It is one of the changes I put in rather recently (in my 11.3 release) and it seemed to help. I tried it before though and got bad results.

There are various guards you can use around this. My implementation looks like this:

Code: Select all

    else if (!node->PV() && (node-1)->extensions == 0 &&
             Capture((node-1)->last_move) == Empty && 
             depth <= 4*DEPTH_INCREMENT && depth>DEPTH_INCREMENT&#41; &#123;
      int margin = depth <= 2*DEPTH_INCREMENT ? &#40;3*PAWN_VALUE/2&#41; &#58; 3*PAWN_VALUE;
      if &#40;scoring.evalu8&#40;board&#41; < node->beta - margin&#41; &#123;
         int v = quiesce&#40;node->beta-1,node->beta,ply,0&#41;;
         if&#40;v < node->beta&#41; &#123;
#ifdef _TRACE
	   indent&#40;ply&#41;; cout << "razored node, score=" << v << endl;
#endif
	   controller->stats->num_razored++;
           return v;
         &#125;
      &#125;

Hi Jon,

thanks for sharing !

Nor razoring if previous move was extended it seem a nice idea, I will try it.

Also in glaurung there is no razoring in PV.

Not razoring at ply one is an idea I have implemented and actually Stockfish 1.2 works that way, but for the new version Joona come up with a better idea.

I have only statistically tested not razoring if previous move is a capture but I have found the % of previous moves that are capture is the same both _before_ and _after_ the qsearch verification search, while according to your scheme after the qsearch this % should have dropped due to captured piece value artifact.

So I have discarded the idea but without actually testing with real games.

There is also one more condition that I won't reveal that seem to work for me, but don't get upset, I am almost ready to release new Stockfish so that you will be able to check yourself.

Marco

P.S: I would guess that before the "else if" in the first line of your code example there is the null move search...

[jdart]

P.S: I would guess that before the "else if" in the first line of your code example there is the null move search...

That is correct. Full source code is available.

--Jon