Store in TT after null search fails high

[mcostalba]

Today, in the main forum, there has been a marathon thread about an (almost sure) Rybka's reverse engineered engine called Ippolit.

Out of curiosity I looked at the sources, well the source, it is a single, horrid to read, file.

I found an idea I never saw before.

When null search fails high we simply return beta, eventually after zugzwang verification search.

In this case, before to return, the null value (the result of the null search) is saved in the TT table as a LOWER BOUND type node (as it should be) but with NO associated move (as normally happens only for upper bound nodes).

I think the logic makes sense: null search is just a normal search but on an undefined move, on an absolutly dumb move, if we anyhow fail high it makes sense to store we are in a cut-off type node and because we don't have searched any specific move we store MOVE_NONE in the hash table.

Does anyone have ever heard of such idea before ? For me it is new, but I am not in this field from a long ago

[Gian-Carlo Pascutto]

I don't think this is a good idea. If you had a best move, you've now just overwritten it with nothing.

I keep the best move if I had one, and if I don't have one, I don't store a best move.

This seems like the most logical thing to do.

[mcostalba]

I don't think this is a good idea. If you had a best move, you've now just overwritten it with nothing.

I keep the best move if I had one, and if I don't have one, I don't store a best move.

This seems like the most logical thing to do.

Sorry I forgot to add that the saving is done only if there isn't an already exsisting tt move.

And this is the only condition BTW, for instance if the node was already marked as UPPER BOUND type, now will be overwritten.

The condition is "not an already exsisting tt move", not "not an already exsisting TT entry".

[Zach Wegner]

I don't think this is a good idea. If you had a best move, you've now just overwritten it with nothing.

I keep the best move if I had one, and if I don't have one, I don't store a best move.

This seems like the most logical thing to do.

I agree, I don't see why one would want to overwrite a good move in case null move doesn't fail high next time.

I would file this under "obvious". Even the lowly ZCT has had this for as long as I can remember. But for some reason it's commented out in the code now, so it overwrites the old move with the null move.

[Mincho Georgiev]

I tried the exact same thing while ago with absolutely no success.
I was just drawn by a simple logic back then, never had seen such an implementation before i tried it. As Bob often say, it doesn't hurt, but it doesn't help either. Which is more like hurting performance than do any good just because of it's presence in the code. (IMHO)

[Edsel Apostol]

Today, in the main forum, there has been a marathon thread about an (almost sure) Rybka's reverse engineered engine called Ippolit.

Out of curiosity I looked at the sources, well the source, it is a single, horrid to read, file.

I found an idea I never saw before.

When null search fails high we simply return beta, eventually after zugzwang verification search.

In this case, before to return, the null value (the result of the null search) is saved in the TT table as a LOWER BOUND type node (as it should be) but with NO associated move (as normally happens only for upper bound nodes).

I think the logic makes sense: null search is just a normal search but on an undefined move, on an absolutly dumb move, if we anyhow fail high it makes sense to store we are in a cut-off type node and because we don't have searched any specific move we store MOVE_NONE in the hash table.

Does anyone have ever heard of such idea before ? For me it is new, but I am not in this field from a long ago

I think Fruit 2.1 and family is already doing that. I am not sure if it is good or not. For example in Fruit after the verification search, it still stores the result in the hash table, meaning it overwrites the previously stored data in the verification search that has depth-5 with depth only. I think it is not accurate.

As for the empty move, Fruit never store it so the hash move in that specific entry is still intact.

[mcostalba]

I think it is not accurate.

Yes, I would agree, after verification search you go almost for sure to overwrite something good, but at low depths verification is not done.

I don't know if in these cases it is better to use the aggressive (!ttMove) as condition, and so overwrite an exsisting entry of type UPPER BOUND, or use the more cautions (!tte), i.e. when the hash entry is empty anyway.

[bob]

Today, in the main forum, there has been a marathon thread about an (almost sure) Rybka's reverse engineered engine called Ippolit.

Out of curiosity I looked at the sources, well the source, it is a single, horrid to read, file.

I found an idea I never saw before.

When null search fails high we simply return beta, eventually after zugzwang verification search.

In this case, before to return, the null value (the result of the null search) is saved in the TT table as a LOWER BOUND type node (as it should be) but with NO associated move (as normally happens only for upper bound nodes).

I think the logic makes sense: null search is just a normal search but on an undefined move, on an absolutly dumb move, if we anyhow fail high it makes sense to store we are in a cut-off type node and because we don't have searched any specific move we store MOVE_NONE in the hash table.

Does anyone have ever heard of such idea before ? For me it is new, but I am not in this field from a long ago

This has been in Crafty for 15 years. In Cray Blitz prior to that. It is not new, and makes perfect sense. If a null-move search fails high in position P, the next time you encounter position P why would it not fail high there as well, assuming the depth is useful???

[bob]

I don't think this is a good idea. If you had a best move, you've now just overwritten it with nothing.

I keep the best move if I had one, and if I don't have one, I don't store a best move.

This seems like the most logical thing to do.

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.

I suspect this is because the normal move ordering is better than a move left over from a shallower search, but am not sure.

[bob]

Today, in the main forum, there has been a marathon thread about an (almost sure) Rybka's reverse engineered engine called Ippolit.

Out of curiosity I looked at the sources, well the source, it is a single, horrid to read, file.

I found an idea I never saw before.

When null search fails high we simply return beta, eventually after zugzwang verification search.

In this case, before to return, the null value (the result of the null search) is saved in the TT table as a LOWER BOUND type node (as it should be) but with NO associated move (as normally happens only for upper bound nodes).

I think the logic makes sense: null search is just a normal search but on an undefined move, on an absolutly dumb move, if we anyhow fail high it makes sense to store we are in a cut-off type node and because we don't have searched any specific move we store MOVE_NONE in the hash table.

Does anyone have ever heard of such idea before ? For me it is new, but I am not in this field from a long ago

I think Fruit 2.1 and family is already doing that. I am not sure if it is good or not. For example in Fruit after the verification search, it still stores the result in the hash table, meaning it overwrites the previously stored data in the verification search that has depth-5 with depth only. I think it is not accurate.

As for the empty move, Fruit never store it so the hash move in that specific entry is still intact.

Personally, you can throw out the verification search crap as well. I tested it in Crafty on the cluster. Zero improvement. I removed it from Fruit, Glaurung, and zero harm. In fact, removing it actually gains 2-3 Elo if you run enough games to measure to that level of accuracy.

I posted this result 3-4 weeks ago here.