Connect4游戏Minimax算法AI错失直接获胜步的问题排查

问题现象 #

• Connect4 AI存在异常：有时会跳过直接获胜的步骤，刻意避开即时胜利操作，虽最终仍能取胜，但不符合Minimax算法逻辑——按算法设计，AI应识别出能得到math.inf最大值的获胜列并直接选择。
• 该AI模型无法通过隐藏测试，我已先后改写三个版本的Minimax代码，问题均未解决。

尝试过的Minimax代码版本 #

版本1 #

yer):
    global COUNT
    COUNT += 1

    opponent = HUMAN if player == AI else AI
    valid_columns = get_valid_columns(board)
    is_terminal = is_terminal_node(board)
    if depth == 0 or is_terminal:
    ### [TODO-1]
        '''
        If the depth is 0 (depth limit has been reached) or
        the node is terminal (indicating a win, lose, or tie state),
        the function returns the (heuristic) value of the node returned by `evaluate_position`.
        '''
        ########### TODO-1: Your code here ###########

        if do_max:
          maxizer = player
          minimizer = opponent
        else:
          maxizer = opponent
          minimizer = player
        if is_terminal:
          if winning_move(board, maxizer):
            value = 1000000
          elif winning_move(board, minimizer):
            value = -1000000
          else:
            value = 0
        else:
          value = evaluate_position(board, maxizer)
        column =  valid_columns[0] if valid_columns else None


        ########### End of your code ###########
        return column, value

    else:
        value = -1000000 if do_max else 1000000
        column = valid_columns[0] if valid_columns else None

        ### [TODO-2]
        '''
        Minimax is a recursive function that explores the game tree to find the best move.
        It alternates between maximizing and minimizing the score based on the current player.
        Here, if 'do_max' is True, function 'minimax' should do maximizing, otherwise it should do minimizing.
        And 'player' refers to the current player that will drop a disc this turn and be evaluated by 'minimax'.
        '''
        ########### TODO-2: Your code here ###########
        for col in valid_columns:
            row = get_curr_row_by_col(board,col)
            drop_disc(board, col, player)
            new_score = minimax(board, depth-1, not do_max, opponent)[1]
            board[row][col] = 0

            if do_max:
                if new_score > value:
                    value = new_score
                    column = col
            else:
                if new_score < value:
                    value = new_score
                    column = col

        ######### End of your code ###########
        return column, value

版本2（尝试在胜利时直接判定终止节点） #

def minimax(board, depth, do_max, player):  #version with instant terminal while win
    global COUNT
    COUNT += 1

    opponent = HUMAN if player == AI else AI
    valid_columns = get_valid_columns(board)
    is_terminal = is_terminal_node(board)
    if depth == 0 or is_terminal:
    ### [TODO-1]
        '''
        If the depth is 0 (depth limit has been reached) or
        the node is terminal (indicating a win, lose, or tie state),
        the function returns the (heuristic) value of the node returned by `evaluate_position`.
        '''
        ########### TODO-1: Your code here ###########

        if is_terminal:
          if winning_move(board, AI):
            value = 1000000
          elif winning_move(board, HUMAN):
            value = -1000000
          else:
            value = 0
        else:
            value = evaluate_position(board, AI)
        column =  None



        ########### End of your code ###########
        return column, value

    else:
        value = -math.inf if do_max else math.inf
        column = valid_columns[0] if valid_columns else None

        ### [TODO-2]
        '''
        Minimax is a recursive function that explores the game tree to find the best move.
        It alternates between maximizing and minimizing the score based on the current player.
        Here, if 'do_max' is True, function 'minimax' should do maximizing, otherwise it should do minimizing.
        And 'player' refers to the current player that will drop a disc this turn and be evaluated by 'minimax'.
        '''
        ########### TODO-2: Your code here ###########

        for col in valid_columns:
            row = get_curr_row_by_col(board,col)
            drop_disc(board, col, player)

            new_score = minimax(board, depth-1, not do_max, opponent)[1]
            board[row][col] = 0

            if do_max:
                if new_score > value:
                    value = new_score
                    column = col
            else:
                if new_score < value:
                    value = new_score
                    column = col

        ######### End of your code ###########
        return column, value

版本3 #

def minimax(board, depth, do_max, player):
    global COUNT
    COUNT += 1

    opponent = HUMAN if player == AI else AI
    valid_columns = get_valid_columns(board)
    is_terminal = is_terminal_node(board)
    if depth == 0 or is_terminal:

        # value = 0
        # if is_terminal:
        #     if winning_move(board, player):
        #         value = 1000000 if do_max else -1000000
        #     elif winning_move(board, opponent):
        #         value = -1000000 if do_max else 1000000
        #     else:  # 平局
        #         value = 0
        # else:

        #     value = evaluate_position(board, AI)

        # column = valid_columns[0] if valid_columns else None
        # return column, value
        if depth == 0 or is_terminal:
            value = evaluate_position(board, AI)
        return None, value

    else:
        value = -math.inf if do_max else math.inf
        best_column = valid_columns[0] if valid_columns else None

        for col in valid_columns:
            row = get_curr_row_by_col(board, col)
            if row is None:
                continue
            drop_disc(board, col, player)

            new_column, new_score = minimax(board, depth-1, not do_max, opponent)
            board[row][col] = 0  # 假设有撤销操作

            if do_max:
                if new_score > value:
                    value = new_score
                    best_column = col
            else:
                if new_score < value:
                    value = new_score
                    best_column = col

        return best_column, value

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