Singular extension tests

[bob]

Finished the rewrite of search and friends to remove duplicate code. While doing this I continued to study the ttSE stuff, and found one significant difference between Crafty and Stockfish that might explain why they seem to get a small Elo boost while I get a small Elo loss using this.

In Crafty, if I have a hash move, I search that move before doing any move generations whatsoever, to save time. I don't remember who suggested the idea, but as a simple optimization, I added the following code: If I fail low at any node, this is stored in the hash table as a "UPPER" position and there is obviously no best move to store. In Crafty, as a search is carried out, I save the first move searched (which may be the hash move, or the first capture tried, or the first killer (if there is no hash or safe capture move) or just the first move generated in the worst case. When I discover that this is a "UPPER" position with no best move, I store the first move searched as the best move. Why? The next time I hit this position, I will search that move without a move generation, and without a best move that is the move I would end up searching first anyway, so why not? All it does is avoid some additional move generations, since this move can cause a cutoff as the bounds change. And if it does cause a cutoff, I avoid the move generation.

However, this now means that _every_ hash hit will have a best move (the EXACT/LOWER positions obviously would, and now UPPER also). Might be that I end up with too many moves to test for TT singular. Am looking at this further before moving on. I don't want to get rid of the UPPER best move as that is a clean optimization that saves time...

[mcostalba]

I don't want to get rid of the UPPER best move as that is a clean optimization that saves time...

Optimization perhaps (although I greatly doubt), clean...well...if it was clean you'd not spend a couple of weeks to find it out.

The point is that if I put an hand in a socket, perhaps it fits, but is not the right place to put an hand: a glove seems more appropiate. If I don't have a glove it doesn't mean is correct to fallback to a socket.

"TT best move" has a meaning that , from what you can guess it means, well, "best move", not first move, a random move, a move that seems pretty to me, it means best move. If in a node you don't find a best move it means you don't have anything to fit in the "best move" socket.

I learned the hard way that in software development it is important to remain stick to the definitions. If a variable is called "a cat" you can store there only a cat, sometimes it is easier to say then to do, but always forcing the meaning of a variable (in this case) leads to hidden, nasty and difficult to find bugs sooner then later.

The bug life is very clear in this case, you force something into "best move" that is not a best move, time passes on, you forget about this, you come back to your code and use "best move" as it is a best move for something completely unrelated, but because now not always is a best move..ooops !

I don't know if the reason of ELO difference is due to this, but I would not call what you have exposed a "best practice".

[bob]

I don't want to get rid of the UPPER best move as that is a clean optimization that saves time...

Optimization perhaps (although I greatly doubt), clean...well...if it was clean you'd not spend a couple of weeks to find it out.

Do not know what you mean. This adds 2 lines of code to the search, one to simply store the first move tried, one conditional as in:

HashStore(....., TYPE==Lower ? first_move_searched : best_move);

So not exactly complicated. I do not follow your "greatly doubt" statement either. It isn't open for debate. It is easy to test. What could _possibly_ be wrong with trying the move you would search first if there was no hash move, but without the necessity of generating that move the next time this position is reached? This is a simple statement of fact, it was worth a few Elo on cluster testing, so there is nothing to doubt at all.

The point is that if I put an hand in a socket, perhaps it fits, but is not the right place to put an hand: a glove seems more appropiate. If I don't have a glove it doesn't mean is correct to fallback to a socket.

"TT best move" has a meaning that , from what you can guess it means, well, "best move", not first move, a random move, a move that seems pretty to me, it means best move. If in a node you don't find a best move it means you don't have anything to fit in the "best move" socket.

The definition of "best move" is "the move you want to search first the next time this position is encountered. For a PV position, we really do store the "best move." Using your logic, however, in a CUT node you would store _nothing_ because you do not know the "best move" in a cut node, you just know a move that is good enough to cause a cutoff. But we all accept that inaccuracy and store a best move anyway, or at least I do. In an ALL node, where I have no idea of a best move, there is certainly nothing wrong with trying the move I would normally search first, which would (in the case of Crafty) be the best capture according to MVV/LVA - SEE ordering, if there is a safe one, otherwise one of the two killer moves, or, finally the first move the move generator will produce. Doing this "best move" trick does not add a single node to the tree search, and saves move generations here and there when that move is good enough to cause a cutoff.

I learned the hard way that in software development it is important to remain stick to the definitions. If a variable is called "a cat" you can store there only a cat, sometimes it is easier to say then to do, but always forcing the meaning of a variable (in this case) leads to hidden, nasty and difficult to find bugs sooner then later.

Then I suggest that you first remove the code that stores a "best move" in a CUT position because that is not "sticking to the definition" of "best move". Or else change the terminology to "good move" which does fit, and also fits my definition as well.

The bug life is very clear in this case, you force something into "best move" that is not a best move, time passes on, you forget about this, you come back to your code and use "best move" as it is a best move for something completely unrelated, but because now not always is a best move..ooops !

I don't know if the reason of ELO difference is due to this, but I would not call what you have exposed a "best practice".

Only in the case of ttSE, which does not appear to be a world-beater idea anyway. I willmake a quick cluster test run removing this (without the ttSE either) just to see what Elo gain this best-move trick gives me. If it gives me +10, and taking it out to add ttSE gives less than +10, then I'll keep the trick alive. More in a few hours.

[Alessandro Damiani]

However, this now means that _every_ hash hit will have a best move (the EXACT/LOWER positions obviously would, and now UPPER also). Might be that I end up with too many moves to test for TT singular. Am looking at this further before moving on. I don't want to get rid of the UPPER best move as that is a clean optimization that saves time...

If a score is an upper bound then this means the opponent disproved the player's strategy. In this case I would not do any extension at all (so, no SE). In other words: do SE if the score is exact or a lower bound.

BTW It was a talk we both had about SE many years ago, when you decided to store the first searched move in the TT when the score is an upper bound.

[bob]

However, this now means that _every_ hash hit will have a best move (the EXACT/LOWER positions obviously would, and now UPPER also). Might be that I end up with too many moves to test for TT singular. Am looking at this further before moving on. I don't want to get rid of the UPPER best move as that is a clean optimization that saves time...

If a score is an upper bound then this means the opponent disproved the player's strategy. In this case I would not do any extension at all (so, no SE). In other words: do SE if the score is exact or a lower bound.

BTW It was a talk we both had about SE many years ago, when you decided to store the first searched move in the TT when the score is an upper bound.

I think that part of the problem is that this code gets executed more frequently. I did not extend every TT entry although I will have to look back thru notes to see what I did test. But several of them were more selective. Some looked at static eval, etc, and they could lead to a ttSE test since there was a hash move to work with...

I am currently testing with this fail-low best move code commented out to see what the gain is, particularly since the current search has had a lot of optimization work done on it in recent weeks...

One side-effect of this optimization is that it can also preserve a best move that would otherwise go lost.

For example, the first move you search is a hash move from a hash hit. However, bounds have changed and the table entry won't cause a cutoff, but has a move to try first. You get no cutoff, because the bounds have changed and now this is an ALL node rather than a CUT node. But by storing the first move searched, the original hash move, the CUT node best move gets preserved in this ALL node search. Turns out this case is not that uncommon and the gain is pretty significant. Still waiting on cluster test to end, results in an hour or two...

[mcostalba]

Then I suggest that you first remove the code that stores a "best move" in a CUT position because that is not "sticking to the definition" of "best move". Or else change the terminology to "good move" which does fit, and also fits my definition as well.

Yes, correct. Indeed it is called ttMove and is a move that caused a beta cut-off.

Note that also in SF you have ttMoves in failed low nodes, but they are actually ttMoves from previous searches that failed high.

The trick here (that I think is the correct one to implement) is to save MOVE_NONE in a failing low node _only_ if there isn't an already exsistant move in the TT entry that corresponds to the position (see tt.cpp for the details). In this way you have the cake and eat it too: preserve old ttMoves when a node fails low and you are sure that the moves are _always_ ttMoves, i.e. moves that caused a beta cut-off somewhere in the past.

[bob]

The following has results for recent Crafty versions, including 23.4 which is the current version we are working on, and 23.4R01 which is 23.4 but with the best-move at ALL nodes idea commented out...

Code: Select all

Crafty-23.4          2675    3    3 30000   65%  2559   22%  
Crafty-23.3          2672    3    3 30000   65%  2559   22%  
Crafty-23.4R01       2649    4    4 23266   62%  2559   22%  
Crafty-23.2          2620    3    3 30000   58%  2559   22%  
Crafty-23.1          2599    3    3 30000   55%  2559   22%  
Crafty-23.0          2509    3    3 30000   44%  2559   20%  

Turns out to be a better idea than I thought. Part of this is certainly related to the optimization issue, but a bigger part is related to preserving a best move stored in a LOWER/EXACT entry when the current search finds that the position is really an UPPER bound now because of window changes. When I
last tested this best-move idea it was not worth this much, but hashing has changed in the past year, along with other things, which makes this idea even better, apparently. Certainly +26 Elo is worth it, where I found no case in either Crafty or Stockfish where the ttSE idea was even close to that. Taking this out and putting ttSE back in is an almost guaranteed loss although I am going to run that test next.

Note that the current test is not quite finished, but the error bar is small enough to be convincing in light of a 26 elo drop (+/-4 currently).

[bob]

Then I suggest that you first remove the code that stores a "best move" in a CUT position because that is not "sticking to the definition" of "best move". Or else change the terminology to "good move" which does fit, and also fits my definition as well.

Yes, correct. Indeed it is called ttMove and is a move that caused a beta cut-off.

Wrong again. What about "exact" nodes that did _not_ get a cutoff. There it is the best move. In the LOWER positions, it could be the best move, or in many cases it could be _any_ move since any move will refute some of the positions encountered where the opponent is way down in material.

Note that also in SF you have ttMoves in failed low nodes, but they are actually ttMoves from previous searches that failed high.

Same in Crafty. I just added another class of these moves that give me a reasonable move to search first when one is not obvious. That "reasonable move" is simply the first move the move selection code tries first in this position if it doesn't have a hash move. In any position that does have a hash move, that automatically gets preserved since it is always tried first...

The trick here (that I think is the correct one to implement) is to save MOVE_NONE in a failing low node _only_ if there isn't an already exsistant move in the TT entry that corresponds to the position (see tt.cpp for the details). In this way you have the cake and eat it too: preserve old ttMoves when a node fails low and you are sure that the moves are _always_ ttMoves, i.e. moves that caused a beta cut-off somewhere in the past.

Again, why? If you reach this position and get "MOVE_NONE" what are you going to do? Call the normal move generation/selection code to pop out the first move to search? I simply remember this move so that if I get a hash hit here later, I can try that move first without any move generation. If it produces a cutoff due to a window shift, good. If not, absolutely nothing lost and nothing hurt since I would try this same move anyway if it were not in the table.

I can test this preserving old best moves but not storing the first move in an ALL node unless it came from an old hash entry, to see what the effect is...

Got that queued up to run right after the current run is done.

I am not a big fan of treating tt moves as "special". They represent a small percentage of total nodes searched since hash hits in the middlegame are in a small minority of total positions. If something is important, it needs to be retained. As in Hsu's SE implementation with the "sticky transposition table" to be sure that singular status does not get lost by overwriting in the main hash table. The idea of randomly picking a subset of moves and extending them seems wrong, logically, yet that is what the ip* ttSE idea does, exactly. If we could extend _all_ fail-high best moves, it _might_ begin to make sense, but if you do some tree dumping, a lot of those moves have no business being extended because in quite a number of positions _every_ move will fail high, the opponent is so bad off in terms of material, where he has tossed a queen + rook for nothing. Any opponent move looks good there. Do I want to extend 'em? Don't think so.

[bob]

For that +26 Elo reported previously, looks like +23 is a result of the hash move being preserved, and +3 for the speed gain. Before this was added, there was specific code in HashStore() that preserved the best move when storing an entry with the identical key but no best move. I removed that since this mechanism did the same thing. The optimization is definite, but quite small, in Crafty, for avoiding generating a move here and there. The biggest gain is avoiding losing the hash move when overwriting a position with a hash move by a table entry that is an UPPER entry (with no best move)...

[mcostalba]

For that +26 Elo reported previously, looks like +23 is a result of the hash move being preserved, and +3 for the speed gain. Before this was added, there was specific code in HashStore() that preserved the best move when storing an entry with the identical key but no best move. I removed that since this mechanism did the same thing. The optimization is definite, but quite small, in Crafty, for avoiding generating a move here and there. The biggest gain is avoiding losing the hash move when overwriting a position with a hash move by a table entry that is an UPPER entry (with no best move)...

To avoiding generating a move here and there you end up overwriting an already exsisting ttMove with a move from an ALL node ! Is this the "optimization" ?