SEE (Static Exchange Evaluation) pruning nodes

[mvanthoor]

Yesterday I was reading around on the Bruce Moreland pages that can still be found through the Way Back machine (I scraped them them a few years ago), and in the SEE topic he says:

You can't discard QxP in MVV/LVA, because it's very possible that the pawn is undefended, which would mean that QxP is a good move. Of course, if the pawn is defended, I doubt that you gain anything significant by searching this move at all. With a SEE, you can figure out if QxP is a losing capture, and if so, either order the capture so that it is searched last, or simply prune it.

Pruning a bad capture because it seems "bad" due to material considerations, took me about 2 seconds to refute, as a chess player. Let's consider the following position:

[d]r5k1/2p2ppp/1p6/8/7q/7P/1Q3PP1/2R3K1 w - - 0 1

White is two pawns down, and basically lost; he just played Rf1-c1, in the hopes of snagging the two pawns on the queen-side. The CORRECT move int his position for black is Qh4-f4, which both defends pawn c7, and attacks rook c1, basically pinning the queen to b2 to keep defending the rook. Rustic finds this move in no-time, even in its current state with only material + PST evaluation:

Code: Select all

info score cp 230 depth 1 seldepth 4 time 0 nodes 71 nps 0 pv h4f4
info score cp 220 depth 2 seldepth 6 time 0 nodes 387 nps 0 pv h4f4 c1d1
info score cp 215 depth 3 seldepth 10 time 1 nodes 4710 nps 4710000 pv h4f4 g2g3 f4d6
info score cp 205 depth 4 seldepth 11 time 8 nodes 34353 nps 4294125 pv h4f4 g2g3 f4d6 c1e1
info score cp 220 depth 5 seldepth 12 time 63 nodes 297575 nps 4723413 pv h4f4 c1e1 a8d8 b2e5 f4e5 e1e5
info score cp 195 depth 6 seldepth 15 time 483 nodes 1962939 nps 4064056 pv h4f4 g2g3 f4d6 b2c2 c7c5 c2e4
info score cp 210 depth 7 seldepth 16 time 3608 nodes 16197700 nps 4489385 pv h4f4 c1e1 a8b8 b2b5 b8f8 b5d5 c7c5
info score cp 200 depth 8 seldepth 18 time 24281 nodes 94803316 nps 3904424 pv h4f4 g2g3 f4d6 b2c2 c7c5 c2e4 a8a2 c1e1

(PS: Stockfish agrees, but after about searching 30 moves deep, it starts preferring Qe7 instead of Qf4, with 0.05 extra advantage.)

Let's say Black makes the colossal mistake of playing Ra8-a7 to defend the pawn, leading to this position:

[d]6k1/r1p2ppp/1p6/8/7q/7P/1Q3PP1/2R3K1 w - - 0 1

Because black now gives up the back rank, this opens the door to a tactical move, which loses both pawns and equalizes the game. Can you see it? Rustic can:

Code: Select all

info score cp -180 depth 1 seldepth 5 time 0 nodes 40 nps 0 pv b2e5
info score cp -190 depth 2 seldepth 8 time 0 nodes 995 nps 0 pv b2e5 c7c5
info score cp -105 depth 3 seldepth 9 time 0 nodes 3473 nps 0 pv b2b6 c7b6 c1c8 h4d8 c8d8
info score cp -10 depth 4 seldepth 11 time 7 nodes 30398 nps 4342571 pv b2b6 a7a8 c1c7 h4e4
info score cp 5 depth 5 seldepth 13 time 57 nodes 223776 nps 3925895 pv b2b6 a7a8 b6b7 a8d8 c1c7
info score cp -5 depth 6 seldepth 15 time 501 nodes 2079270 nps 4150240 pv b2b6 a7a8 b6c7 f7f5 c1c4 a8a1 c4c1 a1c1 c7c1
info score cp 0 depth 7 seldepth 17 time 4066 nodes 15705074 nps 3862537 pv b2b6 a7a8 b6c7 a8e8 c7c6 h4e4 c6e4 e8e4
info score cp -10 depth 8 seldepth 20 time 33879 nodes 136903079 nps 4040942 pv b2b6 a7a8 b6c7 a8e8 c1c4 h4g5 c7d6 g5f5

Right... Qb2xb6!!. Black cannot recapture the queen with pawn c7, because of Rc1-c8+, Qh4-d8 (only move) and Rc8xd8 mate.

If you just evaluate SEE like so: Qb2xb6 +100 ... pawn defended ... c7xb6 ... now more captures... oh, -800. Bad move. Prune it.

In that case you prune your only chance of actually equalizing this position and taking advantage of black's blunder. You _CAN'T_ just prune a move on the only basis that it is a bad material exchange. On a purely material counting basis, Qb2xb6 is about the worst move you could ever make, but it works because c7xb6 DOESN'T work for black.

Is there something about SEE that I'm not SEE-ing correctly here?

The only thing you could do, is put Qb2xb6 last in the list, but then you put your best move last.

[Mike Sherwin]

The example is only a few ply deep. Unless you are writing a retro engine for an Atari 800 I think it misses the point. Now place that example at the horizon of Rustic's search and multiply it by millions of similar situations and it becomes an averaging problem that can't be solved by exact search because there is no more depth.

If you don't like that (I don't like it either) then maybe extend the search for the first sacrifice in any line if there is not a minimal amount of depth left to resolve such a sacrifice. The horizon is always going to be a problem. We just need better ways of dealing with it.

[hgm]

SEE is mostly used for move ordering. MVV/LVA would order QxR captures before PxB captures, because R > B. While the chances that PxB is good are very high, and whether QxR is better or a disastrous blunder is more or less a tossup. With SEE you would know whether QxR is a likely disaster, and if it seems so, you could at least postpone it to after the PxB, in violation of the MVV/LVA ordering. Most strong engines uses the system to order LxH and equal captures according to MVV/LVA, but order the HxL captures by SEE (i.e. using their SEE value instead of MVV as the primary sort key).

Captures with negative SEE are usually referred to as 'bad captures'. Some engines prune these in QS. Note that the example you give would also not be recognized in QS when you do not prune bad captures, because the crux (Rc8#) is a non-capture. But there could of course have been another black Rook on c8, and then it would have been a capture, and it would have been seen.

So yes, SEE is only a very unreliable indication of the outcome of a full capture search. Especially long exchanges, as each capture in them can have side effects (soft-pinning, overloaded protectors...). Which will be ignored in SEE. Given this I usually do not bother, and use the alternative BLIND, which stands for Better, or Lesser If Not Defended: it pospones HxL captures of protected targets to after completion of the normal MVV/LVA queue. So Q x unprotected R is search immediately, Q x protected R would be postponed. Of course Q x protected R can still be good, even SEE-wise, when there is a second attacker (King, or a Rook that was behind the Queen so it could not capture first), and the protector was a Queen.

All these move-ordering or pruning heuristics are extremely error prone. But you apply them on statistical benefits. Examples like the one you give are pretty much 'never-happens' cases. It cannot be helped that your node budget is finite: every node you do search takes the place of a node that could have been searched instead. Captures that are SEE-wise bad have a very much higher than average chance to indeed lower the score. (Which already was too low for stand pat, or you would not consider searching any captures in the first place.) Better save your ammunition for nodes that have at least an average probability of being good. By pruning the 'bad captures' in QS, you might save so much time that you can search 1 ply deeper, which would bring you much more than occasionally finding that a 'bad capture' was causing a beta cutoff.

[connor_mcmonigle]

SEE pruning is most commonly used to prune bad captures (all moves with negative SEE) in the qsearch. In general, as with most search heuristics, SEE pruning has desirable behavior on average, but there are rare exceptional cases. If your search wasn't deep enough to resolve the tactic above before dropping into qsearch, then surely it will be deep enough on the next iteration. Furthermore, it's not like this tactic could be resolved in qsearch anyways as Rc8# is likely considered a quiet move (though not necessarily).

Other engines use SEE pruning in there primary search on nonpv nodes, but usually the SEE pruning margin increases with depth (root always has the highest "depth"). If depth is sufficiently high, SEE pruning is disabled altogether.

Most pruning heuristics work like this with the general idea being to focus the search on more promising/likely moves. At low depth, we're in exploitation mode, trying to take advantage of prior knowledge (such as sacrificing the queen = bad). At higher depths, we're in exploration mode, searching wider to insure nothing has been missed (such as Rc8#).

[chrisw]

SEE pruning is most commonly used to prune bad captures (all moves with negative SEE) in the qsearch. In general, as with most search heuristics, SEE pruning has desirable behavior on average, but there are rare exceptional cases. If your search wasn't deep enough to resolve the tactic above before dropping into qsearch, then surely it will be deep enough on the next iteration. Furthermore, it's not like this tactic could be resolved in qsearch anyways as Rc8# is likely considered a quiet move (though not necessarily).

Other engines use SEE pruning in there primary search on nonpv nodes, but usually the SEE pruning margin increases with depth (root always has the highest "depth"). If depth is sufficiently high, SEE pruning is disabled altogether.

Most pruning heuristics work like this with the general idea being to focus the search on more promising/likely moves. At low depth, we're in exploitation mode, trying to take advantage of prior knowledge (such as sacrificing the queen = bad). At higher depths, we're in exploration mode, searching wider to insure nothing has been missed (such as Rc8#).

SEE is way improved now on what it was, well, if one compares SF SEE to what I used to use a few decades ago.
Very anecdotally. Old SEE used to catch some pinned pieces, but not all. It knew a little about x-ray attacks but with erroring.
New SEE is way improved vis a vis x-rays, and also pinned. New SEE more or less does a Qsearch, except that it considers nothing but the target square.
What gets missed still are queen pins, and overloads in both directions (defenders may have other important tasks elsewhere, the captured piece may also have been performing an important elsewhere task).
Of course, Qsearch has also become slightly SEE-alike, beyond a certain depth some programs only allow re-captures on the prior capture square.
Another SF feature which surprises was that their SEE treats bishops as more valuable than knight, so a protected BxN is.treated as negative, but not vice versa. Works though.

[Ras]

Pruning a bad capture because it seems "bad" due to material considerations, took me about 2 seconds to refute, as a chess player.

My current release would indeed prune Qxb6 because I have added a mini SEE like "prune HxL if L is defended by a pawn". That has tested positive by a handful of Elo over some 10k games. However, it will only be pruned in QS, not in main search. Since Rc1-c8# is a quiet move, it wouldn't be tested in QS anyway so that there is no loss of strength by not examining Qb2xb6 in the first place. It's also why Rustic without this QS pruning needs depth 3 to find that, same as my engine.