Transposition Table - Replacement and PV

[Cheney]

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

[lucasart]

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

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

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

[Steve Maughan]

Hi Cheney,

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

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

[Joost Buijs]

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.

[tpetzke]

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

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

[syzygy]

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

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

I agree it is (much) better to replace, but fine #70 can be solved either way in my experience.

[Cheney]

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.

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
}

I'll try this out, thanks again

[elpapa]

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.

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
}

I'll try this out, thanks again

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?

[lucasart]

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

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

Well then I must be lucky! Solved in 5.79 seconds, running 1 thread on a rather 4 year old PC:

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

So what do you propose exactly: always overwrite ?

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
}

[bob]

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

I make multiple tests but in every case that HashStore() is called, I store that entry, period...