Transposition Table - Replacement and PV
Posted: Tue Dec 04, 2012 1:14 pm
I have integrated a transposition table in my search routine, always replacing entries. Of course, the triangular pv-table does not collect the whole PV when TT positions are discovered early in the search.
There are many comments around stating it is possible to collect the PV from the TT by storing the best move with each position in the TT. Then, basically, make the root move, get the hash and TT index to obtain the next best move, make that move and repeat until the expected depth. Also, I expect the entry to be an EXACT entry.
Here's what I have seen but have not read anything specific to this anywhere else.
At any ply with position p, an amount of moves are found and made one at a time. When each move is unmade, the board returns to position p. The score is compared to alpha and beta and p is indexed into the TT as a lower, upper, or EXACT. Obviously, with a replace always, the EXACT entries are always overwritten for p and that index in the TT will have the last move from the iteration at that ply (if not overwritten at another ply).
I have tried the replace based on search depth >= TT[index].depth. This still replaces the EXACT entries.
The thoughts I have now but have not yet tested are:
1. Only replace EXACT with EXACTs and having a larger depth.
2. Incorporate a score check with #1 so replace if the score is better.
3. Implement a TT for EXACT positions to be used just to collect the PV.
4. If any of the above fail or have a collision, put the entry in a second bucket that which will replace always.
Am I on the right path? I think #3 is my best option because #2 may overwrite good positions even if the score was weaker.
Thank you all for you input and advice
There are many comments around stating it is possible to collect the PV from the TT by storing the best move with each position in the TT. Then, basically, make the root move, get the hash and TT index to obtain the next best move, make that move and repeat until the expected depth. Also, I expect the entry to be an EXACT entry.
Here's what I have seen but have not read anything specific to this anywhere else.
At any ply with position p, an amount of moves are found and made one at a time. When each move is unmade, the board returns to position p. The score is compared to alpha and beta and p is indexed into the TT as a lower, upper, or EXACT. Obviously, with a replace always, the EXACT entries are always overwritten for p and that index in the TT will have the last move from the iteration at that ply (if not overwritten at another ply).
I have tried the replace based on search depth >= TT[index].depth. This still replaces the EXACT entries.
The thoughts I have now but have not yet tested are:
1. Only replace EXACT with EXACTs and having a larger depth.
2. Incorporate a score check with #1 so replace if the score is better.
3. Implement a TT for EXACT positions to be used just to collect the PV.
4. If any of the above fail or have a collision, put the entry in a second bucket that which will replace always.
Am I on the right path? I think #3 is my best option because #2 may overwrite good positions even if the score was weaker.
Thank you all for you input and advice