Cache over-writing and PV's

[bob]

And if a 'sufficient-draft' TT hit would not be sufficient draft for PV search, there obviously is something badly amiss with our depth accounting.

Is that so?

What if an engine never reduces in the PV. Then a 10-ply search starting in a PV node is likely more reliable than a 10-ply search starting in a non-PV node.

Maybe you'll say that something is badly amiss with such an engine, but if it turns out to help playing strength not many people will care.

In such an engine, relying on a 10-ply non-PV bound retrieved from hash in a PV node that is to be searched to 10 ply will introduce an error compared to not taking the cut. (Of course it is not unlikely that accepting this error will actually improve the engine even further.)

Actually I WOULD call that a bug. Why would you treat a PV and non-PV node differently regarding how you reduce? Unless you are CERTAIN you are never going to change your mind from the original PV.

[michiguel]

And if a 'sufficient-draft' TT hit would not be sufficient draft for PV search, there obviously is something badly amiss with our depth accounting.

Is that so?

What if an engine never reduces in the PV. Then a 10-ply search starting in a PV node is likely more reliable than a 10-ply search starting in a non-PV node.

Maybe you'll say that something is badly amiss with such an engine, but if it turns out to help playing strength not many people will care.

In such an engine, relying on a 10-ply non-PV bound retrieved from hash in a PV node that is to be searched to 10 ply will introduce an error compared to not taking the cut. (Of course it is not unlikely that accepting this error will actually improve the engine even further.)

Actually I WOULD call that a bug. Why would you treat a PV and non-PV node differently regarding how you reduce? Unless you are CERTAIN you are never going to change your mind from the original PV.

For the same reason that modern engines do all sort of aggressive stuff, assuming that anything that is closer to the PV is likely better. LMR is the obvious case. Some engines extend in the PV! That is not a bug, it is a feature of all modern engines. So, a TT hit in the PV may not be identical to one far from it. Whether it is worth using it is a not an obvious call and it depends on the architecture of the engine.

Miguel

[bob]

And if a 'sufficient-draft' TT hit would not be sufficient draft for PV search, there obviously is something badly amiss with our depth accounting.

Is that so?

What if an engine never reduces in the PV. Then a 10-ply search starting in a PV node is likely more reliable than a 10-ply search starting in a non-PV node.

Maybe you'll say that something is badly amiss with such an engine, but if it turns out to help playing strength not many people will care.

In such an engine, relying on a 10-ply non-PV bound retrieved from hash in a PV node that is to be searched to 10 ply will introduce an error compared to not taking the cut. (Of course it is not unlikely that accepting this error will actually improve the engine even further.)

Actually I WOULD call that a bug. Why would you treat a PV and non-PV node differently regarding how you reduce? Unless you are CERTAIN you are never going to change your mind from the original PV.

For the same reason that modern engines do all sort of aggressive stuff, assuming that anything that is closer to the PV is likely better. LMR is the obvious case. Some engines extend in the PV! That is not a bug, it is a feature of all modern engines. So, a TT hit in the PV may not be identical to one far from it. Whether it is worth using it is a not an obvious call and it depends on the architecture of the engine.

Miguel

I will say it again. From a purely LOGICAL point of view, it makes absolutely no sense to treat PV different from the rest of the search. If so, why not just SKIP the rest of the search since it is apparently ok to be more aggressive in the pruning in that part of the search. Personally, I have MY program search ALL the root moves, because I hope that it occasionally will find a BETTER move to play. That is much less likely if you treat the PV moves "better" than you treat all the rest, it just makes the rest less likely to replace the PV.

As I said, from a purely analytical perspective, it makes no sense. Whether others do it or not really doesn't matter. That's not a justification for doing so.

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

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.

Think about this more carefully... There are NOT a "log of small PVs" that need to be stored. Almost all of the tree is searched with a null window which has no PV at all. I posted some stats back when I first wrote this pv hash stuff. The number of times this stuff stores a partial PV is incredibly small, even for 1 hour searches... There just aren't that many nodes where alpha != beta - 1.

[xmas79]

Think about this more carefully... There are NOT a "log of small PVs" that need to be stored. Almost all of the tree is searched with a null window which has no PV at all. I posted some stats back when I first wrote this pv hash stuff. The number of times this stuff stores a partial PV is incredibly small, even for 1 hour searches... There just aren't that many nodes where alpha != beta - 1.

I took my stats more than one year back (more or less) when I started to write my engine and discovered that EXACT hash hits would truncate PVs. Probably the way I used PVS and the untuned eval played a major role, so I may have concluded wrong things.

I just did some tests now, I see a "high" count of writes in mate positions (around 1k entries for a 14 plies search of about one minute, don't know how many total nodes since my engine is a bit broken in this moment due to a major cleanup), but I still have my fears: what happens with a 50+ plies search that runs for 2 days, especially in positions where engine keeps changing its mind often?

[hgm]

And if a 'sufficient-draft' TT hit would not be sufficient draft for PV search, there obviously is something badly amiss with our depth accounting.

Is that so?

What if an engine never reduces in the PV. Then a 10-ply search starting in a PV node is likely more reliable than a 10-ply search starting in a non-PV node.

Indeed. So it would be misleading to claim the draft of the stored PV search is the same as the draft of the stored non-PV search (namely 10). The latter should have a lower draft. This is the something that is 'amiss'. It is the draft info in the hash entry that should decide if a stored value is sufficiently accurate to satisfy a given probe.

So a 10-ply hashed result might not be good enough to satisfy a 10-ply PV probe, when you embezzled the information from which type of search it was by not encoding that with the draft, because it might heve been obtained through a non-PV search. (Although you would know that is not the case when the bound type is 'exact', you could not deduce it from other bound types, as PV searches can fail high or low too.) But would it also be better to do a 10-ply PV search to overturn the result of a 15- or 20-ply non-PV search?

Unless you have a truly ridiculous reduction scheme, that would certainly not be the case, and probably an 11-ply non-PV search would already be more reliable than a 10-ply PV search. Which is what the 'no cuts whatsoever in expected PV nodes' would completely miss.

So the fact that this tests as better exposes the fact that you failed to properly encode the search quality in your hash entry, and thus cannot accept superficially sufficient draft when a high-quality search is needed. Now you can 'panic' and not accept any hashed scores at all in this case, but it is clear that this would also do a lot of damage in throwing away hits that would have been usable, together with protecting you from unreliable hits. Better would have been to fix the problem, and accept all hits that were useful, and reject only those that were unreliable. Using the voodoo method of software development would make you miss that opportunity. You will accept 'solutions' that throw away the baby with the bathwater all the time, just because they happen to throw away marginally more bathwater than baby...

[Evert]

This is something that I've wondered about in the past: what is the depth that I should store with a TT entry?

What I know at the point where I store the entry is the nominal depth D (as passed into search()), but reductions and extensions can and will change that, so that the result I got back is probably not quite based on a "real" search from this position to depth D. The depth to the leaf node is some other depth D', which I don't know (but I could, if I backed that up along with the score).

What should I store? I currently store D, trusting that even if the search really produced a depth D', it will do so again if I were to search this position again to the same nominal depth D, so it's ok to store D instead. This is probably not true due to search instability, so the weaker assumption is that it doesn't matter in the end. Even if it did though, I don't think anything can be done about this: even if I store D' in the hash entry, all I can compare it with when I retrieve it is the (then-current) depth D since I can't know how the search would extend and reduce the tree below the current node. Or I could store both entries in the table, and use that information to make a more informed decision about what to do: the difference will tell me if the tree was heavily extended or reduced before reaching the score.

Has anyone else ever thought about this? Did anyone consider it at all useful to store anything other than the nominal depth D? My personal conclusion was that this is really the only honest and self-consistent thing to do, but I'm curious to hear about other opinions.

[hgm]

Nominal depth is fine if extensions and reductions are reproducible. Overdeep hash hits might cause extra depth in a practical realization of a search, but we generally consider that just an 'extra' over the nominal search.

Most of my engines do back up the depth ('depth bootstrapping'), and this can cause the returned depth to be larger than the requested depth. (Because of hash hits, but QS nodes often return d=1 or d=2 even without hashing.) In these cases it is the achieved depth that goes into the hash.

If reductions / extensions are not reproducible, this is a bad problem. Some LMR implementations have this, because they reduce depending on move ordering, which can be different. (Even exempting killers from LMR can be a problem.) Or 'tactical connection', which is also a nightmare. E.g. a recapture extension is very difficult to hash, because it depends on the preceding move. You would almost be forced to store the previous to-square in the hash on which the search was based, and if that is different from how you reach it now, do a research only on the moves that now deserve extra extension,and use the hashed score for the remaining ones.

[bob]

This is something that I've wondered about in the past: what is the depth that I should store with a TT entry?

What I know at the point where I store the entry is the nominal depth D (as passed into search()), but reductions and extensions can and will change that, so that the result I got back is probably not quite based on a "real" search from this position to depth D. The depth to the leaf node is some other depth D', which I don't know (but I could, if I backed that up along with the score).

What should I store? I currently store D, trusting that even if the search really produced a depth D', it will do so again if I were to search this position again to the same nominal depth D, so it's ok to store D instead. This is probably not true due to search instability, so the weaker assumption is that it doesn't matter in the end. Even if it did though, I don't think anything can be done about this: even if I store D' in the hash entry, all I can compare it with when I retrieve it is the (then-current) depth D since I can't know how the search would extend and reduce the tree below the current node. Or I could store both entries in the table, and use that information to make a more informed decision about what to do: the difference will tell me if the tree was heavily extended or reduced before reaching the score.

Has anyone else ever thought about this? Did anyone consider it at all useful to store anything other than the nominal depth D? My personal conclusion was that this is really the only honest and self-consistent thing to do, but I'm curious to hear about other opinions.

From my perspective, there is only one "draft" you have, the remaining depth when you reach a node. But IMHO when you reach ANY node with depth=D, you should search it the same way each and every time, otherwise you invite search instability, and this is NOT just on EXACT hits. ANY hit where you treat branches below this node differently based on prior path info (such as PV or non-PV) is going to produce search inconsistencies. That's why I believe that treating PV and non-PV nodes differently regarding reductions and extensions is a flawed idea, because now the hash table has inconsistent results stored. The whole idea is that when you reach the same position you should be able to avoid the effort required to search it a second time. But if you search it differently the second time, inconsistencies crop up.

Just seems wrong. And until someone offers a really convincing explanation for why it isn't, I would suggest simply avoiding this flaw.

We already accept an inconsistent result due to the "L" in LMR. You reduce moves based on their search order, but their search order depends on prior path information (such as hash move, killer moves, history counters, etc). If you reach position D two different times, it is unlikely that the tree below D will be searched the same in both of those searches since move ordering will change, which will affect reductions at least... That you really have to accept else the ttable becomes useless. But intentionally adding even more serious differences between the two searches below D seems to add another LARGE level of inconsistency that ought to be avoided without any evidence that it is justified.

[bob]

Think about this more carefully... There are NOT a "log of small PVs" that need to be stored. Almost all of the tree is searched with a null window which has no PV at all. I posted some stats back when I first wrote this pv hash stuff. The number of times this stuff stores a partial PV is incredibly small, even for 1 hour searches... There just aren't that many nodes where alpha != beta - 1.

I took my stats more than one year back (more or less) when I started to write my engine and discovered that EXACT hash hits would truncate PVs. Probably the way I used PVS and the untuned eval played a major role, so I may have concluded wrong things.

I just did some tests now, I see a "high" count of writes in mate positions (around 1k entries for a 14 plies search of about one minute, don't know how many total nodes since my engine is a bit broken in this moment due to a major cleanup), but I still have my fears: what happens with a 50+ plies search that runs for 2 days, especially in positions where engine keeps changing its mind often?

What you will discover is that if you double the search time, you double the number of PV stores as a max. I've been writing up the hash path idea. Here is a bit of data. I used fine #70 which is a real stress-test for hashing.

Total probes/stores done = 387,877,352
Total times exact code executed (either HashProbe() OR HashStore()) = 2813

So almost 400M nodes searched, and I either probed OR stored an entry in the hash path table 2800 times. You can't even measure that in terms of time expended, it is so small. The benefit is that (a) you don't do this ridiculous "don't allow EXACT hash hits on the PV" which gives up some efficiency and (b) you get PVs that are complete every time except for the random hash hit. But I use a bucket size of 16 for this table since it is so infrequently accessed, which really drives overwrites down, and it doesn't require a huge table either.

Here's a sample output:

Code: Select all

Position win at chess #71 (I just picked one that produces a truncated PV in a short amount of time to show the problem):

         13     0.34         -0.92   1. Qd3 Qg4 2. Be5 Rhe8 3. Rbe1 Qg6
                                     4. Qd2 <HT>

And here is the same position with all settings identical, except that this includes the path hashing fix.  Note that with the "grafting" the PV is actually a 15 ply search, not 13.  No extensions in this PV as this version only used the check extension and none of the moves are checks.  Not only do you see "over the horizon" you also see what led to that -0.92 score

         13     0.33         -0.92   1. Qd3 Qg4 2. Be5 Rhe8 3. Rbe1 Qg6
                                     4. Qd2 Re7 5. Qa5 Ne4 6. Bc7 Rde8
                                     7. a4

Short PV gone.  No measurable overhead.  No throwing out the baby with the bathwater using HGM's analogy.  Here is what I get when I set up wac 71, then read and append the above PV to the position and use crafty's "score" command&#58;

Black&#40;7&#41;&#58; sco
note&#58; scores are for the white side
                        +-----------white----------+-----------black----------+
material.......  -1.05  |    comp     mg      eg   |    comp     mg      eg   |
pawns..........  -0.39  |   -0.46   -0.47   -0.42  |    0.07    0.11   -0.05  |
passed pawns...  -0.70  |    0.00    0.00    0.00  |   -0.70   -0.70   -0.72  |
knights........  -0.20  |    0.12    0.12    0.12  |   -0.32   -0.32   -0.32  |
bishops........  -0.07  |    0.35    0.32    0.50  |   -0.42   -0.39   -0.57  |
rooks..........  -0.42  |    0.41    0.44    0.29  |   -0.83   -0.89   -0.59  |
queens.........  -0.04  |    0.03    0.03    0.03  |   -0.07   -0.07   -0.07  |
kings..........   1.95  |   -0.23   -0.19   -0.40  |    2.18    2.61    0.40  |
development....   0.00  |   -0.48   -0.60    0.00  |    0.48    0.60    0.00  |
pawn races.....   0.00  +--------------------------+--------------------------+
total..........  -0.92

perfect match

Which is what I wanted when I came up with this idea. I want to see the exact endpoint that led to this score, not some halfway point where I have to use imagination to guess what happened after that <HT> sentinel in the first example.