第5章：对抗搜索（Adversarial Search）
一、导读
1.1 本章学习目标
第5章介绍了一类特殊但极其重要的搜索问题——对抗搜索。在博弈中，多个智能体相互竞争，每个智能体的行动都会影响其他智能体的选择。这种环境需要完全不同的搜索策略：我们不仅要考虑自己的最优行动，还要考虑对手的最优反应。
本章的核心学习目标包括：
- 掌握博弈的形式化方法：理解博弈的要素——初始状态、玩家、行动、结果函数和效用函数。
- 掌握极小极大算法：理解最优博弈策略的原理，学会构建博弈树并计算极小极大值。
- 掌握 Alpha-Beta 剪枝：理解剪枝的原理和正确性，掌握移动排序等优化技术。
- 理解启发式评估函数：当搜索深度有限时，如何用评估函数估计局面价值。
- 了解蒙特卡洛树搜索（MCTS）：理解随机模拟与树搜索的结合，以及在围棋等复杂博弈中的应用。
- 了解 AlphaGo/AlphaZero 的突破：深度学习与 MCTS 结合如何改变了游戏 AI。
1.2 为什么第五章如此重要
对抗搜索是AI历史上最成功的领域之一。从 1997 年 Deep Blue 击败国际象棋世界冠军，到 2016 年 AlphaGo 击败围棋世界冠军，博弈 AI 一直是展示 AI 能力的标志性应用。
更重要的是，对抗搜索的思想远不止于游戏。商业竞争、军事对抗、网络安全等领域都涉及多方博弈。极小极大思想和 Alpha-Beta 剪枝技术是理解竞争性决策的基础。
1.3 核心问题引导
在阅读本章时，请带着以下问题思考：
极小极大策略是否"理性"？ 如果对手不按极小极大策略行动，我们的策略是否仍然最优？
Alpha-Beta 剪枝为什么正确？ 剪枝不改变结果的根本原因是什么？
评估函数的设计：在国际象棋中，如何设计一个好的评估函数？子力、位置、王的安全等因素如何权衡？
MCTS 为什么适合围棋？ 围棋的分支因子约为 250，为什么传统的 Alpha-Beta 搜索不适用？
AlphaZero 的启示：不使用人类知识、仅通过自我对弈学习，为什么能达到超人水平？
二、核心概念详解
2.1 博弈的形式化
2.1.1 博弈的要素
一个博弈可以用以下要素来描述：
- S₀：初始状态
- Player(s)：当前轮到谁行动
- Actions(s)：在状态 s 下的合法行动
- Result(s, a)：执行行动 a 后的新状态
- Terminal-Test(s)：判断状态 s 是否为终局
- Utility(s, p)：在终局 s 下玩家 p 的效用值
python
class Game:
def __init__(self, initial):
self.initial = initial
def actions(self, state):
raise NotImplementedError
def result(self, state, action):
raise NotImplementedError
def is_terminal(self, state):
raise NotImplementedError
def utility(self, state, player):
raise NotImplementedError
def to_move(self, state):
raise NotImplementedError
# 井字棋
class TicTacToe(Game):
def __init__(self):
initial = {
'board': [['.' for _ in range(3)] for _ in range(3)],
'to_move': 'X'
}
super().__init__(initial)
def actions(self, state):
actions = []
for r in range(3):
for c in range(3):
if state['board'][r][c] == '.':
actions.append((r, c))
return actions
def result(self, state, action):
board = [row[:] for row in state['board']]
r, c = action
board[r][c] = state['to_move']
next_player = 'O' if state['to_move'] == 'X' else 'X'
return {'board': board, 'to_move': next_player}
def is_terminal(self, state):
board = state['board']
for player in ['X', 'O']:
for r in range(3):
if all(board[r][c] == player for c in range(3)):
return True
for c in range(3):
if all(board[r][c] == player for r in range(3)):
return True
if all(board[i][i] == player for i in range(3)):
return True
if all(board[i][2-i] == player for i in range(3)):
return True
if all(board[r][c] != '.' for r in range(3) for c in range(3)):
return True
return False
def utility(self, state, player):
board = state['board']
for p in ['X', 'O']:
for r in range(3):
if all(board[r][c] == p for c in range(3)):
return 1 if p == player else -1
for c in range(3):
if all(board[r][c] == p for r in range(3)):
return 1 if p == player else -1
if all(board[i][i] == p for i in range(3)):
return 1 if p == player else -1
if all(board[i][2-i] == p for i in range(3)):
return 1 if p == player else -1
return 0
def to_move(self, state):
return state['to_move']2.2 极小极大算法
2.2.1 最优博弈策略
极小极大算法基于以下思想：假设对手也采取最优策略，我们选择使自己在最坏情况下收益最大化的行动。
python
def minimax_decision(state, game):
player = game.to_move(state)
def max_value(state, depth=0):
if game.is_terminal(state):
return game.utility(state, player)
v = float('-inf')
for action in game.actions(state):
v = max(v, min_value(game.result(state, action), depth + 1))
return v
def min_value(state, depth=0):
if game.is_terminal(state):
return game.utility(state, player)
v = float('inf')
for action in game.actions(state):
v = min(v, max_value(game.result(state, action), depth + 1))
return v
best_action = None
best_value = float('-inf')
for action in game.actions(state):
value = min_value(game.result(state, action))
if value > best_value:
best_value = value
best_action = action
return best_action
# 在井字棋中使用极小极大
game = TicTacToe()
state = game.initial
state['board'] = [
['X', '.', 'O'],
['.', 'X', '.'],
['O', '.', '.']
]
best_move = minimax_decision(state, game)
print(f"极小极大最佳走法: {best_move}")2.2.2 极小极大算法的性质
- 完备性：在有限博弈树中，算法总能找到解
- 最优性：如果对手采取最优策略，算法给出最优结果
- 时间复杂度：O(b^m)，其中 b 是分支因子，m 是深度
- 空间复杂度：O(bm)，使用深度优先搜索
2.3 Alpha-Beta 剪枝
2.3.1 剪枝的原理
Alpha-Beta 剪枝通过维护两个参数来减少搜索节点数：
- α：MAX 能保证的最低值
- β：MIN 能保证的最高值
当 α ≥ β 时，当前节点可以被剪枝。
python
def alpha_beta_search(state, game):
player = game.to_move(state)
def max_value(state, alpha, beta):
if game.is_terminal(state):
return game.utility(state, player)
v = float('-inf')
for action in game.actions(state):
v = max(v, min_value(game.result(state, action), alpha, beta))
if v >= beta:
return v
alpha = max(alpha, v)
return v
def min_value(state, alpha, beta):
if game.is_terminal(state):
return game.utility(state, player)
v = float('inf')
for action in game.actions(state):
v = min(v, max_value(game.result(state, action), alpha, beta))
if v <= alpha:
return v
beta = min(beta, v)
return v
best_action = None
best_value = float('-inf')
for action in game.actions(state):
value = min_value(game.result(state, action), float('-inf'), float('inf'))
if value > best_value:
best_value = value
best_action = action
return best_action
# Alpha-Beta 剪枝的效果
game = TicTacToe()
state = game.initial
move = alpha_beta_search(state, game)
print(f"Alpha-Beta 最佳走法: {move}")2.3.2 移动排序
移动排序能显著提升 Alpha-Beta 的剪枝效率。好的移动应该先被搜索。
python
def alpha_beta_with_ordering(state, game, depth_limit=6):
player = game.to_move(state)
def evaluate(state):
if game.is_terminal(state):
return game.utility(state, player)
if depth_limit <= 0:
return heuristic_eval(state, player)
return heuristic_eval(state, player)
def heuristic_eval(state, player):
board = state['board']
score = 0
opponent = 'O' if player == 'X' else 'X'
for r in range(3):
for c in range(3):
if board[r][c] == player:
score += 1
elif board[r][c] == opponent:
score -= 1
return score
def max_value(state, alpha, beta, depth):
if game.is_terminal(state) or depth == 0:
return evaluate(state)
v = float('-inf')
for action in sorted(game.actions(state), key=lambda a: move_priority(a, state, player)):
v = max(v, min_value(game.result(state, action), alpha, beta, depth - 1))
if v >= beta:
return v
alpha = max(alpha, v)
return v
def min_value(state, alpha, beta, depth):
if game.is_terminal(state) or depth == 0:
return evaluate(state)
v = float('inf')
for action in sorted(game.actions(state), key=lambda a: move_priority(a, state, player)):
v = min(v, max_value(game.result(state, action), alpha, beta, depth - 1))
if v <= alpha:
return v
beta = min(beta, v)
return v
def move_priority(action, state, player):
r, c = action
if r == 1 and c == 1:
return 0
if (r, c) in [(0,0),(0,2),(2,0),(2,2)]:
return 1
return 2
best_action = max(game.actions(state),
key=lambda a: min_value(game.result(state, a), float('-inf'), float('inf'), depth_limit))
return best_action2.4 蒙特卡洛树搜索（MCTS）
2.4.1 MCTS 的原理
MCTS 通过随机模拟来评估局面价值，不需要人工设计的评估函数。它包含四个步骤：
选择（Selection）：从根节点出发，使用 UCB1 公式选择子节点
扩展（Expansion）：在叶节点添加一个新子节点
模拟（Simulation）：从新节点开始随机对弈到终局
回传（Backpropagation）：将模拟结果回传到路径上的所有节点
python
import math
import random
class MCTSNode:
def __init__(self, state, parent=None, action=None):
self.state = state
self.parent = parent
self.action = action
self.children = {}
self.visits = 0
self.value = 0.0
def ucb1(self, c=1.414):
if self.visits == 0:
return float('inf')
exploitation = self.value / self.visits
exploration = c * math.sqrt(math.log(self.parent.visits) / self.visits)
return exploitation + exploration
def best_child(self, c=1.414):
return max(self.children.values(), key=lambda child: child.ucb1(c))
def mcts(game, state, n_simulations=1000):
root = MCTSNode(state)
for _ in range(n_simulations):
node = root
sim_state = state.copy() if isinstance(state, dict) else state
while not game.is_terminal(sim_state) and node.children:
node = node.best_child()
sim_state = game.result(sim_state, node.action)
if not game.is_terminal(sim_state):
action = random.choice(game.actions(sim_state))
new_state = game.result(sim_state, action)
if action not in node.children:
node.children[action] = MCTSNode(new_state, node, action)
node = node.children[action]
sim_state = new_state
while not game.is_terminal(sim_state):
action = random.choice(game.actions(sim_state))
sim_state = game.result(sim_state, action)
result = game.utility(sim_state, game.to_move(state))
while node is not None:
node.visits += 1
node.value += result
node = node.parent
if not root.children:
return random.choice(game.actions(state))
return max(root.children.values(), key=lambda c: c.visits).action
# 使用 MCTS 下井字棋
game = TicTacToe()
state = game.initial
move = mcts(game, state, n_simulations=5000)
print(f"MCTS 最佳走法: {move}")2.5 AlphaGo 与深度学习
AlphaGo 结合了深度神经网络和 MCTS，在围棋上实现了突破。
python
class AlphaGoLikeAgent:
def __init__(self, game):
self.game = game
self.policy_network = None
self.value_network = None
self.n_simulations = 1600
def select_action(self, state):
root = MCTSNode(state)
for _ in range(self.n_simulations):
node = root
sim_state = state.copy() if isinstance(state, dict) else state
while not self.game.is_terminal(sim_state) and node.children:
node = self._puct_select(node)
sim_state = self.game.result(sim_state, node.action)
if not self.game.is_terminal(sim_state):
prior = self._get_policy(sim_state)
for action, prob in prior.items():
if action not in node.children:
new_state = self.game.result(sim_state, action)
node.children[action] = PUCTNode(new_state, node, action, prob)
node = max(node.children.values(), key=lambda c: c.puct_value())
sim_state = self.game.result(sim_state, node.action)
value = self._evaluate(sim_state)
while node is not None:
node.visits += 1
node.value += value
node = node.parent
return max(root.children.values(), key=lambda c: c.visits).action
def _puct_select(self, node):
return max(node.children.values(), key=lambda c: c.puct_value())
def _get_policy(self, state):
actions = self.game.actions(state)
probs = {a: 1.0 / len(actions) for a in actions}
return probs
def _evaluate(self, state):
if self.game.is_terminal(state):
return self.game.utility(state, self.game.to_move(self.game.initial))
return 0
class PUCTNode(MCTSNode):
def __init__(self, state, parent, action, prior=0.0):
super().__init__(state, parent, action)
self.prior = prior
def puct_value(self, c=5.0):
if self.visits == 0:
return float('inf')
q = self.value / self.visits
u = c * self.prior * math.sqrt(self.parent.visits) / (1 + self.visits)
return q + u三、实战案例
3.1 案例一：完整的井字棋 AI 对战
python
def play_tic_tac_toe(x_agent, o_agent, verbose=True):
game = TicTacToe()
state = game.initial
while not game.is_terminal(state):
if verbose:
print_board(state['board'])
player = game.to_move(state)
if player == 'X':
action = x_agent(game, state)
else:
action = o_agent(game, state)
state = game.result(state, action)
if verbose:
print(f"{player} 走: {action}")
if verbose:
print_board(state['board'])
u = game.utility(state, 'X')
if u > 0:
print("X 获胜!")
elif u < 0:
print("O 获胜!")
else:
print("平局!")
return game.utility(state, 'X')
def print_board(board):
for row in board:
print(' '.join(row))
print()
def human_player(game, state):
print_board(state['board'])
while True:
try:
r = int(input("行 (0-2): "))
c = int(input("列 (0-2): "))
if (r, c) in game.actions(state):
return (r, c)
except (ValueError, IndexError):
pass
print("非法走法，请重试")
def random_player(game, state):
return random.choice(game.actions(state))
def minimax_player(game, state):
return alpha_beta_search(state, game)
# 人机对战
# play_tic_tac_toe(human_player, minimax_player)
# AI 对战
result = play_tic_tac_toe(minimax_player, minimax_player, verbose=True)
print(f"结果: {result}")3.2 案例二：比较不同搜索算法的效率
python
import time
def benchmark_algorithms(game, state, n_trials=10):
algorithms = {
'Minimax': lambda g, s: minimax_decision(s, g),
'Alpha-Beta': lambda g, s: alpha_beta_search(s, g),
'MCTS-100': lambda g, s: mcts(g, s, 100),
'MCTS-1000': lambda g, s: mcts(g, s, 1000),
}
for name, algo in algorithms.items():
times = []
actions = []
for _ in range(n_trials):
start = time.time()
action = algo(game, state)
elapsed = time.time() - start
times.append(elapsed)
actions.append(action)
avg_time = sum(times) / len(times)
print(f"{name}: 平均时间={avg_time:.4f}s, 走法={actions[0]}")
game = TicTacToe()
state = game.initial
benchmark_algorithms(game, state)四、本章小结
本章介绍了对抗搜索——多智能体竞争环境中的决策方法。我们从极小极大算法开始，学习了最优博弈策略的原理。然后介绍了 Alpha-Beta 剪枝，它通过消除不必要的搜索大幅提升了效率。最后，我们讨论了蒙特卡洛树搜索和 AlphaGo 的突破。
核心知识点回顾：
- 博弈的形式化：状态、玩家、行动、结果、效用
- 极小极大算法保证在对手最优时的最优结果
- Alpha-Beta 剪枝不改变结果但大幅减少搜索量
- 评估函数用于在深度限制时估计局面价值
- MCTS 通过随机模拟评估局面，适合高分支因子博弈
- AlphaGo 结合了策略网络、价值网络和 MCTS
五、思考与练习
思考题
Alpha-Beta 的最坏情况：在什么情况下 Alpha-Beta 剪枝不能减少任何节点？给出一个例子。
评估函数的设计：在国际象棋中，子力价值（兵=1, 马=3, 象=3, 车=5, 后=9）是一种简单的评估函数。如何改进它？考虑位置、王的安全、兵的结构等因素。
MCTS 的收敛性：随着模拟次数的增加，MCTS 是否总能收敛到最优策略？需要什么条件？
编程练习
实现四子棋 AI：用 Alpha-Beta 搜索实现一个四子棋（Connect Four）AI，设计合适的评估函数。
实现 MCTS 围棋 AI：在 9×9 的小棋盘上实现 MCTS 围棋 AI，观察不同模拟次数对棋力的影响。
自我对弈学习：实现一个简单的自我对弈框架，让 AI 通过与自己对弈来改进评估函数的参数。