user27097: 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?

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

27097: <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>
 24693: <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>
