How good is your SEE?

[mjlef]

I was wondering how detailed various program's Static Exchange Evaluators were. Mine currently correctly handles x-ray attacks, but toally ignore pieces that might be pinned to the appropriate king, and so cannot take part in the capture sequence. How important do you think that is? Has anyone implemented this and if so, did it effect playing strength. I can run some tests since I have functions that should detect pinned pieces, but I am still interested in what other have found.

Note I use SEE both to improve move ordering (in "full width" nodes) and to totally prune nodes (in the capture search).

Mark

[H.G.Muller]

Joker uses SEE for the same purposes as you. I decided to have it test the first capture (after the starting move, which is not determined by the SEE but handed to it by the move generator, and thus always legal) for legality, though.

I have not really tested it, but my guess was that the pin status is just one of the many side effects that make SEEs inherently inaccurate. Even if there is a pin, perhaps it can be solved without loss of tempo (e.g. by trading the pinner, or interposing a defended Pawn that attacks the pinner. The pinner might even be one of the pieces involved in the exchange. Or pieces used up in the exchange might cause a formerly non-pinned piece to become pinned.)

The reason I do the pin test for the first capture is that I wanted to be the SEE to be able to provide me with a (legal) recapture move before doing move generation. (But it turned out to be a bad idea to search such a move first, even if the SEE tells us that it is good. I might still want to try this for capturing Queens, though, as I can't conceive of any situation where capturing a Queen would not be the first move in my move ordering anyway.)

In the future, the fact that the first capture has to be legal will also come in handy for when I have to detect if a check is worth extending. (I want to do this only if there is no good capture on the checker.)

Anyway, the bulk of most SEEs does not go very deep at all. The fact that I catch the simple case of a square defended by only a single pinned piece (so in fact not defended at all, except against King) already drives up the accuracy enormously. Especially since this is a case where pinning/unpinning of pieces by previous captures cannot occur.

[Tony van Roon-Werten]

I was wondering how detailed various program's Static Exchange Evaluators were. Mine currently correctly handles x-ray attacks, but toally ignore pieces that might be pinned to the appropriate king, and so cannot take part in the capture sequence. How important do you think that is? Has anyone implemented this and if so, did it effect playing strength. I can run some tests since I have functions that should detect pinned pieces, but I am still interested in what other have found.

Note I use SEE both to improve move ordering (in "full width" nodes) and to totally prune nodes (in the capture search).

Mark

I don't think it's worth the bother to make it better.
It can become quite complicated. Think about a piece that can't recapture because it's pinned, but the pinner is the piece that did the first capture.

If you implement all exceptions it isn't called a SEE anymore but a quiescence search.
They other way around also goes: You can't expect a simple SEE to do a job as good as a quiescence search.

Handling x-rays is imo needed to make the SEE (much) more accurate without adding too much complications. The rest adds too much complications and too little added value.

Tony

[Tord Romstad]

I was wondering how detailed various program's Static Exchange Evaluators were. Mine currently correctly handles x-ray attacks, but toally ignore pieces that might be pinned to the appropriate king, and so cannot take part in the capture sequence. How important do you think that is? Has anyone implemented this and if so, did it effect playing strength.

I have never implemented an SEE which understands pins and overloaded pieces, but I once experimented with a simple SEE which was aware of its own limitations. The program detected pins, overloaded pieces, and some other factors (at least pawns on the 7th rank, IIRC), and decided whether or not the SEE should be trusted based on these factors. In positions with pinned pieces, I would simply not use the SEE to prune captures in the qsearch.

This worked OK, and was easy to implement, but I was never able to prove that it performed better than a plain SEE. I went back to the plain SEE in order to keep things simple.

Tord

[mjlef]

I went ahead and added absolute pin detection (pins of pieces to its own king). Before the change, my program won 43% of its games versus my stanard 6 opponents. After the change, still 43%. I found less than 1% of the positions I passed to my SEE routine detecting such pins (and I do not know how they might have effected the result of the SEE). I also do not see much of a slowdown in doing this since it is rare a piece moving in the SEE eval is pinned. Maybe I will leave it in for capture search move tossing but just ignore it for move ordering.

My next stupid idea is to try and determine other wasy capture searches fail and continue my data mining for better search techniques. I have a lot of ideas...like this one. Lets say a move like NxP appears to be a loss. But the N move exposes a R to a B attack. The SEE fails in this case, since the other side would need to move its rook to save it, probably allowing the N to escape. It should be pretty fast to do tests like this, since it only involve long range pieces in perfect alignment. I might be able to discover the most likely situations where SEE fails via some simple searches comaring search results with and without the SEE cutoff.

Mark

Mark

[Richard Pijl]

I was wondering how detailed various program's Static Exchange Evaluators were. Mine currently correctly handles x-ray attacks, but toally ignore pieces that might be pinned to the appropriate king, and so cannot take part in the capture sequence. How important do you think that is? Has anyone implemented this and if so, did it effect playing strength. I can run some tests since I have functions that should detect pinned pieces, but I am still interested in what other have found.

Note I use SEE both to improve move ordering (in "full width" nodes) and to totally prune nodes (in the capture search).

Mark

I don't think it's worth the bother to make it better.
It can become quite complicated. Think about a piece that can't recapture because it's pinned, but the pinner is the piece that did the first capture.

This particular exception is not that difficult to exclude, and that is what I did in the Baron. As I'm using SEE or SEE-like functions also in the evaluation function I like the added accuracy. However, I still found the benefit in playing strength to be very limited.
Richard.

[mjlef]

I added some code to search for positions where pruning moves based on SEE failed in some way. Many of the failures involved pruning promotions to queens. Although the pawn (well now queen) was lost, the response by the opponent is forced if the queening move is a checking move as well (I normally pruning losing checking moves in the qsearch). But when the opponent was forced to capture the queen, the other isde often has another threat on the board. I tried not pruning losing promotions in this case and it seems to help. I should check and see how other programs handle promotion checks.

[Richard Pijl]

I added some code to search for positions where pruning moves based on SEE failed in some way. Many of the failures involved pruning promotions to queens. Although the pawn (well now queen) was lost, the response by the opponent is forced if the queening move is a checking move as well (I normally pruning losing checking moves in the qsearch). But when the opponent was forced to capture the queen, the other isde often has another threat on the board. I tried not pruning losing promotions in this case and it seems to help. I should check and see how other programs handle promotion checks.

I'm doing that too. And in a very simple way: I only prune losing capures/promotions that lose more than a pawn. It will also keep the almost equal captures (like giving two pieces for rook and pawn). This seems to find some tactics a bit faster, at only a low cost.
Richard.

[mjlef]

I'm doing that too. And in a very simple way: I only prune losing capures/promotions that lose more than a pawn. It will also keep the almost equal captures (like giving two pieces for rook and pawn). This seems to find some tactics a bit faster, at only a low cost.
Richard.[/quote]

Neat and simple idea. I will steal it and let you know if it works for me.

[H.G.Muller]

I am still going to test one day how much time pruning these losing captures saves in the first place (at equal tactical strength).

The reason is that it interferes with Joker's depth bootstrapping. With an all-captures QS a d=0 node with eval < alpha - POSMARGIN is actually valid as a d=1 search, as all non-captures would be futile anyway in the latter. But if losing captures were pruned, you cannot do that, as in the d=1 such captures might not be futile.

So what you seem to save in the current iteration, you would have to do in the next iteration anyway, when redoing the node at d=1. And in addition, you would have to redo all the good captures as well. Even if they would be hash hits at that time (i.e. if your QS nodes survived in the hash table...), you would have to do several expensive hash probes to get them. If you would have been able to store the result immediately as d=1, a single hash hit on an entry that is more likely to survive would have done it. And even that hash probe would probably not have been done, as the parent node of this all-node would be a cut-node, and the d=1 result for the all-node would thus bootstrap that cut-node from d=1 to d=2, satisfying the hash probe of the next (or next two) iteration there.

So in short: even if there is an advantage in pruning losing captures in a regular search, depth bootstrapping will erode, or might even invert tha advantage.

Furthermore, if losing captures are really losing more than 1 Pawn, the tree searching them is unlikely to ever call the full evaluation, as all nodes where it could want to stand pat will be pruned by futility. Thus, searching the losing captures is generally quite cheap.