search extensions

[bob]

I think I have just finished wasting about 6 months (or more) of time working on trying some historic extension ideas.

Here's a list of the things I have tried, and tested exhaustively.

(1) simple singular extensions as found in robbolito/stockfish/who knows what other program. The idea is that (a) a move from the hash table is a candidate singular move. Ignoring a few details, you search every other move (except for the hash move) using an offset window, and if all other moves fail low against that window, this move gets extended. Never thought much of it, and at one point I removed it from Stockfish and my cluster testing (gauntlet NOT self-testing) suggested it was a zero gain/loss idea. I've tested this extensively on Crafty and reached the same conclusion, it doesn't help me at all. When I do self-testing, there were tunings that seemed to gain 5-10 Elo, but when testing against a gauntlet, they were either Elo losing or break-even. I gave up on this.

(2) Bruce Moreland and I played around with a different approach back in the late 90's. At the top of search, do a reduced-depth search with a downward offset window, and if one failed high (only one) then search it with the normal window (a null-window however). If it fails high, call it singular and extend it when it is searched in the real search here. This can find some cute tactical shots, but once again, in real testing with large numbers of games, it is an Elo drop.

(3) Finally, I decided to bite the bullet and do the full Hsu singular extension idea, complete with sticky transposition table (see the hsu article in JICCA in 1988 and a follow-on by Thomas in 1992). I have beat this to death and once again the best I have done is a break-even algorithm. It sees some things quicker, but the overhead slows it down enough that overall it does not work. I won't explain the details unless someone is interested, but I did both fh-singular and pv-singular, using a sticky TT for both.

(4) Hsu also mentioned a null-move threat extension that Donninger later wrote a paper about as well. The idea is that when a move fails high (or becomes a new pv move by backing up a score > alpha) before accepting that score, you do a null-move search with a downward offset window and if it fails low, something is up. You are in a position where doing nothing loses, but playing the PV/FH move is good, meaning this position is likely dangerous, since there is only one move that keeps the roof from falling in. So extend it by one ply and search again. Once again, I have gotten close to break-even, but it doesn't work to gain anything and generally loses Elo overall.

For a point of discussion, if you look at Hsu's 1988 paper, they originally claimed almost +200 Elo, because they played 20 games and did something like win 16 and drew 4 (don't hold me to those exact numbers but they are close). Thomas (Anantharanman) wrote a follow-up paper where he did much more accurate testing, and found that singular extensions (Hsu algorithm) really only gained +9 elo. But he did claim that the threat extension was worth almost +50 Elo. So it seems that my measurements match theirs on normal singular extensions (but not on the threat extension). And for fun, I went back and played a match where I disabled modern things like LMR and suddenly I was seeing a slight gain for SE. Turning LMR back on and SE went south Elo-wise.

After a zillion hours of testing, I have concluded that we are getting to the SE idea but in a different way. Ed and I had a debate years ago about extensions and reductions. I pointed out that if you take program A and only extend checks by 1 ply, and play it against B (where you reduce every move BUT checks by 1 ply) they would play equally. Yes, B would report a deeper depth, but who cares? If you do it by hand, you see both search the same tree with a given node count. So how are we extending? Because most now use a tapered LMR where later moves are searched less deeply because they are reduced more. Early moves are, effectively, extended, using this "negative extension" reasoning. And with history ordering, you have a better chance of getting good moves earlier in the list, so that they are reduced less (or extended more thinking backwardly).

I have written all of this off as experience gained / time wasted. But I will NOT be returning to singular extensions or threat extensions in the future. There is probably some more interesting things to try to push moves closer to the front of the move list if they appear to be better, or closer to the end of the list if they appear to be worse, but that is a different topic that I am going to look at next. About the only good thing from this is that I ended up completely redoing my search function so that the duplicated code in the parallel search part no longer exists. There is a search front-end that does everything prior to cycling through the move list and searching each one, and then there is a backend that is called by either the front-end or the parallel thread code to cycle through the moves. So at least I ended up with a better search code that has no duplicated code of any kind.

Anyone else tried any of this? And the obvious follow-up is "anyone else tried any of this and actually seen it produce an Elo gain in a real testing framework (self-test seems to give contradictory results for this particular kind of stuff, then gauntlet test brings things back down to earth with a dose of reality).

Be happy to provide more details for anyone interested. Bruce Moreland liked the extension test he was using. And it will produce some pretty long PVs when search depths are shallow. But with today's 30+ plies, it simply would not work for me. None of them would.

More if there are questions or comments...

BTW the treat extension is the easiest to implement, followed by the robbolito approach. Hsu's idea is really a giant PITA. And one other idea I tried that I have not seen mentioned period, was to use that sticky transposition table idea for the threat extension. If a position meets the threat extension criteria, then the second time it does not need to be tested, it just needs to be extended. If if failed the extension criteria, it won't be extended and the next time it is reached, it won't be tested nor extended. Reduces the search tree below the normal threat extension overhead, but this was the final version I tested and found no gain.

I have returned back to the extend non-losing checks and nothing else...

[Ferdy]

Thanks Bob, I thought I will try (4), sounds expensive but fail high on first move is common, perhaps this should not be done always and I am thinking of loading some conditions before trying this. Conditions like promote moves, capture move, or non-capture, previous iteration score perhaps, or piece specific moves like rook to 7th rank, or knight to safe center squares.

[bob]

Thanks Bob, I thought I will try (4), sounds expensive but fail high on first move is common, perhaps this should not be done always and I am thinking of loading some conditions before trying this. Conditions like promote moves, capture move, or non-capture, previous iteration score perhaps, or piece specific moves like rook to 7th rank, or knight to safe center squares.

(4) sounds logical. I used it in some early versions of Crafty. Comments suggest it was first tried in version 3.4, back in the days of 4-5-6 ply searches, max. However, I had no luck with the current version. And I have been beating on both threat extensions and singular extensions for the whole time. I hope someone has some luck, but I have become convinced that the reduction stuff (sort of an anti-extension idea) is in direct conflict with singular/threat extensions. I have looked at so many tree dumps I am almost blind.

Good thing about (4) is that it is trivial to implement. You certainly want to limit it by remaining depth. But the question is, what kind of null-move reduction do you use? I tried the idea I have been using for quite a while off and on, an adaptive R value. I also tried things like a static R value and even depth/2 for the actual null-move search depth. The issue is that the more you reduce to limit overhead, the more you hide deep tactics. If you play with it, I can describe most every combination I tried. But some basics:

can't be in check, null-move search will be bogus

no point on ALL nodes since everything fails low. Nice thing about waiting to you get a fail-high before doing the null-move threat search is that you won't do it on any ALL nodes since there is never a fail high on those anyway. No point in doing it if you already extended the move assuming you don't allow more than 1 ply of extension per move (I tried going further and got quite a few non-terminating searches that hit beyond 200 plies easily).

Have fun..

[Henk]

Perhaps search extensions is an alternative for LMR. For instance I don't understand if you can apply LMR in a node if that position is expected to fail high. For instance If you apply LMR after four moves it should already have failed high but it did not so why would you reduce the next moves and introduce even more error. If the node did not fail high during the first moves then perhaps the best move in the parent node was not the best move and LMR should not have been applied in the parent node as well. Maybe it would be best to trigger a research as soon as possible in that situation.

[mcostalba]

(4) Hsu also mentioned a null-move threat extension that Donninger later wrote a paper about as well. The idea is that when a move fails high (or becomes a new pv move by backing up a score > alpha) before accepting that score, you do a null-move search with a downward offset window and if it fails low, something is up. You are in a position where doing nothing loses, but playing the PV/FH move is good, meaning this position is likely dangerous, since there is only one move that keeps the roof from falling in. So extend it by one ply and search again. Once again, I have gotten close to break-even, but it doesn't work to gain anything and generally loses Elo overall.

This is an interesting idea although it is expressed in an incorrect way because at the time you fail high with a new move eveything is already done: a null search that failed low before and a possibly extended search, but it doesn't matter if you didn't write it properly.

Code: Select all

The core idea that if a null search fails low and instead a normal search fails high then there is some 'tension' in the position and it is worth to extend it.

...for the details of the implementation it is better to do on our owns...

[Ferdy]

I tried the following conditions.

Search the hash move first, if it failed high, check the mate threat flag from null move.

Code: Select all

// Threat extension
if(     mt                                   // mate threat from null move search
    && depth <= 12*PLY 
    && node_type != NODE_ALL 
    && !&#40;capture_move&#40;move&#41;)
    && !moveischeck
    && wpc >= 2                        // non-pawn and non-king white pc counts
    && bpc >= 2
)
&#123;	
    //print_board&#40;);
    //print_fen&#40;);
    te = true;
&#125;
else&#123;
    return x;
&#125;

&#91;...&#93;

// Search other moves noting on the te flag
ext = calculate_ext&#40;);
if&#40;!ext && te&#41;
   depth += PLY;    

There is promising trend so far. It always leads in self-test match, at
TC 30s + 100ms/move.

Code: Select all

[...]
Finished game 240 (D125 vs D126): 1/2-1/2 {Draw by 3-fold repetition}
Score of D126 vs D125: 70 - 56 - 114  [0.529] 240
Started game 246 of 80000 (D125 vs D126)
Finished game 241 (D126 vs D125): 1/2-1/2 {Draw by 3-fold repetition}
Score of D126 vs D125: 70 - 56 - 115  [0.529] 241
Started game 247 of 80000 (D126 vs D125)
Finished game 242 (D125 vs D126): 1/2-1/2 {Draw by 3-fold repetition}
Score of D126 vs D125: 70 - 56 - 116  [0.529] 242
Started game 248 of 80000 (D125 vs D126)
Finished game 244 (D125 vs D126): 1/2-1/2 {Draw by 3-fold repetition}
Score of D126 vs D125: 70 - 56 - 117  [0.529] 243
Started game 249 of 80000 (D126 vs D125)
Finished game 243 (D126 vs D125): 1-0 {White wins by adjudication}
Score of D126 vs D125: 71 - 56 - 117  [0.531] 244
Started game 250 of 80000 (D125 vs D126)
Finished game 249 (D126 vs D125): 1/2-1/2 {Draw by 3-fold repetition}
Score of D126 vs D125: 71 - 56 - 118  [0.531] 245
Started game 251 of 80000 (D126 vs D125)

I may test this with other engines if it looks good eventually.

[Ferdy]

Perhaps search extensions is an alternative for LMR. For instance I don't understand if you can apply LMR in a node if that position is expected to fail high. For instance If you apply LMR after four moves it should already have failed high but it did not so why would you reduce the next moves and introduce even more error. If the node did not fail high during the first moves then perhaps the best move in the parent node was not the best move and LMR should not have been applied in the parent node as well. Maybe it would be best to trigger a research as soon as possible in that situation.

There are times when best move in the position is buried late in the move list. For every program there is this peculiar theme where you always failed to see such moves early - this can be rectified by dumping these position in log file and study it there.
To possibly retrieve that best move fast you may apply more depth reductions as moves tried increases. On the other hand, if you have already tried 70% or so of the possible moves from a given position and yet you still could not improve, then stop searching this position and consider this position as bad (verified with other conditions), I earn some points from this.

[jdart]

I haven't tried these techniques. I do have a variety of extensions, including check, forced check evasions, pawn push, and capture of the last opponent piece.

> There is probably some more interesting things to try to push moves closer
to the front of the move list if they appear to be better

I recently did some experiments with this, for example adding some positional knowledge to the ordering, but surprisingly it performed worse. It does sound intuitively like it ought to work though.

--Jon

[elcabesa]

Hi marco, I'm trying to play with your sentence.

The core idea that if a null search fails low and instead a normal search fails high then there is some 'tension' in the position and it is worth to extend it.

I've just trying to test the idea in the code and these are my first result.

I started count all the time a search end with a fail high if the null move:
1- hasn't been executed
2- has failed low
3- has failed high

those are my result so far for a given set of positions

1- 36%
2- 64%
3- 0%
after some thought it looks the results are ok.


take the case 3, if the nullmove fail high it's very probable you will return without doing the search, so the probability is 0%.

so a fail high can appen only after not having tested the null move at all or after a null move fail-low. it's not a TROUBLESOME position, but a standard position.

this is what I get without adding any new type of search but only counting how many times a fail high appens after the null move fail-low

[bob]

(4) Hsu also mentioned a null-move threat extension that Donninger later wrote a paper about as well. The idea is that when a move fails high (or becomes a new pv move by backing up a score > alpha) before accepting that score, you do a null-move search with a downward offset window and if it fails low, something is up. You are in a position where doing nothing loses, but playing the PV/FH move is good, meaning this position is likely dangerous, since there is only one move that keeps the roof from falling in. So extend it by one ply and search again. Once again, I have gotten close to break-even, but it doesn't work to gain anything and generally loses Elo overall.

This is an interesting idea although it is expressed in an incorrect way because at the time you fail high with a new move eveything is already done: a null search that failed low before and a possibly extended search, but it doesn't matter if you didn't write it properly.

You didn't read carefully. On a fail high, you then search with a DOWNWARD OFFSET null window. Hsu used 1/3 of a pawn. The original null-move search you did was usually done with beta, beta+1 as the window. There is a significant difference between the two null searches.

Code: Select all

The core idea that if a null search fails low and instead a normal search fails high then there is some 'tension' in the position and it is worth to extend it.

...for the details of the implementation it is better to do on our owns...

Of course. However the idea has been written up and published TWICE in the JICCA, once by Hsu, once by Donninger. Certainly makes sense to read first, then jump in afterward. This is what I did. In fact, I had already implemented it once, very early in Crafty development (as well as trying it in Cray Blitz).

Just note that this is an offset null, not using beta, beta+1 as I mentioned.