Store in TT after null search fails high

[jwes]

I think the "zero move" is logical. The null-move is now the "best move" for this position. You _could_ try to keep the original best move (assuming the signatures match) but when I have tried this anywhere in the tree, it has hurt a little bit. For example, suppose an old hash entry says "fail high here" and you store the best move, then you search that position to a deeper depth and get "fail low here" with no best move. Do you save the old best move (since the positions are the same, but the depths are different and the entry type is different?) When I tried this, it was worse overall.

Storing a null move when failing high for null move is different than storing a real move when failing low. The latter is clearly silly.

It isn't even "silly". It is "wrong". On a fail low, there is no best move, of course.

You can store the first move you searched at the fail low. It will sometimes save you a move generation and won't change move ordering.

[bob]

I think the "zero move" is logical. The null-move is now the "best move" for this position. You _could_ try to keep the original best move (assuming the signatures match) but when I have tried this anywhere in the tree, it has hurt a little bit. For example, suppose an old hash entry says "fail high here" and you store the best move, then you search that position to a deeper depth and get "fail low here" with no best move. Do you save the old best move (since the positions are the same, but the depths are different and the entry type is different?) When I tried this, it was worse overall.

Storing a null move when failing high for null move is different than storing a real move when failing low. The latter is clearly silly.

It isn't even "silly". It is "wrong". On a fail low, there is no best move, of course.

You can store the first move you searched at the fail low. It will sometimes save you a move generation and won't change move ordering.

I haven't forgotten that. Got it on my to do list to test on the cluster in fact.

[Gian-Carlo Pascutto]

I tried everything up thru 30/30. I found no change from very fast thru that time control. I could run 60/60 but the test turns into a long one since it would run at about 128 games per hour. 1000 games in 8 hours. 10,000 games in 80 hours. So we need about 2 weeks. Don't see the need.

It hurt uniformly at every time control I tried. That was good enough for me. And not only in Crafty. I removed it from Glaurung 2 as well and got the same sort of result. If you believe it helps at even longer time controls, fine by me. But I don't. There are three types of things you can add to a program. Those that help, those that don't change anything at all, and those that hurt. I don't care whether I get burned a little or a lot, I don't want to get burned at all. Neither do I want to give up any skill by using something that appears to not work well enough to even break even.

I am surprised, are you still able to do basic mates after this?

Does the result hold without any EGTB?

[bob]

I think the "zero move" is logical. The null-move is now the "best move" for this position. You _could_ try to keep the original best move (assuming the signatures match) but when I have tried this anywhere in the tree, it has hurt a little bit. For example, suppose an old hash entry says "fail high here" and you store the best move, then you search that position to a deeper depth and get "fail low here" with no best move. Do you save the old best move (since the positions are the same, but the depths are different and the entry type is different?) When I tried this, it was worse overall.

Storing a null move when failing high for null move is different than storing a real move when failing low. The latter is clearly silly.

It isn't even "silly". It is "wrong". On a fail low, there is no best move, of course.

You can store the first move you searched at the fail low. It will sometimes save you a move generation and won't change move ordering.

I haven't forgotten that. Got it on my to do list to test on the cluster in fact.

OK, got results. This was worth yet another 2-3 Elo. It is a gain in speed, because with a reasonable best move (even in an ALL [fail-low] node) Crafty avoids a move generation. When the ALL node flips to a CUT node (not so common, but it does happen as the depth changes from iteration to iteration) this stored best move from the "UPPER" hash entry does avoid a move generation which saves some time. On the down side, sometimes this "best move" comes from the killer moves, and on occasion the killer that was stored (the first move tried) would not be the first move tried at the new search point since killers have been modified.

I found some of this on testposition (run one is always old crafty, run two (log.002) is always the new version (I will explain the fix in a minute):

log.001: time=5.57 mat=0 n=14469336 fh=95% nps=2.6M
log.002: time=9.00 mat=0 n=22370561 fh=95% nps=2.5M

So slower in this position (Kopec 22, Bxe4) the change hurts. In WAC 2, a deeper position:

log.001: time=27.44 mat=0 n=79588504 fh=91% nps=2.9M
log.002: time=38.45 mat=0 n=108129448 fh=90% nps=2.8M

Again, looks worse.

Fine 70 searched to 44 plies:

log.001: time=5.51 mat=1 n=18926369 fh=92% nps=3.4M
log.002: time=2.31 mat=1 n=9100183 fh=95% nps=3.9M

Finally the complete WAC test set run at 1 second per move on my core2 duo laptop (note that everything I have run is using only one CPU for repeatibility and to avoid the SMP variability).

Code: Select all

old:
test results summary:

total positions searched..........         300
number right......................         296
number wrong......................           4
percentage right..................          98
percentage wrong..................           1
total nodes searched..............   149733606
average search depth..............         5.0
nodes per second..................     2877832
total time........................       52.03

new:
test results summary:

total positions searched..........         300
number right......................         296
number wrong......................           4
percentage right..................          98
percentage wrong..................           1
total nodes searched..............   136323895
average search depth..............         5.0
nodes per second..................     2830058
total time........................       48.17

Slightly faster. Tough to decide whether it is good or bad?

Cluster says +2-4 Elo which seems in line with the speedup this adds by skipping some move generations.

[bob]

I tried everything up thru 30/30. I found no change from very fast thru that time control. I could run 60/60 but the test turns into a long one since it would run at about 128 games per hour. 1000 games in 8 hours. 10,000 games in 80 hours. So we need about 2 weeks. Don't see the need.

It hurt uniformly at every time control I tried. That was good enough for me. And not only in Crafty. I removed it from Glaurung 2 as well and got the same sort of result. If you believe it helps at even longer time controls, fine by me. But I don't. There are three types of things you can add to a program. Those that help, those that don't change anything at all, and those that hurt. I don't care whether I get burned a little or a lot, I don't want to get burned at all. Neither do I want to give up any skill by using something that appears to not work well enough to even break even.

I am surprised, are you still able to do basic mates after this?

Does the result hold without any EGTB?

I am not using EGTBs on the cluster at all. I haven't used them in several years in fact, not on the cluster, not on ICC, not in the CCT/ACCA events...

The results were consistent for Crafty with/without the verification search (I had not been using it, added 2-3 lines to Crafty's search, and ran it on the cluster. Results were slightly worse (2-3 Elo). I then removed it from Glaurung 2, and it was 2-3 elo better (although this was only against Crafty, since the tests are always Crafty vs everyone.

Made absolutely no difference with respect to finding mates. Never has. No released version of Crafty has ever used the verification search after a null-move fail high. When it was first suggested, I tested and found it no better (I could not do the kind of cluster testing I do today when that paper was first published in the JICCA.) I have tested it a couple of times since, the last time being a few weeks back when I used full cluster runs. Then I could actually measure the 2-3 elo loss this caused.

All of the "good null-move programs" were developed without any verification search at all. It isn't a surprise that it is an overall negative. yes you might pick up on a zugzwang here and there. But as always, what is more important is "what about the general" case?" The general case (to me) says "Don't use it."

[bob]

Forgot the explanation.

In Search() I know whether I have searched a single legal move or not because of the YBW counter "moves_searched". I call NextMove() / etc to return a move, and if moves_searched == 0 (no legal moves searched so far) I simply save this move in a variable "first_tried". When I complete the search, I have two choices. Alpha has been raised (which means this is a PV node since a cutoff would have happened before we ran out of moves, and is caught earlier in the search loop) where I store the current PV move as the hash best move, or if alpha has not been changed, this is an ALL node and I store "first_tried" rather than zero.

The benefit from this is that in Crafty, I try the hash move before generating moves. If I get a cutoff, I avoid the move generation overhead which makes things faster. In an ALL node, there is no best move, but storing the first move tried (likely a capture, possibly a killer, rarely a completely random move) gives me something to try without a move generator call. If you don't use this avoid-the-generator trick, then this is not going to help a bit. In looking at traces, most of the time, the "best move" (stored in an ALL node) is the first capture move I search. In quiet positions, it is quite often a killer move since I try those when there is no capture. In the cases where both killers are illegal, then the best move is just the first move searched in whatever order the move generator produced them.

So a very simple optimization that speeds things up slightly. But any improvement in speed is worthwhile if it doesn't wreck code readability or functionality.