博弈论——两人取子游戏与威佐夫博弈，隐藏在背后的黄金分割

本文始发于个人公众号： TechFlow ，原创不易，求个关注

今天是 算法和数据结构专题 第25篇文章，我们继续博弈论专题。

在上一篇文章当中我们了解了最简单的巴什博奕，今天我们来看看另一个经典的博弈模型—— 威佐夫博弈 。博弈论和机器学习有些类似，数学家们针对场景进行建模，设计出了几个经典模型。然后我们在面临具体问题的时候，对问题进行深入分析，寻找最合适的模型应用来解决它。

石子问题

我们来看一道经典的例题，有两堆石子，有两个 绝顶聪明 的人在玩一个游戏。每次每个人可以从其中一堆石子当中取走任意数量的石子，或者是从两堆当中同时取走相同数量的石子。无法取石子的人落败，请问，在告知两堆石子数量的情况下，这两个人当中哪一方会获胜？

我们简单分析一下，会发现 一些局面是先手必败的 。比如说(0, 0)，再比如(1, 2)。我们简单分析一下(1, 2)，先手有4种策略，首先他可以取走第一堆，那么后手可以取完第二堆，显然后手获胜。他也可以在第二堆当中取1个，这时剩下(1, 1)，后手会同时取完，同样是后手获胜。第三种是他取走第二堆，后手可以取完第一堆，后手获胜。第四种是他在第一堆和第二堆当中同时取走一个，这时第二堆剩下一个，后手胜。

那么，这些 必败的状态之间有什么规律呢 ？我们怎么找到这个规律，并且找到解呢？

分析

我们可以枚举几个必败的状态：(0, 0), (1, 2), (3, 5), (4, 7)…

我们观察一下这些状态，可以找到两条规律。我们假设从小到大排的第k个必败状态是(x, y)，并且x < y。我们可以发现y = x + k。也就是说 必败状态两个数的差值是递增的 ，这也说明了每一个必败状态的差值都各不相同。

其实这是很容易证明的，我们用反证法，假设(a, a+k), (b, b+k)都是必败状态，并且a < b。那么先手在面临(b, b+k)的时候，只需要在两堆当中同时取走b-a个石子，那么给后手的局面就是(a, a+k)。对于后手来说，这是一个必败的局面，这就和(b, b+k)先手必败矛盾，所以 不存在两个必败局面的差值相等 。

我们也可以作图分析，我们 把两堆石子的数量看成是坐标轴上的一个点 。所以游戏就变成了：棋盘上有一个点，每次每个人可以将它向下、向左或者向左下移动若干个格子，不能移动的人输。终止节点显然是原点， 一步就能移动到原点的点显然是必胜点 ，假设我们给这些所有必胜点都染色的话，剩下的的没当中横纵坐标和最小的点就是下一个必败点。因为它不论如何移动，都会给对手留下一个必胜点。

我们根据上面的逻辑把必败点都染色，可以得到下面这张图：

从这张图可以看出，必败点之间不能通过一次移动得到，换句话说 可以一次移动到必败点的点都是必胜点 ，从图上可以看出，除了必败点的之外的点都是必胜点，并且每一个自然数都必然只会被包含在一个必败状态当中。

到这里，我们距离解法已经很接近了，现在剩下的问题是，我们如何根据x和y的取值快速判断它们是否构成一个必败局面呢？也就是说我们能不能 找出一个通项公式 ，对于第k个必败局面，它的坐标是( \(x_k, y_k\) )呢？

求解

为了写出通项公式，我们需要引入 Betty定理 。

设a和b是两个正无理数，并且 \(\frac{1}{a} + \frac{1}{b} = 1\)

记P={[ \(a_n\) ], \(n \in N^+\) }, Q={[ \(b_n\) ], \(n \in N^+\) }，则 \(P \cap Q = \varnothing\) ， \(P\cup Q = N^+\)

证明

\(P\cap Q = \varnothing\)

反证，我们假设存在 \(k \in P\) 并且 \(k \in Q\) ，即存在正整数n， m满足 k < an, bm < k+1。

也就是： \(\frac{n}{k} > \frac{1}{a} > \frac{n}{k+1}, \frac{m}{k} > \frac{1}{b} > \frac{m}{k+1}\) 两个式子相加可以得到： \(\frac{m+n}{k} > 1 > \frac{m+n}{k}\)

即 \(k < n+m < k+ 1\) ，这与n，m，k都是正整数矛盾

\(P \cup Q = N^+\)

反证，假设存在 \(k \notin P\) 且 \(k \notin Q\) ，即存在正整数n，m满足 \(an < k < a(n+1)-1, bm < k < b(m+1)-1\)

即： \(\frac{n}{k} < \frac{1}{a} < \frac{n+1}{k+1}, \frac{m}{k} < \frac{1}{b} < \frac{m+1}{k+1}\)

相加，可以得到： \(\frac{m+n}{k} < 1 < \frac{n+m+2}{k+1}\)

即：n + m < k < n + m + 1，这与n，m，k均为正整数矛盾

我们花了这么大力气来证明Betty定理就是为了用的，因为我们发现 必败状态的通项和Betty定理序列很像 。我们不妨假设存在这样的a, b同时满足Betty定理与必败状态的性质：

\[[an] + n = [bn], \frac{1}{a} + \frac{1}{b} = 1 \]

\[[an] + n = [an + n] = [(a+1)n] = [bn] \]

代入可以得到：

\[\frac{1}{a} + \frac{1}{a+1} = 1 \]

解这个方程，可以得到 \(a = \frac{1 + \sqrt{5}}{2}\approx 1.618\) ，熟悉数学的同学相信一下就看出来了，这个数是 黄金分割 的比例，这是巧合吗，还是藏着更深的道理呢？

至少，求出了a之后，我们就可以非常简单地判断必败状态了：

import math
def lose_or_win(a, b):
    if a > b:
        a, b = b, a
    
    k = b - a
    # 根据差值k求出第k个必败状态，判断是否相等
    return not (int(k * (math.sqrt(5)+1) / 2)) == a

总结

和之前介绍的巴什博奕相比，威佐夫博弈的推导过程要复杂得多，但是虽然推导过程依然复杂，但是仍然挡不住最后实现的代码非常简单。

另外，在推导的过程当中，我们用到了Betty定理，这个定理的推导和证明虽然不难，但是如果不是数学专业的同学，可能大概率都没有接触过。这其实体现了博弈论本身和数学的关系是非常紧密的。一个看起来非常简单的问题，引申出了一系列眼花缭乱的推导和证明，怎么样，大家看得还过瘾吗？

今天的文章到这里就结束了，如果喜欢本文，可以的话，请 点个关注 ，给我一点鼓励，也方便获取更多文章。