一、博弈论基础 (Game Theory Basics)

1.1 博弈论简介

• 博弈论 (Game Theory): 研究被称为“参与者 (players)”的“互动实体 (interactive entities)”的学科。
• 从计算机科学角度看，参与者是人工智能体 (artificial agents)。
• Homo rationalis (理性人): 总是目标明确、行为合乎逻辑、致力于最大化自身目标并具备相应计算能力的个体。

• 约翰·纳什 (John F. Nash, Jr.): 数学家，1994年诺贝尔经济学奖得主，奠定了博弈论的数学基础，区分了“合作博弈”与“非合作博弈”，并定义了著名的“纳什均衡”。

1.2 博弈的分类

• 非合作博弈 (Non-cooperative game):
• 参与者之间存在竞争。
• 没有约束性协议。

• 合作博弈 (Cooperative game):
• 参与者之间存在竞争。
• 存在约束性协议。

• 静态博弈 (Static game):
• 所有参与者同时行动，或在不知道其他参与者行动的情况下行动，通常只进行一次。
• 示例: 石头剪刀布。

• 动态博弈 (Dynamic game):
• 参与者轮流行动，后行动者可以看到先行动者的行为。
• 示例: 象棋、围棋、扑克。

• 零和博弈 (Zero-Sum Games) (双人):
• 参与者的效用完全对立 (一方的收益即为另一方的损失)。
• 可以视为一方最大化某个值，另一方最小化该值。
• 纯粹的对抗性竞争。

• 一般和博弈 (General-Sum Games) (双人):
• 参与者的效用是独立的，不一定完全对立。

1.3 博弈的关键元素

• 参与者 (Players):。

• 行动 (Actions): 。

• 信息 (Information): 。

• 效用/支付/结果 (Utility/Payoff/Outcome)。

• 一个参与者的解决方案 (solution) 是一个策略 (strategy)，即在每一步如何行动。

1.4 最佳应对与纳什均衡

• 最佳应对 (Best response):
• 给定其他参与者的行动，一个参与者能够最大化其自身支付的行动。

• 纳什均衡 (Nash Equilibrium):
• 所有参与者都选择了针对其他参与者策略的最佳应对。
• 没有任何参与者可以通过单方面改变自身策略来获得更好的结果。
• 每个参与者都选择不改变策略（或者改变与不改变无差异）。

• 经典静态博弈案例:
• 囚徒困境 (Prisoner's Dilemma):
• 参与者: 两名嫌疑人 (爱丽丝和鲍勃)。
• 行动: 坦白 (Confess) / 否认 (Denial)。
• 支付矩阵示例:

爱丽丝/鲍勃	坦白	否认
坦白	(-5, -5)	(0, -10)
否认	(-10, 0)	(-1, -1)

• 纳什均衡: (坦白, 坦白)。只有一个均衡点
• 性别之战 (The Battle of the Sexes):
• 参与者: 情侣 (爱丽丝和鲍勃)，选择约会活动。
• 行动: 足球 (Football) / 芭蕾 (Ballet)。
• 支付矩阵示例:

爱丽丝/鲍勃	足球	芭蕾
足球	(10, 1)	(0, 0)
芭蕾	(0, 0)	(1, 10)

• 纳什均衡: (足球, 足球) 和 (芭蕾, 芭蕾)。这是一个协调博弈 (Coordination game)。具有两个NE
• 石头剪刀布 (Rock-Paper-Scissors):
• 参与者: 爱丽丝和鲍勃。
• 行动: 石头 (Rock) / 剪刀 (Scissors) / 布 (Paper)。
• 支付: 赢+1, 输-1, 平0。
• 纯策略纳什均衡: 不存在。
• 混合策略纳什均衡: 存在 (例如，以1/3的概率分别选择石头、剪刀、布)。

二、对抗性搜索 (Adversarial Search)

2.1 对抗性搜索问题

• 定义: 当其他智能体与我们计划相悖，且目标冲突时，需要提前规划。

• 特点:
• 通常为双人零和博弈。
🌻
这意味着，一方的受益最大，另外一方的受益就最小
• 完全信息 (Complete Information): 所有参与者了解博弈规则和所有可能的行动。
• 完美信息 (Perfect Information): 每个参与者在做决策时了解博弈历史中所有之前的行动。

• 组成部分:
• 初始状态 (Initial State):。
• 行动 (Actions): 。
• 结果/转移模型 (Results/Transition Model): (确定性的)。
• 如果转移模型是不确定的，就是后边的贝叶斯网络和马尔可夫模型了
• 终止状态与效用 (Terminal State & Utility): (或其他数值)。

• 目标: 找到一个最佳策略 (best strategy) 来最大化终止状态的效用。

2.2 博弈树 (Game Trees)

• 定义: 初始状态、行动函数和结果函数共同定义了博弈的博弈树。
• 节点 (Nodes): 代表博弈状态。
• 边 (Edges): 代表行动 (moves)。

• 示例: 井字棋 (Tic-Tac-Toe)。

• 状态的价值 (Value of a State): 从该状态可获得的最佳效用。
• 非终止状态:
• 终止状态:

2.3 Minimax 算法

• 核心思想: 在一个零和博弈中，一个玩家 (MAX) 试图最大化结果，而另一个玩家 (MIN) 试图最小化结果。Minimax 算法计算每个节点在双方都采取最优策略时的价值。

• Minimax 值:
• MAX 节点:
• MIN 节点:
• 终止节点:

• Minimax 示例: 课件中有图示说明如何从叶节点向上计算各节点的 Minimax 值。

• 效率:
• 类似于（穷举式）深度优先搜索 (DFS)
• 时间复杂度: ，其中 b 是分支因子，m 是最大深度。
• 空间复杂度: 。
• 对于复杂游戏 (如象棋，)，精确解完全不可行。

2.4 资源限制与评估函数

• 问题: 在现实游戏中，通常无法搜索到博弈树的叶节点。

• 解决方案: 深度限制搜索 (Depth-limited search)。
• 只搜索到树中的一个有限深度。
• 用一个评估函数 (evaluation function) 替代非终止位置的终止效用。

• 评估函数 (Evaluation Functions):
• 作用: 为深度限制搜索中的非终止节点打分。
• 理想函数: 返回该位置的真实 Minimax 值。
• 实践中: 通常是特征的加权线性总和:
例如，(我方棋子数−对方棋子数) 等。

• 深度的重要性 (Depth Matters):
• 评估函数总是不完美的。
• 在博弈树中搜索得越深，评估函数通常越容易设计且越准确，但搜索复杂度也越高。
• 需要在特征复杂度和计算复杂度之间进行权衡。

2.5 Alpha-Beta 剪枝 (Alpha-Beta Pruning)

• 剪枝的意义: 允许我们忽略搜索树中那些对最终选择没有影响的部分，从而提高效率。

• Alpha-Beta 剪枝原理:
• 维护两个值:
• (Alpha): MAX 玩家在当前搜索路径上，目前能确保获得的最低分数的下限。
• (Beta): MIN 玩家在当前搜索路径上，允许 MAX 玩家获得的最高分数的上限。
• 剪枝条件:
• 在 MIN 节点评估其子节点时，如果发现某个子节点的 Minimax 值 v 小于或等于其父 MAX 节点当前的 α 值 (v≤α)，则可以停止评估该 MIN 节点的其他子节点 (Beta 剪枝)。



• 在 MAX 节点评估其子节点时，如果发现某个子节点的 Minimax 值 v 大于或等于其父 MIN 节点当前的 β 值 (v≥β)，则可以停止评估该 MAX 节点的其他子节点 (Alpha 剪枝)。

• Alpha-Beta 剪枝的性质:
• 剪枝不影响为根节点计算出的 Minimax 值。
• 好的子节点排序可以提高剪枝效率。
• 例如，三个节点中先探索2，则其余两个可以直接剪掉；如果最后探索2，则相当于没有简化

• 效率提升:
• 在“完美排序”下，时间复杂度可以降至 。
• 这相当于将可解的搜索深度加倍。
• 但对于如围棋这样的游戏，完全搜索仍然是奢望。

三、包含不确定性的博弈 (Games with Uncertainty)

3.1 不确定性的来源

• 不确定性是由信息限制而非计算限制引起的。

• 例如：掷骰子，对手的随机行为。

3.2 最坏情况 vs. 平均情况

• Minimax 关注的是最坏情况下的结果。

• 当结果由机会而非对抗性对手控制时，应关注平均情况。

3.3 Expectimax 搜索

• 适用场景: 结果不确定的博弈，如包含掷骰子，或对手行为不可预测 (例如，Pacman 中的鬼魂随机响应)。

• 核心思想: 将Minimax策略中的第二个玩家（假设是mini）替换成随机的概率），计算平均得分或期望效用，而不是最坏情况的效用。

• 节点类型:
• MAX 节点: 与 Minimax 中的一样，选择最大化自身效用的行动。
• 机会节点 (Chance Nodes / EXP Nodes): 计算其子节点效用的加权平均值 (期望值)，权重是每个子节点发生的概率。

• Expectimax 剪枝: 通常情况下，Alpha-Beta 剪枝不适用于 Expectimax 搜索，因为期望值的计算需要考虑所有分支。
• 除非我们提前知道数据的范围则可以进行剪枝。例如，我们提前知道数据的范围是2-12，则下图所示的Expectmax或许可以剪枝。

• 深度限制 Expectimax:
• 与 Minimax 类似，当无法搜索至叶节点时，同样使用评估函数。
• 复杂度: ，其中 n 是机会节点的平均分支数 (不同随机结果的数量)。

3.4 建模假设与现实

• 危险的乐观 (Dangerous Optimism): 当世界是对抗性的时，却假设它是随机的 (例如，用 Expectimax 对抗一个 Minimax 对手)。

• 危险的悲观 (Dangerous Pessimism): 当情况并非最坏时，却假设是最坏情况 (例如，用 Minimax 对抗一个随机对手)。

• 假设 vs. 现实: 课件中 Pacman 游戏的例子表明，选择正确的模型 (Minimax vs. Expectimax) 对抗不同类型的对手至关重要。

四、其他博弈类型与效用理论 (Other Game Types and Utility Theory)

4.1 混合层次类型 (Mixed Layer Types)

• 例如: 西洋双陆棋 (Backgammon)，其中包含玩家决策和骰子投掷 (机会)。

• Expectiminimax: 将环境（如掷骰子）视为一个额外的“随机智能体”参与者，在每个 min/max 智能体之后行动。每个节点计算其子节点的适当组合 (max, min, 或 expectation)。

4.2 一般和博弈 (General Sum Games)

• 特点:
• 博弈结果不是零和的。
• 可能有多于两个参与者。
🌻
因为不再是零和的，所以必须把所有玩家的效用写全

• Minimax 的推广:
• 终止节点具有效用元组 (utility tuples) (e.g., (1, 6, 6) 代表三个玩家各自的效用)。
• 节点值也是效用元组。
• 每个参与者最大化其自身的效用分量，而不关心其他人的
• 可以动态地产生合作和竞争。

4.3 效用理论 (Utility Theory)

• 效用 (Utilities):
• 是从结果（世界状态）到实数的函数，描述了智能体的偏好 (preferences)。
• 在博弈中可能很简单 (如 +1/-1)，但通常总结了智能体的目标。

• 理性偏好 (Rational Preferences):
• 智能体必须在以下各项中拥有偏好:
• 奖品 (Prizes): A, B 等。
• 抽奖 (Lotteries): 具有不确定奖品的情境，如 表示以概率 p 获得 A，以概率 (1−p) 获得 B。
• 理性的公理 (Axioms of Rationality) (课件中列举，如传递性等):
• 有序性 (Orderability):
• 传递性 (Transitivity):
• 连续性 (Continuity):
• 可替代性 (Substitutability):
• 单调性 (Monotonicity):

• 冯·诺依曼-摩根斯坦效用定理: 任何满足这些理性公理的偏好都可以被一个效用函数 U 所描述，使得智能体的行为表现为最大化期望效用。
• 偏好与效用值对应
• 抽奖的效用等于期望效用

• 人类效用与理性:
• 阿莱悖论 (Allais Paradox): 展示了人类的选择有时会违反期望效用理论的预测，表明人类的理性可能并非总是符合这些公理。
💡
人类只具有相对理性，不具有绝对理性

• 金钱与效用 (Money and Utility):
• 金钱本身不直接等同于效用。我们谈论的是拥有金钱的效用。
对于抽奖 ，期望货币价值 (Expected Monetary Value - EMV):
通常，。而是呈现下面的曲线分布：



• 风险态度:
• 风险规避 (Risk-averse): (效用函数是凹的)。人们愿意支付保险费来减少风险。
• 风险中性 (Risk-neutral): (效用函数是线性的)。
• 风险寻求 (Risk-seeking): (效用函数是凸的)。
• 保险示例: 保险行业的存在是因为人们通常是风险规避的，愿意支付一定费用（保险费，即 EMV 与确定等价值之间的差额）来避免潜在的巨大损失。

五、总结 (Summary from Slides)

• 一个博弈可以通过初始状态、每个状态下的合法行动、每个行动的结果、一个终止测试（判断游戏何时结束）以及一个应用于终止状态的效用函数来定义。

• 在具有完美信息的双人零和博弈中，Minimax 算法可以通过对博弈树进行深度优先枚举来选择最优行动。

• Alpha-Beta 搜索算法计算与 Minimax 相同的最优行动，但通过消除可证明不相关的子树来获得更高的效率。

• 通常情况下，即使使用 Alpha-Beta 剪枝，考虑整个博弈树也是不可行的，因此我们需要在某个点截断搜索，并应用一个启发式评估函数来估计状态的效用。

• 机会博弈 (Games of chance) 可以通过对 Minimax 算法进行扩展来处理，即通过取其所有子节点效用的加权平均值（按每个子节点的概率加权）来评估机会节点 (即 Expectimax)。

习题