Extracting PV from TT

[bob]

Sure the PV is the single most important variation, but the transposition table was not designed to store entire variations. It was designed to store scores and bestmoves of individual positions that the search may encounter in the near future. And being able to retrieve an entire variation (including the PV) has nothing to do with move ordering, UNLESS we're about to search a position near the root of that variation. Of course at the beginning of a search it is useful to have the entire PV in the hash table, because that's the variation we want to search first, but after that, it's not as relevant.

How is it not relevant? The PV is relevant to the entire search, unless you know for sure the current iterations is your last (and even then, you want the PV, so you need to store it ANYWAY).

Actually that is not true. The PV is only relevant while you are searching the PV for the next iteration. It is meaningless for the rest of that iteration. And, in fact, it become irrelevant quicker than that. For example, if you depth N PV is 20 moves long, when you start the next iteration this PV becomes irrelevant after searching exactly 20 nodes, as now you have tried all the PV moves and you are done with them for this iteration.

And it's trivial (both in CPU time and programming time) to feed the PV back into the TT immediately preceding a new search.

If you do this, you're just using two tables to do what could be accomplished by one.

Perhaps, but also perhaps there is benefit in not treating EXACT entries in a special way since they lock up certain entries in the table for a long time. In a set associative cache, if it behaved this way performance would go in the tank, because you _rarely_ use those entries. In fact, you only use them at the beginning of the iteration for the first N nodes (where N is the length of the PV) but you then make it impossible to replace those by anything else for the remainder of that iteration. Even if the PV changes and most of those moves are no longer on the actual PV, they will stick around.

Also, saying that a design is buggy simply because it doesn't have the same set of advantages and disadvantages that you prefer is ridiculous. I could just as easily say that your design is buggy because it throws away data more relevant to the remaining search in favor of keeping PV data, which may be less relevant to the remaining search.

But it's not - as explained above the PV is always relevant - so again you're just proving my case for me.

My elementary teachers taught me that _any_ sentence with the word "always" or "never" was always false (never mind the contradiction that causes. ) But in this case, a 20 ply search, over a tree of (say) 100M nodes, will only use those PV entries in about 20 nodes of the search.

[bob]

Here's the final results. 4 runs with old TT replacement (23.1) and 4 runs with new TT replacement (23,1a, never replace EXACT entries during a complete search, only replace them once those entries are old (next real game move is played).

Code: Select all

   4 Crafty-23.1-1        2596    4    4 40000   48%  2613   23% 
   5 Crafty-23.1-2        2593    4    4 40000   47%  2613   22% 
   6 Crafty-23.1-4        2593    4    4 40000   47%  2613   22% 
   7 Crafty-23.1a-3       2591    4    4 40000   47%  2613   22% 
   8 Crafty-23.1a-2       2591    4    4 40000   47%  2613   22% 
   9 Crafty-23.1-3        2591    3    4 40000   47%  2613   22% 
  10 Crafty-23.1a-1       2591    4    4 40000   47%  2613   22% 
  11 Crafty-23.1a-4       2589    4    4 40000   47%  2613   23% 

Note that there is a bit of overlap now, but well within the +/-4, confidence that one is better is not high, although the bayeselo LOS output suggests that 23.1 is almost certainly stronger.

[bob]

Here's the final results. 4 runs with old TT replacement (23.1) and 4 runs with new TT replacement (23,1a, never replace EXACT entries during a complete search, only replace them once those entries are old (next real game move is played).

Code: Select all

   4 Crafty-23.1-1        2596    4    4 40000   48%  2613   23% 
   5 Crafty-23.1-2        2593    4    4 40000   47%  2613   22% 
   6 Crafty-23.1-4        2593    4    4 40000   47%  2613   22% 
   7 Crafty-23.1a-3       2591    4    4 40000   47%  2613   22% 
   8 Crafty-23.1a-2       2591    4    4 40000   47%  2613   22% 
   9 Crafty-23.1-3        2591    3    4 40000   47%  2613   22% 
  10 Crafty-23.1a-1       2591    4    4 40000   47%  2613   22% 
  11 Crafty-23.1a-4       2589    4    4 40000   47%  2613   23% 

Note that there is a bit of overlap now, but well within the +/-4, confidence that one is better is not high, although the bayeselo LOS output suggests that 23.1 is almost certainly stronger.

A comment after studying the primary difference between these two replacement ideas. Idea 1 is what I was doing, which is an _always_ store a hash entry. Idea 2 was the suggested case of not overwriting EXACT entries.

In doing a significant amount of testing and displaying trees, I am convinced this last idea is really not good. The reason the Belle approach works is that it is _guaranteed_ to store the current hash entry somewhere. This is a "local tree" value that is likely important in searching this sub-tree. The special case of never overwriting an EXACT entry, to avoid replacing a PV entry that would make it impossible to extract the complete PV from the hash table, seems to be flawed in this specific case, because we may not store the current entry if the "bucket" is full of EXACT entries, which does happen. Or if we reach this same position later, with greater depth, due to a transposition of moves that adds an extension or two (or eliminates a reduction or two) and now we have a UPPER/LOWER bound to store with draft N, but we already have an existing entry with this same signature with an EXACT score and a smaller draft.

I am convinced, after studying this for a good bit, that always storing is the correct solution. One could address this by allowing a single entry to have several different drafts and bounds, but that impacts the number of entries and also memory bandwidth.

Feel free to chime in. But I am convinced that if you refuse to do a store, for _any_ reason, you are setting yourself up to hit a "wall" at some point. Say a very long search because your opponent failed low, so that you begin to reach a point where you have enough EXACT entries that you are unable to store significant numbers of entries because you refuse to overwrite them. Seems like a bad idea. Nothing wrong with trying to avoid overwriting an EXACT entry, but refusing to do so is probably a bad idea...

[jwes]

If you extracted the PV from the hash table each time the PV changes, you would be much less likely to have an entry overwritten.

[Zach Wegner]

My suggestion for an algorithm:

1. Out of the N entries, if the current position exists, overwrite that.

2. Otherwise, look for positions from an old search that aren't exact. Overwrite the lowest if there is at least one.

3. Otherwise, look for positions from an old search that are exact. Overwrite the lowest if there is at least one.

4. Otherwise, look for positions from the current search that aren't exact. Overwrite the lowest if there is at least one.

5. Otherwise, overwrite the lowest draft. In this case each entry would be an exact entry from the current search, which is pretty rare, so this is just a worst case.

3 and 4 could possibly be switched.

[bob]

My suggestion for an algorithm:

1. Out of the N entries, if the current position exists, overwrite that.

Fails. You can reach P the first time with draft D, and store as EXACT. You can then reach P through a different path with draft D+1, and store as LOWER. And now you have lost the PV move. Already ran into this when I started the testing.

2. Otherwise, look for positions from an old search that aren't exact. Overwrite the lowest if there is at least one.

3. Otherwise, look for positions from an old search that are exact. Overwrite the lowest if there is at least one.

Tried both of those together, then tried just replace old search regardless. Made very little difference.

4. Otherwise, look for positions from the current search that aren't exact. Overwrite the lowest if there is at least one.

5. Otherwise, overwrite the lowest draft. In this case each entry would be an exact entry from the current search, which is pretty rare, so this is just a worst case.

it is not _that_ rare. It happened in a very short search (<1 second) when I first wrote the code. I had neglected to allow for the case where all four buck entries were EXACT and ended up with a null REPLACE pointer. Crashed in a heartbeat on the first 3 positions I tried before I figured it out.


3 and 4 could possibly be switched.[/quote]

[bob]

If you extracted the PV from the hash table each time the PV changes, you would be much less likely to have an entry overwritten.

It does reduce the problem, but doesn't eliminate it, as you still do a lot of searching on the first root move on non-PV nodes that can transpose and overwrite some of the shallow-draft entries out near the end of the original PV.

[Edsel Apostol]

If you extracted the PV from the hash table each time the PV changes, you would be much less likely to have an entry overwritten.

This makes sense to me. If you don't wait to finish the entire iteration before printing the PV this is a valid solution. For example if a move returns a score greater than alpha, you retrieve immediately the PV from the hash table and display it. It doesn't matter if the succeeding moves overwrite those EXACT entries from the PV as the PV has already been displayed.

[Zach Wegner]

My suggestion for an algorithm:

1. Out of the N entries, if the current position exists, overwrite that.

Fails. You can reach P the first time with draft D, and store as EXACT. You can then reach P through a different path with draft D+1, and store as LOWER. And now you have lost the PV move. Already ran into this when I started the testing.

How is that "failing"? It's arguable, if you meant D-1 instead of D+1, that it would be better to keep the old EXACT entry. I suppose I'd want to keep the newest, but that's just a gut feeling. But with your scheme, which apparently doesn't check for being the same position, you would store _both_ entries in different buckets, which is clearly wrong.

2. Otherwise, look for positions from an old search that aren't exact. Overwrite the lowest if there is at least one.

3. Otherwise, look for positions from an old search that are exact. Overwrite the lowest if there is at least one.

Tried both of those together, then tried just replace old search regardless. Made very little difference.

I don't imagine it should, I was just describing basically an "ideal" replacement scheme.

4. Otherwise, look for positions from the current search that aren't exact. Overwrite the lowest if there is at least one.

5. Otherwise, overwrite the lowest draft. In this case each entry would be an exact entry from the current search, which is pretty rare, so this is just a worst case.

it is not _that_ rare. It happened in a very short search (<1 second) when I first wrote the code. I had neglected to allow for the case where all four buck entries were EXACT and ended up with a null REPLACE pointer. Crashed in a heartbeat on the first 3 positions I tried before I figured it out.

Rare enough that what you do in that situation probably won't make a huge difference. I think it would be better to overwrite one of the exact entries rather than store nothing though.

[bob]

My suggestion for an algorithm:

1. Out of the N entries, if the current position exists, overwrite that.

Fails. You can reach P the first time with draft D, and store as EXACT. You can then reach P through a different path with draft D+1, and store as LOWER. And now you have lost the PV move. Already ran into this when I started the testing.

How is that "failing"? It's arguable, if you meant D-1 instead of D+1, that it would be better to keep the old EXACT entry. I suppose I'd want to keep the newest, but that's just a gut feeling. But with your scheme, which apparently doesn't check for being the same position, you would store _both_ entries in different buckets, which is clearly wrong.

The issue is retrieving _the_ PV from the hash table. Where "the PV" is defined as the set of moves, leading from the root position to the terminal position that produced the static evaluation that was backed up to the root as the best score." In the above, you replace the EXACT draft=D entry which has "the PV" move at this ply, with a new LOWER draft=D+1 entry which may well have a _different_ best move which does not lead to the correct terminal position.

That was the only problem I was trying to explain. "The PV" is difficult to extract from the hash table for all positions. And it might be difficult to extract for more than just a few positions. While the usual "triangular array" approach works flawlessly. And adds no measurably significant overhead

2. Otherwise, look for positions from an old search that aren't exact. Overwrite the lowest if there is at least one.

3. Otherwise, look for positions from an old search that are exact. Overwrite the lowest if there is at least one.

Tried both of those together, then tried just replace old search regardless. Made very little difference.

I don't imagine it should, I was just describing basically an "ideal" replacement scheme.

4. Otherwise, look for positions from the current search that aren't exact. Overwrite the lowest if there is at least one.

5. Otherwise, overwrite the lowest draft. In this case each entry would be an exact entry from the current search, which is pretty rare, so this is just a worst case.

it is not _that_ rare. It happened in a very short search (<1 second) when I first wrote the code. I had neglected to allow for the case where all four buck entries were EXACT and ended up with a null REPLACE pointer. Crashed in a heartbeat on the first 3 positions I tried before I figured it out.

Rare enough that what you do in that situation probably won't make a huge difference. I think it would be better to overwrite one of the exact entries rather than store nothing though.

I agree. NO store should be skipped, regardless of what is potentially being overwritten. It is easy to imagine positions where the positions for the first N plies take enough hash entries so that many of the positions near the tips can't be stored at all. Yet they are out where tree growth is a killer, still.

And there is still the issue that whenever you overwrite an EXACT entry, you can be destroying a key PV entry that will make retrieval of the PV impossible.