4

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?

Improve this question

1 Answer 1

Reset to default
2

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.

Improve this answer
5
  • 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?
    – Miguel Silva
    Mar 25, 2021 at 12:03
  • @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.
    – koedem
    Mar 25, 2021 at 16:04
  • 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
    – Miguel Silva
    Mar 25, 2021 at 17:46
  • 1
    @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.
    – koedem
    Mar 26, 2021 at 4:18
  • thank you! i'll try to implement it!
    – Miguel Silva
    Mar 26, 2021 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.