bob wrote:
1. If the current hash signature matches any of the 4 table entries exactly, I overwrite that entry, period.
[...]
Version 23.1a does the same, except steps 1 and 3 do not replace a type of EXACT, unless the new entry itself is of type EXACT. The depth/draft is still used exactly as above.
This sounds wrong. So if an old PV node now fails low or high, you keep the result as if it were a PV node?
That should cause some performance loss indeed.
How are you going to stop that? All you had said was "if type is EXACT then it is a PV node".
The way you describe it sounds like if you have a position (a) which gets an exact score, and in the next search you get (a) but a bound result (with deeper draft), you don't replace the result for (a).
This is wrong and will lower performance (and not contribute to keeping the PV).
bob wrote: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.
Yes, exactly, this is the flaw in your implementation that I already pointed out...
bob wrote:
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."
OK, definition problem.
The principal variation refers to the particular variation that is the most advantageous to the current player, assuming each other player will respond with the move that best improves their own position. In other words, it is the "best" or "correct" line of play.
I agree that in the above case, i.e. a transposition into the PV with a larger remaining depth, you will lose the "Bob PV", but the question is whether this is _*_*the*_*_ PV.
If you have a need to have the line that led to the evaluation (and such a link exists in your program) then I admit you need to explicitly store it and my argumentation in this thread is irrelevant.
bob wrote:
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."
OK, definition problem.
The principal variation refers to the particular variation that is the most advantageous to the current player, assuming each other player will respond with the move that best improves their own position. In other words, it is the "best" or "correct" line of play.
I agree that in the above case, i.e. a transposition into the PV with a larger remaining depth, you will lose the "Bob PV", but the question is whether this is _*_*the*_*_ PV.
If you have a need to have the line that led to the evaluation (and such a link exists in your program) then I admit you need to explicitly store it and my argumentation in this thread is irrelevant.
I think that for the concept of tree searching, the term "PV" is well-defined as the path leading from the root position to the terminal position that produces the best score backed up to the root. I agree that the overwrites might well cause the PV to have a _better_ move than the move that leads to the terminal position, but that's not going to help much in debugging.
That's been my only complaint about this from the beginning. The "triangular array" has no significant cost that I have measured, and it does provide this most of the time (except for EXACT hash hits on the PV which are always problematic).
bob wrote:
1. If the current hash signature matches any of the 4 table entries exactly, I overwrite that entry, period.
[...]
Version 23.1a does the same, except steps 1 and 3 do not replace a type of EXACT, unless the new entry itself is of type EXACT. The depth/draft is still used exactly as above.
This sounds wrong. So if an old PV node now fails low or high, you keep the result as if it were a PV node?
That should cause some performance loss indeed.
How are you going to stop that? All you had said was "if type is EXACT then it is a PV node".
The way you describe it sounds like if you have a position (a) which gets an exact score, and in the next search you get (a) but a bound result (with deeper draft), you don't replace the result for (a).
This is wrong and will lower performance (and not contribute to keeping the PV).
Did you not say "do not overwrite EXACT" entries? Or do you age across iterations rather than across complete searches? I could try across iterations which would solve this completely. Not sure whether it will help or hurt but I'll give it a test to see...
jwes wrote: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.
However, it is not a 100% fix. You typically search the PV path first, but before you finish searching that root move, you have a really large tree to traverse, and the pathways in that tree can cross due to transpositions and still cause the PV to be overwritten.
bob wrote:Did you not say "do not overwrite EXACT" entries? Or do you age across iterations rather than across complete searches? I could try across iterations which would solve this completely. Not sure whether it will help or hurt but I'll give it a test to see...
There's a difference between overwriting EXACT entries with some random position with a bound score and overwriting EXACT entries with a deeper search of the same position. Obviously your PV is going to change, and when PV nodes from the last iteration get refuted, you're definitely going to want to store that, not the old EXACT entry.
bob wrote: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.
Yes, exactly, this is the flaw in your implementation that I already pointed out...
However, in my test results I did _not_ have this flaw. I never write over an EXACT entry with anything but an EXACT entry of greater draft. It appears that this hurt performance but only by a couple of Elo which is quite hard to measure.
So I don't consider it a "flaw" it it provides a performance (Elo) _increase_. At least that would be a somewhat odd definition of "flaw" since it is actually better.
bob wrote:Did you not say "do not overwrite EXACT" entries? Or do you age across iterations rather than across complete searches? I could try across iterations which would solve this completely. Not sure whether it will help or hurt but I'll give it a test to see...
There's a difference between overwriting EXACT entries with some random position with a bound score and overwriting EXACT entries with a deeper search of the same position. Obviously your PV is going to change, and when PV nodes from the last iteration get refuted, you're definitely going to want to store that, not the old EXACT entry.
Depends. Do you want to be able to reconstruct the path from the root to the tip for the PV score? That's what the discussion is about. I contend that worrying about preserving the PV nodes themselves (the ones the represent the actual path from the root to the tip) is less important that providing optimal search performance. And I contend you can _not_ do both. My test results suggest that the issue is small, but small is not equal to zero, and I'll take an elo here and there when I find one.
