Cache over-writing and PV's

[Evert]

You are essentially proposing an hash table only for storing exact entries.

Actually I'm not proposing anything - I'm wondering how much worse such an approach would be.
It's not quite the same as storing only "exact" entries, since you do store the entire path in the entry. If I can retrieve a PV of length N, I don't care if some entry N-k gets trashed.

(1) Performance: at a given (PV) node at depth D you get the PV by searching its best move deep, and store it in the related bucket. But when you have already searched the best move in this node, how do you retrieve the PV coming from the best move node? You should make (again) the best move, probe the hash path, unmake, then stick the best move in front of the retrieved PV, and store again in the hash. Everything starts by simply putting one move on the tips, so the back-up keeps adding moves in front of it, eventually reaching the root.

I guess it's true that for efficiency you can't beat the triangular array. However, you would only need to know two things from the ply+1 search: whether it is a PV node (which you can tell from the score) and the hash key where the full path was stored.

(2) Robustness: how many entries you should have? And what assures you that your probe will get a PV that is what you was really looking for? Indeed you cannot have such guarantee, since the best move is searched first (and stored first), then in the other part of the tree you could overwrite that entry, defating the purpose. So you could even have truncated PV during a backup.

Sure, nothing beats a triangular array for accuracy. Again, I wasn't trying to do that, I was wondering how much worse it would be.

[syzygy]

..The non-clipped part is correct. The clipped part is clipped, so you obviously don't see it. Does not make the clipped part incorrect. ...

SF is no different from other engines in how it searches the leftmost branch of the tree: TT probe to avoid generating moves etc.. etc... How can a (badly) clipped PV retrieved from TT not influence move ordering at ply in which clipping occurs?

Am I saying anywhere that it does not?

If you think SF could be improved by somehow forcing it to keep track of the whole PV, then by all means prepare a patch and try it out.

[syzygy]

What Rein describes is commonly known as 'not doing hash cuts in PV nodes'. No one calls it differently, no one does it any differently.

Except that Rein calls it differently and Arasan does it differently.

[hgm]

Did Rein say how he calls it?

[syzygy]

Question: with the hashed path, do you still need the triangular PV array, or can you get rid of it?

Obviously the risk of losing the PV becomes much higher in that case (and you would always need to get at least a root move from the search), but I'm wondering how often you could just use the "hash path" to extract the PV instead of the triangular array. If it's reliable, it may prompt more people to try it in favour of extracting a PV from the transposition table.

Still needed. It is used to construct the correct PV as you back up. The hashed path stuff starts the PV at a hash hit by adding all the path info that would normally have been backed up from the terminal node we end up at. So both are needed.

But couldn't you just as easily get rid of the triangular array and retrieve the full PV from the separate "hash path" table?

Maybe Crafty does not do what I thought it did. I thought it had a separate, but smaller, hash table just like the tt table that was only used to store results from PV nodes. Those entries would normally not be overwritten, so the full PV could be obtained from it by simply following the stored best moves (and probably verifying that the stored scores match, although this might not go wrong anyway).

You are essentially proposing an hash table only for storing exact entries.

Actually I'm not proposing anything - I'm wondering how much worse such an approach would be.
It's not quite the same as storing only "exact" entries, since you do store the entire path in the entry. If I can retrieve a PV of length N, I don't care if some entry N-k gets trashed.

I would not store the entire path. Chances of entries getting overwritten seem really small unless you use a tiny table. In fact you could use large buckets or some kind of chaining combined with a suitable aging rule to ensure that practically nothing gets overwritten.

[syzygy]

Did Rein say how he calls it?

What you call "not doing hash cuts in PV nodes" with reference to what Rein does, Rein describes as follows:

I do actually take hash cuts in PV nodes, but not indiscriminately but only if the stored exact value exceeds the current search bounds.

[hgm]

Maybe Crafty does not do what I thought it did. I thought it had a separate, but smaller, hash table just like the tt table that was only used to store results from PV nodes. Those entries would normally not be overwritten, so the full PV could be obtained from it by simply following the stored best moves (and probably verifying that the stored scores match, although this might not go wrong anyway).

Indeed, this is not what Crafty does at all.

What it does is store the complete PV with each PV node, rather than just the first move of it. A whole PV of upto 64 moves in a single hash entry.

[bob]

Question: with the hashed path, do you still need the triangular PV array, or can you get rid of it?

Obviously the risk of losing the PV becomes much higher in that case (and you would always need to get at least a root move from the search), but I'm wondering how often you could just use the "hash path" to extract the PV instead of the triangular array. If it's reliable, it may prompt more people to try it in favour of extracting a PV from the transposition table.

Still needed. It is used to construct the correct PV as you back up. The hashed path stuff starts the PV at a hash hit by adding all the path info that would normally have been backed up from the terminal node we end up at. So both are needed.

But couldn't you just as easily get rid of the triangular array and retrieve the full PV from the separate "hash path" table?

Maybe Crafty does not do what I thought it did. I thought it had a separate, but smaller, hash table just like the tt table that was only used to store results from PV nodes. Those entries would normally not be overwritten, so the full PV could be obtained from it by simply following the stored best moves (and probably verifying that the stored scores match, although this might not go wrong anyway).

You are essentially proposing an hash table only for storing exact entries.

Actually I'm not proposing anything - I'm wondering how much worse such an approach would be.
It's not quite the same as storing only "exact" entries, since you do store the entire path in the entry. If I can retrieve a PV of length N, I don't care if some entry N-k gets trashed.

I would not store the entire path. Chances of entries getting overwritten seem really small unless you use a tiny table. In fact you could use large buckets or some kind of chaining combined with a suitable aging rule to ensure that practically nothing gets overwritten.

You have to have the info before you can store it. Where does the PV come from when you store one of the PV table entries (and you are correct, a separate table (different format obviously, but one entry holds the entire PV, not just one move of the PV)). Without the triangular array at any node in the tree, how do I get the PV? With transpositions, how do I get the moves that lead to the transposition table to tie them to the fragment of the PV coming from the path table?

In thinking about it, perhaps it is possible. But I am hesitant to play with something that is working flawlessly. But it provides food for thought.

[syzygy]

Did Rein say how he calls it?

What you call "not doing hash cuts in PV nodes" with reference to what Rein does, Rein describes as follows:

I do actually take hash cuts in PV nodes, but not indiscriminately but only if the stored exact value exceeds the current search bounds.

I have no idea whether "no pv cut" originates from Fruit, but I interpret this post and this post as saying that Fruit at that time, like Arasan now, never takes hash cuts in nodes that are searched with alpha+1 != beta. (I may have incorrectly written alpha +1 == beta earlier in this thread.)

And if we take a look at Senpai:

Code: Select all

      if (sg.trans.retrieve(key, trans_depth, bd.ply(), trans_move, score, flags) && !pv_node) { // assigns trans_move #
         if (flags == score::FLAGS_LOWER && score >= beta)  return score;
         if &#40;flags == score&#58;&#58;FLAGS_UPPER && score <= alpha&#41; return score;
         if &#40;flags == score&#58;&#58;FLAGS_EXACT&#41; return score;
      &#125;

In "expected" PV nodes (alpha+1 != beta) it probes, but only to retrieve a move.

[hgm]

Well, that is very detrimental, agreed? It either wastes a lot of time on a pointless search, which is not going to add any moves to the backed-up PV, or it will embrace a result that is already found to be wrong by a deeper search.