棋盘游戏的Minimax函数

Question

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)

我尝试实现最小最大算法来获得最大深度的黑色或白色的最佳运动。当我用我的测试用例运行它时，它只返回第一个操作，而不是最佳操作，这会导致所有操作中评价最高。我无法找出代码中的问题..

Answer 1

假设你调用的函数都是正确的（如

invert_board

，...），仍然存在这个问题：

虽然棋盘是颠倒的，但你并没有颠倒分数。对白色有利的对黑色不利，反之亦然，所以你应该反转分数。

我会改变这个：

score, _ = max_value(next_board, depth + 1)

对此：

score = -max_value(next_board, depth + 1)[0]

一些不相关的评论：

• 我会让

  depth

  倒数而不是向上倒数。这样您就可以与 0 进行比较（对于基本情况），并且不需要在此函数中访问

  max_depth

  。然后，初始调用者应传递

  max_depth

  作为参数。

• invert_board

  可能会对运行时间产生相当大的负面影响。一旦你开始工作，你可以通过让所有函数（如

  evaluate

  ）意识到轮到谁，并让它们从该玩家的角度返回一个值来提高性能。

• 与上述观点相关：您的函数上方的代码注释提到了

  is_black

  ，但目前尚未实现。

• state_change

  也可能对运行时间产生负面影响。如果是这样，您可以通过 mutating

  board

  来改进（因此不要制作副本），然后创建一个可以执行先前移动的 undo 的函数。您可以在进行递归调用后调用它。

• 基本情况

  if

  语句可以以相反的顺序执行两个条件：这将在达到最大深度时节省您对

  is_game_over

  的调用。

• 与此相关：

  is_game_over

  还可以在游戏结束时返回评价分数。所以它可以返回一个分数（表示游戏结束）或

  None

  （表示游戏尚未结束）。这可以用来保存对

  evaluate

  的单独调用，这可能需要再次执行相同的游戏结束检查。

• 考虑实施alpha-beta剪枝：它可能有助于减少要分析的状态数量，同时仍然确保返回相同的分数。