三种经典博弈（取石子问题）-Toy模板网

这篇具有很好参考价值的文章主要介绍了三种经典博弈（取石子问题）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

三种经典博弈（取石子问题）

博弈是有一种很有意思的游戏，就是有物体若干堆，可以是火柴棍或是围棋子等等均可。两个人轮流从堆中取物体若干，规定最后取光物体者取胜。这是我国民间很古老的一个游戏，别看这游戏极其简单，却蕴含着深刻的数学原理。下面我们来分析一下要如何才能够取胜。

巴什博奕

有一堆 $n$ 个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取 $m$ 个。最后取光者得胜。

显然，如果 $n = m + 1$ ，那么由于一次最多只能取 $m$ 个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。

因此我们发现了如何取胜的法则：如果 $n = (m + 1) r + s$ ，（ $r$ 为任意自然数， $s\leq m$ ），那么先取者要拿走 $s$ 个物品，如果后取者拿走 $k$ （ $\leq m$ ）个，那么先取者再拿走 $m + 1 - k$ 个，结果剩下 $(m + 1) (r - 1)$ 个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下 $(m + 1)$ 的倍数，就能最后获胜。

这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到 $100$ 者胜。

威佐夫博奕

有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

这种情况下是颇为复杂的。我们用 $a_k,b_k)$ $(a_k \leq b_k, k=0,1,2,\ldots,n)$ 表示两堆物品的数量并称其为局势，如果甲面对 $(0, 0)$ ，那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是： $(0, 0)$ 、 $(1, 2)$ 、 $(3, 5)$ 、 $(4, 7)$ 、 $(6, 10)$ 、 $(8, 13)$ 、 $(9, 15)$ 、 $(11, 18)$ 、 $(12, 20)$ 。（统计小规模数据）

可以看出， $a_0=b_0=0$ ， $a_k$ 是未在前面出现过的最小自然数，而 $b_k= a_k + k$ 。发现规律，得到猜想。

奇异局势有如下三条性质：

任何自然数都包含在一个且仅有一个奇异局势中。

由于 $a_k$ 是未在前面出现过的最小自然数，所以只需证明 $b_k$ 不会出现在前面的奇异局势中即可。由于 $a_k > a_{k-1}$ ，而 $b_k= a_k + k > a_{k-1} + (k-1) = b_{k-1} > a_{k-1}$ 。所以性质 1 成立。（从第 0 项到第 $k$ 项， $a_k$ 是递增的；由于 $b_k=a_k+k$ ，所以 $b_k$ 也是递增的。）

任意操作都可将奇异局势变为非奇异局势。

事实上，若只改变奇异局势 $a_k,b_k)$ 的某一个分量，那么另一个分量不可能在其他奇异局势中（性质 1），所以必然是非奇异局势。如果使 $a_k,b_k)$ 的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差（因为 $k$ 是递增的，所以每个奇异局势对应唯一一个差），因此也是非奇异局势。

采用适当的方法，可以将非奇异局势变为奇异局势。

假设面对的局势是 $(a, b)$ （设 $a\leq b$ ，否则先交换 $a$ 和 $b$ ），若 $b = a$ ，则同时从两堆中取走 $a$ 个物体，就变为了奇异局势 $(0, 0)$ ；如果 $a=a_k$ ， $b>b_k$ ，那么，取走 $b-b_k$ 个物体，即变为奇异局势；如果 $a=a_k$ ， $b<b_k$ ，则同时从两堆中拿走 $a_k-a_b-a_k$ 个物体，变为奇异局势 $ab-a_k,ab-a_k+b-a_k)$ ；如果 $a>a_k$ ， $b=a_k+k$ ，则从第一堆中拿走多余的数量 $a-a_k$ 即可；如果 $a<a_k$ ， $b=a_k+k$ ，分两种情况，第一种， $a=a_j$ （ $j < k$ ），从第二堆里面拿走 $b-b_j$ 即可；第二种， $a=b_j$ （ $j < k$ ），从第二堆里面拿走 $b-a_j$ 即可。

从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。
给定一个局势 $(a, b)$ ，如何判断它是否为奇异局势呢？我们可以使用以下公式：

$a_k = \left\lfloor k\left(1+\sqrt{5}\right)/2 \right\rfloor, \quad b_k = a_k + k \quad (k=0,1,2,\ldots,n)$

其中， $\lfloor x \rfloor$ 表示取整函数。有趣的是，公式中出现了黄金分割数 $(1+\sqrt{5})/2 = 1.618\ldots$ ，因此由 $a_k$ 和 $b_k$ 组成的矩形近似为黄金矩形。我们可以先求出 $\lfloor a(\sqrt{5}-1)/2 \rfloor$ ，然后判断：

若 $a = a_j$ ，则 $a$ 是奇异局势， $b = a_j + j$ ；
若 $a = a_{j+1}$ ，则 $a_{j+1}$ 是奇异局势， $b = a_{j+1} + j + 1$ ；
否则，继续按照上述方法进行判断，直到找到奇异局势或者判断结束。

另一种判断方法是：给定 $(a, b)$ （ $a < b$ ），先计算 $k = b - a$ ，然后根据 $k$ 计算 $a_k$ 和 $b_k$ 。如果 $a_k = a$ 且 $b_k = b$ ，那么 $(a, b)$ 是奇异局势，否则不是。

尼姆博奕

有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。这种情况最有意思，它与二进制有密切关系，我们用 $(a, b, c)$ 表示某种局势，首先 $(0, 0, 0)$ 显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是 $(0, n, n)$ ，只要与对手拿走一样多的物品，最后都将导致 $(0, 0, 0)$ 。仔细分析一下， $(1, 2, 3)$ 也是奇异局势，（我先拿之后，）无论对手如何拿，接下来都可以变为 $(0, n, n)$ 的情形。

计算机算法里面有一种叫做按位模 2 加，也叫做异或的运算，我们用符号 $(+)$ 表示这种运算。这种运算和一般加法不同的一点是 $1 + 1 = 0$ 。先看 $(1, 2, 3)$ 的按位模 2 加的结果：

$\text{二进制 } 01 \\ 2 = \text{二进制 } 10 \\ 3 = \text{二进制 } 11 \\ 1 \text{ (+) } 2 \text{ (+) } 3 = 0 \text{ (注意不进位)}$

对于奇异局势 $(0, n, n)$ 也一样，结果也是 $0$ 。任何奇异局势 $(a, b, c)$ 都有 $\text{ (+) } b \text{ (+) } c = 0$ 。

如果我们面对的是一个非奇异局势 $(a, b, c)$ ，要如何变为奇异局势呢？假设 $a < b < c$ ，我们只要将 $c$ 变为 $\text{ (+) } b$ 即可，因为有如下的运算结果：

$\text{ (+) } b \text{ (+) } (a \text{ (+) } b) = (a \text{ (+) } a) \text{ (+) } (b \text{ (+) } b) = 0 \text{ (+) } 0 = 0$

要将 $c$ 变为 $\text{ (+) } b$ ，只要从 $c$ 中减去 $\text{ (+) } b)$ 即可。文章来源地址https://www.toymoban.com/news/detail-475441.html

到了这里，关于三种经典博弈（取石子问题）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

三种经典博弈（取石子问题）

巴什博奕

威佐夫博奕

尼姆博奕

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2