Cache over-writing and PV's

[bob]

Here is where _I_ came in:

I never replied to _that_ post, so you are confused.

You should learn to read what you are replying to before reflexively replying.

You should try it. The thread had a clear starting point. Then it digressed to incomplete PVs vs Hash overwrites. What you replied to I have no idea any longer since your comments relate to neither.

[bob]

Onno's definition is precise and useful in the context of PVS enhanced alpha-beta.

If someone wants to say "Type-1 node by Knuth's definition in the context of plain alpha-beta", they can say that

Onno's definition is indeed very precise and useful.

Knuth's definition of type 1/2/3 nodes obviously served Knuth's purpose, which was to prove something about the alpha-beta algorithm, just fine. But, unless one applies Onno's common sense approach, Knuth's definition is completely useless for describing an actual search algorithm. For starters, Knuth is only classifying the nodes of a minimal tree and chess programs can't assume they are only searching the minimal tree.

Marsland and Popowich, who introduced the terms PV, CUT and ALL nodes, are discussing an actual search algorithm, so are in fact applying common sense and talking about "expected" type 1/2/3 nodes. When they talk about "PV splitting" they don't mean to limit splitting to type 1 nodes of the minimal tree which is only known after the search is done.

Actually PV splitting meant EXACTLY that. Assuming you search left to right, PV split ONLY splits along the left-most branch of the tree. Which both assumes that move ordering is perfect AND it is based on the YBW concept since the first branch from each node down the left-hand side is searched sequentially, and the rest are searched in parallel. Several of us used this in the late 70's and early 80's, but it doesn't scale very well at all with > 4 processors...

The point is that, in HGM's terminology, a PV node (say a node with beta == alpha+1) that fails high is not a PV node. It is/was only an "expected PV node". But PVSplit obviously still splits in such nodes and all papers refer to them as "PV nodes". Real trees are not perfectly ordered. PVSplit is/was used to search real trees. Likewise, it would have been silly if your DTS paper had consistently referred to "expected" PV, CUT, ALL nodes.

Before you start protesting something, I'll just note we are likely in complete agreement on this point.

You are mixing apples and oranges. PV split simply takes the principle variation from the PREVIOUS iteration, searches those moves first along the left-hand side of the tree, and starting at the tip, works its way backward splitting at each node along that left-hand edge until it reaches the root and splits there. At that point, splitting is OVER until the next iteration is started. For fixed depth, PV split would split N times only on a depth N search.

I will have to re-read that paper, which I think is publicly available on my web page. I thought that I was pretty careful with the terminology, but perhaps I was not. Without the term "expected" the term "PV node" becomes ambiguous, however, except when move ordering is perfect.

[syzygy]

What you replied to I have no idea any longer since your comments relate to neither.

I quote for a reason. I am not going to explain to you the purpose of quoting.

[syzygy]

You are mixing apples and oranges. PV split simply takes the principle variation from the PREVIOUS iteration, searches those moves first along the left-hand side of the tree, and starting at the tip, works its way backward splitting at each node along that left-hand edge until it reaches the root and splits there. At that point, splitting is OVER until the next iteration is started. For fixed depth, PV split would split N times only on a depth N search.

So what is it now.

Does PVSplit split at "PV nodes"?

Or does PVSplit split at "expected PV nodes"?

The first answer you gave:

Marsland and Popowich, who introduced the terms PV, CUT and ALL nodes, are discussing an actual search algorithm, so are in fact applying common sense and talking about "expected" type 1/2/3 nodes. When they talk about "PV splitting" they don't mean to limit splitting to type 1 nodes of the minimal tree which is only known after the search is done.

Actually PV splitting meant EXACTLY that.

Exactly the type 1 nodes of the minimal tree? So "PV nodes" / "type 1 nodes" and not just "expected PV nodes" / "expected type 1 nodes"?

[bob]

You are mixing apples and oranges. PV split simply takes the principle variation from the PREVIOUS iteration, searches those moves first along the left-hand side of the tree, and starting at the tip, works its way backward splitting at each node along that left-hand edge until it reaches the root and splits there. At that point, splitting is OVER until the next iteration is started. For fixed depth, PV split would split N times only on a depth N search.

So what is it now.

Does PVSplit split at "PV nodes"?

Or does PVSplit split at "expected PV nodes"?

The first answer you gave:

Marsland and Popowich, who introduced the terms PV, CUT and ALL nodes, are discussing an actual search algorithm, so are in fact applying common sense and talking about "expected" type 1/2/3 nodes. When they talk about "PV splitting" they don't mean to limit splitting to type 1 nodes of the minimal tree which is only known after the search is done.

Actually PV splitting meant EXACTLY that.

Exactly the type 1 nodes of the minimal tree? So "PV nodes" / "type 1 nodes" and not just "expected PV nodes" / "expected type 1 nodes"?

It splits at PV nodes, as defined by Knuth/Moore/etc, whether the tree is perfectly ordered or not does not come into play with PV split. It simply assumes perfect ordering. As I said, the left-hand side of the tree ONLY, assuming depth-first alpha/beta searching left to right. It splits NOWHERE else. If you search to depth D, you have exactly D split points, no more. Down the left-hand edge of that tree.

That was the flaw with PV split (called PVS at the time, but not the same as what we call PVS today, completely different topic) that led me to first develop something I called "EPVS" (E for enhanced) as there were too many times when processors were sitting idle while we were on the last branch of one of those PV nodes with just one processor busy working.

DTS came from the shortcomings of EPVS, and let me split anywhere, any time.

One can argue the terminology forever. but knuth/moore were pretty precise in their definitions. Of course when move ordering is wrong, the left-hand edge no longer contains all of the actual PV nodes, if you want to use the definition of "PV = any node where alpha != beta - 1". But in their definition, the ONLY PV node they defined was that the ROOT node is a PV node, and the first successor of any PV node is also a PV node. No other nodes at all would be called PV by their definition.

[syzygy]

You are mixing apples and oranges. PV split simply takes the principle variation from the PREVIOUS iteration, searches those moves first along the left-hand side of the tree, and starting at the tip, works its way backward splitting at each node along that left-hand edge until it reaches the root and splits there. At that point, splitting is OVER until the next iteration is started. For fixed depth, PV split would split N times only on a depth N search.

So what is it now.

Does PVSplit split at "PV nodes"?

Or does PVSplit split at "expected PV nodes"?

The first answer you gave:

Marsland and Popowich, who introduced the terms PV, CUT and ALL nodes, are discussing an actual search algorithm, so are in fact applying common sense and talking about "expected" type 1/2/3 nodes. When they talk about "PV splitting" they don't mean to limit splitting to type 1 nodes of the minimal tree which is only known after the search is done.

Actually PV splitting meant EXACTLY that.

Exactly the type 1 nodes of the minimal tree? So "PV nodes" / "type 1 nodes" and not just "expected PV nodes" / "expected type 1 nodes"?

It splits at PV nodes, as defined by Knuth/Moore/etc, whether the tree is perfectly ordered or not does not come into play with PV split. It simply assumes perfect ordering.

Some of those "PV nodes" turn out not to be type 1 nodes of the minimal tree. Move ordering is not perfect.

You sure you don't mean "expected type 1 nodes"? (Yes, those on the left-hand side.)

[bob]

You are mixing apples and oranges. PV split simply takes the principle variation from the PREVIOUS iteration, searches those moves first along the left-hand side of the tree, and starting at the tip, works its way backward splitting at each node along that left-hand edge until it reaches the root and splits there. At that point, splitting is OVER until the next iteration is started. For fixed depth, PV split would split N times only on a depth N search.

So what is it now.

Does PVSplit split at "PV nodes"?

Or does PVSplit split at "expected PV nodes"?

The first answer you gave:

Marsland and Popowich, who introduced the terms PV, CUT and ALL nodes, are discussing an actual search algorithm, so are in fact applying common sense and talking about "expected" type 1/2/3 nodes. When they talk about "PV splitting" they don't mean to limit splitting to type 1 nodes of the minimal tree which is only known after the search is done.

Actually PV splitting meant EXACTLY that.

Exactly the type 1 nodes of the minimal tree? So "PV nodes" / "type 1 nodes" and not just "expected PV nodes" / "expected type 1 nodes"?

It splits at PV nodes, as defined by Knuth/Moore/etc, whether the tree is perfectly ordered or not does not come into play with PV split. It simply assumes perfect ordering.

Some of those "PV nodes" turn out not to be type 1 nodes of the minimal tree. Move ordering is not perfect.

You sure you don't mean "expected type 1 nodes"? (Yes, those on the left-hand side.)

Again, two different definitions.

Knuth/Moore/etc discussed only the perfect ordering situation. And for PV split, it worked just as I mentioned. One thread searches all the way down to the first tip encountered, and then splits. Then backs up one ply and splits, then backs up one ply and splits, until it backs up to the root and splits. So it ONLY splits down the left-hand side, which is simple, and works reasonably for 2-4 threads. Beyond that, not so good. Beyond 8, about the best you can hope for is a speedup of 3-4x, if you are lucky and get really good move ordering.

as far as "expected type 1 nodes" go, I suppose you could define that any way you like, since Knuth/Moore did not use such a term. The simple "root is type 1, first successor of a type-1 is type-1 is all they gave.

I would probably define PV node a bit differently myself, but that is a different issue. Would be nice if someone wrote a NEW paper on contemporary alpha/beta and came up with a better terminology that closes the loopholes...

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

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. Since they are very likely to change it would be foolish to rely on them. Therefore the PV is unreliable.

I save the PV's and then use the engine to search each and every move in it to ferret out all the trash moves. I can't ever recall a case where the PV was accurate. I always find errors and the evaluations always change.

Sure, but what do you expect?

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.

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). I actually thought Arena had frozen. It hadn't. SF was still calculating but hadn't generated any output for over two days. To get around this problem I appended the PV to the game and began analyzing it. I figured that it would be a long and difficult analysis. It wasn't. It went very rapidly and in less than an hour I had a usable line of play.

Since then I run into these positions all the time, although not quite as extreme as this case. To speed things up when this happens I began appending the PV's and analyzing them as a matter of course. When I started doing this on a regular basis is when I started noticing the rather large number of errors in the PV's. But like I said, this is a secondary issue, although the two could be related. I.E. the inability to find the errors in the PV on it's own could be causing the excessive time usage on an iteration, but I don't know for sure that this is the case.

If the root position is searched to depth 40, then the position after 20 half moves was searched only to depth 20. That's just how things work.

Even if you get SF (or any other engine) to return a long PV, putting a lot of trust in the second half of the PV isn't very wise.

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!

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.

I also know that making each move in the PV the root position in a search has an almost magical ability to make the engine find errors with out extensive searching. i.e. the number of errors found is disproportionate to the time spent finding them if the erroneous move is at ply one in a search.

Note that the OP is complaining about the moves of "perfectly accurate" PVs. (Those output by somewhat recent versions of SF are accurate in so far as they are not clipped.)

Somewhat more recent?

I'll change versions if it fixes the problem. I just don't like changing with every compile and I won't change at all (except for critical fixes) after I start a project with a version because it can waste a huge amount of time. 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?

The main issue of the program vacillating for long periods of time due to insufficient cache, still appears to be a problem, although I found a temporary work around until I have more time to spend on it.

The last issue:

Stockfish, on occasion, will take disproportionately large amounts of time to complete an iteration as compared to previous iterations.

If you walk along this PV while letting the engine search, then obviously the score keeps changing as the engine is searching deeper and deeper. This is what the OP must be talking about in the part I am quoting, unless he is not using SF5 or something more recent.

This IS NOT what the OP is talking about.

Your first statement isn't true. If you almost never do deep searches then you will almost never see a PV that doesn't change even at significant depth. I see them all the time. I've seen PV's that wont change a single move in the PV with large amounts of additional search. i.e. 20 plies deeper. These PV's do exist contrary to what you seem to think. These are not the ones that concern me however.

If you always do shallow searches you should expect the PV to change almost at random even within a single iteration. This means something. It means the program has no clue as to what the best line of play is. When these random changes to the PV stop occurring, it also means something. It means the program "might" have a clue about the position. I prefer the later type myself.

What I don't like is a PV that's 50 or more plies long that has an inaccurate move near the root. Maybe that's all the program is capable of. I don't know. But like I said, my real interest is in why under certain circumstances SF can't get the next iteration done in a reasonable period of time. The natural question that comes to my mind is are these two problems related?

Regards,

Forrest

[bob]

I wonder if you are not actually sing two different things?

Certainly the closer you get to the tips the greater the probability you get bogus moves if you use the hash table to extract the PV. Known problem for that algorithm. Some do like the simplicity of the algorithm, for reasons I don't fathom. I suppose anyone can do what they want, however, nobody can force anyone to use an idea that produces clean PVs with insignificant overhead.

However, obviously programs are not perfect either, and when you say "bogus second move" I wonder if that is not just flawed analysis by the engine, rather than it being a bogus move pulled from the hash table?

Getting a bad PV move at ply = 2 could certainly happen, but it should be incredibly rare unless you see some major transpositions with deep and shallow searches and a shallow search somewhere overwrites the entry for the ply=2 move you think is wrong. But it really ought to be pretty rare I would think...

[Zenmastur]

I wonder if you are not actually sing two different things?

Certainly the closer you get to the tips the greater the probability you get bogus moves if you use the hash table to extract the PV. Known problem for that algorithm. Some do like the simplicity of the algorithm, for reasons I don't fathom. I suppose anyone can do what they want, however, nobody can force anyone to use an idea that produces clean PVs with insignificant overhead.

However, obviously programs are not perfect either, and when you say "bogus second move" I wonder if that is not just flawed analysis by the engine, rather than it being a bogus move pulled from the hash table?

Getting a bad PV move at ply = 2 could certainly happen, but it should be incredibly rare unless you see some major transpositions with deep and shallow searches and a shallow search somewhere overwrites the entry for the ply=2 move you think is wrong. But it really ought to be pretty rare I would think...

I agree that a bad move at ply=2 on a long search seems improbable. In all fairness, more than half of the bad moves do occur in the last half of the PV. Which still leaves too large of a number in the first half. I have no clue as to what the cause is. I'm not even slightly familiar with stockfish's code so I'm not going to venture a guess. All I can do is note that a lot of the PV's have errors that seem too shallow in the PV to be coincidence. But what do I know, maybe they're just the result of aggressive pruning.

There is always a chance that more than one problem exists. Telling them apart can be difficult if they have similar symptoms. If they are interacting with each other then the problem is much harder to analyze. The only way to tell for sure is to find positions that exhibit the problem and start experimenting.

Regards,

Forrest