def minimax(
board: Board,
depth: int,
max_depth: int,
is_black: bool
) -> tuple[Score, Move]:
"""
Finds the best move for the input board state.
Note that you are black.
Parameters
----------
board: 2D list of lists. Contains characters "B", "W", and "_",
representing black pawn, white pawn, and empty cell, respectively.
depth: int, the depth to search for the best move. When this is equal
to `max_depth`, you should get the evaluation of the position using
the provided heuristic function.
max_depth: int, the maximum depth for cutoff.
is_black: bool. True when finding the best move for black, False
otherwise.
Returns
-------
A tuple (evalutation, ((src_row, src_col), (dst_row, dst_col))):
evaluation: the best score that black can achieve after this move.
src_row, src_col: position of the pawn to move.
dst_row, dst_col: position to move the pawn to.
"""
def max_value(board, depth):
if utils.is_game_over(board) or depth == max_depth: #if game is over or depth is max_depth return current score
return evaluate(board), None # Return v along with action
v = float('-inf')
best_action = None # Initialize best action
for action in generate_valid_moves(board): #for each action in valid moves
next_board = utils.state_change(board, action[0], action[1], False) #generate next state
next_board = utils.invert_board(next_board, False) #invert the board for the white turns(because all the function is applied for black), so invert board will flip the board and turn white to black
score, _ = max_value(next_board, depth + 1) #get the score for the next state
if score > v:
v = score
best_action = action # Update best action
return v, best_action
return max_value(board, depth)
我已经try 实现了一个最小最大算法,以获得最优的移动为黑色或白色与最大深度.当我用我的测试用例运行它时,它只返回第一个操作,而不是产生所有操作中最高判断的最佳操作.我在代码中找不到问题所在.
def minimax(
board: Board,
depth: int,
max_depth: int,
is_black: bool
) -> tuple[Score, Move]:
"""
Finds the best move for the input board state.
Note that you are black.
Parameters
----------
board: 2D list of lists. Contains characters "B", "W", and "_",
representing black pawn, white pawn, and empty cell, respectively.
depth: int, the depth to search for the best move. When this is equal
to `max_depth`, you should get the evaluation of the position using
the provided heuristic function.
max_depth: int, the maximum depth for cutoff.
is_black: bool. True when finding the best move for black, False
otherwise.
Returns
-------
A tuple (evalutation, ((src_row, src_col), (dst_row, dst_col))):
evaluation: the best score that black can achieve after this move.
src_row, src_col: position of the pawn to move.
dst_row, dst_col: position to move the pawn to.
"""
if depth == max_depth or utils.is_game_over(board):
return evaluate(board), None
# Determine the best move and its evaluation
if is_black:
best_evaluation = float('-inf')
best_move = None
for action in generate_valid_moves(board):
new_board = utils.state_change(board, action[0], action[1], in_place=False)
opponent_evaluation, _ = minimax(new_board, depth + 1, max_depth, False)
if opponent_evaluation > best_evaluation:
best_evaluation = opponent_evaluation
best_move = (action[0], action[1])
return best_evaluation, best_move
else:
best_evaluation = float('inf')
best_move = None
for action in generate_valid_moves(utils.invert_board(board, in_place=False)):
new_board = utils.state_change(utils.invert_board(board, in_place=False), action[0], action[1], in_place=False)
opponent_evaluation, _ = minimax(utils.invert_board(new_board, in_place=False), depth + 1, max_depth, True)
if opponent_evaluation < best_evaluation:
best_evaluation = opponent_evaluation
best_move = (action[0], action[1]) # Convert from black's perspective to white's
return best_evaluation, best_move
我只是try 了一种不同的方法,其中切换情况时每次黑白,通过使用内部实现倒置表.所以它基本上通过了解决方案的公共测试用例,但它遇到了这样的问题:"确保使用正确的输入调用‘EVALUATE’,特别是对于白人",我不明白为什么?我认为我的判断正确地判断了白色和黑色,因为我在白色转弯后颠倒了黑板.