Singular Extensions

[bob]

It has finally popped up to the top of my "to-do" list, so I am fixing to start experimenting with this again. I once released a version of Crafty that had Singular Extensions, but removed it later.

First, a little bit of background on what I tried in conjunction with Bruce Moreland, or in Cray Blitz.

Hsu/Campbell clearly defined their SE implementation, which is somewhat messy and complex. Key points:

(1) Using the usual PV, CUT and ALL node types, Hsu defined SE for PV and CUT, but not for ALL nodes. CUT (He called this FH-singular) is pretty simple. When a move fails high, before you return the FH score, you do a singular test on the remaining moves, using an offset (downward) alpha/beta window and a reduced-depth search. If no moves fail high on the offset window, you re-search the fail-high move you just searched, but one ply deeper. We call this move a FH-singular move since it appears to be significantly better than any other move.

(2) for PV-singular, the process is more complex. After you get a score for the first move, you search the remainder to the same depth, but with an offset (downward) window. If all still fail low, the move that produced the score is called PV-singular, and gets re-searched one ply deeper. If any move fails high on the offset-window search, you now have two moves to test to see if one is significantly better than the other. Which makes this messy. And other moves can also fail high on that downward offset window. When you finish this mess, either one move is clearly better, and gets extended, or else none do.

(3) Hsu was also concerned about inconsistencies, and therefore created a special small hash table he called the "sticky TT". If a move gets extended as being singular, the position and move is entered into this table. It lets us avoid all the singular testing the next time we encounter this position, and also guarantees us that independent of the depth, we will extend this move as singular each time we encounter it, to avoid the case where a move appears to be singular at one depth and not at another. There is a complex aging scheme so that we don't do this forever and a move can fall out of "singular" status.

That's all complex. I implemented it in Cray Blitz, and it appeared to certainly help in tactical positions. Unfortunately, our testing was extremely limited, so I never produced any quantitative proof showing it was better in real games. The code was lost, although I _might_ have a printout of it. But Carey and I tried to OCR a version of Cray Blitz and it was beyond hopeless, since "1" (one) and "l" (ell) look the same. Since fortran doesn't require variables to be declared before they are used, this absolutely wrecks a program and it has to be debugged line by line. Not for me with that many lines of code. And it would not transfer to Crafty very well anyway, since it was an iterated version of alpha/beta written in fortran, rather than a recursive version in C>

(4) There are some "el-cheapo" approaches that we tested. One is quite simple. Whenever you get a fail-high, you can do a quick reduced-depth with offset window search, and if the move appears to be singular, it can be searched more deeply. Not so hard to do and I have this code saved somewhere.

(5) At the front of search, you can first do a quick reduced-depth search to see if you can identify a singular move. Get a score for the first move, search the rest with a downward offset window, and if they all fail low, remember this move as singular. All of this was done at the same reduced-depth. Then, when you get into the regular search and search a move that matches the singular move, you extend it by one ply (or whatever fraction you choose). The downside is that the SE search is done at _every_ node. The upside is that it is cheap if you use a reduced-depth search and will likely see most searches terminated by hash hits anyway.

(6) We tried the ip* TT-SE idea where you wait until you get a hash hit that does not terminate the search. If the depth is close to being "good enough" (close but no cigar, of course else the search would terminate here immediately) then you can use this is a "hint" that you have a singular move. If the score appears to be "reasonably better" than the current search bound, you can do the quick reduced-depth search on the other moves to make sure they fail low on a lowered window, and then extend this move as part of a normal search. Extra overhead for the "proof" search, but how many hash hits do you get in the middlegame, 25%? How many will have a lower bound significantly better than current beta?

There might be another idea or two I have not remembered. The point of this is to first discuss potential ideas to see if anyone has anything better/different to try. I intend on trying all the old ideas (except Hsu's approach unless I find a lot of extra energy somewhere) and run 'em thru the cluster tests.

There are a couple of related ideas, such as Donninger's "threat extension." Idea is that when you get a fail-high (or a new best move) you do a null-move search to reduced depth with a downward offset window. If that fails low, and the current move fails high, while doing nothing with a lowered window still fails low, this move might be our only move that holds off some significant threat by the opponent (often it is a check or horizon-effect type move). So we extend the thing. Somewhere in the single-digit versions of Crafty we used this for quite a while, but again with nowhere near proper testing. It saw some impressive tactics at times, but it had a definite cost as well (all those null-move proof searches are not free).

Any other comments, corrections, additions or suggestions???

[mcostalba]

Any other comments, corrections, additions or suggestions???

Yes, idea (6) is not correctly laid-out, in particular this part is to be removed:

Code: Select all

If the score appears to be "reasonably better" than the current search bound

I suggest to better document yourself reading the sources (instead of being told about them) before to start your tests.


BTW if idea (6) doesn't work for you it means is an implementation bug

[Mangar]

Hi Bob,

I suggest to first implement the idea to find singular moves in front of search with a shallow depth search. This is the most flexible approach as you have the information about the singular move as ealy as possible. First you should try a "base" test. Test crafty with the "find singular moves an do nothing with the information" implementation. Then you know the elo reduction you get for the work to find singular moves.

Some ideas to try then:

1. Use a non constant downward offset window. It sould be a function of remaining search depth. A position value calculated at higher depth sould be more stable. Thus take a smaller offset window, if remaining seach depth is large.

2. Even if you identify a singular extension move in front of of search, let him prove it is good at normal search before you extend. Thus research it at depth + 1 if it really fails high on cut nodes or raises alpha at pv nodes.

3. Try to not singular extend in the pv line itself, thus only if a move in the pv line changes. The pv line is allready very deept compared to other move sequences.

4. Consider effects between lmr and singular extensions. Try the following: If you find a singular move in front of search try to return alpha without any additional search if the ply before has a late move reduction. It seems somehow rediculous to extend the only relevant move in a reduced search. I´d like to test this without any "real" singular extensions.

Greetings Volker

[hgm]

Basically, you are chasing the requirements for a beta cutoff in a d=N node to one of the following:

1) A single move with score >= beta searched at d=N+1
2) A move with score >= beta at d=N, plus one with score >= beta-SHIFT at d=N-REDUCTION.

Because (2) is in general cheaper to obtain, you start trying that. But as the major purpose of the hash table is to store the information on how to acheive a quick cutoff, it would be logical to store both moves you need for (2) in the hash. (Hash move + Support move.)

A danger of the whole scheme seems to be that the hash move and the support move could be related by a transposition. E.g. I could gain back a Pawn by NxB, PxB, NxP, and it would not matter with which Knight I started capturing. The algoritm would fail to see that there is really only one way to gain the Pawn. Perhaps one could guard against this by backing up the hash key of the evaluated position towards the root, together with its score. If two different moves then are returning the same 'score-ID', you know they are related, and you could consider them as one. (Which then might make the position singular after all.)

[Daniel Shawul]

Overall I find (5) elegant and that is what I tried, but it failed badly.
I will eagerly await your test results on this.
Variations I tried include avoiding singularity tests at ALL nodes.
Seems also that originally Hsu tried PV/CUT signular only. And also avoiding captures from the test as well.
You mentioned in the past about recaptures being intentionally avoided in the singularity test,
but I do not see anything in your post here. What is the stance?

About PV-singular,when two moves become "interesting",isn't it better to leave the test ?
Trying further search sounds like beating a dead horse. I know at a PV node a singular extension
could help a lot, but if that is the case I would just extend the second move by UNITDEPTH / 2 and
move on..

I do not store the result of singularity test in TT. Because on the next ply a "forced" regular
search is conducted with all of its results stored in TT. That should make it cheap..
Some store the result of a singular search in the regualr TT (by modifying the hash_key) or "sticky TT"
as you mentioned. Is this really necessary ?

Finally I think that (5) is by far the most elegant of all and cheaper IMHO. I already do IID at every
node (sometimes I exclude ALL nodes). So that already gives me something to test. I am infact a little bit
surprized to learn that Hsu/Campbell's original scheme sounds a bit ad hoc. FH-singular,sticky TT ??

Finally you said you tried (6), was that any good ?

Daniel

[Daniel Shawul]

I think that PXB would be singular in that case. But I am not sure because I heard that re-captures are intentionally avoided from being singularly extended.
I would also prefer to avoid further tests if two moves seem singular due to transposition or otherwise. With the general singularity test scheme, we get way more "singular" moves than we would like to extend, so why look for more ?

[Daniel Shawul]

You say that like it is a good thing to do ? I asked you about it couple of weeks ago but you preferred to ignore it.
I guess you have a better reason than increasing the number of nodes on which singularity is being tried. If it did work for you (and it looks like it did), it is because of bugs like that

[bob]

Any other comments, corrections, additions or suggestions???

Yes, idea (6) is not correctly laid-out, in particular this part is to be removed:

Code: Select all

If the score appears to be "reasonably better" than the current search bound

I suggest to better document yourself reading the sources (instead of being told about them) before to start your tests.

Not sure what you are talking about. This is code that I have from 10-15 years ago when several of us were experimenting with it. I am not quoting how anybody is doing this today, other than to mention that ip*, robo* used the _idea_ that you guys copied. I didn't give a single idea above that I do not already have code for (unfortunately most of it is going to need significant modification since crafty has changed a ton since the 1997 time frame when much of this was written and tested... When I played with this, one limit I tried was to check the TT bound. Didn't seem very useful to do the SE test on a position that returned a bound somewhat lower than current window...

BTW if idea (6) doesn't work for you it means is an implementation bug

Just like the null-move verification search doesn't work for me? And when I comment it out of SF I get a 2-3 elo improvement as well?

[bob]

Hi Bob,

I suggest to first implement the idea to find singular moves in front of search with a shallow depth search. This is the most flexible approach as you have the information about the singular move as ealy as possible. First you should try a "base" test. Test crafty with the "find singular moves an do nothing with the information" implementation. Then you know the elo reduction you get for the work to find singular moves.

Remember, I don't have to "implement" anything (unless I decide to try the _real_ SE idea as laid out by Hsu/Campbell. All of the other ideas were done in the past and I have the code. It will certainly need some modification since lots of things have changed inside Crafty since 1997, but I don't have to write a ton of code for anything I listed except the Hsu approach. I'm hoping for _other_ ideas that might be worth considering, since I can now get an extremely accurate measurement of how each idea affects Elo, something I could not do in 1997, other than by watching ICC ratings which are not the most stable things on the planet...

Some ideas to try then:

1. Use a non constant downward offset window. It sould be a function of remaining search depth. A position value calculated at higher depth sould be more stable. Thus take a smaller offset window, if remaining seach depth is large.

2. Even if you identify a singular extension move in front of of search, let him prove it is good at normal search before you extend. Thus research it at depth + 1 if it really fails high on cut nodes or raises alpha at pv nodes.

That is something I did not try.

3. Try to not singular extend in the pv line itself, thus only if a move in the pv line changes. The pv line is allready very deept compared to other move sequences.

Nor that. But the idea here is not just to _improve_ the score. The idea is to see problems along the PV that would justify playing a different move. I'll take a look, but this sees as wrong as not doing reductions along the PV, or not doing null-move along the PV. I don't quite see what makes the PV "sacred".

4. Consider effects between lmr and singular extensions. Try the following: If you find a singular move in front of search try to return alpha without any additional search if the ply before has a late move reduction. It seems somehow rediculous to extend the only relevant move in a reduced search. I´d like to test this without any "real" singular extensions.

Greetings Volker

I have a few non-singular ideas, and the above is one that has been on the back burner for a while. Seems reasonable to consider what has been done, before doing something that effectively "undoes" that. Years ago I did the opposite, and always looked at what had been done earlier in the current path with regard to extensions, before I would do any serious pruning or reductions. But again, that was before I could really get accurate measurements. I plan on beating on search for a good long while here, since there are other things I have on my list to try. But SE has been on there for a while, and since search is mainly what I have been working on for the last year or so (Tracy has been doing most eval changes) I felt that SE (among other things) was prime for testing.

[bob]

I think that PXB would be singular in that case. But I am not sure because I heard that re-captures are intentionally avoided from being singularly extended.
I would also prefer to avoid further tests if two moves seem singular due to transposition or otherwise. With the general singularity test scheme, we get way more "singular" moves than we would like to extend, so why look for more ?

I am pretty certain that you do _not_ want a recapture to be singular. I did do some testing in this, and reached the same conclusion Hsu and Campbell reached, which was that extending every recapture (and many will appear to be singular when there is just one way to recapture) can cause the search to blow up significantly, without learning anything new. I already have a note to myself to test this since I was, at one point, doing a recapture extension, which I do not do any longer.