Cache over-writing and PV's

[syzygy]

I don't know if I agree 100%, but I do know that if your dredging your cache for the PV and the time control is long enough that major portions of the cache are over written before the move is made or analysis stopped, the last PV out put is likely to be trashed. This makes it completely unreliable and is a nightmare as far as time is concerned.

Clipping of the PV in SF does not make the non-clipped part unreliable.

I assume that you are stating that the clipped PV leads to the position that produced the current score.

Obviously not.

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.

I'm saying that the fact that it got clipped in the first place is a good indication that the PV is going to change in the near future.

1. That the PV got clipped is NOT an indication that the PV is going to change in the future.
2. The PV IS going to change in the future.

Since they are very likely to change it would be foolish to rely on them. Therefore the PV is unreliable.

Sure...

Rely on them for what?

You have to realise that the value of terminal node of the (non-clipped) PV is based on a call to eval() which is incredibly unreliable.

I expect a PV that doesn't have a bad/losing move at ply 2 after a 45-60 ply search. I have run across this condition on several occasions.

With SF5? I kind of doubt it.

But this issue is a secondary issue. The reason I began saving the PV's in the first place WAS NOT so I could find errors in them. It was the direct result of having the program complete an iteration in just under 4 minutes and then not being able to complete the next iteration in over a hundred hours of analysis. (100*60/4=1500 times as long).

Such things happen. Search is a complicated thing. If you know the perfect solution, by all means contribute to SF development.

You make it sound like the first half of the PV is perfect and everything that is bad in the PV occurs in the second half. I know that's not true and I suspect that you do as well!

Of course I am simplifying. It seems I got the point across, so it worked.

The probability of there being an error in the PV at any particular move is a function of its distance from the root position. The exact nature of this function isn't clear to me since, as yet, I haven't kept track of every error and its position in the PV. If I had then I could plot them and or find an equation that mimics their behavior. While this could still be done it would be time consuming. I didn't really think that that level of proof was required to mention it in passing in this forum. This wasn't the reason I started this thread, but it is a problem none the less.

It is only a problem if you want it to be a problem. It is inherent in how alpha-beta search works.

[syzygy]

So what you are saying is that the 09042014 compile has this issue and If I get a newer version the PV's will always lead to the node that produced the score displayed even if the PV has been clipped. Is that correct?

Yes, compiles from April have this problem. They don't always clip where they should. It is fixed in SF5.

[Evert]

The main point to me is that my "hash path" idea has no measurable cost, it is quite simple to implement, and it can solve the problem period. I still get short PVs because I have a max path length of 128 moves, and with this grafting, one can easily blow that in endgames. I'm not going to increase it further because I don't want to have a 4gb minimum memory size to run the thing.

But the idea really is simple to implement, and has no measurable performance cost. Ergo, why do anything else. I wrote this back when HGM, I and others were talking about the issue and the REALLY ugly solution of "no EXACT matches on PV nodes" which really makes no sense to me at all. Sort of like burning your hand on a hot stove, then reaching the same position a day later and deciding to try it again.

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.

[xmas79]

The main point to me is that my "hash path" idea has no measurable cost, it is quite simple to implement, and it can solve the problem period. I still get short PVs because I have a max path length of 128 moves, and with this grafting, one can easily blow that in endgames. I'm not going to increase it further because I don't want to have a 4gb minimum memory size to run the thing.

But the idea really is simple to implement, and has no measurable performance cost. Ergo, why do anything else. I wrote this back when HGM, I and others were talking about the issue and the REALLY ugly solution of "no EXACT matches on PV nodes" which really makes no sense to me at all. Sort of like burning your hand on a hot stove, then reaching the same position a day later and deciding to try it again.

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.

The use of the hashed path is to help the completion of the truncated PV you get during hash hits on EXACT scores. You cannot get rid of triangular PV array.

[hgm]

Sure you will need it. It is the PVs obtained from the triangular array that go into the PV hash table. The hashing is only to prevent you would lose that info when taking a hash cutoff in the PV.

Basically the whole idea is that a PV node doesn't return just a score and perhaps a move to its caller, but also a PV. So to make a hash cutoff fully mimic the original search you have to hash that PV as well. It is just the triangular-array method made hash proof.

[xmas79]

..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? I mean, if at the end of iteration of depth, say, 15 you get a PV with lenght, say, 8 that means that at ply 8 the engine could not find a TT hash move. So when the iteration 16 starts and gets to the leftmost branch of the tree at ply 8, it doesn't know which move to try... So you can hope that killers captures and so on will produce a good ordering here... From what I learnt the TT content can be anything, so IMHO from this ply on everything is supposed to be searched again with much more effort than a hash probe.

[Evert]

The use of the hashed path is to help the completion of the truncated PV you get during hash hits on EXACT scores. You cannot get rid of triangular PV array.

Why not?
You obtain an exact score for a node (let's say it's a PV node), you store that in the TT and at the same time you store the path that lead to the leaf node. So when you get back to the root, one of the entries in the hash path table should be the full PV, which you've also collected using the triangular array.

Ok, so how do you get the path that you store in the path hash? If you have a triangular array, you can (and would) use that. If you don't - the path hash has the information to tell you what the path below the current node is. All you need to do is retrieve it, stick the best move found in the front, and store the result for the current position.

It's not quite as simple as I thought, but the path hash should contain the path from any PV node to the terminal position - and that's all you need to extract the PV.

[hgm]

Even in your post the term "PV node" can only refer (for the non-mind reader) to a node that at that point in the search appears to be a PV node.

After I have seen the hashed score, it would no longer appear to be a PV node to me. No fortune telling involved. A sufficient-depth hash hit grafts the sub-tree that obtained the hashed result onto the current search tree. So it advances the search to a point where (if the result was a fail) it no longer is a PV node. The fail promoted an existing side branch to the new PV of the tree you have at that point.

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. You are the only one who is making a fuss about it.

[bob]

The main point to me is that my "hash path" idea has no measurable cost, it is quite simple to implement, and it can solve the problem period. I still get short PVs because I have a max path length of 128 moves, and with this grafting, one can easily blow that in endgames. I'm not going to increase it further because I don't want to have a 4gb minimum memory size to run the thing.

But the idea really is simple to implement, and has no measurable performance cost. Ergo, why do anything else. I wrote this back when HGM, I and others were talking about the issue and the REALLY ugly solution of "no EXACT matches on PV nodes" which really makes no sense to me at all. Sort of like burning your hand on a hot stove, then reaching the same position a day later and deciding to try it again.

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.

Don't forget this is where the hashed path comes from in the first place, where it is stored in the path table.

[xmas79]

The use of the hashed path is to help the completion of the truncated PV you get during hash hits on EXACT scores. You cannot get rid of triangular PV array.

Why not?
You obtain an exact score for a node (let's say it's a PV node), you store that in the TT and at the same time you store the path that lead to the leaf node. So when you get back to the root, one of the entries in the hash path table should be the full PV, which you've also collected using the triangular array.

Ok, so how do you get the path that you store in the path hash? If you have a triangular array, you can (and would) use that. If you don't - the path hash has the information to tell you what the path below the current node is. All you need to do is retrieve it, stick the best move found in the front, and store the result for the current position.

It's not quite as simple as I thought, but the path hash should contain the path from any PV node to the terminal position - and that's all you need to extract the PV.

You are essentially proposing an hash table only for storing exact entries. This can be done as you say, but I see few problems:

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

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

(1) is done nicely in the triangular PV, and you don't lose time making/unmaking the move and probing TT.
(2) triangular PV doesn't have that kind of problem, because PV is backed-up togheter with the score.

So I would say is a no-go way.