Disable null-move in IID?

[thomasahle]

The most common reason for me not having a hash-move seems to be that at a lower depth my position failed-high on null move.
Hence, if I call

Code: Select all

search(depth - R)

to try and find a new hash-move, it just null moves again, and I don't learn anything.
Meanwhile if I call

Code: Select all

search(depth - R, disable_nullmove=True)

, it seems I nearly always get a move.
Is there any reason not to do this?

[hgm]

If you first tried the null move at maximum depth, and it failed low, that fail low score should be in the TT for the position after that null move. The lower-depth search would probe this, and thus get a fail low on null move as well through a TT hit. And consequently find a real hash move, if there is one to find.

So the problem you describe suggest your TT is not working properly.

[thomasahle]

I see. I guess my TT works a little different from the usual case, since I store the depth as part of the key.
I know this is not considered cool, but I'm keeping my engine free from search-instability for now.

Your answer suggests another issue with my approach though: Even if I disable null-move in the IID search, the null-move fail high from that depth would still be stored in the TT and I would just get that score thrown back in my face. Good thing I also store "can_nullmove" as part of my key

Anyway. I understand now why this is not an issue for other engines. Thanks!

[hgm]

The problem with that design is that you leave all kind of information in the TT that has already been invalidated, and will be constantly misleading the search. The null-move problem you encountered is just one manifestation of that.

[thomasahle]

What do you mean "invalidated"? Just that "you're using depth k information when k+1 information would be better"?

[hgm]

Indeed. If a certain position would have a good (lower bound) score from, say, a d=3 search, but a very bad (upper-bound) score from a d=6 score, the d=6 score would virtually always be correct in concluding this position is bad. With the usual TT design the d=3 result would have been overwritten by the d=6 result. But you leave it in. So if you would encounter that position again through a less efficient path that ate away some depth so that the requested depth is again 3, you will mislead the engine into thinking that the position is good.

[syzygy]

I see. I guess my TT works a little different from the usual case, since I store the depth as part of the key.

Then how do you expect to find a hash move by doing IID? Any move found by IID will be stored with the key for a lower depth.

Or are you looping through all depths and probing the TT for each depth?

[thomasahle]

I see. I guess my TT works a little different from the usual case, since I store the depth as part of the key.

Then how do you expect to find a hash move by doing IID? Any move found by IID will be stored with the key for a lower depth.

Or are you looping through all depths and probing the TT for each depth?

I actually store moves in a separate hash table from scores. This table doesn't use the depth in the key.
This doesn't introduce search instability because the hash-move only affects the order I search thing, but the hypothetical tree being searched is the same.

[thomasahle]

Indeed. If a certain position would have a good (lower bound) score from, say, a d=3 search, but a very bad (upper-bound) score from a d=6 score, the d=6 score would virtually always be correct in concluding this position is bad. With the usual TT design the d=3 result would have been overwritten by the d=6 result. But you leave it in. So if you would encounter that position again through a less efficient path that ate away some depth so that the requested depth is again 3, you will mislead the engine into thinking that the position is good.

You are right of course, but I considered this use of the TT wasn't important enough for me to introduce the instability.
With my TT I still get the benefits of not doing the same work multiple times in ID and with different windows (gammas in MDT).

As I said, I know worrying about search instability is not the popular choice, but I can't be asked to deal with the extra mental and code complexity of it right now.

I'm considering another design though, which would allow me to do get rid of the depth part of the key, while keeping search stability:
At each depth of ID I keep two TTs: tt_old and tt_new. The search only uses tt_old, but writes to tt_new. At the end of the depth, I add everything from tt_new to tt_old.
What do you think? I expect you still think the whole endeavour is pointless...

[syzygy]

I see. I guess my TT works a little different from the usual case, since I store the depth as part of the key.

Then how do you expect to find a hash move by doing IID? Any move found by IID will be stored with the key for a lower depth.

Or are you looping through all depths and probing the TT for each depth?

I actually store moves in a separate hash table from scores. This table doesn't use the depth in the key.

OK, that removes my confusion.