Singular extension

[hgm]

You could also make the modification of the hash key that distinguishes shifted-window from normal search only in the part of the key that provides the signature, and keep the part that provides the index the same. Then they would map to the same hash bucket. This is equivalent to having a double-length entry, but only for nodes that indeed occur in both searches. Which would only be a small fraction of the nodes. You would not burden the entire table with bigger entries, but just 'forge' them on the fly by recruiting two smaller entries in the rare case where the bigger entry is needed.

The hash probe could then always probe for both keys without significant cost, as after the first probe the entire bucket would be in L1. And if the key modification is an XOR, the key conversion works both ways, so the search would not have to be aware of whether it is shifted-window or normal. You would just always probe for both signatures.

[petero2]

You could also make the modification of the hash key that distinguishes shifted-window from normal search only in the part of the key that provides the signature, and keep the part that provides the index the same. Then they would map to the same hash bucket. This is equivalent to having a double-length entry, but only for nodes that indeed occur in both searches. Which would only be a small fraction of the nodes. You would not burden the entire table with bigger entries, but just 'forge' them on the fly by recruiting two smaller entries in the rare case where the bigger entry is needed.

The hash probe could then always probe for both keys without significant cost, as after the first probe the entire bucket would be in L1. And if the key modification is an XOR, the key conversion works both ways, so the search would not have to be aware of whether it is shifted-window or normal. You would just always probe for both signatures.

When I implemented singular extensions in texel, I first implemented something quite similar to the above. After quite a bit of tweaking I managed to get this to only lose 5 elo. At that point I gave up on attempting to improve it further and instead decided to add singular extensions, in the hope that the win from SE would be bigger than the 5 elo loss from the hash table changes. This turned out to be the case, +7 elo for SE + hash table change, so I kept this combined change.

After that I tried reverting the hash table change but keep the SE change. I was surprised to find that this gave an additional +9 elo.

My task would have been a lot easier if I hadn't worried about this potential hash overwrite problem and had just implemented singular extensions using the existing hash table implementation.

[Cardoso]

This is why I thought it could be better to just 'shift' the hash key by a constant when working on exclusion searches.

Probably not a good idea. Precise hash keys are necessary for a PVS search. Fuzzy hash key entries can damage a PVS search for some reason.

There is nothing 'fuzzy' about the hash key. They are precisely altered by XORing them with an extra key only used during the shifted-window search. So that the latter does effectively use a different hash table than the normal search, and they won't spoil the depth, bounds and move of the positions they have in common. So that either search will find back the info on each node in their tree undamaged in the next iteration, instead ofinfo that is useless to them.

I am not sure there is a good answer here. This approach hides good hash hits that came from non-singular searches, which is bad. Not doing this overwrites good entries that came from non-singular searches with entries that have a lower depth and which come from the singular search.

I played with the idea of one hash entry but with two depths, two scores, two types of scores, one for normal, one for singular only. But it seemed to hurt rather than help since every hash entry grew by 32 bits reducing the number of entries... I tried not storing SE searches, but that also hurts since the shifted windows cause many or the normal values to be unusable, and the SE searches have enough "meat" that a tt hit is useful...

I need to go back and re-read Hsu's paper but I don't think they addressed this since that was done in the day of 10 ply - 12 ply searches where the effect is probably less noticeable...

When we invoke Search() with an excluded move, maybe we should not store in the hash table at that given ply, because if we store, then the hash entry will have shifted bounds and the hash move will be the second best move if any. On the subtrees of that node storing will be correct because at those nodes we don't exclude moves for singular move detection.
Also if we keep track of the ratio of:
singular nodes found / exclusion searches
maybe that will give us an idea of how sound our singular extensions implementation is. Depending on the implementation we may be surprised that the ratio maybe low, I mean we will have many exclusions searches but few of them will produce a singular move.
If on the other hand the singular moves counter approaches the exclusions searches counter then our implementation must be good.
Another parameter I would like to see discussed is the singular margin, that is the amount of the shift to apply to the window:
1/10th of a pawn?
1/2 of a pawn?

Alvaro

[jwes]

Recaptures are very often singular. Should they be extended?

[hgm]

Usually captures are exempted from reduction, which already is a form of extension. So, yes, they deserve to be extended, but overdoing it is never good, and one would have to balance it with the LMR scheme.

[cdani]

Usually captures are exempted from reduction, which already is a form of extension. So, yes, they deserve to be extended, but overdoing it is never good, and one would have to balance it with the LMR scheme.

Andscacs has capture extension with some restrictions, and every time I try to remove it, it's a regression. Of course all the other alpha_beta stuff is accommodated to this. Kind off but inversed to singular extensions, no way to make it work.

[Steve Maughan]

...(snip)The unanswered question is - why extend at all on fail-high nodes?

A better question, how would you extend on fail low nodes? Fail high nodes are caused by a good move. You would like to be sure it is really good and that the roof doesn't fall in farther down the PV...

I think both questions have obvious answers.

You extend fail high because you don't know if there is imminent danger just over the horizon. For example the Greek gift Bxh7+, will look like a fail high for black for several moves - he's a piece up. So you need to extend to see the checkmate by white. This logic applies to any score above alpha; not just fail high.

On a fail low there is no need to extend. It's a bad move and you already have a better one (i.e. the one associated with the alpha bound). There is no need to establish if it's *really bad*.

- Steve

[D Sceviour]

You extend fail high because you don't know if there is imminent danger just over the horizon. For example the Greek gift Bxh7+, will look like a fail high for black for several moves - he's a piece up. So you need to extend to see the checkmate by white. This logic applies to any score above alpha; not just fail high.

Hello Steve,
Checks are normally already extended so there is no need to do an exclusion search for Bxh7+. However, this seems the correct idea. More conditions are necessary to know when to do an exclusion search. Whether to do an exclusion search is determined on a positional basis first (CUT/ALL phase), and not a move unless some more information can be determined about the transposition best move. This would be especially difficult to assess if the tt best move were a non-capturing move.

[lucasart]

When I implemented singular extensions in texel, I first implemented something quite similar to the above. After quite a bit of tweaking I managed to get this to only lose 5 elo. At that point I gave up on attempting to improve it further and instead decided to add singular extensions, in the hope that the win from SE would be bigger than the 5 elo loss from the hash table changes. This turned out to be the case, +7 elo for SE + hash table change, so I kept this combined change.

After that I tried reverting the hash table change but keep the SE change. I was surprised to find that this gave an additional +9 elo.

My task would have been a lot easier if I hadn't worried about this potential hash overwrite problem and had just implemented singular extensions using the existing hash table implementation.

It is still a mystery to me how Singular Extension can work so well. But it is an humongous elo boost in Stockfish.

I removed SE, and ran a 20k games elo measure in 20+0.2: 45 elo loss
http://tests.stockfishchess.org/tests/v ... 227df16caf

I retuned LMR and LMP, in the absence of SE, so as to give the non SE version a fair change and measure the effect of SE per se (optimal LMP and LMR values are potentially different with and without SE). Still running, but looks like it's going to be a massive elo loss as well:
http://tests.stockfishchess.org/tests/v ... 227df16cd9

[bob]

When I implemented singular extensions in texel, I first implemented something quite similar to the above. After quite a bit of tweaking I managed to get this to only lose 5 elo. At that point I gave up on attempting to improve it further and instead decided to add singular extensions, in the hope that the win from SE would be bigger than the 5 elo loss from the hash table changes. This turned out to be the case, +7 elo for SE + hash table change, so I kept this combined change.

After that I tried reverting the hash table change but keep the SE change. I was surprised to find that this gave an additional +9 elo.

My task would have been a lot easier if I hadn't worried about this potential hash overwrite problem and had just implemented singular extensions using the existing hash table implementation.

It is still a mystery to me how Singular Extension can work so well. But it is an humongous elo boost in Stockfish.

I removed SE, and ran a 20k games elo measure in 20+0.2: 45 elo loss
http://tests.stockfishchess.org/tests/v ... 227df16caf

I retuned LMR and LMP, in the absence of SE, so as to give the non SE version a fair change and measure the effect of SE per se (optimal LMP and LMR values are potentially different with and without SE). Still running, but looks like it's going to be a massive elo loss as well:
http://tests.stockfishchess.org/tests/v ... 227df16cd9

That seems like a huge gain, especially when the deep thought guys ended up reporting a 10-15 Elo gain, and they did the full SE implementation rather than the partial version SF is using. But then again, you quoted +40 on FishTest which probably explains it as self-play greatly exaggerates the Elo gain...