Singular extension

[D Sceviour]

Once one of the alternate moves have failed high on the shifted window, we already know the PV move was non-singular, and there is no need to do further exclusion searches.

Yes, that would seem to make more sense, and explain the rapid cutoffs noted in the exclusion search.

So it will have to search, and then overwrite the entry with its low-depth result, making it unusable for the normal search.

If a move failed high or low in the exclusion search then the moves would be unused. What would they be used for in a normal search since the first transposition best move is expected to cutoff, whether singular or not?

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.

[Eelco de Groot]

I tried Singular Extension for the first time. Surprisingly it is not that difficult to code, and there are several modern examples available. What is astounding is the less than 2% hit rate for singular extensions. The extra exclusion search should produce a decrease in overall strength. Either the singular hit is very successful (as it sometimes indicates in tactical test positions), or the exclusion search is so shallow and fast that delay is un-noticeable. The exclusion search would return quickly on hash hits with the reduced depth. So far, the results seem to accomplish no overall gain (or loss) in tests. Better extension conditions seem necessary.

The unanswered question is - why extend at all on fail-high nodes?

I do think the main effect is on the PV. In Harm Geert's implementation it is only PV nodes. In that case you are not extending a Cut node (extending a fail high node in your terms), technically PV nodes are ALL nodes. And you can have extensions for both colors, every ply, so I think that is a reason why the PV searches can get extended further by Singular Extensions than nullwindow searches leading from Cut nodes. The main reason why you are doing that (extending PV nodes) is I think safety, you have to look as far ahead as possible to avoid mistakes, as long as the selective deeper search is not too expensive of course. (The search becomes more selective, more "intelligent" if you wish, but it is not sure that in all cases strength is improved, that depends on so many factors)

In the nullwindow searches from CUT nodes, it is mainly safety as well, in CUT nodes where you have the move you have to look as far ahead as possible to make sure they are really CUT nodes, and there is only one move that works. In the side branches of the Rootnode it is the opponent who has the move in CUT nodes, but if his singular move fails, suddenly it is an ALL node for him. A lot of the tree becomes useless if the singular move fails (that goes for all singular nodes) and if you have done an exclusion search at least part of the new tree will be ordered. So a form of preemptive internal iterative deepening.

[D Sceviour]

I tried Singular Extension for the first time. Surprisingly it is not that difficult to code, and there are several modern examples available. What is astounding is the less than 2% hit rate for singular extensions. The extra exclusion search should produce a decrease in overall strength. Either the singular hit is very successful (as it sometimes indicates in tactical test positions), or the exclusion search is so shallow and fast that delay is un-noticeable. The exclusion search would return quickly on hash hits with the reduced depth. So far, the results seem to accomplish no overall gain (or loss) in tests. Better extension conditions seem necessary.

The unanswered question is - why extend at all on fail-high nodes?

I do think the main effect is on the PV. In Harm Geert's implementation it is only PV nodes. In that case you are not extending a Cut node (extending a fail high node in your terms), technically PV nodes are ALL nodes. And you can have extensions for both colors, every ply, so I think that is a reason why the PV searches can get extended further by Singular Extensions than nullwindow searches leading from Cut nodes. The main reason why you are doing that (extending PV nodes) is I think safety, you have to look as far ahead as possible to avoid mistakes, as long as the selective deeper search is not too expensive of course. (The search becomes more selective, more "intelligent" if you wish, but it is not sure that in all cases strength is improved, that depends on so many factors)

In the nullwindow searches from CUT nodes, it is mainly safety as well, in CUT nodes where you have the move you have to look as far ahead as possible to make sure they are really CUT nodes, and there is only one move that works. In the side branches of the Rootnode it is the opponent who has the move in CUT nodes, but if his singular move fails, suddenly it is an ALL node for him. A lot of the tree becomes useless if the singular move fails (that goes for all singular nodes) and if you have done an exclusion search at least part of the new tree will be ordered. So a form of preemptive internal iterative deepening.

Thank you for the theoretical analysis.

I temporarily changed the exclusion search from CUT nodes to PV nodes. The result was terrible, with a large search explosion. More code considerations are obviously required, but the examples for SE have all been for CUT nodes.

Safety is an insufficient reason to attempt a Singular Extension with a shallow exclusion search. Rather, safety is more of a bonus if something unexpected shows up on the horizon. Occasionally in the past, I have experimented with a PV extension at the horizon. This was not done for safety, but to produce a more accurate bound for the root. However, even if safety were the main reason for SE, it does not help to offer a code reason to pass on an exclusion search. There has to be a better reason for doing an SE.

Preemptive internal iterative deepening is another matter. New ideas for better move ordering are always interesting. H.G. Muller has been experimenting with self-deepening which looks like a hybrid between IID and SE. Getting it to do better than a classical alpha-beta search is also another matter.

[bob]

I tried Singular Extension for the first time. Surprisingly it is not that difficult to code, and there are several modern examples available. What is astounding is the less than 2% hit rate for singular extensions. The extra exclusion search should produce a decrease in overall strength. Either the singular hit is very successful (as it sometimes indicates in tactical test positions), or the exclusion search is so shallow and fast that delay is un-noticeable. The exclusion search would return quickly on hash hits with the reduced depth. So far, the results seem to accomplish no overall gain (or loss) in tests. Better extension conditions seem necessary.

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

[D Sceviour]

I tried Singular Extension for the first time. Surprisingly it is not that difficult to code, and there are several modern examples available. What is astounding is the less than 2% hit rate for singular extensions. The extra exclusion search should produce a decrease in overall strength. Either the singular hit is very successful (as it sometimes indicates in tactical test positions), or the exclusion search is so shallow and fast that delay is un-noticeable. The exclusion search would return quickly on hash hits with the reduced depth. So far, the results seem to accomplish no overall gain (or loss) in tests. Better extension conditions seem necessary.

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 am at a loss for an answer. If one extends a fail high, then one also extends the fail lows for the next ply, and you are no further ahead. Rather than preventing the roof from falling in, SE might be better described as lifting oneself by ones own bootstraps, and finding out that gravity works against it.

[bob]

I tried Singular Extension for the first time. Surprisingly it is not that difficult to code, and there are several modern examples available. What is astounding is the less than 2% hit rate for singular extensions. The extra exclusion search should produce a decrease in overall strength. Either the singular hit is very successful (as it sometimes indicates in tactical test positions), or the exclusion search is so shallow and fast that delay is un-noticeable. The exclusion search would return quickly on hash hits with the reduced depth. So far, the results seem to accomplish no overall gain (or loss) in tests. Better extension conditions seem necessary.

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 am at a loss for an answer. If one extends a fail high, then one also extends the fail lows for the next ply, and you are no further ahead. Rather than preventing the roof from falling in, SE might be better described as lifting oneself by ones own bootstraps, and finding out that gravity works against it.

The problem is, how do you know a move is "singular" when every move at this ply is bad? If you do an offset window search at EVERY node, overhead will kill you. With a fail-high move, you know this one is good, so you can invest the time to see if the rest of the moves here are bad, and have a chance of doing better than break even.

But, for example, if you are down in material, does it help you at all to know that one of your moves at a ply where (a) you are failing low and (b) material is way down, that a move is "singular"? Probably not so much.

I would suggest reading Hsu's paper in the JICCA. He describes PV-singular, and FH-singular (principal variation node and fail high node) and also why testing at fail-low is counter-productive...

[hgm]

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.

[D Sceviour]

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.

If the intention were to use two separate hash tables, then would it be better to allocate separate memory for two hash tables rather than damaging the main hash table? This seems like a waste of resources for something that "breaks even" (not sure about variants).

[hgm]

If the intention were to use two separate hash tables, then would it be better to allocate separate memory for two hash tables rather than damaging the main hash table? This seems like a waste of resources for something that "breaks even" (not sure about variants).

I don't think so. For one, you would have to decide in advance how much space to allocate to each, and in situations where the actual demand for one or the other becomes less, it means you will waste space on storing less important data (i.e. lower-draft entries, that could be easily recalculated) while having to overwrite more valuable entries in the other table. By letting them all compete for the same pool of entries you can be sure to always replace the least valuable entries.

Another issue is that it would needlessly drive up code complexity. Each time you do a hash probe you would have to worry first which table you want to probe, meaning you have to pass explicit information around the tree of whether you are doing an exclusion search or a normal search, etc.

[bob]

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