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
Transposition Table - Replacement and PV
Moderators: hgm, Rebel, chrisw
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: Transposition Table - Replacement and PV
This is what I use in DiscoCheck currently:Cheney wrote: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
- if the keys are different
- or (if the keys are equal, but) the depth is >= current entry depth
- then overwrite
It's the dumbest thing ever, and it works very well. I'm not claiming it's best, of course, but I don't think any alternative will give you a significant elo increase over this (it will surely give you headaches and bugs to fix, if you get it wrong though).
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
-
- Posts: 1221
- Joined: Wed Mar 08, 2006 8:28 pm
- Location: Florida, USA
Re: Transposition Table - Replacement and PV
Hi Cheney,
This means an exact score will be preserved in the TT. The only reason it wouldn't be preserved would be if another position overwrites the entry.
Best,
Steve
This is wrong. You don't update the TT for position p after every child move. You only update p's TT entry after all sub-moves have been search (i.e fail low or exact) or after a fail high.Cheney wrote:....[snip]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).
[snip]...
This means an exact score will be preserved in the TT. The only reason it wouldn't be preserved would be if another position overwrites the entry.
Best,
Steve
-
- Posts: 1563
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: Transposition Table - Replacement and PV
What works the best for me is:
Always overwrite entrys of an older table genereration.
And if the table generation is the same then:
Lowerbound and exact will always overwrite an existing entry if the depth >= existing depth or the existing entry is an upperbound.
Upperbounds will only overwrite upperbounds with lesser or equal depth.
So upperbounds wil never overwrite lowerbound or exact entrys from the same table generation.
Always overwrite entrys of an older table genereration.
And if the table generation is the same then:
Lowerbound and exact will always overwrite an existing entry if the depth >= existing depth or the existing entry is an upperbound.
Upperbounds will only overwrite upperbounds with lesser or equal depth.
So upperbounds wil never overwrite lowerbound or exact entrys from the same table generation.
-
- Posts: 686
- Joined: Thu Mar 03, 2011 4:57 pm
- Location: Germany
Re: Transposition Table - Replacement and PV
If I understood you right you don't replace an entry for the same position when you encounter this position stored with greater depth in the TT ?This is what I use in DiscoCheck currently:
- if the keys are different
- or (if the keys are equal, but) the depth is >= current entry depth
- then overwrite
This is wrong. You should replace it, because if the position with greater depth would be worth something, you would not have come to the point where you want to store that position with lower depth again, you would have just used what you did found. You are really lucky if you are able to solve FINE 70 with that replacement strategy.
Thomas...
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Transposition Table - Replacement and PV
I agree it is (much) better to replace, but fine #70 can be solved either way in my experience.tpetzke wrote:If I understood you right you don't replace an entry for the same position when you encounter this position stored with greater depth in the TT ?This is what I use in DiscoCheck currently:
- if the keys are different
- or (if the keys are equal, but) the depth is >= current entry depth
- then overwrite
This is wrong. You should replace it, because if the position with greater depth would be worth something, you would not have come to the point where you want to store that position with lower depth again, you would have just used what you did found. You are really lucky if you are able to solve FINE 70 with that replacement strategy.
-
- Posts: 104
- Joined: Thu Sep 27, 2012 2:24 am
Re: Transposition Table - Replacement and PV
Thanks Steve. Interesting. I whacked at a poor code sample below. Now that I typed it out, that makes sense and has to be the issue.
I'll try this out, thanks again
Code: Select all
alphabeta(depth,ply,alpha,beta)
{
// I do not have this line but will add it based on your observation
int hashtype=lower
// process the TT check and return values. Omitted from this sample.
if depth = 0 then
{
// This is what I do now. But, have seen where alpha/beta is
// checked here and the TT stored based on that
TTAddPosition(board.hash, exact, depth)
return board.evaluation()
}
for each move in generatedmoves()
{
makemove(move)
value=-alphabeta(depth-1, ply+1, -beta, -alpha)
unmake(move)
if value >= beta then
{
// I have this and think this is valid since it fails high
recordTT(board.hash, upper)
return beta
}
if value > alpha then
{
alpha=value
// Add this line to be used when all moves are made
hashtype=exact
// Remove this line and stop adding the position to the TT at this point
// recordTT(board.hash, exact)
}
else
{
// Stop adding the "lower" position to the TT at this point
// recordTT(board.hash, lower)
}
} // End the foreach loop of the generated moves
// Add the position to the TT here instead of within the foreach
recordTT(board.hash, hashtype)
return alpha
}
-
- Posts: 211
- Joined: Sun Jan 18, 2009 11:27 pm
- Location: Sweden
- Full name: Patrik Karlsson
Re: Transposition Table - Replacement and PV
I think you have upper and lower bounds mixed up. If you have a score that is 'at least' beta wouldn't that be a lower bound?Cheney wrote:Thanks Steve. Interesting. I whacked at a poor code sample below. Now that I typed it out, that makes sense and has to be the issue.
I'll try this out, thanks againCode: Select all
alphabeta(depth,ply,alpha,beta) { // I do not have this line but will add it based on your observation int hashtype=lower // process the TT check and return values. Omitted from this sample. if depth = 0 then { // This is what I do now. But, have seen where alpha/beta is // checked here and the TT stored based on that TTAddPosition(board.hash, exact, depth) return board.evaluation() } for each move in generatedmoves() { makemove(move) value=-alphabeta(depth-1, ply+1, -beta, -alpha) unmake(move) if value >= beta then { // I have this and think this is valid since it fails high recordTT(board.hash, upper) return beta } if value > alpha then { alpha=value // Add this line to be used when all moves are made hashtype=exact // Remove this line and stop adding the position to the TT at this point // recordTT(board.hash, exact) } else { // Stop adding the "lower" position to the TT at this point // recordTT(board.hash, lower) } } // End the foreach loop of the generated moves // Add the position to the TT here instead of within the foreach recordTT(board.hash, hashtype) return alpha }
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: Transposition Table - Replacement and PV
Well then I must be lucky! Solved in 5.79 seconds, running 1 thread on a rather 4 year old PC:tpetzke wrote:If I understood you right you don't replace an entry for the same position when you encounter this position stored with greater depth in the TT ?This is what I use in DiscoCheck currently:
- if the keys are different
- or (if the keys are equal, but) the depth is >= current entry depth
- then overwrite
This is wrong. You should replace it, because if the position with greater depth would be worth something, you would not have come to the point where you want to store that position with lower depth again, you would have just used what you did found. You are really lucky if you are able to solve FINE 70 with that replacement strategy.
Thomas...
Code: Select all
position fen 8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - -
go
info score cp 104 depth 1 nodes 5 time 0 pv a1b2
info score cp 68 depth 2 nodes 21 time 0 pv a1b2
info score cp 92 depth 3 nodes 44 time 0 pv a1b2
info score cp 92 depth 4 nodes 81 time 0 pv a1b2
info score cp 104 depth 5 nodes 201 time 0 pv a1b2
info score cp 92 depth 6 nodes 313 time 0 pv a1b2
info score cp 92 depth 7 nodes 484 time 0 pv a1b2
info score cp 92 depth 8 nodes 729 time 0 pv a1b2
info score cp 92 depth 9 nodes 1043 time 1 pv a1b2
info score cp 92 depth 10 nodes 1600 time 1 pv a1b2
info score cp 92 depth 11 nodes 2707 time 2 pv a1b2
info score cp 92 depth 12 nodes 3997 time 3 pv a1b2
info score cp 92 depth 13 nodes 5272 time 4 pv a1b2
info score cp 92 depth 14 nodes 6290 time 5 pv a1b2
info score cp 92 depth 15 nodes 8055 time 6 pv a1b2
info score cp 92 depth 16 nodes 9599 time 7 pv a1b2
info score cp 92 depth 17 nodes 11610 time 9 pv a1b2
info score cp 92 depth 18 nodes 13903 time 11 pv a1b2
info score cp 92 depth 19 nodes 16283 time 12 pv a1b2
info score cp 92 depth 20 nodes 23732 time 18 pv a1b2
info score cp 92 depth 21 nodes 26174 time 20 pv a1b2
info score cp 92 depth 22 nodes 40021 time 29 pv a1b2
info score cp 92 depth 23 nodes 151175 time 103 pv a1b2
info score cp 92 depth 24 nodes 172789 time 117 pv a1b2
info score cp 92 depth 25 nodes 191517 time 130 pv a1b2
info score cp 92 depth 26 nodes 198507 time 136 pv a1b2
info score cp 108 depth 27 nodes 4602096 time 1517 lowerbound
info score cp 125 depth 27 nodes 6939736 time 2245 lowerbound
info score cp 157 depth 27 nodes 13567245 time 4348 lowerbound
info score cp 199 depth 27 nodes 18054906 time 5789 pv a1b1
PS: Here's my code, just to clarify
Code: Select all
if (kt.key != slot.key_type.key // key != replacement_slot.key
|| depth >= slot.depth
|| slot.generation != generation)
{
// overwrite
}
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Transposition Table - Replacement and PV
I don't think this works very well. One needs to ALWAYS store an entry, period. The only question is, what gets overwritten, not IF something gets overwritten. Otherwise you can "outsearch" the TT and reach a point where it doesn't help at all because you refuse to overwrite, and the stuff you are trying to store is important for future efficiency.Joost Buijs wrote:What works the best for me is:
Always overwrite entrys of an older table genereration.
And if the table generation is the same then:
Lowerbound and exact will always overwrite an existing entry if the depth >= existing depth or the existing entry is an upperbound.
Upperbounds will only overwrite upperbounds with lesser or equal depth.
So upperbounds wil never overwrite lowerbound or exact entrys from the same table generation.
I make multiple tests but in every case that HashStore() is called, I store that entry, period...