吃晃的狙击手

笔者小时候幻想过如下问题：假设士兵 Alice 在一块空旷的草地上被敌方狙击手 Bob 瞄准，要如何让自己尽可能活命。专业人士告诉我们，如果 Bob 训练有素，Alice 的存活概率是 0。

当然，我们直觉上会认为，通过随机地跑 S 线（不断转向）躲开狙击手的枪线，无疑更有可能迷惑其判断使其空枪。因此，我们不妨假设 Bob 是一名吃晃的狙击手，来探讨 Alice 应该采取怎样的策略提高自身的存活概率。

游戏规则

我们把问题抽象为如下游戏：Alice 在 坐标的整数点上运动，初始位置为 。在每个整数时刻 ，Alice 可以选择向左或右移动一个身位（对应于逃跑过程中的转向），即 ；Bob 则可以在任何整数时刻 ，决定瞄准 轴上的任何一个位置 开枪。Alice 的位置在任何时刻都是被 Bob 知晓的（因为他有瞄准镜），但 Alice 并不知道 Bob 会在哪一时刻开枪。

那么，如何定义 Bob 的「吃晃」呢？我们假设 Bob 的反应很慢，从决定开枪到真正扣下扳机，需要 个时间步；或者也可以理解为，子弹要经过 个时间步才能飞行到目标。无论采用哪种理解方式，总而言之，游戏遵循「Bob 成功击中 Alice 并获胜，当且仅当 」。很显然，Bob 无论何时开枪，都只有三个合理的瞄准位置，让他有机会命中，分别是 。

为了让 Alice 有一丝存活的概率，我们假设 Bob 只有一发子弹。草地是无限大且没有掩体的，即该游戏的进行时间是无限的。这个游戏我们记为 。粗略地讲，我们希望求出，在双方的最优策略下，Alice 的存活概率是多少；稍后我们将给出这个问题的严格叙述。

为了便于分析，我们也定义该游戏的有限时间版本：我们定义 与上述游戏唯一的区别是，我们限制 Bob 必须在第 个时刻及之前开枪，即进一步要求 。我们将通过分析 时 的性质来获得 的性质。

博弈论科普

我们刚刚谈到，我们想要求解的问题是：

在双方的最优策略下，Alice 的存活概率是多少？

在开始分析之前，我们必须要先弄清楚两个问题： - 什么叫「双方的最优策略」？ - 为什么在双方策略都可以调整的情形下，Alice 的存活概率是一个可以计算的确切的值？

事实上，上述游戏是「双玩家零和博弈」的一个实例，这是博弈论研究的最简单的一类问题，有非常成熟的工具解决它。下面我们为没有接触过相关理论的读者介绍所需的基础概念。如果读者已经非常熟悉，请跳过这一节。

在一个双玩家零和博弈中，最基本的情形是，双方玩家都采取一个确定的策略；两名玩家（Alice 和 Bob）的策略集（考虑有限情形）是两个有限集（不妨编号为 和 ），而博弈的 payoff 完全由两个玩家的策略决定，因此可以总结为一个矩阵 。对于两个玩家而言，他们的收益总是互为相反数，即分别为 和 。Alice 的目标是使 尽可能大（即最小化 的值），Bob 的目标是使 尽可能大。

在博弈论中，我们更关心双方玩家在「随机化策略」的意义下，能够获得的期望 payoff、以及相对应的「混合策略」是什么。一个混合策略即是在所有的策略上的概率分布。将分布写成向量，即两个玩家的策略 分别属于 那么，最终「Alice 选择 ，Bob 选择 」这个事件出现的概率是 ，因此，payoff 的期望是

这是一个双线性形式。因此，这类游戏也被称为 finite-dimensional zero-sum bilinear game。

那么，作为玩家之一，在不事先知道对方策略的前提下，应该如何选择己方的策略呢？我们以 Alice 的视角为例：假定她选择策略 ，那么在最坏情形下（这里的变量即是对方的策略 ，对 Alice 来说，最坏情形即是 最大的时候，因为她希望最小化之），她能保证的结果是 其中 表示 的第 个列向量；第一个等号是因为，我们总可以在 最大的分量上赋予全部的概率（即取 是 one-hot 向量），以此最大化想要的值。

Alice 希望最坏情况下的结果尽可能好，因此她希望最小化「上述值」，即她希望从下式中求解 作为她的最优策略：容易看出，这等价于如下线性规划问题 因而是有程序化的方法求解的。

同理，Bob 的最优策略 通过求解下式得到 至此，问题的对称性已经初具雏形。由于其对称的形式，此类博弈也被称为 min-max game。

纳什均衡

下面的定理给出了我们要用到的核心结论： 定理 (von Neumann). 对于任意 min-max game，存在 满足 被称为这个博弈的纳什均衡。由纳什均衡定义的 被称为博弈的「价值」。

von Neumann 定理有诸多证明，网络上很容易搜索到。证明之一是：验证两个 min-max game 对应的线性规划问题互为对偶，并利用强对偶性。如果读者没有接触过优化理论的知识，也没有关系，本文的叙述并不依赖该定理的证明。

纳什均衡是一类更广泛的博弈的产物，其更广泛的存在性需要用更高等的数学工具来证明。但是对于这里的情形，它有一个基于线性对偶理论的证明。我们推荐数学基础较好的读者参看文末的证明。对于本文的目的而言，我们只希望读者验证以下重要事实：

在纳什均衡处，即使一方玩家事先知道对方策略，他也不能取得更好的结果。

这个结论是十分迷人的：虽然双方玩家都是在不知晓对方策略的情形下，独立导出的己方最优策略；但双方策略形成的均衡，却使得双方都没有改变策略的动机（即使知晓了对方的策略）。

对于一般的零和博弈，其价值往往难以计算，但上述定理保证了其存在性，并且可以通过构造策略来证明它的上下界。具体地，如果我们构造了某个策略 ，满足 即 因而 即 只会比任意 Alice 策略保证的下界更小，即给出了一个 的上界。同理，可以通过构造 Bob 的策略来给出 的下界。

有限时间

我们用 来作为实例，感受一下 von Neumann 定理的强度。在博弈 中，Bob 只能在 时刻开枪，因此其有意义的策略仅有 ，共 种；Alice 是否中枪，只取决于其前两个时刻的行为，因此其策略（用两个时刻先后到达的位置表示）包括 共 种。这个博弈的 payoff 矩阵 因而是

	-2	0	2
(-1, -2)	1	0	0
(-1, 0)	0	1	0
(1, 0)	0	1	0
(1, 2)	0	0	1

对于任意 Alice 的逃跑策略 ，Bob 都可以选择瞄准三个位置中 Alice 到达的概率最大的那个，以最大化其收益（即命中的概率），显然这个值不小于 。因此，Alice 应该让这三个概率相等，即使得 一个满足要求的策略是 ，请读者验证，无论此时 是什么， 的值都等于 。类似地，请读者进一步验证， 也满足类似的性质，从而 是纳什均衡，博弈的价值为 。

类似地，可以证明 。我们指出，。

也许一些敏锐的读者会感到惊讶：不管 Bob 在哪一时刻开枪，Alice 都可以选择让自己 个时刻后处在三个位置的概率相等，从而让中弹的概率（即游戏的价值）至多是 ；按照这个思路，对于任意 价值不应该恒等于 吗？问题的关键在于，Alice 并不知道 Bob 开枪的时刻。为了实现上述策略，她必须保证自己在每一时刻的概率都均摊，通过研究 的性质，就可以发现这是做不到的。当然，如果 Alice 确切地知道 Bob 何时开枪，那么确实有 了。

无限时间

至此，完整问题的严格叙述已经呼之欲出了。我们想要解决的问题：

在双方的最优策略下，Alice 的存活概率是多少？

事实上就是求：

因此，我们要研究 作为一个数列的性质。首先，它显然是单调不降的，这是因为对于狙击手 Bob 而言，在 中，他总可以采取 中的策略，这样他至少可以保证 的结果，因此至少有 。特别地，。

另一方面，对于任意 ，如前文所说，我们可以也构造一个 Alice 的策略 ，保证任何情况下 不大于某个常数，从而证明一个 的上界。我们尝试构造如下一类策略，它包含一个参数 ：

在 时，Alice 以 的概率向左走（到达 ），以 的概率向右走（到达 ）。此后，她每一步以 的概率保持上一步的方向继续前进，或以 的概率调转方向。

这个策略的重要之处在于，它每一步的决策过程都是完全对称的（这与我们上一节中为 构造的最佳策略不同）。按照这样定义的策略，无论 Bob 在何时 开枪， 时刻 Alice 的位置在 三个点的概率值总分别是 或 。对 Alice 而言的最坏情况下，Bob 总会选择瞄准这三个概率中最大者对应的位置，因此，Alice 应当尽可能使这三个值都很小。注意到 ，因此事实上，这一类策略中最优者应该最小化 求得 此时 Bob 的 payoff（即他能保证的最大命中概率）为 这不是最佳策略，因此该值只是一个上界，即 至此我们证明了， 是一个单调有界的序列，因此保证了 的存在性（事实上，如果读者足够细心，应当在此之前就提出了存在性的疑问）。那么，这个上界能取到吗？首先，我们观察到一个有趣的事实：

命题. 是有理数。 证明. 的 payoff matrix 是一个元素均为 0 或 1 的矩阵。这个 min-max game 对应的线性规划问题为：线性规划问题的解在可行域的顶点处取得，即 是某个由部分约束方程的等式形式确定的解。但是，三类约束方程的变量系数均为有理数，因此 也是有理数。

因此，事实上有： 命题. Samuel Karlin 于 1958 年证明了，虽然任意有限的 都取不到这个上界，但 确实收敛到这个值。证明没有用到任何高深的工具，只牵涉到一些计算技巧，对于掌握中学数学知识的读者是完全可以理解的。下面让我们来欣赏这个证明。

直面递推

很容易想到，由于问题是递归定义的，应该可以对问题进行递推的拆解。对于 ，我们定义 为：Alice 固定采取「 时，以 的概率向左， 的概率向右」的策略时， 的价值。显然有 。很显然也应该有 ，。

那么， 的递推是什么呢？这依赖于 Alice 第二步的策略，所以我们记其策略中，「第一步向左时，第二步也向左」的概率为 ，「第一步向右时，第二步向左」的概率为 。这样，用 三个参数，我们就可以描述 Alice 在两步之内的任何一种策略了。两步之后，她可以所处的位置和概率分别为 如果 Bob 在 时刻开枪，那么对 Alice 来说，最坏情况下 Bob 会瞄准这三个位置中概率最大的那一个（三个选项）；当然，只要 ，Bob 也可以不在 时刻开枪（第四个选项），这种情况下他只能在之后的 个时刻内开枪，因此他能获得的最大收益是 于是，对 Alice 的最坏情况下，Bob 会选择四种选项中 payoff 最大者，因此有递推：边界为 直接计算可得，，，且在剩余区间内它是线性函数。

设 收敛到 。 应该是递推式的不动点，即满足 我们要求的即是 这里取得最小值的 不是唯一的，所以我们记满足 的 中最小者为 。那么应当有 进一步设这里的 由 取得，那么有 注意到最后一行的 ，所以 ，所以 ，由对称性也有 再看第二行，我们有 ，因此 。

下面我们来证明 也不能成立。若不然，由 相加得 右边在 上是单调递减的，且 ，因此 解得 ，这与 是矛盾的。因此，。

因此 中的第二项至少是 ，因而必须等于 ，从而 从而 解得 。由此证明了