Transposition Table

[Pablo Vazquez]

Hi,

I'm implementing a transposition table in my program and I am running into a few problems:

1-If I get a hit in the root, I return without a move. What I do now is that I check if the search returned an empty pv, and if so, I check the root position in the hash and return the corresponding move. I don't know if this is the correct way to do things, I heard that some programs look for the end of the pv (whether it is empty or not) and start adding moves as long as there are hash hits. Another solution is not to probe at the root. Another one that I have also heard about is not probing on pv nodes.

2-In a game, my engine was winning but it decided to repeat moves because it got hits at the root and couldn't see the repetition as there was no search. Any solutions to this?

Thanks

[MattieShoes]

Hi,

I'm implementing a transposition table in my program and I am running into a few problems:

1-If I get a hit in the root, I return without a move. What I do now is that I check if the search returned an empty pv, and if so, I check the root position in the hash and return the corresponding move. I don't know if this is the correct way to do things, I heard that some programs look for the end of the pv (whether it is empty or not) and start adding moves as long as there are hash hits. Another solution is not to probe at the root. Another one that I have also heard about is not probing on pv nodes.

2-In a game, my engine was winning but it decided to repeat moves because it got hits at the root and couldn't see the repetition as there was no search. Any solutions to this?

Thanks

1) You definitely want to probe hash at the root and other PV nodes, for move ordering if nothing else. Those are the exact nodes where move ordering is so crucial!

You can crawl the hash following best moves to generate a PV if you really want one.

I unrolled the root search at 0 ply from the rest of search so I could do different things there -- For instance, it doesn't generate moves again, remembers move scores from previous iterations, etc.

2) Check for a repetition and return draw score before ever probing hash.

[Pablo Vazquez]

Hi,

I'm implementing a transposition table in my program and I am running into a few problems:

1-If I get a hit in the root, I return without a move. What I do now is that I check if the search returned an empty pv, and if so, I check the root position in the hash and return the corresponding move. I don't know if this is the correct way to do things, I heard that some programs look for the end of the pv (whether it is empty or not) and start adding moves as long as there are hash hits. Another solution is not to probe at the root. Another one that I have also heard about is not probing on pv nodes.

2-In a game, my engine was winning but it decided to repeat moves because it got hits at the root and couldn't see the repetition as there was no search. Any solutions to this?

Thanks

1) You definitely want to probe hash at the root and other PV nodes, for move ordering if nothing else. Those are the exact nodes where move ordering is so crucial!

You can crawl the hash following best moves to generate a PV if you really want one.

I unrolled the root search at 0 ply from the rest of search so I could do different things there -- For instance, it doesn't generate moves again, remembers move scores from previous iterations, etc.

2) Check for a repetition and return draw score before ever probing hash.

Hi Matt,

I forgot to mention that currently, I only use the hash for cutoffs, not for move ordering.

I do check for repetition before probing the hash.

I've seen that all strong engines don't use the hash score for a cutoff at the root (maybe they do for move ordering) and I would like to know why.I don't clear hash between moves and sometimes, the first few iterations are all cutoffs at the root.

Maybe I have bugs, heres my code:

Code: Select all

int TransRetrieve(U64 key, int *move, int *score, int alpha, int beta, int depth, int ply)
{
  ENTRY *entry;

  entry = tt + (key & MASK);
  if (entry->key == key) {
    if (entry->depth >= depth) {
      if (&#40;entry->flags == UPPER && entry->score <= alpha&#41; ||
          &#40;entry->flags == LOWER && entry->score >= beta&#41; ||
          &#40;entry->flags == EXACT&#41;) &#123;
        if &#40;entry->score >= MATE_SCORE&#41;
          *score = entry->score - ply;
        else if &#40;entry->score <= -MATE_SCORE&#41;
          *score = entry->score + ply;
        else
          *score = entry->score;
        return 1;
      &#125;
    &#125;
    *move = entry->move;
  &#125;
  return 0;
&#125;

void TransStore&#40;U64 key, int move, int score, int flags, int depth, int ply&#41;
&#123;
  ENTRY *entry;

  entry = tt + &#40;key & MASK&#41;;
  if &#40;move || entry->key != key&#41;
    entry->move = move;
  if &#40;score >= MATE_SCORE&#41;
    entry->score = score + ply;
  else if &#40;score <= -MATE_SCORE&#41;
    entry->score = score - ply;
  else
    entry->score = score;
  entry->flags = flags;
  entry->depth = depth;
  entry->key = key;
&#125;
int Search&#40;)
&#123;
  ...
  if &#40;RepCheck&#40;))
    return 0;
  if &#40;TransRetrieve&#40;p->key, &move, &score, alpha, beta, depth, ply&#41;)
    return score;
  o_alpha = alpha;
  while (&#40;move = NextMove&#40;))) &#123;
   score = -Search&#40;);
    if &#40;score >= beta&#41; &#123;
      TransStore&#40;p->key, move, beta, LOWER, depth, ply&#41;;
      return beta;
    &#125;
    if &#40;score > alpha&#41;
      alpha = score;
  &#125;
  if &#40;alpha > o_alpha&#41;
    TransStore&#40;p->key, pv&#91;0&#93;, alpha, EXACT, depth, ply&#41;;
  else
    TransStore&#40;p->key, 0, alpha, UPPER, depth, ply&#41;;
  return alpha;
&#125;

[Sven]

Hi,

I'm implementing a transposition table in my program and I am running into a few problems:

1-If I get a hit in the root, I return without a move. What I do now is that I check if the search returned an empty pv, and if so, I check the root position in the hash and return the corresponding move. I don't know if this is the correct way to do things, I heard that some programs look for the end of the pv (whether it is empty or not) and start adding moves as long as there are hash hits. Another solution is not to probe at the root. Another one that I have also heard about is not probing on pv nodes.

2-In a game, my engine was winning but it decided to repeat moves because it got hits at the root and couldn't see the repetition as there was no search. Any solutions to this?

Thanks

First of all: how can you "return without a move" in this case? Do you have iterative deepening and time control, or do you just start one tree search with a fixed depth? With iterative deepening you should never run into this case, I think. If the root position is stored in the hash with search depth N then the first N iterations will terminate quickly with your algorithm but then iteration N+1 can't use the hash anymore for the root node and will perform a real search.

Since you report different behaviour one could assume that you do *not* use iterative deepening.

Regarding repetition detection: do you return a draw score already when detecting the first repetition of a node that belongs to the current tree search (i.e., second occurrence), or only on the second repetition (third occurrence) which is the final draw by FIDE rules? Doing it already for the first repetition has advantages, and if you don't do this yet you should try at least.

And it might also fix your problem, for this reason: Currently you may have the case that your engine "knows" (during the previous search that visits the position occurring later on in the game) that it can win with move M2 but move M1 leads to repetition of the current position where M2 is possible again, so for M1 it returns the same score that is returned for M2, and it therefore considers M1 and M2 to be equal, so it is possible that it stores M1 in the hash which causes the problem later on.

This does not yet answer your question why top engines don't probe hash at the root node (I assume this is true, I did not check it). So I guess there is even more trouble that can be avoided by not probing there.

Sven

[hgm]

I do probe hash in the root in uMax. I just suppress the cutoffs.

There are strong engines that do not cutoff in any PV node, and this would automatically include the root.

[Sven]

This does not yet answer your question why top engines don't probe hash at the root node (I assume this is true, I did not check it). So I guess there is even more trouble that can be avoided by not probing there.

I can imagine it is due to the 50 moves rule which is a similar issue as repetition (see my post above) and which obviously can't be fixed without doing a search of at least one ply.

Consider you store a score S > 0 and a best move M1 for an endgame position P in the hash. Later on, in the game you encounter this position through a different path and the 50 moves counter is now quite high. The hash tells you the position is won by making M1 based on a different 50 moves counter at that time, so your engine makes M1 and the opponent can play into the 50 moves draw.

This won't happen if you do a real search since you would most probably find a move M2 that also wins but avoids the 50 moves draw.

Sven

[Pablo Vazquez]

Hi,

I'm implementing a transposition table in my program and I am running into a few problems:

1-If I get a hit in the root, I return without a move. What I do now is that I check if the search returned an empty pv, and if so, I check the root position in the hash and return the corresponding move. I don't know if this is the correct way to do things, I heard that some programs look for the end of the pv (whether it is empty or not) and start adding moves as long as there are hash hits. Another solution is not to probe at the root. Another one that I have also heard about is not probing on pv nodes.

2-In a game, my engine was winning but it decided to repeat moves because it got hits at the root and couldn't see the repetition as there was no search. Any solutions to this?

Thanks

First of all: how can you "return without a move" in this case? Do you have iterative deepening and time control, or do you just start one tree search with a fixed depth? With iterative deepening you should never run into this case, I think. If the root position is stored in the hash with search depth N then the first N iterations will terminate quickly with your algorithm but then iteration N+1 can't use the hash anymore for the root node and will perform a real search.

Since you report different behaviour one could assume that you do *not* use iterative deepening.

Regarding repetition detection: do you return a draw score already when detecting the first repetition of a node that belongs to the current tree search (i.e., second occurrence), or only on the second repetition (third occurrence) which is the final draw by FIDE rules? Doing it already for the first repetition has advantages, and if you don't do this yet you should try at least.

And it might also fix your problem, for this reason: Currently you may have the case that your engine "knows" (during the previous search that visits the position occurring later on in the game) that it can win with move M2 but move M1 leads to repetition of the current position where M2 is possible again, so for M1 it returns the same score that is returned for M2, and it therefore considers M1 and M2 to be equal, so it is possible that it stores M1 in the hash which causes the problem later on.

This does not yet answer your question why top engines don't probe hash at the root node (I assume this is true, I did not check it). So I guess there is even more trouble that can be avoided by not probing there.

Sven

Hi Sven,

I use iterative deepening, and what happens is exactly what you say, first n iterations get a cut and from n + 1 on, the search goes normally, the problem is that sometimes there is no time to finish depth n + 1.

Regarding repetition, I currently don't keep track of the fifty move rule. I score the first repetition as a draw, I don't wait for a second. And I only consider repetitions inside the tree.

[adams161]

I don't know if this is another one of pulsars cheap tricks but its allways seemed to work for me ( i make this comment in regard to you knowing from hash a depth X search but have no time for a depth X + 1 search).

If my best move after completing a depth X search is e4, in searching depth x+1 i search e4 first. This requires a root order function to make sure the last depths best move is ordered first. I actually apply this root ordering a little deper and if a X-1 or X-2 search had an even different move it would be ordered seocnd and third at the root etc.

Now here is why i do that. If depth X move e4 was best and depth X+1 plays e4 first, and it completes the move i know e4s score at depth X+1. There may be 40 moves at the root. I now try depth X+1 's root second move and if time the third move, if i'm lucky i try all 40. but here is the draw to this method for me. Lets say i fully complete the first 3 moves at depth X+1 and abort search in the middle of root move 4. Well if i threw away that partial search i'd be playing the move i searched first ( e4) anyway since it was the best at depth X. but i know the scores for both the first, second and third moves. I can compare move 2 and move 3 against e4 and choose to play them over e4 ( say that move cracks at the next highest depth).

I dont know the best move at depth X+1 yet because i only have 3 moves searched. But i do know the score of the move i woudl play by default if i threw away the search, and two other moves so i can find the comparativly best move of the 3 moves.

Mike