(Python) Minimax Connect 4 算法不阻止玩家移动

Question

（Connect 4 是一款游戏，您可以放下圆圈并尝试以垂直、水平或对角线形式创建 4 个相连的颜色圆圈。）

我正在构建一个 connect 4 minimax 算法，它无法防止损失，但似乎只是努力获胜。它只尝试连接自己的部分，而不阻止我连接我的部分。

算法：（X是玩家，O是计算机）

def minimax(board, depth, is_maximizing, depthLimit):
    if detect(board, ' O '):
        return 100 - depth
    elif detect(board, ' X '):
        if is_maximizing:
            return 100 - depth
        else:
            return -100
    elif boardFull(board):
        return 0
    elif depth == depthLimit + 1:
        return 0

    if is_maximizing:
        max_eval = float('-inf')
        for row in range(6):
            for column in range(7):
                if board[row][column] == '   ' and not isColumnFull(board, column):
                    board[row][column] = ' O '
                    eval = minimax(board, depth + 1, False, depthLimit)
                    board[row][column] = '   '
                    max_eval = max(max_eval, eval)
        return max_eval
    else:
        min_eval = float('inf')
        for row in range(6):
            for column in range(7):
                if board[row][column] == '   ' and not isColumnFull(board, column):
                    board[row][column] = ' X '
                    eval = minimax(board, depth + 1, True, depthLimit)
                    board[row][column] = '   '
                    min_eval = min(min_eval, eval)
        return min_eval

def isColumnFull(board, column):
    for row in range(6):
        if board[row][column] == '   ':
            return False
    return True

def computerMove(board):
    best_score = float('-inf')
    best_move = None
    
    for row in range(6):
        for column in range(7):
            print(f'{round(((row/6)*100)+(column/7)*10, 2)}% Done Calculating')
            if board[row][column] == '   ' and not isColumnFull(board, column):
                board[row][column] = ' O '
                score = minimax(board, 0, False, depth)
                board[row][column] = '   '
                if score > best_score:
                    best_score = score
                    best_move = column

    for row in range(6):
        if board[row][best_move] != '   ':
            board[row - 1][best_move] = ' O '
            break
        elif row == 5:
            board[row][best_move] = ' O '
            break

    if detect(board, ' O '):
        print('O Wins!')
        return False
    return True

'board' 本质上是一个包含板的矩阵：

board = [['   ' for i in range(7)] for f in range(6)]

示例：

我还排除了

detect()

函数有问题的可能性，因为它可以很好地检测胜利。 （

detect()

本质上是检查是否有 4 个相同颜色/玩家的相连棋子）

Answer 1

问题似乎出在这里。

def minimax(board, depth, is_maximizing, depthLimit):
    if detect(board, ' O '):
        return 100 - depth
    elif detect(board, ' X '):
        if is_maximizing:
            return 100 - depth
        else:
            return -100

如果 O 获胜，它总是返回一个大的正值。如果 X 获胜，它会返回负数或正数，具体取决于轮到谁。如果我们要最大化，那么就轮到 X 了，所以我们返回一个大的正数。换句话说，AI 在 X 轮到 O 获胜和 X 获胜之间无关紧要。

解决方法是使 X 与 O 相反：

def minimax(board, depth, is_maximizing, depthLimit):
    if detect(board, ' O '):
        return 100 - depth
    elif detect(board, ' X '):
        return -100 + depth

进行此更改后，它可以找出如何阻止 X 获胜。

Answer 2

您的极小极大算法似乎没有正确阻止玩家的移动以防止他们获胜。问题在于您在极小极大评估期间更新电路板的方式。在您的

minimax

函数中，您不会在评估移动后恢复对棋盘所做的更改。因此，它无法准确模拟对手的动作。

要解决此问题，您需要在评估极小极大算法中的移动时正确修改棋盘。这是

minimax

函数的更新版本，具有正确的板处理：

def minimax(board, depth, is_maximizing, depthLimit):
    if detect(board, ' O '):
        return 100 - depth
    elif detect(board, ' X '):
        if is_maximizing:
            return 100 - depth
        else:
            return -100
    elif boardFull(board):
        return 0
    elif depth == depthLimit + 1:
        return 0

    if is_maximizing:
        max_eval = float('-inf')
        for row in range(6):
            for column in range(7):
                if board[row][column] == '   ' and not isColumnFull(board, column):
                    board[row][column] = ' O '
                    eval = minimax(board, depth + 1, False, depthLimit)
                    board[row][column] = '   '  # Revert the move after evaluation
                    max_eval = max(max_eval, eval)
        return max_eval
    else:
        min_eval = float('inf')
        for row in range(6):
            for column in range(7):
                if board[row][column] == '   ' and not isColumnFull(board, column):
                    board[row][column] = ' X '
                    eval = minimax(board, depth + 1, True, depthLimit)
                    board[row][column] = '   '  # Revert the move after evaluation
                    min_eval = min(min_eval, eval)
        return min_eval

通过在评估每个动作后正确地恢复棋盘，极小极大算法将正确模拟对手的动作并考虑阻止玩家的获胜动作。

此外，您应该更新

computerMove

函数来存储在极小极大评估之后放置“O”标记的最佳行，而不仅仅是最佳列。这是更新后的

computerMove

函数：

def computerMove(board):
    best_score = float('-inf')
    best_move = None
    
    for row in range(6):
        for column in range(7):
            print(f'{round(((row/6)*100)+(column/7)*10, 2)}% Done Calculating')
            if board[row][column] == '   ' and not isColumnFull(board, column):
                board[row][column] = ' O '
                score = minimax(board, 0, False, depth)
                board[row][column] = '   '
                if score > best_score:
                    best_score = score
                    best_move = (row, column)  # Store both row and column

    if best_move:
        row, col = best_move
        for r in range(5, -1, -1):
            if board[r][col] == '   ':
                board[r][col] = ' O '
                break

    if detect(board, ' O '):
        print('O Wins!')
        return False
    return True

通过这些更新，您的极小极大算法现在应该可以正确阻止玩家的获胜动作，并在游戏过程中做出更多战略决策。