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!