Transposition Table for chess move generation inside minimax function

Question

Background

I am trying to optimize my minimax algorithm for chess and have so far used alpha-beta pruning. I also implemented iterative deepening for later optimization with transposition tables. What I got so far is basically this in some python code:

# Original call
def ai_make_move(gamestate):
    for depth in range(1, max_depth):
        move, evaluation = minimax(gamestate, depth, -math.inf, math.inf, maximizing_player)

# Minimax
def minimax(gamestate, depth, -math.inf, math.inf, maximizing_player):
    board.is_human_turn = not maximizing_player
    children = board.get_all_possible_moves()

    if depth == 0 or board.is_draw or board.is_check_mate:
        return None, evaluate(board)

    best_move = children[0]

    if maximizing_player:
        max_eval = -math.inf
        for child in children:
            board.make_move(child)
            current_eval = minimax(board, depth - 1, alpha, beta, False)[1]
            board.unmake_move()

            if current_eval > max_eval:
                max_eval = current_eval
                best_move = child
            alpha = max(alpha, current_eval)

            if beta <= alpha:
                break

        return best_move, max_eval

    else:
        min_eval = math.inf
        for child in children:
            board.make_move(child)
            current_eval = minimax(board, depth - 1, alpha, beta, True)[1]
            board.unmake_move()

            if current_eval < min_eval:
                min_eval = current_eval
                best_move = child
            beta = min(beta, current_eval)

            if beta <= alpha:
                break
        return best_move, min_eval

Problem

Since I have iterative deepening I thought I could take advantage of the previously calculated valid_moves (children of a position) from previous depths. So when calculating a position at depth 1 it calcs all valid moves for black in that position. When calculating at depth 2 it will start with calc the same positions valid moves for black again which seems like an unnecessary operation since I already did that in the last loop. So I should just be able to retrieve this from the saved valid_moves in the table.

I have used zobrist hashing to get an almost unique number for each position and tried to use it like this in my minimax function:

# Minimax
def minimax(gamestate, depth, -math.inf, math.inf, maximizing_player):

    if gamestate.zobrist_key in gamestate.transposition_table:
        children = gamestate.transposition_table[gamestate.zobrist_key]
    else:
        board.is_human_turn = not maximizing_player
        children = board.get_all_possible_moves()

    if depth == 0 or board.is_draw or board.is_check_mate:
        return None, evaluate(board)

   ......

For some reason, the engine makes completely irrational moves that is not legal in the current position and it doesn't seem to work.

What I have tried

I have checked that:

• My Zobrist is calculated in the correct way.
• The make_move and unmake_move functions work as they should (when playing human vs human).
• The AI seems to be working and playing good and valid moves when not having the concept of transposition tables.

Question

I can't figure out what is going wrong and if this is the rights way to proceed at all. Any guidance is highly appreciated!

Answer 1

You can't assume the evaluations the engine is making with shallower depths is accurate as the position might change the very next move with a simple capture of your queen for example. This is why instead of not calculating the previously searched move at all you can do move ordering and calculate the most promising moves from the previous iterations from the table first and more often than not alpha-beta pruning will make this faster than just searching from a fixed depth.