I am trying to use the alpha-beta minimax trimming algorithm to return a valid transition from my board. The algorithm returns the correct value, but I have no idea how I should return the move. In the case of this code, I would like to return the child to get_successor_stateswhen the value of bestValue is greater than the current alpha. I was thinking about returning two values ββat the end of max and min, like return bestValue, child, but I have no idea how to get this to work with other calls
def alpha_beta_pruning(board, depth, alpha, beta, isMaximizingPlayer):
if depth == 0:
return evaluate_state(board)
if isMaximizingPlayer:
bestValue = -sys.maxint - 1
bestMove = None
for child in get_successor_states(board):
temp_board = copy.deepcopy(board)
temp_board.move_queen(child[0], child[1])
temp_board.shoot_arrow(child[2])
bestValue = max(bestValue, alpha_beta_pruning(temp_board, depth-1, alpha, beta, False))
del temp_board
alpha = max(alpha, bestValue)
if beta <= alpha:
break
return bestValue
else:
bestValue = sys.maxint
for child in get_successor_states(board):
temp_board = copy.deepcopy(board)
temp_board.move_queen(child[0], child[1])
temp_board.shoot_arrow(child[2])
bestValue = min(bestValue, alpha_beta_pruning(temp_board, depth-1, alpha, beta, True))
del temp_board
beta = min(beta, bestValue)
if beta <= alpha:
break
return bestValue
source
share