棋盘游戏Minimax算法实现问题：最优选择异常与评估输入疑问

第一版代码运行测试用例时，只会返回第一个可行动作，而非对应最高评估值的最优动作，无法定位问题：

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)

问题分析 #

第一版代码的核心错误是未区分最大化（黑方）和最小化（白方）玩家的逻辑：整个递归仅调用max_value，但Minimax算法要求黑方回合执行最大化操作，白方回合执行最小化操作。你试图通过翻转棋盘让白方回合复用max_value，但翻转后evaluate的得分视角仍是黑方的，白方作为最小化玩家本应让黑方得分尽可能低，这种逻辑混淆导致算法无法正确比较所有动作的评估值，最终出现只返回第一个动作的问题。

改用黑白回合分支+棋盘翻转的第二版代码通过了公开测试用例，但收到报错提示“Make sure that 'evaluate' is called with the correct input, especially for white”，已在白方回合后翻转棋盘，不理解为何仍有此问题：

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

问题分析 #

报错的核心原因是白方回合触发终止条件时，evaluate收到的棋盘视角错误：

1. 根据函数注释，evaluate是从黑方视角计算得分的，但当is_black=False（白方回合）递归到终止条件时，直接传入当前的白方视角棋盘调用evaluate，导致评估逻辑与视角不匹配。
2. 白方回合的动作处理存在冗余翻转：多次重复调用utils.invert_board，不仅浪费资源，还会导致返回的动作坐标是翻转后棋盘的坐标，未转换回原始棋盘视角，同时递归传递时的棋盘转换逻辑没有覆盖终止条件的评估环节。

修复建议 #

• 调整终止条件的评估逻辑，确保evaluate始终从黑方视角计算得分：

  if depth == max_depth or utils.is_game_over(board):
      # 白方回合终止时，翻转棋盘回到黑方视角再评估
      eval_board = utils.invert_board(board, in_place=False) if not is_black else board
      return evaluate(eval_board), None
  

• 优化白方回合的动作处理，避免重复翻转棋盘，并将动作坐标转换回原始视角：

  else:
      best_evaluation = float('inf')
      best_move = None
      inverted_board = utils.invert_board(board, in_place=False)
      board_size = len(board)
      for action in generate_valid_moves(inverted_board):
          # 复用翻转后的棋盘生成新状态
          inverted_new_board = utils.state_change(inverted_board, action[0], action[1], in_place=False)
          # 翻转回原始视角进入黑方递归
          original_new_board = utils.invert_board(inverted_new_board, in_place=False)
          opponent_evaluation, _ = minimax(original_new_board, depth + 1, max_depth, True)
          if opponent_evaluation < best_evaluation:
              best_evaluation = opponent_evaluation
              # 将翻转后的动作坐标转换回原始棋盘坐标（示例为上下翻转的转换逻辑，需根据实际翻转规则调整）
              src_row_inv, src_col_inv = action[0]
              dst_row_inv, dst_col_inv = action[1]
              original_src = (board_size - 1 - src_row_inv, src_col_inv)
              original_dst = (board_size - 1 - dst_row_inv, dst_col_inv)
              best_move = (original_src, original_dst)
      return best_evaluation, best_move
  

内容的提问来源于stack exchange，提问作者anonymous