Is SEE really worthwhile?

[mambofish]

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.

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.

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!

Am I missing something important?

Vince

[hgm]

I think it depends a lot on other aspects of the engine if sorting by SEE, or pruning bad captures in QS, gives an improvement. Like you remark, the latter is a theoretically unsound pruning, and its effect cannot be judged by looking at search times for given positions, but must be measured in games to ensure that the move quality doesn't suffer more than the search-time reduction helps.

MVV/LVA is not a very inferior method at all, and very effectively suppresses QS explosions. Its Achilles' heel, the HxL captures, can often be remedied satisfactorily by not using pure MVV/LVA, but postponing such captures always, or dependent on some partial (but faster to obtain) information than a full SEE, e.g. if the piece is completely undefended or not.

[Harald Johnsen]

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.

[Harald Johnsen]

position from another thread
[d] 1r4k1/5ppp/2Q5/2p1qP2/6n1/3Br1P1/2P4P/RR4K1 b - -

Code: Select all

8 110 246 713493 Rd8 Qg2 Qd4 Kh1 Re5 Qf3 Nf2+ Kg2 Nxd3 cxd3 Qxd3 Qxd3 Rxd3
9 110 376 1109563 Rd8 Qg2 Qd4 Kh1 Re5 Qf3 Nf2+ Kg2 Nxd3 cxd3 Qxd3 Qxd3 Rxd3
10 94 650 1986912 Rd8 Qg2 Qd4 Kh1 Re5 Qf3 Nf2+ Kg2 Nxd3 Qxd3 Qxd3 cxd3 Rxf5

if keeping captures with negative see, checks with negative see, removing futility pruning in qs :

Code: Select all

8 124 501 2169131 Re8 Kh1 Nf2+ Kg1 Nxd3 cxd3 Rxd3 Ra8 Qd4+ Kg2 Rd2+ Kh3 Rf8 Rxf8+ Kxf8
9 128 775 3368381 Re8 Kh1 Nf2+ Kg1 Nxd3 cxd3 Rxd3 Ra8 Rdd8 Rxd8 Rxd8 f6
10 128 1339 5621331 Re8 Kh1 Nf2+ Kg1 Nxd3 cxd3 Qd4 Kh1 Qxd3 Rf1 Qc2 Ra7

So the difference is allready over 100% at low depth.

HJ.

[hgm]

I am not sure what the numbers you give here are supposed to prove. Why disable futility pruning? The whole difference could be due to that alone, and it was not a topic of discussion.

Furthermore, the moves found are different in the two cases. So how do we know which move is better? Even if with futility pruning the no-pruning-of-bad-captures case would take twice as long to search, a better movemight well be worth it...

[Harald Johnsen]

Of course the moves and the scores are differents, the question was not about wich search gives the best score or pv but if the op could yes or no win a ply of search.

With fp enabled the difference is lower you are right, but anyway it's just an example.

HJ.

[Tony]

Of course the moves and the scores are differents, the question was not about wich search gives the best score or pv but if the op could yes or no win a ply of search.

With fp enabled the difference is lower you are right, but anyway it's just an example.

HJ.

If you switch off beta cutoffs, the difference is even bigger

Tony

[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.

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.

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!

Am I missing something important?

Vince

SEE is definitely worth it. If you can find an older version of Crafty that supported both, you could set it to use SEE or MVV/LVA at will, and compare the differences. You can also find a long thread on the old rec.games.chess.computer between myself and Hsu about this. Here was the gist of the thread:

SEE is more efficient than MVV/LVA. Roughly 10% smaller trees if all you do is use the SEE score rather than the MVV/LVA score. But there is more. Much more. If you use SEE to discard losing captures from the q-search, and just keep equal or winning captures (something you can not do with MVV/LVA) then you reduce the tree size by _another_ 50%. Which at today's branching factor is an additional ply which is very significant...

SEE is not hard to implement, and it is simply more accurate than MVV/LVA. MVV/LVA was not intended as a software solution, it was originally created when Ken did the 1980 Bell chess machine that implemented everything, including the alpha/beta search, in hardware. He needed something that fit a finite-state-machine architecture (things can't take variable amounts of time, and SEE definitely does that depending on how many attackers/defenders there are) so he came up with MVV/LVA as a simple hardware solution. He gave up some accuracy to get the much faster hardware speed he produced.

There was a ton of test results in the old r.g.c.c thread if you google it...

[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...

[mambofish]

Thanks everyone for your comments.

I decided to run the example through my engine, and the results were quite interesting...

First, without SEE, ermintrude simply didn't find Rd8 within 60 seconds, preferring Re8 instead. (This seems odd, but more of that later!) Then I added SEE to qsearch, pruning all captures that didn't win at least a pawn (I saw no point in trading off for equal material, on the basis that the resulting positions are invariably more difficult for the computer to win, given the reduction in tactical possibilities).

But, even with SEE pruning, Rd8 wasn't found within 60 seconds, although the preferred move changed to Rxb1+, rather than Re8.

I was beginning to get a bit suspicious particularly because Bob and Harald have been so insistent that SEE really is worthwhile, so I decided to isolate its effects as much as possible. Ermintrude uses Late Move Reduction pruning so I turned it off, and tried again. Et voila! This time, SEE did its job and Rd8 was found in 12.6 seconds. It seems that, LMR was interfering in some way...

I didn't want to turn off LMR, so I switched it back on, and instead experimented with the SEE results, this time discarding any captures that didn't win at least 2 pawns. (I persuaded myself that there was some logic to this: capturing a single pawn might end up wrecking your position with insufficient compensation, but being two pawns up is probably worth any amount of positional havoc!)

Anyway, to cut a long story short, with this configuration, the engine found the move in just 7 seconds. Quite a result.

Of course I am concerned that I have introduced some terrible problem into the code, but initial tests indicate nothing untoward - yet. Obviously, I will have to a lot more testing (including checking to see if I've got a weird bug in the SEE code that could account for this strange behaviour). But on the strength of the evidence so far, SEE does seem to be doing the business....