Minimax Skill 入门指南：从零构建你的第一个 AI 博弈算法

3次阅读

没有评论

共计 2683 个字符，预计需要花费 7 分钟才能阅读完成。

Minimax 算法的核心在于博弈树的构建与遍历。博弈树是一种树形结构，每个节点代表游戏的一个状态，分支代表可能的走法。对于两人零和博弈（如井字棋），一方试图最大化自己的收益（Max 层），另一方则试图最小化对手的收益（Min 层）。

Max 层：当前玩家选择对自己最有利的走法（最大值）
Min 层：对手选择对玩家最不利的走法（最小值）

递归搜索会从当前状态出发，模拟所有可能的走法直到终局（叶子节点），然后回溯评分。

标准 Minimax 实现存在两个主要问题：

计算爆炸 ：分支因子(branching factor) 大的游戏（如围棋）会导致树节点指数级增长
重复计算：同一游戏状态可能通过不同路径到达多次

常见错误包括：

忘记实现深度限制导致无限递归
评分函数设计不合理（如忽视中期优势）
没有正确处理游戏提前结束的情况

def minimax(state, depth, is_maximizing):
    """
    state: 当前游戏状态对象
    depth: 当前搜索深度
    is_maximizing: 当前是否为 Max 层
    """
    if depth == 0 or state.is_terminal():
        return state.evaluate()

    if is_maximizing:
        max_eval = -float('inf')
        for move in state.get_legal_moves():
            new_state = state.make_move(move)
            eval = minimax(new_state, depth-1, False)
            max_eval = max(max_eval, eval)
        return max_eval
    else:
        min_eval = float('inf')
        for move in state.get_legal_moves():
            new_state = state.make_move(move)
            eval = minimax(new_state, depth-1, True)
            min_eval = min(min_eval, eval)
        return min_eval

Alpha-Beta 剪枝通过记录当前搜索路径的最优值范围，提前终止无效分支的搜索：

def alphabeta(state, depth, alpha, beta, is_maximizing):
    if depth == 0 or state.is_terminal():
        return state.evaluate()

    if is_maximizing:
        value = -float('inf')
        for move in state.get_legal_moves():
            new_state = state.make_move(move)
            value = max(value, alphabeta(new_state, depth-1, alpha, beta, False))
            alpha = max(alpha, value)
            if alpha >= beta:
                break  # Beta 剪枝
        return value
    else:
        value = float('inf')
        for move in state.get_legal_moves():
            new_state = state.make_move(move)
            value = min(value, alphabeta(new_state, depth-1, alpha, beta, True))
            beta = min(beta, value)
            if beta <= alpha:
                break  # Alpha 剪枝
        return value

优化效果：最佳情况下时间复杂度从 O(b^d)降到 O(b^(d/2))

class TicTacToe:
    def __init__(self):
        self.board = [' ']*9

    def is_terminal(self):
        # 检查胜利条件
        lines = [(0,1,2),(3,4,5),(6,7,8),
                (0,3,6),(1,4,7),(2,5,8),
                (0,4,8),(2,4,6)]
        for a,b,c in lines:
            if self.board[a] == self.board[b] == self.board[c] != ' ':
                return True
        return ' ' not in self.board

    def evaluate(self):
        # 评分函数
        lines = [...] # 同胜利条件检查
        for a,b,c in lines:
            if self.board[a] == self.board[b] == self.board[c] == 'X':
                return 10
            elif self.board[a] == self.board[b] == self.board[c] == 'O':
                return -10
        return 0

    def get_legal_moves(self):
        return [i for i, spot in enumerate(self.board) if spot == ' ']

# 使用示例
game = TicTacToe()
best_move = None
best_value = -float('inf')
for move in game.get_legal_moves():
    new_game = game.make_move(move)
    value = alphabeta(new_game, 5, -float('inf'), float('inf'), False)
    if value > best_value:
        best_value = value
        best_move = move

测试数据（3×3 井字棋，depth=5）：