Using SEE to prune in main search

[bob]

Instead of pruning I reduce capture moves with bad SEE in main search, similar to LMR - got around 4 to 8 rating points on this. There could be some potential in utilizing SEE for pruning and reduction.

This is also what worked for me. At one point, I followed the dogma of "do not reduce checks, captures, etc." I now modify that to "do not reduce those moves if SEE >= 0, which lets me reduce spite checks and horrible captures like QxP when P is protected... I have not yet found any success with pruning except for in the last 4 plies as my "modified futility pruning" approach does currently. In the last few plies, if score is below alpha by some margin that increases as the remaining plies increases, I will prune the moves outright...

and what about "upping the ante"? i.e in addition to what you are doing, look at further reductions when SEE <0 at low depths.

That is one of the areas I am experimenting with at the moment, in fact. I am studying the idea of variable reductions, particularly after adding history move ordering back in so that there is some sense of how good a move is by how early or late it is ordered...

When you say "low depths" I assume you mean well out into the tree, not near the root?

absolutely - nodes near the leaves of the tree, say when depth<3

That is what I thought. I refer to those as low draft. "low depth" traditionally means "closer to the root" which I was pretty sure you were not thinking of.

[phhnguyen]

Having a look at the latest stockfish, they are using SEE in a different way, to help prune non-captures in the main search.

Have not studied stockfish yet, but this makes me so confuse. Can you or someone explain how stockfish applies SEE to non-captures? Or is that not "original" SEE (which always works with captures) as we usually understand?

[micron]

Have not studied stockfish yet, but this makes me so confuse. Can you or someone explain how stockfish applies SEE to non-captures? Or is that not "original" SEE (which always works with captures) as we usually understand?

Common SEE functions work, with no code changes, for non-capture moves. The returned score is in the range [-value_of_moving_piece, 0]. Thus the SEE value of a non-capture move can easily be used for decisions about pruning and reduction (and for move-ordering).

There is, however, a different kind of SEE that returns not a score but in effect a boolean (move_loses_material). I have no experience of that kind.

Robert P.

[silentshark]

Having a look at the latest stockfish, they are using SEE in a different way, to help prune non-captures in the main search.

This makes a lot of sense.. the idea I guess is that at low depths, moves which needlessly throw away a piece are pruned right out.

It makes sense, but I wonder whether it would be a valid idea to prune even more aggressive. They prune if (depth < 2 && SEE < 0). A much more aggressive condition could look like

if (depth < 8 && SEE < Min(0, 1 - depth) * PAWN_VALUE) then prune

The assumption behind the formula is: Moves that throw away lots of material can be pruned earlier, compared to moves which throw away few material.

Given the depth SF reaches on today's computer hardware depth 7 is still rather near the leaf.

well, that would be more aggressive! I will have a play with this interesting idea, thanks!

btw, I think the SF code is slightly more aggressive than you indicate - it's more like if (depth - lmrdepth < 2 && SEE < 0).. i.e if the move would be lmr'd, and this would take the depth to less than 2.

[bob]

Having a look at the latest stockfish, they are using SEE in a different way, to help prune non-captures in the main search.

Have not studied stockfish yet, but this makes me so confuse. Can you or someone explain how stockfish applies SEE to non-captures? Or is that not "original" SEE (which always works with captures) as we usually understand?

My SEE (in Crafty) simply requires a move to test. If the move is not a capture, then you are essentially asking "can I safely move to the destination square without losing material?" I use this to test to see if checks are safe, for example. I don't extend losing (SEE) checks and I will even reduce them...

[phhnguyen]

Having a look at the latest stockfish, they are using SEE in a different way, to help prune non-captures in the main search.

Have not studied stockfish yet, but this makes me so confuse. Can you or someone explain how stockfish applies SEE to non-captures? Or is that not "original" SEE (which always works with captures) as we usually understand?

My SEE (in Crafty) simply requires a move to test. If the move is not a capture, then you are essentially asking "can I safely move to the destination square without losing material?" I use this to test to see if checks are safe, for example. I don't extend losing (SEE) checks and I will even reduce them...

Thank you and Purves for explaining it to me.

Now I understand how Stockfish and Crafty use non-capture SEE.

In case of Stockfish which uses non-capture SEE to prune, I think:

- It is so expensive because SEE itself is not cheap and the number of all normal non-capture moves is much bigger than the number of capture ones (and the number of checks in case of Crafty)

- It starts to work so late: after pv move, winning capture moves, killer moves, history moves

thus it can't help much. Am I correct?

[bob]

Having a look at the latest stockfish, they are using SEE in a different way, to help prune non-captures in the main search.

Have not studied stockfish yet, but this makes me so confuse. Can you or someone explain how stockfish applies SEE to non-captures? Or is that not "original" SEE (which always works with captures) as we usually understand?

My SEE (in Crafty) simply requires a move to test. If the move is not a capture, then you are essentially asking "can I safely move to the destination square without losing material?" I use this to test to see if checks are safe, for example. I don't extend losing (SEE) checks and I will even reduce them...

Thank you and Purves for explaining it to me.

Now I understand how Stockfish and Crafty use non-capture SEE.

In case of Stockfish which uses non-capture SEE to prune, I think:

- It is so expensive because SEE itself is not cheap and the number of all normal non-capture moves is much bigger than the number of capture ones (and the number of checks in case of Crafty)

- It starts to work so late: after pv move, winning capture moves, killer moves, history moves

thus it can't help much. Am I correct?

It depends on what you use it for. In the case of crafty, I spend one SEE cycle to see if a check is safe, and if not, I don't extend and do reduce. Most checks are not safe, so the SEE cycle saves 2-3 plies of search depth which is very significant. If you use it to prune, then the effort you spend (SEE) has to be offset by ripping away chunks of the search space so that the SEE cost is more than offset by the reduced search effort...

[CThinker]

Having a look at the latest stockfish, they are using SEE in a different way, to help prune non-captures in the main search.

Have not studied stockfish yet, but this makes me so confuse. Can you or someone explain how stockfish applies SEE to non-captures? Or is that not "original" SEE (which always works with captures) as we usually understand?

Its the basic captures-only SSE. However, the first call to it passes a non-capture move. I do this to test that a moving (non-capture) piece does not end-up as a hanging piece.

[outAtime]

Instead of pruning I reduce capture moves with bad SEE in main search, similar to LMR - got around 4 to 8 rating points on this. There could be some potential in utilizing SEE for pruning and reduction.

This is also what worked for me. At one point, I followed the dogma of "do not reduce checks, captures, etc." I now modify that to "do not reduce those moves if SEE >= 0, which lets me reduce spite checks and horrible captures like QxP when P is protected... I have not yet found any success with pruning except for in the last 4 plies as my "modified futility pruning" approach does currently. In the last few plies, if score is below alpha by some margin that increases as the remaining plies increases, I will prune the moves outright...

One of the first open source engines to ignore some of these dogmas must have been zct from Zach Wegner.
I ran tests for him and everytime tried to make a "sane" version.
Failed everytime

C:\Documents and Settings\Administrator\My Documents\Downloads\zct-032451_ja.zip
[0] Archive type: ZIP
[DETECTION] Is the TR/Crypt.XPACK.Gen Trojan
--> zct-032451_ja/zct32_ja.exe
[DETECTION] Is the TR/Crypt.XPACK.Gen Trojan
--> zct-032451_ja/zct32_smp_ja.exe
[DETECTION] Is the TR/Crypt.XPACK.Gen Trojan

Sourceforge from ccrl. Maybe a clean version should be added.

[F. Bluemers]

Instead of pruning I reduce capture moves with bad SEE in main search, similar to LMR - got around 4 to 8 rating points on this. There could be some potential in utilizing SEE for pruning and reduction.

This is also what worked for me. At one point, I followed the dogma of "do not reduce checks, captures, etc." I now modify that to "do not reduce those moves if SEE >= 0, which lets me reduce spite checks and horrible captures like QxP when P is protected... I have not yet found any success with pruning except for in the last 4 plies as my "modified futility pruning" approach does currently. In the last few plies, if score is below alpha by some margin that increases as the remaining plies increases, I will prune the moves outright...

One of the first open source engines to ignore some of these dogmas must have been zct from Zach Wegner.
I ran tests for him and everytime tried to make a "sane" version.
Failed everytime

C:\Documents and Settings\Administrator\My Documents\Downloads\zct-032451_ja.zip
[0] Archive type: ZIP
[DETECTION] Is the TR/Crypt.XPACK.Gen Trojan
--> zct-032451_ja/zct32_ja.exe
[DETECTION] Is the TR/Crypt.XPACK.Gen Trojan
--> zct-032451_ja/zct32_smp_ja.exe
[DETECTION] Is the TR/Crypt.XPACK.Gen Trojan

Sourceforge from ccrl. Maybe a clean version should be added.

looks ok with http://www.kaspersky.com/scanforvirus

zct-032451_ja.zip/zct-032451_ja/src/zct.c - OK
zct-032451_ja.zip/zct-032451_ja/src/zct.h - OK
zct-032451_ja.zip/zct-032451_ja/x64 4-8 thread test builds/zct64_smp_4t-ja.exe - OK
zct-032451_ja.zip/zct-032451_ja/x64 4-8 thread test builds/zct64_smp_8t_ja.exe - OK
zct-032451_ja.zip/zct-032451_ja/ZCT.ini - OK
zct-032451_ja.zip/zct-032451_ja/zct32_ja.exe - OK
zct-032451_ja.zip/zct-032451_ja/zct32_smp_ja.exe - OK
zct-032451_ja.zip/zct-032451_ja/zct64_ja.exe - OK
zct-032451_ja.zip/zct-032451_ja/zct64_smp_ja.exe - OK