Answers.Body: <p>I am not sure I understand your exact code but my guess here is that you return a transposition table result, no matter the depth of the entry. So if you encounter a position and calculate it one ply deep, store it in the transposition table, and then the next iteration you want to search two plies deep but instead retrieve a one ply deep evaluation from the transposition table. The way around this is to store the depth in the transposition table entry and then only accept an entry if its depth is greater or equal than the required depth.</p>
  <p>Another issue to take note of is that with an alpha beta search, for most nodes you won't know the exact evaluation, only an upper or lower bound. So if you store something in the transposition table you also have to remember whether the evaluation is an upper or lower bound, and then when retrieving have logic accordingly.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-25T12:03:19.560Z
Answers.Text: I've implemented some flags on my transposition tables to check whether its an upper or lower bound and program now achieves the correct result more often, or one pretty much similar to the optimal. The thing is, when iterative deepening, after a shallow iteration, I clean the transposition table. You're suggesting me to keep those values? How would I use them if after every iteration the search gets deeper?
Answers.UserDisplayName: Miguel Silva
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-25T16:04:07.507Z
Answers.Text: @MiguelSilva the trick about the transposition table is you can reach them through different move orders. That can also mean different depths. Consider for instance 1.d4 d5, or 1.d3 d6 2.d4 d5. Those are the same position, but searching from the starting position one will have more depth left than the other. Keeping the 1.d4 d5 entry can then help for the second line even at a deeper iteration. What if the depth is not high enough? Then you can still use the move information, i.e. search the expected best move first as to improve the move ordering.
Answers.UserDisplayName: koedem
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-25T17:46:06.197Z
Answers.Text: I've been helding a record for the best move found each search. That way, the pruning becomes more agressive when I evaluate it first as you said, by improving my move ordering. I still cant grasp the concept of different depths though. Lets say, by iterative deepening, I find one position in a evaluation of depth 3. In the next iteration, in a search of depth 4, I encounter that same position once again. Why would I care about a shallow search result? Sorry if im missing the point
Answers.UserDisplayName: Miguel Silva
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-26T04:18:28.417Z
Answers.Text: @MiguelSilva well, you will presumably only record the best variation for each search, not the best move for each position searched? (the latter case is exactly a transposition table) So the TT might for instance also hold the "refutation" of the second best move, something that you would not otherwise store. So you can search that move first when looking at the second best move. 
  Plus, as given in the example, even at a deeper iteration you can still encounter the same position at a shallower depth.
Answers.UserDisplayName: koedem
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-26T19:28:09.867Z
Answers.Text: thank you! i'll try to implement it!
Answers.UserDisplayName: Miguel Silva
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-23T01:34:31.753Z
Answers.LastActivityDate: 2021-03-23T01:34:31.753Z
Answers.UserDisplayName: koedem
Body: <p>I've been writing my chess engine for 2 months now, and I've come across this bug that I can't manage to solve. Basically, when I disable my transposition table, the engine plays fine and the minimax search selects one of the best options every time. With that said, when I enable them once again, it results in the selection of different moves than the optimal, which should not be happening (as their purpose is efficiency oriented).</p>
  <pre><code>    if maximizing_player:
          
          max_eval = -1*10**5
  
          for state in possible_states:
              
              node+= 1
              eval = hawkins.minimax(self, state, depth-1, alpha, beta, False, castling_chance, last_move, quiet)
              if eval[0] &gt; max_eval:
                  max_eval = eval[0]
                  chosen = state
              alpha = max(alpha, eval[0])
              if beta &lt;= alpha:
                  cut += 1
                  break
          transposition_table[mx] = (max_eval, chosen)
          return (max_eval, chosen)
  
      else:
  
          min_eval = 1*10**5
  
          for state in possible_states:
              node += 1
              eval = hawkins.minimax(self, state, depth-1, alpha, beta, True, castling_chance, last_move, quiet)
              if eval[0] &lt; min_eval:
                  min_eval = eval[0]
                  chosen = state
              beta = min(beta, eval[0])
              if beta &lt;= alpha:
                  cut += 1
                  break
          transposition_table[mx] = (min_eval, chosen)
          return (min_eval, chosen)
  </code></pre>
  <p>This is a simple minimax search implementation. When the depth reaches zero, I have a separate call to return a static evaluation. With that said, in my mind, I'm recording the best move possible and its score into a transposition table that has &quot;mx&quot; (the string that contains my game state) as a key. A little bit above the code snippet embedded, I wrote the following:</p>
  <pre><code>        if mx in transposition_table.keys():
  
          return transposition_table[mx]
  </code></pre>
  <p>So when we would find our &quot;mx&quot; once again, it would not spend resources trying to the best move possible. Could you please help me find what wrong with my implementation?</p>
  
Tags: <engines><transpositions>
Title: Transposition Tables Bug, implementation produces different results
ThreadText: # Transposition Tables Bug, implementation produces different results
  
  (Asked by: username_0 on 2021-03-22)
  
  I've been writing my chess engine for 2 months now, and I've come across this bug that I can't manage to solve. Basically, when I disable my transposition table, the engine plays fine and the minimax search selects one of the best options every time. With that said, when I enable them once again, it results in the selection of different moves than the optimal, which should not be happening (as their purpose is efficiency oriented).
  
  ```
      if maximizing_player:
          
          max_eval = -1*10**5
  
          for state in possible_states:
              
              node+= 1
              eval = hawkins.minimax(self, state, depth-1, alpha, beta, False, castling_chance, last_move, quiet)
              if eval[0] > max_eval:
                  max_eval = eval[0]
                  chosen = state
              alpha = max(alpha, eval[0])
              if beta <= alpha:
                  cut += 1
                  break
          transposition_table[mx] = (max_eval, chosen)
          return (max_eval, chosen)
  
      else:
  
          min_eval = 1*10**5
  
          for state in possible_states:
              node += 1
              eval = hawkins.minimax(self, state, depth-1, alpha, beta, True, castling_chance, last_move, quiet)
              if eval[0] < min_eval:
                  min_eval = eval[0]
                  chosen = state
              beta = min(beta, eval[0])
              if beta <= alpha:
                  cut += 1
                  break
          transposition_table[mx] = (min_eval, chosen)
          return (min_eval, chosen)
  
  ```
  
  This is a simple minimax search implementation. When the depth reaches zero, I have a separate call to return a static evaluation. With that said, in my mind, I'm recording the best move possible and its score into a transposition table that has "mx" (the string that contains my game state) as a key. A little bit above the code snippet embedded, I wrote the following:
  
  ```
          if mx in transposition_table.keys():
  
          return transposition_table[mx]
  
  ```
  
  So when we would find our "mx" once again, it would not spend resources trying to the best move possible. Could you please help me find what wrong with my implementation?
  
  **Tags:** engines, transpositions
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-03-23. Score: 2 | Accepted answer
  
  I am not sure I understand your exact code but my guess here is that you return a transposition table result, no matter the depth of the entry. So if you encounter a position and calculate it one ply deep, store it in the transposition table, and then the next iteration you want to search two plies deep but instead retrieve a one ply deep evaluation from the transposition table. The way around this is to store the depth in the transposition table entry and then only accept an entry if its depth is greater or equal than the required depth.
  
  Another issue to take note of is that with an alpha beta search, for most nodes you won't know the exact evaluation, only an upper or lower bound. So if you store something in the transposition table you also have to remember whether the evaluation is an upper or lower bound, and then when retrieving have logic accordingly.
  
  > **Comments:**
  > **username_0**: I've implemented some flags on my transposition tables to check whether its an upper or lower bound and program now achieves the correct result more often, or one pretty much similar to the optimal. The thing is, when iterative deepening, after a shallow iteration, I clean the transposition table. You're suggesting me to keep those values? How would I use them if after every iteration the search gets deeper?  
  > **username_1**: @username_0 the trick about the transposition table is you can reach them through different move orders. That can also mean different depths. Consider for instance 1.d4 d5, or 1.d3 d6 2.d4 d5. Those are the same position, but searching from the starting position one will have more depth left than the other. Keeping the 1.d4 d5 entry can then help for the second line even at a deeper iteration. What if the depth is not high enough? Then you can still use the move information, i.e. search the expected best move first as to improve the move ordering.  
  > **username_0**: I've been helding a record for the best move found each search. That way, the pruning becomes more agressive when I evaluate it first as you said, by improving my move ordering. I still cant grasp the concept of different depths though. Lets say, by iterative deepening, I find one position in a evaluation of depth 3. In the next iteration, in a search of depth 4, I encounter that same position once again. Why would I care about a shallow search result? Sorry if im missing the point  
  > **username_1**: @username_0 well, you will presumably only record the best variation for each search, not the best move for each position searched? (the latter case is exactly a transposition table) So the TT might for instance also hold the "refutation" of the second best move, something that you would not otherwise store. So you can search that move first when looking at the second best move.  Plus, as given in the example, even at a deeper iteration you can still encounter the same position at a shallower depth.  
  > **username_0**: thank you! i'll try to implement it!  
  
  ---
  
  