42楼smartwxc
(......)
发表于 2009-3-2 15:26
只看此人
回复 39#海市蜃楼 的帖子
这些都是博弈论的内容，做学生时有过这样一门课，因为喜欢所以搜了点资料，附上一篇看看是否有帮助
在所有双人对局游戏中，拈是极其古老且饶富兴趣的一个课题。据说，拈源自中国，经由被贩卖到美洲的奴工们外传。辛苦的工人们，在工作闲暇之余，用石头玩游戏以排遣寂寞。流传到高级人士，则用辨士 (Pennils)，在酒吧柜台上玩。最有名的是将十二枚辨士分三列排成「三、四、五」的游戏，如下图：
游戏的规则很简单。两人轮流取铜板，每人每次需在某一列取一枚或一枚以上的铜板，但不能同时在两列取铜板，直到最后，将铜板拿光的人赢得此游戏。也可以做相反的规定：最后将铜板拿光的人输。
一个头脑灵活的赌棍不久就会发现，先取的人，在第一列的三枚铜板中取走二枚，就能稳操胜算。一个显而易见的规律是，只要你留下两列枚数相同的铜板，必可获胜。在这里对称扮演极重要的角色。
如果这个游戏只是「三、四、五」型态，那么不久后，大部份人就能熟悉其中规律，并且变得没有兴趣。有一个改变的方法是，将铜板的列数增加，每一列的枚数改变。这样的做法，的确使人有毫无规律的感觉，至少不至于像「三、四、五」型态的拈一样易于把握。
直到本世纪初，哈佛大学数学系副教授查理士．理昂纳德．包顿 (Chales Leonard Bouton) 提出一篇极详尽的分析和证明，利用数的二进制表示法，解答了这个游戏的一般法则：对任意列数的铜板，每列有任意枚数，如何取得致胜之道？
在包顿的术语中，拿过后剩下的残局不是安全 (safe) 就是不安全 (unsafe) 的局面。在所有安全的情况下，不管对方如何拿总是到一不安全的情况，你可以再取适当枚数的铜板（在适当的某一列），达到另一安全的情况，这样一直到拿光铜板为止，当然最后一次拿光铜板的一定是你。反之，你如果留下不安全的情况，对方必有方法在适当的某一列，取走适当枚数的铜板，达到他的安全情况，也就是说你输定了。
包顿的方法很简单。首先，将各列铜板的枚数化成二进制数，相加，但不进位，然后再看和的各个位数。如果和的各个位数都是偶数，则表示一安全残局;否则，如果有一位是奇数，则为不安全残局。例如「三、四、五」游戏，一开始就是不安全残局，先拿的人可以适当取二枚而造成他的安全残局。
[例一]
另一个不安全残局的例子如下：
[例二]
或者
为什么安全残局和不安全残局可以利用上述的方法判定呢？这个道理其实很简单。首先，如果将各列铜板数化为二进制表示法，相加，但不进位，得到的各个位数都是偶数的话，不论对方取那一列，多少枚铜板，则那一列铜板数所对应的二进制表示法中，必有某一位或数字由 0 变成 1 或者由 1 变成 0，其相加的和也相对的有某一位或数位由偶数变成奇数。例如，{1,4,5}这个安全残局，从第二列的 4 枚铜板取走 2 枚，则
相反的，如果和的某一位或数字是奇数，则我们有办法在某一列取走适当枚数的铜板，使得新的和的各个位数都是偶数。首先，选取和中所有为奇数的各个位数 ；例如在 {14,15,18,22} 的例子中和的第 1 和第 3 位是奇数。其次看这些位数中那一个是最左边一位；本例中当然是第 3 位。找某一列，使其二进制表示法在此位上刚好是 1；本例中，可以找第一例的14，也可以找第二列的15。然后将此列的铜板数所对应的二进制数中，凡是第 ai 位，都改变其数值，亦即若为 0 则变为 1，若为 1 则变为 0，如此得到一新数，我们只要在此列铜板取走适当的数目，使达到这新的枚数，即可以使新的和的各个位数都是偶数；例如，若考虑第一列的 14=1110 枚铜板，将其第 1 和第 3 位改变得到 1011=11 枚铜板，所以要在第一列取走 3 枚铜板。
相反规定，拿光铜板的人算输峙，只耍将上面的规律略加修饰，也可以控制局面。如果你一直拥有安全残局，对方一直处于不安全的情况，到某一时候，对方留下来的不安全残局一定会出现一种特殊型态，即是，除某一列铜板的枚数大于 1，其它各列均只有一枚铜板（拿光的各列不管它），这时候你的拿法要开始注意，你需将较多枚铜板这一列全部取光，或者拿到只剩下一枚，决定采取何者，完全看你拿了之后，要能使剩下的列数为奇数，当然每一列均只有一枚铜板。显而易见的是，以后一人都取一列，也是一枚，到最后拿的一定是对方，于是你就赢了。
有很多人把这个方法写成计算机程序，来和人对抗，不知就理的人被骗得团团转，无不惊叹计算机的神奇伟大。其实说穿了，只因为它计算比人快，数的转化为二进制其速度快得非人能比，如此罢了。
标题: (二)威氏游戏 (Wythoff's Game)
用来玩拈的道具不限于铜板。工余之时，石头可以玩；无聊磕瓜子时，瓜子可以玩；围棋子可以玩……。也可以将石头分堆放置，一堆相当于一列。这些都不是重点，我们甚至可以改变取铜板的规定，最后取光时输赢的规定……，于是，各种不同的变型游戏遂产生。
在拈的游戏中，如果只有两列铜板，则很容易看出来，留下两列枚数相同的铜板是致胜的安全残局。也就是我们一开始说的对称这个想法。事实上，包顿很巧妙的将对称化成二进制和的各个位数为偶数，将问题给一般化，这是很天才的想法。所以两列的拈是没有什么可说的。
将拈的规定略加修改，成为只有两列的威氏游戏，却极其有意思。规定是这样的，铜板只有两列，每列的枚数随玩者任意规定，两人轮流取铜板，取的时候，需要任一列中取一枚或多枚铜板，或者同时在两列取同样枚数的铜板，直到最后将铜板取光的人赢。当然也可以像拈一样有相反的规定，最后将铜板取光的人输。今只讨论前者。
拈的玩法完全不能适用于威氏游戏。所有拈的安全残局 {n,n}，在威氏游戏中都是不安全残局。因为我们加了一个规定，可以从两列铜板中同时取相同枚数的铜板。
[例3] 若 n 是正整数，则 {0,n} 和 {n,n} 都是不安全残局。
[例4] {1,2} 是安全残局。因为
不管如何取，总是成为不安全残局。
[例5] {3,5} 是安全残局。因为
不管对方如何取，不是到达例 3 的不安全残局，就是你可以再适当取，使成例 4 的安全残局。
继续推演下去，可以得到许多组安全残局 {1,2},{3,5},{4,7},{6,10},…。一般而言，第 n 组安全残局 {an,bn} 可由下式定义得到
(1) a1=1,b1=2。
(2) 若 已经求得，则定义 an 为未出现在以上这 2n-2 个数中的最小整数。
(3) bn=an+n。
做成表就是
n 1 2 3 4 5 6 7 8 9 10
an 1 3 4 6 8 9 11 12 14 16
bn 2 5 7 10 13 15 18 20 23 26
由(1)、(2)、(3)所定义的二数列 ，具有下列特性：
(甲) 数列 和 均是严格递增数列，而且 bn=an+n。
(乙) , 其中 N 表示正整数的集合， ,
(丙) 若 {an,bn}={am,bm}，则 n=m，即 an=am, bn=bm。
事实上，相反的，具有(甲)、(乙)性质的数列，也就是具有(1)、(2)、(3)性质的数列。
[定理] {an,bn} 是威氏游戏的安全残局，其余的组合 {x,y} 都是不安全残局。
[证] 我们只要证明下面二点即可。
(1)由任何一组 {an,bn} 取铜板，不管如何取，都不会成为另一组 {am,bm}。
假设从一组 {an,bn} 中的 an 取 x，bn 取 y 而能达到另一组 {am,bm}，则 an-x=am，bn-y=bm。
(i) 当 x=0，y>0 时，an=am 则 n=m，得 y=0，矛盾。
(ii) 当 x>0，y=0 时，bn=bm 则 n=m，得 x=0，矛盾。
(iii) 当 x=y>0 时， m=bm-am=(bm+y)-(am+x)=bn-an=n，矛盾。
(2)由任一组不是 {an,bn} 型的 {x,y} 可以适当取铜板使成某一组 {am,bm}。为方便计，可假设 y >= x。
(i)当 x 为某个 bm 时， y-am=y-(bm-m)=(y-x)+m>0，可在 y 中取 y-am，变成 {bm,am}。
(ii)当 x 为某个 am，且 y>bm 时，在 y 中取 y-bm，变成 {am,bm}。
(iii)当 x 为某个 am，且 时，y-x<m，令 k=y-x，则 y-bk=x+k-(ak+k)=x-ak>0。在 x 中取x-ak，在 y 中取 y-bk=x-ak 则变成 {ak,bk}。
这个定理不但告诉我们 {an,bn} 是威氏游戏的安全残局，其证明过程更暗含从不安全残局取铜板变成安全残局的法则。我们只要记住这个法则，还有 {an,bn} 组合，则无不处于优势。但是有一个问题是，当数目很大的时候，要记住一大堆 {an,bn} 是一件非常吃力不讨好的工作。我们于是自然会问，有没有像拈类似的法则用来判断任何一组 {x,y} 是否为威氏游戏的安全残局，而不必逐一计算 {a1,b1},{a2,b2} …。答案是有的，在解答这之前，我们需要谈谈费氏数列及相关的问题。
标题: (五)单堆游戏
在所有拈的变型游戏中，单堆游戏似乎是比较简单的。最常见而为大众熟悉的玩法是这样的：「两人轮流取一堆石头，每人每次最少取 1 个，最多取 k 个，最后取光石头的人赢得此游戏。」请问有何致胜之道？
和前面一样，所有的情况，可以分为安全和不安全两种。在这里 k+1 这个数扮演着极重要的角色，因为每次某一人拿的石头数 i，合于 1 <= i < k + 1，可见 1 <= k + 1 - i <= k，另一人总是可以取 k+1-i 个石头，使这两次所取的石头共有 k+1 个，由是可见 k+1 是安全残局，利用归纳法则 k+1 的倍数必为安全残局。反之，不是 k+1 倍数的任一自然数 n=q(k+1)+r，其中 1 <= r <= k，一次拿 r 个石头就能到达 q(k+1)，即某一安全残局，可见此时为不安全残局。
相反的规定：「最后取光石头的人输」，也可以分析知道，安全残局是 q(k+1)+1 这种型态的数。
并不是所有单堆游戏都是如此容易的，例如「奇偶游戏」则是较复杂的一种。所谓「奇偶游戏」只是将上述的问题略加修改，最后取光石头时的输赢的规定不同，即「两人轮流取一堆石头，每人每次最少取 1 个，最多取 k 个，到最后石头被取光时，若手中所有石头总数为奇数，则此人赢得此游戏。（也可以规定石头总数为偶数的人赢得此游戏）。」显而易见的是，原先这堆石头的总数要是奇数才有意义。这个游戏较前者更复杂，其安全残局视k的奇偶和 k+1 或 k+2 的倍数有关系。
另一个和骰子有关的单堆游戏由古先生 1 提出来，问题是这样的：「有一堆石头，数目不拘。首先任意掷一骰子，看出现几点，就取去几个石头。然后两人轮流翻转骰子到前次骰子出现那一面的旁边四面中任一面，但不可以翻到对面，也不可以不翻，翻到几点，就取去几个石头，如此轮流玩到一方没有办法拿石头，也就是说，剩下的石头数比他翻到的数目还小的时候，则他就算输了。」
首先耍了解的一点是，骰子上面六个数目安排的方法。从1到6的各个自然数在骰子上各出现一次， 1的对面是6，2的对面是5，3的对面是4。
这个游戏和第一个单堆游戏有点类似，却不相同。如果骰子出现i的时候，轮到你，则从1到6中的各数有两个，即是i和7-i，你不能翻到，其余四个随你高兴爱翻那一个都可以。所以每次你能够取的石头数，依前次对方所翻到的数目而定，而对方翻的数又因你前次翻的而定，如此相互影响，就显得很复杂了。仔细分析的结果，可以发现其安全残局和8的倍数有密切关系。有兴趣的读者可以自已试试看。
如果把骰子加成两个，然后规定每次翻两个骰子，把翻到的两个数字和算出来，取掉同样数目的石头，则又如何呢？如果还是有两个骰子，但每次只任选其中一个将它翻到新数目，看这数目是多少，就取掉多少石头，则又如何？或者，还是两个骰子，每次只任意翻转其中一个到新数目，但把这个新数目和另一个未翻的骰子相加，算出其和，取掉同样数目的石头，则又如何？当然，增加骰子的数目，则游戏更复杂。
最后我们想仔细讨论的一个单堆游戏叫做「双倍游戏」。这个游戏和骰子的单堆游戏有一共同的特性：每次所拿石头的个数受上次对方所拿石头的个数影响。
问题是这样的：「两人轮流取石，每人每次至少取 1 个石头，至多取上次对方所拿石头数目的两倍；最后拿光石头的人赢得此游戏。当然，第一个人不能第一次就取光所有石头。」
[例8] 2 是安全残局，因对方只能取 1。
[例9] 3 是安全残局。因
[例10] 5 是安全残局。因
如此继续推演下去，一个很有意思的结论是，所有费氏级数的项 fn 均是安全残局其余都是不安全残局。要证明这件事情可以分几步完成，主要的概念还是在于自然数的费氏数列标准表示法。
(i) 如果 n >= 1，则 fn<fn+1<2fn。
[证明]因为 f1=2，f2=3，f3=5，所以 n=1,2, 时易知为对。
若 n<k 时定理成立，则
两式相加
由归纳法得证。
ii) 如果你留下 x=fk1+fk2+ … +fkn-1+fkn 个石头，其中 i = 1,2,...n-1，而且对方下次所能取走的石头数目小于 fkn 则你留下的是一安全残局。
[证明] 假设对方拿走 个石头，其中 , , i=1,2,…,m-1。
当 时， 则
所以你可以取走 y' 个石头，使剩下 x'=fk1+fk2+ … +fkn-1 个石头，而且
也就是对方下次所能取走的石头数目小于 fkn+1 如此又可用归纳法继续推演本定理。其次，如果 kn>2+kn+1 分解
其中 t 为 >= 3 为奇数，而且 kn-t=kn+1 或 1+kn+1。
所以你可以取走 y' 个石头，使剩下
个石头，而且
2y'<2fkn-t<fkn-t+fkn-t+1=fkn-t+2
也就是下次对方所能取走的石头数目小于 fkn-t+2。同理可用归纳法。
(iii) 双倍游戏中的安全残局是 fn, n=1,2,…。
[证明] x=fn 时就如(ii)所述，对方所取的石头不超过 ，所以你是留下安全残局。
若一开始 x 不是 fn 型态，化为费氏标准式，
对方可以取去 fkm 剩下 ；轮到你时不得取超过 ，由(ii)可知他留下了他的安全残局，所以一开始是你的不安全残局。
[ 本帖最后由 smartwxc 于 2009-3-2 15:30 编辑 ].
