Is SEE really worthwhile?

[AndrewShort]

Does anyone use SEE to eliminate bad captures from the main search? I haven't heard of that, and it seems very risky, but so is null move, whose risk no one seems to mind...

[Dann Corbit]

Does anyone use SEE to eliminate bad captures from the main search? I haven't heard of that, and it seems very risky, but so is null move, whose risk no one seems to mind...

Bad captures will be ordered last by SEE, but SEE never eliminates anything.

[hgm]

Does anyone use SEE to eliminate bad captures from the main search? I haven't heard of that, and it seems very risky, but so is null move, whose risk no one seems to mind...

Given the nature of Chess, it is always a bad idea to prune in the main search. It does pay to reduce bad branches, but in the end you have to deepen any branch without limit, or the engine will start to make fatal mistakes, now and then.

If you use LMR, and use SEE to order the captures, pushing bad captures to the back, you are implicitly using SEE to make the decision to reduce.

[gladius]

Does anyone use SEE to eliminate bad captures from the main search? I haven't heard of that, and it seems very risky, but so is null move, whose risk no one seems to mind...

I don't even use LMR on losing captures in the main search (especially not PV nodes), let alone prune them. The risk of overlooking a tactical shot in the main search is just too high it appears. I've tested a bunch of variations on adding extra reductions to losing captures, and they've all tested worse than just not reducing them at all for some reason. I haven't tried completely pruning them, but that just seems too dangerous.

[AndrewShort]

what about in q-search? does a bad capture (using SEE) get ordered last, or does it simply get ignored? (I realize it may end up getting ignored anyway, due to an earlier beta cutoff). I thought Dr. Hyatt was suggesting to eliminate bad captures in q-search, but perhaps he meant order them last, which effectively eliminates them if there is a cutoff before they are considered....

[Harald Johnsen]

You can prune bad captures in qs (those with see() < 0), it's rather safe to do that.

HJ.

[hgm]

No, he meant to really prune them, even if all other captures previously searched failed low.

My guess is that an important concern is for which purpose you order the moves. Is it to get as small a search tree as possible in QS, or is it to order moves in interior nodes close to the root. The requirements might be quite different.

In QS trying bad captures is not very harmful, as they tend to get refuted quite cheaply. So trying QxR without having a clue as to whether the Rook is defended or not is not such a bad gamble. If it was not you get the highest prize, and thus a small tree, as most replies would be futile. If it was defended the opponent will try the recapture of Q first, and then you are so much behind that all your remaining captures are likely to be futile. So the number of wasted nodes remains limited to two. And, as a bonus, you will pre-empt a lot of cases where the Rook was undefended, but attacking your Queen, in which all moves with better SEE would be refuted by RxQ.

For internal nodes, the stakes are higher. The main risk here is that a bad capture would still be good enough to cause a beta cutoff. You will then stick to this sub-optimal refutation line at larger depth, (as the cut-move is passed through the hash table), which is likely to be much more expensive than a refutation through a good capture (after which you can afford many more null moves before the opponent gets even).

[michiguel]

I recall a thread some time back where the relative merits of MVV/LVA and SEE move-scoring was debated without a definitive conclusion being reached. I tried both schemes, and MVV/LVA seemed to work better, though I know others have reached the opposite conclusion.

Are you asking if sorting with see score is worth it or if using see to find out if a capture is good or not is worth it ?
Knowing that a 'bad' capture like QxP is indeed winning is priceless and this capture must be searched first.

The other place SEE is often used is in qsearch, when determining whether to skip searching a particular sequence of captures, presumably to help avoid qsearch explosions. However in these cases, it seems obvious you could end up missing a sacrifice leading ultimately to a won game (e.g. unstoppable pawn). This is because the end-position of the skipped capture sequence is not evaluated.

There is no such thing as winning sacrifice in qsearch because you do not search quiet move so you can not refute anything in qsearch (and we can not make threats like pawn/knight fork, etc).

When I add SEE into my qsearch I only get a small speed improvement, maybe 5-10%. If SEE was worth an extra ply of search at any reasonable time control, it would be a different matter, but as it doesn't seem to, I can't really see the practical benefit!

See() uses more cpu, does your node count is reduced by only 10% ?
I'll try to find real numbers, this number is very suspect.

HJ.

10% sounds right if you do not fully use SEE. If you use it to discard losing captures, the result is closer to a 55% overall tree size reduction, this has been tested both over lots of test positions and lots of test games...

What is % of Q nodes over the total? it should be quite high to remove a proportion of them and end up with a tree 55% smaller. All that reduction will come from Q-nodes not visited, and I doubt SEE cutoffs remove them all. Do SEE cutoffs really remove most of the Q-nodes?

Miguel

55% seems to much,

[jwes]

I recall a thread some time back where the relative merits of MVV/LVA and SEE move-scoring was debated without a definitive conclusion being reached. I tried both schemes, and MVV/LVA seemed to work better, though I know others have reached the opposite conclusion.

Are you asking if sorting with see score is worth it or if using see to find out if a capture is good or not is worth it ?
Knowing that a 'bad' capture like QxP is indeed winning is priceless and this capture must be searched first.

The other place SEE is often used is in qsearch, when determining whether to skip searching a particular sequence of captures, presumably to help avoid qsearch explosions. However in these cases, it seems obvious you could end up missing a sacrifice leading ultimately to a won game (e.g. unstoppable pawn). This is because the end-position of the skipped capture sequence is not evaluated.

There is no such thing as winning sacrifice in qsearch because you do not search quiet move so you can not refute anything in qsearch (and we can not make threats like pawn/knight fork, etc).

When I add SEE into my qsearch I only get a small speed improvement, maybe 5-10%. If SEE was worth an extra ply of search at any reasonable time control, it would be a different matter, but as it doesn't seem to, I can't really see the practical benefit!

See() uses more cpu, does your node count is reduced by only 10% ?
I'll try to find real numbers, this number is very suspect.

HJ.

10% sounds right if you do not fully use SEE. If you use it to discard losing captures, the result is closer to a 55% overall tree size reduction, this has been tested both over lots of test positions and lots of test games...

What is % of Q nodes over the total? it should be quite high to remove a proportion of them and end up with a tree 55% smaller. All that reduction will come from Q-nodes not visited, and I doubt SEE cutoffs remove them all. Do SEE cutoffs really remove most of the Q-nodes?

Miguel

55% seems to much,

In crafty, 70% of nodes are Q nodes.

[bob]

I recall a thread some time back where the relative merits of MVV/LVA and SEE move-scoring was debated without a definitive conclusion being reached. I tried both schemes, and MVV/LVA seemed to work better, though I know others have reached the opposite conclusion.

Are you asking if sorting with see score is worth it or if using see to find out if a capture is good or not is worth it ?
Knowing that a 'bad' capture like QxP is indeed winning is priceless and this capture must be searched first.

The other place SEE is often used is in qsearch, when determining whether to skip searching a particular sequence of captures, presumably to help avoid qsearch explosions. However in these cases, it seems obvious you could end up missing a sacrifice leading ultimately to a won game (e.g. unstoppable pawn). This is because the end-position of the skipped capture sequence is not evaluated.

There is no such thing as winning sacrifice in qsearch because you do not search quiet move so you can not refute anything in qsearch (and we can not make threats like pawn/knight fork, etc).

When I add SEE into my qsearch I only get a small speed improvement, maybe 5-10%. If SEE was worth an extra ply of search at any reasonable time control, it would be a different matter, but as it doesn't seem to, I can't really see the practical benefit!

See() uses more cpu, does your node count is reduced by only 10% ?
I'll try to find real numbers, this number is very suspect.

HJ.

10% sounds right if you do not fully use SEE. If you use it to discard losing captures, the result is closer to a 55% overall tree size reduction, this has been tested both over lots of test positions and lots of test games...

What is % of Q nodes over the total? it should be quite high to remove a proportion of them and end up with a tree 55% smaller. All that reduction will come from Q-nodes not visited, and I doubt SEE cutoffs remove them all. Do SEE cutoffs really remove most of the Q-nodes?

Miguel

55% seems to much,

Not when you think about it. In a normal implementation, there are at least as many calls to quiesce as not, because of the leaf node issue. But then there are captures beyond that. it is quite easy for the q-search to be 90% of the total nodes searched, or even more at times. So cutting the total tree size by 50% is not much of a task...

But this is easy to test, if you don't believe it...