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

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???

But don't you risk to overwrite an existing tt move ? or an existing upper bound type node ?

[Zach Wegner]

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.

As long as you only store real moves that fail high or get exact scores, you shouldn't overwrite them with anything else, or zero them. They should also always be better than no hash move, as even a 1-ply search gives more accurate data than any static criteria. I'm not really sure why your test (keeping an old fail-high instead of zeroing it out) said it was worse, but seems wrong to me. A bug perhaps?

[Uri Blass]

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.

verification search is not crap because without it you can never see some zugzwangs.

If you found that you lose 2-3 elo at fast time control(you probably had no time to run enough games at 120/40 or even 40/40 time control) then I suspect that at slower time control you may earn 2-3 elo.

Uri

[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.

As long as you only store real moves that fail high or get exact scores, you shouldn't overwrite them with anything else, or zero them. They should also always be better than no hash move, as even a 1-ply search gives more accurate data than any static criteria. I'm not really sure why your test (keeping an old fail-high instead of zeroing it out) said it was worse, but seems wrong to me. A bug perhaps?

There I do not agree. If you complete a search with no change to alpha, I found that simply replacing the old hash entry (where the draft was not useful, and which had a real best move recorded) performed better. I don't want to keep an old best move from a shallow search, but continue to fail low for several iterations while this move lives on in the hash table, and keep trying it first each time I get to this position again.

You should test it of course, but when I tried, it was better to just lose the move if there is no current best move, rather than trying to save the old one.

[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.

verification search is not crap because without it you can never see some zugzwangs.

If you found that you lose 2-3 elo at fast time control(you probably had no time to run enough games at 120/40 or even 40/40 time control) then I suspect that at slower time control you may earn 2-3 elo.

Uri

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.

[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???

But don't you risk to overwrite an existing tt move ? or an existing upper bound type node ?

Certainly. I currently have a bucket of 4 entries. I am going to replace one of them no matter what, but the one I replace is the least valuable in terms of depth. You will lose information no matter what you do unless you have infinite memory.

[mcostalba]

Certainly. I currently have a bucket of 4 entries. I am going to replace one of them no matter what, but the one I replace is the least valuable in terms of depth. You will lose information no matter what you do unless you have infinite memory.

I mean for the same position.

If you already have an entry for that node you will overwrite that exact entry, not another one.

So it can end up turning an UPPER BOUND node in a lower bound type

[mcostalba]

Certainly. I currently have a bucket of 4 entries. I am going to replace one of them no matter what, but the one I replace is the least valuable in terms of depth. You will lose information no matter what you do unless you have infinite memory.

I mean for the same position.

If you already have an entry for that node you will overwrite that exact entry, not another one.

So it can end up turning an UPPER BOUND node in a lower bound type

...or even worse IMHO to convert a lower bound node with an high value in a lower bound node with a lesser value and so be less probable to be useful for a possible cut-off when probed again. It is easy IMHO that a null search, although failing high, ends up with a null value that is lower of that obtained by a specific tt move found, in the past, on that same position.

[bob]

Certainly. I currently have a bucket of 4 entries. I am going to replace one of them no matter what, but the one I replace is the least valuable in terms of depth. You will lose information no matter what you do unless you have infinite memory.

I mean for the same position.

If you already have an entry for that node you will overwrite that exact entry, not another one.

So it can end up turning an UPPER BOUND node in a lower bound type

Absolutely. But you can't have it both ways either. Either it is a fail low position or a fail high position. Can't overwrite useful positions of course since you would have already terminated the search had that happened.

[bob]

Certainly. I currently have a bucket of 4 entries. I am going to replace one of them no matter what, but the one I replace is the least valuable in terms of depth. You will lose information no matter what you do unless you have infinite memory.

I mean for the same position.

If you already have an entry for that node you will overwrite that exact entry, not another one.

So it can end up turning an UPPER BOUND node in a lower bound type

...or even worse IMHO to convert a lower bound node with an high value in a lower bound node with a lesser value and so be less probable to be useful for a possible cut-off when probed again. It is easy IMHO that a null search, although failing high, ends up with a null value that is lower of that obtained by a specific tt move found, in the past, on that same position.

Sounds like you are "over-thinking" this. Whatever happened the last time is what I want to happen the next time. I don't want to turn a hash entry into a small stack since for any position you could have failed high or low or gotten an exact score, and for the fail high/low cases, the bounds could be anything. I keep the last one, period, if the signatures match. Otherwise I would not have gotten to this point since had the entry I am overwriting been useful, it would have terminated the search before I got to this point.