null move and hash table

[cdani]

Hi!

I see that Stockfish does not store in tt when null move works, but instead senpai it does.

I tried in Andscacs to store in tt and was good for fast games but very bad for slow games.

Has someone a good idea if this must work?

Thanks!

[Ferdy]

Hi!

I see that Stockfish does not store in tt when null move works, but instead senpai it does.

I tried in Andscacs to store in tt and was good for fast games but very bad for slow games.

Has someone a good idea if this must work?

Thanks!

If that is the case turn it off when playing in longer TC .
Engines are not the same, might work for one but not for others. Let's see if team K7 and H4 will give their comments.

[bob]

Hi!

I see that Stockfish does not store in tt when null move works, but instead senpai it does.

I tried in Andscacs to store in tt and was good for fast games but very bad for slow games.

Has someone a good idea if this must work?

Thanks!

Why would it NOT work? The purpose of the TT is to avoid re-searching the same position more than once whenever possible. If null move fails high in "this" position, why would I want to do null move somewhere else, but in exactly the same position, since I already knew it failed high here?

Here's the nitty-gritty. It is easy to screw up most anything in a chess program. And the easiest way to fix the screw up is to just not do that specific thing any more. Some examples:

(1) don't store mate scores, they are problematic. Yes, they need to be adjusted, but storing them works flawlessly.

(2) don't use exact hash matches on PV nodes, because you get short PVs. Fix the short PV issue instead.

the list goes on and on. But done correctly, the tt works. If I failed high at this position at this point in the tree, I should fail high at this position at another point in the tree, or I have a bug.

[hgm]

Be careful: searches can have effects that go beyond the score they return.

Taking a (sufficiently deep) low-failing null-move score from the hash table without searching does sound like a time saver. But had you done the search, you would have found the refutation move, and that move might have been promoted to killer, (and would have affected history). So that in the first real move you search, you would search the killer early, while otherwise you might have been searching some irrelevant killer still hanging there from an unrelated branch.

So the possible 'fix' might require something like copying the hash move on a fail-high hash cut to the killer table. That would help when you get the hash hit in the node directly after null move. If you already decide to hash-prune earlier, e.g. because you somehow store the info that the null-move failed low in the hash entry of the move that made it, so that it can refrain from trying it on a revisit, it is more difficult to fix. Because then you have no idea which move refuted the null move. So to fix it might require you to store the null-move refutation (for copying back to the killer table) in the hash entry for the node that made the null move. I.e. put a second hash move in there, rather than just a bit flag that told you the null move failed low. Which of course has a price, in terms of hash density.

[bob]

Be careful: searches can have effects that go beyond the score they return.

Taking a (sufficiently deep) low-failing null-move score from the hash table without searching does sound like a time saver. But had you done the search, you would have found the refutation move, and that move might have been promoted to killer, (and would have affected history). So that in the first real move you search, you would search the killer early, while otherwise you might have been searching some irrelevant killer still hanging there from an unrelated branch.

So the possible 'fix' might require something like copying the hash move on a fail-high hash cut to the killer table. That would help when you get the hash hit in the node directly after null move. If you already decide to hash-prune earlier, e.g. because you somehow store the info that the null-move failed low in the hash entry of the move that made it, so that it can refrain from trying it on a revisit, it is more difficult to fix. Because then you have no idea which move refuted the null move. So to fix it might require you to store the null-move refutation (for copying back to the killer table) in the hash entry for the node that made the null move. I.e. put a second hash move in there, rather than just a bit flag that told you the null move failed low. Which of course has a price, in terms of hash density.

I don't quite follow. In Crafty, if NM fails high, I store the entry and return. If it fails low, I do not store anything at all, and continue on to do a normal search here.

If you are talking about what goes on BELOW the NM search, I suppose anything can affect move ordering down there anyway. But those ttable entries should not affect anything below a non-null-move search since the draft would be insufficient.

[cdani]

If that is the case turn it off when playing in longer TC .

It's a possibility, but I prefer to try to understand what happens.

Here's the nitty-gritty. It is easy to screw up most anything in a chess program. And the easiest way to fix the screw up is to just not do that specific thing any more.

Of course. I also say the same on non related things to other people. As you say, fix the bug is better.
I asked the question with only a few words just to leave it very open.

Why would it NOT work? The purpose of the TT is to avoid re-searching the same position more than once whenever possible. If null move fails high in "this" position, why would I want to do null move somewhere else, but in exactly the same position, since I already knew it failed high here?

I supposed also it's like this, but sometimes I prefer to ask. May be there is something difficult under this idea that, nothing less than stockfish team, don't use it.

I will continue investigating it.
Thanks!

[tpetzke]

Hi Daniel,

like HGM already said, doing the Null Move can have side effects that might be beneficial even if the null move fails low.

Consider the idea of Internal Iterative Deepening which looks like a useless overhead but overall is useful as it orders your tree a bit better.

Also if you have a position and the null move failed low then it is the combination of position and bounds that made it fail low. If you renter the same position with different bounds you can have a different experience. But I guess you are aware of that.

Thomas

[cdani]

Hi Daniel,
Consider the idea of Internal Iterative Deepening which looks like a useless overhead but overall is useful as it orders your tree a bit better.

Yes, I use it to some extent but sure it can be improved a lot.

Also if you have a position and the null move failed low then it is the combination of position and bounds that made it fail low. If you renter the same position with different bounds you can have a different experience. But I guess you are aware of that.

Thanks for your advice. Anyway I decided to rewrite all the alpha_beta stuff. It's getting too dirty after so many changes.

[lucasart]

like HGM already said, doing the Null Move can have side effects that might be beneficial even if the null move fails low.

That is a far fetched, and far too vague explanation. The reason why storing null search result is wrong is very simple, IMO:
* you do a null search (non pv node) and get a fail low or a fail high.
* next time you research that node, with the same zero window, you play the null move and get immediate TT pruning in the child node (unless entry was overwritten).
* besides, the child node TT entry is more valuable because it has a non null move. It can be used for move ordering. so you dont want some silly null moves entries overwriting proper entries in general.

In fact, I conjecture that storing null search results in TT is harmful when you test with a strong hash pressure. You just add redundant info in the TT which is both a slowdown and a waste of TT memory. No surprise it doesnt scale at LTC where the hash pressure is larger.

Testing that stuff is not about tc but about hash pressure. TT related stuff should be tested with loose or strong hash pressure, no need to waste time with LTC if you have limited resources.

[tpetzke]

It actually never occurred to me that you store the result of a null move in the TT. I was referring to the case where you store just a flag that the null move in that node will likely fail low (because of threats present) along with the usual information of that node in the TT. And here it might be sometimes more beneficial to do the null move even if you know it fails low because you cause side effects that might be beneficial (like tree ordering or getting a threat move you can use)

But surprisingly senpai actually really stores the null move fail high result. I don't do it in iCE. I haven't tested it yet and before making statements whether it works I should. But it is currently not on my todo list.