title: Transposition table causes chess engine to lose
body: <p>Prelude: I understand this question may be a little too broad for the likes of Stack Overflow. Although, I tried to add as much information as I could come up with.</p>
  
  <p>I'm coding a chess engine in C++ from scratch, and it's mostly done (except that it has a weak evaluation function). What is weird though is that the engine loses every single time the transposition table is enabled, by an amazingly obvious blunder (gives away a queen, or sometimes a queen and another piece). When the transposition table probing is disabled, the engine wins easily against both Nero and TSCP.</p>
  
  <p>I use a very simple transposition table implementation with an always-replace scheme, taken from Bruce Morland's site <a href="http://web.archive.org/web/20080315233307/http://www.seanet.com/~brucemo/topics/hashing.htm" rel="nofollow noreferrer">here</a>.</p>
  
  <p>Here's the probe implementation:</p>
  
  <pre><code>bool probe_table(TranspositionTable&amp; t_table, unsigned int ply,
  uint64 hash_key, unsigned int depth, unsigned int&amp; pv_move, int&amp; score,
  int alpha, int beta)
  {
      unsigned int index = hash_key % t_table.num_entries;
  
      assert(index &lt; t_table.num_entries);
  
      if(t_table.t_entry[index].hash_key == hash_key)
      {
          pv_move = t_table.t_entry[index].move;
  
          if(t_table.t_entry[index].depth &gt;= depth)
          {
              score = t_table.t_entry[index].score;
  
              if(score &gt; IS_MATE) score -= ply;
              else if(score &lt; -IS_MATE) score += ply;
  
              switch(t_table.t_entry[index].flag)
              {
                  case TFALPHA:
                  {
                      if(score &lt;= alpha)
                      {
                          score = alpha;
                          return 1;
                      }
                  }
                  case TFBETA:
                  {
                      if(score &gt;= beta)
                      {
                          score = beta;
                          return 1;
                      }
                  }
                  case TFEXACT:
                  {
                      return 1;
                  }
                  default: assert(false); // At least one flag must be set.
              }
          }
      }
  
      return 0;
  }
  </code></pre>
  
  <p>During alpha-beta search, the table is probed (the entries are stored correctly as well, depending on cutoffs and such):</p>
  
  <pre><code>if(probe_table(board.t_table, board.ply, board.hash_key, depth, pv_move,
      score, alpha, beta))
  {
      return score;
  }
  </code></pre>
  
  <p><strong>Edit</strong>: For completeness, here's a snippet of the important bits of storing code in search:</p>
  
  <pre><code>if(score &gt; alpha) // Alpha cutoff.
  {
      if(score &gt;= beta) // Beta cutoff.
      {
          ...
  
          store_entry(board.t_table, board.ply, board.hash_key, best_move,
                      beta, depth, TFBETA);
  
          return beta;
      }
  
      alpha = score;
  
      ...
      }
  }
  
  ...
  
  assert(alpha &gt;= old_alpha);
  
  if(alpha != old_alpha)
  {
      store_entry(board.t_table, board.ply, board.hash_key, best_move,
          best_score, depth, TFEXACT);
  }
  else
  {
      store_entry(board.t_table, board.ply, board.hash_key, best_move,
          alpha, depth, TFALPHA);
  }
  </code></pre>
  
  <p>I have considered and explored failures in every other part of the engine, and none is happening. Disabling the probing entirely (but still using the table to store PV lines), works beautifully.</p>
  
  <p>I also considered whether my naive implementation of pondering was affecting things. To ponder, I simply print out <code>bestmove xxxx ponder xxxx</code> to UCI whenever a ponder move is available. If pondering is enabled, the GUI lets the engine ponder (which is just a regular search, but will be later used by means of the transposition table).</p>
  
  <p>To test, I disabled pondering entirely, which did not show any improvement. After having a winning score for a while, the engine simply gave away its queen. I believe this is happening either due to some bad entry in the table, or perhaps some other sort of instability that I'm unable to comprehend.</p>
  
  <p>And this is where I need somebody who has run into this before to point me into a general direction.</p>
  
  <p><strong>Edit</strong>: As grek40 asked, here's an example that just took place (the engine is white, white to move):</p>
  
  <p><a href="https://i.stack.imgur.com/dVDOb.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/dVDOb.jpg" alt="Position"></a></p>
  
  <p>The engine one again, lost the game based on stupid moves. Please note that the engine reached a bad position such as this one probably because of the transposition table itself.</p>
  
  <p>Analysing this position <strong><em>with</em></strong> the transposition table filled during the game:</p>
  
  <pre><code>info score cp -425 depth 1 nodes 1 time 0 pv e1d1
  info score cp -425 depth 2 nodes 2 time 0 pv e1d1
  info score cp -425 depth 3 nodes 3 time 0 pv e1d1
  info score cp -425 depth 4 nodes 4 time 0 pv e1d1
  info score cp -425 depth 5 nodes 5 time 0 pv e1d1
  info score cp -425 depth 6 nodes 6 time 0 pv e1d1
  info score cp -425 depth 7 nodes 7 time 0 pv e1d1
  info score cp -425 depth 8 nodes 8 time 0 pv e1d1
  info score cp -425 depth 9 nodes 9 time 0 pv e1d1
  info score cp -425 depth 10 nodes 10 time 0 pv e1d1
  info score cp -440 depth 11 nodes 10285162 time 3673 pv f5f8 e7f8 b2b3 b7b5 e1c1 d6d5 a3a4
  info score cp -440 depth 12 nodes 29407669 time 10845 pv f5f8 e7f8 e1f1 f8e7 f1f5 d6d5
  bestmove f5f8 ponder e7f8
  </code></pre>
  
  <p>Analysing once again <strong><em>without</em></strong> the transposition table (actually, with the table, but cleared):</p>
  
  <pre><code>info score cp -415 depth 1 nodes 82 time 0 pv f5f8
  info score cp -415 depth 2 nodes 200 time 0 pv f5f8 e7f8
  info score cp -405 depth 3 nodes 900 time 0 pv f5f8 e7f8 b2b3
  info score cp -425 depth 4 nodes 2936 time 1 pv f5f8 e7f8 b2b3 f8e7
  info score cp -415 depth 5 nodes 10988 time 4 pv f5f8 e7f8 b2b3 b7b5 e1d1
  info score cp -425 depth 6 nodes 65686 time 25 pv f5f8 e7f8 e1f1 d7e7 f1d1 b7b5
  info score cp -420 depth 7 nodes 194124 time 76 pv f5f8 e7f8 b2b3 b7b5 e1f1 f8e7 f1f7
  info score cp -425 depth 8 nodes 357753 time 141 pv f5f8 e7f8 b2b3 b7b5 e1f1 f8e7 f1f5 d7c7
  info score cp -425 depth 9 nodes 779686 time 292 pv f5f8 e7f8 e1f1 f8e7 f1f5 h4h8
  info score cp -425 depth 10 nodes 1484178 time 560 pv f5f8 e7f8 e1f1 f8e7 f1f5 h4h8
  info score cp -435 depth 11 nodes 29481132 time 11117 pv f5f8 d6d5 e1e5
  info score cp -435 depth 12 nodes 106448053 time 41083 pv f5f8 e7f8
  bestmove f5f8 ponder e7f8
  </code></pre>
  
  <p>It's noteworthy that on depth <code>10</code>, the score is accurate from the transposition table search.</p>
  
  <p><strong>Edit</strong>: This position was analysed after the game. During the game, the engine did not have enough time to complete the search to a higher depth, resulting in it playing <code>e1d1</code>, which is ridiculous.</p>
  
  <p>Why would this even happen? The engine finds a better move since depth 1, but a different move was found from the transposition table. I also wonder why there is no PV line in the transposition table search.</p>
  
  <p><strong><em>My best guess</em></strong> would be the search instability quote from Bruce Morland's site here: The Zobrist key does not take into account the path taken to get to a node.  Not every path is the same.  It is possible that the score in a hash element might be based upon a path that would contain a repetition if encountered at some other point in the tree.  A repetition might result in a draw score, or at least a different score.</p>
  
  <p><strong>Edit</strong>: I tried disabling storing to the table when there is no TFEXACT value. That is, I stopped storing and retrieving TFALPHA/TFBETA values and it works beautifully. Does anybody know why?</p>