GameTheroy

博弈论与极大极小定理笔记

1. 课程概述

本课程探讨了博弈论在计算机科学中的应用，重点包括：

零和博弈与极小极大最优策略
随机算法与博弈论的联系
一般和博弈及纳什均衡

2. 博弈论基础

博弈的定义

玩家（Players）：参与者
策略（Actions）：玩家可以采取的决策
收益（Payoff）：由玩家的联合决策决定

3. 经典零和博弈：射手-守门员博弈

设定

玩家：射手（Shooter） vs. 守门员（Goalie）
动作：左（L）或右（R）
规则：
- 若射手和守门员选择相同方向，守门员成功扑救
- 否则，射手得分

收益矩阵

守门员扑救：(+1, -1)
射手进球：(-1, +1)
这是一个零和博弈，满足 r+c=0

行矩阵/列矩阵

4. 纯策略 vs. 混合策略

纯策略：玩家每次都选择固定动作
混合策略：玩家按一定概率分配动作选择

收益计算

若两个玩家独立随机选择策略，预期收益计算为：

$$
E[payoff]=∑piqjR(i,j)E[\text{payoff}] = \sum p_i q_j R(i,j)
$$

其中 p,q 分别是行玩家和列玩家的混合策略概率分布。

那么如何计算混合策略的收益矩阵呢？答案是期望收益。

5. 极小极大最优策略

p*矩阵：指行玩家在考虑列玩家的所有行动下时，q在使p最小时能够获得的最大收益。

所谓的lower bound，下界，就是在这里的定义的。

同样也存在q*矩阵。那么接下来引入关键公式：

upper bound 上界可以从列玩家的角度考虑，即在考虑p的所有策略的最大值之后仍然使得其收益最小的值。一般来说，ub >= lb.

6. 博弈论在随机算法中的应用

寻找最优策略时可以视为纯策略：

列玩家的最优策略当然是选择pR概率最小的解的权重为1，因此此时情况退化到纯策略博弈

计算举例：

修改后，守门员在左侧的能力变弱，即射手选择左侧射门时的成功率提高（从 -1 变成 -1/2）。由于守门员在左侧的防守变差，射手的最优策略偏向左侧，最优概率调整为 p=4/7p = 4/7p=4/7（即 57.14% 选择左，42.86% 选择右）。

这一变化提升了射手的预期收益，并且使得博弈的值（value of the game）从 0 变为 1/7，即射手在长期博弈中比之前更占优势。

在 minimax 策略中，行玩家的目标是最大化自己最坏情况下的收益：
$$
\max_p min⁡(1−2p,2−4p)
$$

(1) 画图分析
右侧的图显示了两个期望收益的变化：

1−2p 是一条斜率为 -2 的下降直线。

2−4p是一条斜率为 -4 的下降直线。

要最大化最小收益，我们要寻找这两条曲线的交点，即：

1−2p=2−4p

解得：p=1/2

但这并不意味着 p=1/2 是最优策略，我们还要检查端点的收益。

(2) 端点分析

当 p=0 时：

1−2(0)=1

2−4(0)==2

最小值是 1。

当 p=1 时：

1−2(1)=−1

2−4(1)=−2

最小值是 -2。

行玩家希望 最大化最小收益，所以选择最大值的最小值：=1

因此，最优策略是 p=0，即行玩家始终选择第二行。

解释直觉

Minimax 原则：行玩家要确保即使在最坏的情况下，自己的收益也是最大的。

选择 p=0 时，列玩家无论怎么选，行玩家至少能得到 1，这是最优选择。

**如果选择 p=1，列玩家就可以让行玩家的收益变成 -2，这是更差的情况。

最终，行玩家的 minimax 策略是选择 p=0，而列玩家的最优策略是始终选择第一列，游戏值为 1。