python - 为什么我的 connect4 minimax 不能正常工作？

Question

你能解释一下为什么我的 AI 可以正常播放，直到玩家在第六或第七列连续 3 个，然后我的 AI 拒绝阻止他。另一个问题是当我的 AI 可以在 1 步中获胜，但他宁愿选择更长的游戏。谁能帮帮我。

返回获胜着法的值

def utility(board):
    if terminal(board):
        if winning_move(board, X):
            return 1000000
        elif winning_move(board, O):
            return -10000
        else:
            return 0

计算depth=0时position的得分

def compute_score(block, board, col, row):
    score = 0

    if block.count(X) == 4 and block.count("-") == 0:
        score += 100000
    elif block.count(X) == 3 and block.count("-") == 1:
        score += 10
    elif block.count(X) == 2 and block.count("-") == 2:
        score += 3

    if block.count(O) == 4 and block.count("-") == 0:
        score -= 1000000
    elif block.count(O) == 3 and block.count("-") == 1:
        score -= 6
    elif block.count(O) == 2 and block.count("-") == 2:
        score -= 2
    return score

赋予每一个可能的“四 block ”值(value)

def score_position(board):
    score = 0
    mid_section = []

#increases score because playing in middle is usually good move
    for col in range(5):
        mid_section.append(board[col][x // 2])
    score += mid_section.count(X) * 3

#claculates score of all horizontal 4 in a rows
    for row in range(y):
        for col in range(x - 3):
            block = board[col: col + 4]
            score += compute_score(block, board, col, row)

#claculates score of all vertical 4 in a rows
    for col in range(x):
        for row in range(y - 3):
            block = [board[row][col], board[row + 1][col], board[row + 2][col], board[row + 3][col]]
            score += compute_score(block, board, col, row)


#claculates score of all diagonals from left bottom to right top 4 in a rows
    for row in range(y - 3):
        for col in range(x - 3):
            block = [board[row][col], board[row + 1][col + 1], board[row + 2][col + 2], board[row + 3][col + 3]]
            score += compute_score(block, board, col, row)

#claculates score of all diagonals from right bottom to left top 4 in a rows
    for row in range(y - 3):
        for col in range(x - 1, 2, -1):
            block = [board[row][col], board[row + 1][col - 1], board[row + 2][col - 2], board[row + 3][col - 3]]
            score += compute_score(block, board, col, row)
    return score

minimax 算法(如果您想了解更多关于此算法的信息，请观看此视频 - https://www.youtube.com/watch?v=l-hh51ncgDI)

def minimax(board, depth):
    #if terminal(board):
     #   return None

    best_move = None
    alpha = -math.inf
    beta = math.inf

    if player(board) == X:
        if board == initial_state():
            best_move = x//2
            return best_move

        best_score = -math.inf
        for action in actions(board):
            score = minimaze(result(board, action), alpha, beta, depth)
            alpha = max(alpha, score)
            if score > best_score:
                best_score = score
                best_move = action
        return best_move

    else:
        best_score = math.inf
        for action in actions(board):
            score = maximaze(result(board, action), alpha, beta, depth)
            beta = min(beta, score)
            if score < best_score:
                best_score = score
                best_move = action
        print(best_move)
        return best_move

The minimizing player(返回最好的玩家移动四的特定位置)

def minimaze(board, alpha, beta, depth):
    if terminal(board):
        return utility(board)
    elif depth <= 0:
        return score_position(board)

    v = math.inf
    for action in actions(board):
        v = min(v, maximaze(result(board, action), alpha, beta, depth - 1))
        beta = min(beta, v)
    return v

最大化 AI(返回最佳 AI 在特定位置移动四次)

def maximaze(board, alpha, beta, depth):
    if terminal(board):
        return utility(board)
    elif depth <= 0:
        return score_position(board)

    v = -math.inf
    for action in actions(board):
        v = max(v, minimaze(result(board, action), alpha, beta, depth - 1))
        alpha = max(alpha, v)
    return v

Answer 1

我最近一直在做完全相同的项目:)
对于你的第二个问题，为了让 AI 尽可能快地获胜，你应该改变你的分数系统。

• 当游戏还没有结束时，您可以使用您的score_position 函数。
• 当游戏结束时(一些玩家赢得了游戏)，根据游戏经过的回合数给出分数。同时也表示游戏结束。
  当有四个棋子连成一排时，您可以通过更改分数加法来做到这一点:

if block.count(X) == 4 and block.count("-") == 0:
    score += 100000 * (places_in_board - turns_played + 1)

if block.count(O) == 4 and block.count("-") == 0:
    score -= 1000000 * (places_in_board - turns_played + 1)

其中 places_in_board 是您棋盘的位置数，turns_played 是游戏中经过的回合数。

请注意，当您在更少的回合中赢得比赛时，您获得的分数会更高。
这样，AI 会“更喜欢”走捷径来获胜——它获得的分数只会更高。

而且，作为副作用，您的 AI 又得到了改进!!
如果 AI 不知何故陷入了它总是失败的境地(如果对手打得完美)，它宁愿选择最长的方式来失败。为什么？因为在'longest lose'中turns_played会更大，所以

score -= 1000000 * (places_in_board - turns_left + 1)

会降低分数。分数会更高，所以 AI 更愿意接受那个“长期失败”。

如果您需要一些引用，这里是我的 connect4 AI 的链接:https://github.com/YotamZaiger1/connect_4_AI
我的评分函数在 Board 文件中，名为“state_value”。

希望我有所帮助，祝你好运!