TalkChess.com

[Robert Hyatt]

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