Cache over-writing and PV's

[syzygy]

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.

You might be right, but maybe there is more to it. The reason for avoiding hash cuts altogether is to avoid PV clipping and to improve search stability. Of course the question is whether it does improve stability (in a manner that gains the engine anything).

But how common are hash cuts in PV nodes anyway? The PV from the previous iteration is searched first. In those nodes you're unlikely to find any tt entries with sufficient depth to allow a hash cut. So we're talking about nodes that become part of the PV after a (non-first) move from the PV branch failed high. When resolving the new PV the difference is made (for good or for worse). Maybe it does help if there is a significant difference in how the search reduces/extends PV nodes and non-PV nodes...

[bob]

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.

That is simply ignoring EXACT matches. Nothing new at all, and while it avoids the EXACT PV truncation problem, it still has the same problem with bogus moves particularly near the end of the PV...

Ignoring hash entries with EXACT scores when the score lies between current alpha/beta bounds seems like a big waste, efficiency-wise. But to each his own.

[bob]

And what they do is known as 'not taking hash cutoffs in PV nodes'. And the price is that you lose the possibility to look over the horizon by grafting.

I once did the following: after I returned from the search (with my triangular PV), I extended the PV with whatever the hashtable was able to graft onto it. This is something like a poor-man's version of Bob's path hash.

Worked ok, but doesn't really solve the problem it's meant to alleviate, so I eventually got rid of it.

Crafty did that for years. And you get some nonsensical moves on the end of the PV to boot, just like anybody that uses the hash table to produce the PV.

And actually, the code to do that is more complicated than the code to save/graft the PV.

[Zenmastur]

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.

1.) Is your claim. My claim, which is based solely on what I have witnessed it do time and time again, is that when it starts clipping the PV it's going to change.

2.) "The PV IS going to change in the future." is flat out wrong. The trivial case is when only one line of play leads to mate and all other lines lose. Once it finds this line of play it will never leave it unless there is a bug. There are, of course, a huge number of other possibilities which lead to the same behavior by the engine. I'm not going to waste a bunch of time trying to list all possibilities, one only needs to engage one's brain to envision what the other possibilities are. e.g. huge material advantage vice huge material loss etc.

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?

To make your next move among other things.

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'm well aware that eval() is unreliable. If it were reliable there wouldn't be any need to conduct an extensive search. You could simply produce all legal moves, make each one, call eval(), and select the one with the best score. Since we all know that this algorithm doesn't work well, we all know that eval() is unreliable even if we haven't thought about it explicitly.

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.

Why do you doubt it?

Do you believe that SF5 is perfect?

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.

I don't have the "perfect" solution. I don't even have "a" solution. What I do have is a few leads.

I'm still considering if I should embark on another chess programming venture. I have lots of ideas that I didn't get to try out the last time I did this. My problem is this, my health is not very good. I do plan to do something, I just haven't determined what that is yet. I would prefer something that I have a reasonable chance of completing. So for the time being, open ended projects are off the table for me.

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.

There is nothing inherent in the alpha-beta process that prescribes that each ply deeper into the search must be searched to a depth one ply less than the last. i.e. like this:

Example 1:
9-8-7-6-5-4-3-2-1

There is no reason that something like this couldn't be done:

Example 2:
9-8-7-6-5-5-5-4-3-2-1

or this

Example 3:
9-8-7-6-5-4-3-3-3-3-3-2-1

There are advantages to the alternatives. One is time usage. e.g. if a 1 ply search requires one unit of time and each addition ply of depth doubles the search time then example 1 requires 256 units of time. Example 2 requires 288 units of time and example three requires 272 units of time. Example 2 gets its search horizon extended by two plies and example 3 gets its search horizon extended 4 plies. Both use considerably less time than an 11-ply search (1024 units of time) or a 13-ply search (4096 units of time). Neither is as good as their more traditional counter parts of the same length but they are much better than a straight 9-ply search.

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.

This is not a compile from April, the date is Sept. 4 2014. I downloaded it on Sept. 12. Since Sept 12, it's the only version of stockfish I have used.

Regards,

Forrest

[bob]

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.

1.) Is your claim. My claim, which is based solely on what I have witnessed it do time and time again, is that when it starts clipping the PV it's going to change.

2.) "The PV IS going to change in the future." is flat out wrong. The trivial case is when only one line of play leads to mate and all other lines lose. Once it finds this line of play it will never leave it unless there is a bug. There are, of course, a huge number of other possibilities which lead to the same behavior by the engine. I'm not going to waste a bunch of time trying to list all possibilities, one only needs to engage one's brain to envision what the other possibilities are. e.g. huge material advantage vice huge material loss etc.

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?

To make your next move among other things.

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'm well aware that eval() is unreliable. If it were reliable there wouldn't be any need to conduct an extensive search. You could simply produce all legal moves, make each one, call eval(), and select the one with the best score. Since we all know that this algorithm doesn't work well, we all know that eval() is unreliable even if we haven't thought about it explicitly.

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.

Why do you doubt it?

Do you believe that SF5 is perfect?

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.

I don't have the "perfect" solution. I don't even have "a" solution. What I do have is a few leads.

I'm still considering if I should embark on another chess programming venture. I have lots of ideas that I didn't get to try out the last time I did this. My problem is this, my health is not very good. I do plan to do something, I just haven't determined what that is yet. I would prefer something that I have a reasonable chance of completing. So for the time being, open ended projects are off the table for me.

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.

There is nothing inherent in the alpha-beta process that prescribes that each ply deeper into the search must be searched to a depth one ply less than the last. i.e. like this:

Example 1:
9-8-7-6-5-4-3-2-1

There is no reason that something like this couldn't be done:

Example 2:
9-8-7-6-5-5-5-4-3-2-1

or this

Example 3:
9-8-7-6-5-4-3-3-3-3-3-2-1

There are advantages to the alternatives. One is time usage. e.g. if a 1 ply search requires one unit of time and each addition ply of depth doubles the search time then example 1 requires 256 units of time. Example 2 requires 288 units of time and example three requires 272 units of time. Example 2 gets its search horizon extended by two plies and example 3 gets its search horizon extended 4 plies. Both use considerably less time than an 11-ply search (1024 units of time) or a 13-ply search (4096 units of time). Neither is as good as their more traditional counter parts of the same length but they are much better than a straight 9-ply search.

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.

This is not a compile from April, the date is Sept. 4 2014. I downloaded it on Sept. 12. Since Sept 12, it's the only version of stockfish I have used.

Regards,

Forrest

The depth examples you gave above are actually not unusual. I've been debugging an extension idea in Crafty, and during debugging I have been printing out lots of stuff and I have seen the depth go unchanged for 5-6 plies on several occasions. You also will see the depth drop by far more than 1 for several iterations as reductions are applied.

[Zenmastur]

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.

1.) Is your claim. My claim, which is based solely on what I have witnessed it do time and time again, is that when it starts clipping the PV it's going to change.

2.) "The PV IS going to change in the future." is flat out wrong. The trivial case is when only one line of play leads to mate and all other lines lose. Once it finds this line of play it will never leave it unless there is a bug. There are, of course, a huge number of other possibilities which lead to the same behavior by the engine. I'm not going to waste a bunch of time trying to list all possibilities, one only needs to engage one's brain to envision what the other possibilities are. e.g. huge material advantage vice huge material loss etc.

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?

To make your next move among other things.

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'm well aware that eval() is unreliable. If it were reliable there wouldn't be any need to conduct an extensive search. You could simply produce all legal moves, make each one, call eval(), and select the one with the best score. Since we all know that this algorithm doesn't work well, we all know that eval() is unreliable even if we haven't thought about it explicitly.

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.

Why do you doubt it?

Do you believe that SF5 is perfect?

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.

I don't have the "perfect" solution. I don't even have "a" solution. What I do have is a few leads.

I'm still considering if I should embark on another chess programming venture. I have lots of ideas that I didn't get to try out the last time I did this. My problem is this, my health is not very good. I do plan to do something, I just haven't determined what that is yet. I would prefer something that I have a reasonable chance of completing. So for the time being, open ended projects are off the table for me.

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.

There is nothing inherent in the alpha-beta process that prescribes that each ply deeper into the search must be searched to a depth one ply less than the last. i.e. like this:

Example 1:
9-8-7-6-5-4-3-2-1

There is no reason that something like this couldn't be done:

Example 2:
9-8-7-6-5-5-5-4-3-2-1

or this

Example 3:
9-8-7-6-5-4-3-3-3-3-3-2-1

There are advantages to the alternatives. One is time usage. e.g. if a 1 ply search requires one unit of time and each addition ply of depth doubles the search time then example 1 requires 256 units of time. Example 2 requires 288 units of time and example three requires 272 units of time. Example 2 gets its search horizon extended by two plies and example 3 gets its search horizon extended 4 plies. Both use considerably less time than an 11-ply search (1024 units of time) or a 13-ply search (4096 units of time). Neither is as good as their more traditional counter parts of the same length but they are much better than a straight 9-ply search.

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.

This is not a compile from April, the date is Sept. 4 2014. I downloaded it on Sept. 12. Since Sept 12, it's the only version of stockfish I have used.

Regards,

Forrest

The depth examples you gave above are actually not unusual. I've been debugging an extension idea in Crafty, and during debugging I have been printing out lots of stuff and I have seen the depth go unchanged for 5-6 plies on several occasions. You also will see the depth drop by far more than 1 for several iterations as reductions are applied.

I think the difference is that the extensions and reductions will be applied on top of example 2 or 3 ( or similar structures) vice example 1.

Regards,

Forrest

[bob]

There are advantages to the alternatives. One is time usage. e.g. if a 1 ply search requires one unit of time and each addition ply of depth doubles the search time then example 1 requires 256 units of time. Example 2 requires 288 units of time and example three requires 272 units of time. Example 2 gets its search horizon extended by two plies and example 3 gets its search horizon extended 4 plies. Both use considerably less time than an 11-ply search (1024 units of time) or a 13-ply search (4096 units of time). Neither is as good as their more traditional counter parts of the same length but they are much better than a straight 9-ply search.

I am not quite sure I follow. Example 1 goes 8 ply deep. 2^8 = 256 so we agree there. But example 2 goes 2 plies deeper. By my calculations, that turns into 1024 units of time, not the 288 you mentioned, so perhaps I don't quite follow what you mean with the consecutive same depths (if that is what those numbers represent).

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

Am I saying anywhere that it does not?

You actually didn't say, but it also seemed to me that in your opinion the truncated PV was fine... What do you mean then with "Does not make the clipped part incorrect"?

I was only pointing out another reason why the truncated PV is actually a problem... No need to submit a patch at all. I already know it SF would be a better engine with complete PVs.

[xmas79]

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.

My feelings are that table size depends on search time. More the time you give search, bigger the table. So how to tune?

And this is not going to work anyway with big search times, because the tree is internally full of "sub PVs" which are removed naturally during back-ups (eg a searchat depth 30 contains a lot of PVs at ply 16, and only one will survive the back-up at ply 15. Then consider that lot of PVs at ply 15, and only one surviving at ply 14 and so on...). So you are going to store a lot of PVs in the hash, and as depth goes on, your chances of overwriting entries gets bigger and bigger. Triangular PV method removes them "internally", so no problem at all.

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

You actually didn't say, but it also seemed to me that in your opinion the truncated PV was fine... What do you mean then with "Does not make the clipped part incorrect"?

Indeed I did not say it, so I really wonder why you quoted that specific part of what I did write and did (apparently not) respond to it. Whether what SF is doing is fine or not I will leave for you to decide. Again, feel free to improve it in terms of Elo (as you were worrying about clipping affecting its strength).

What I mean by not incorrect I have explained. In any event I only see one possible reasonable explanation for what it means for a (clipped) PV to be "correct".