约翰纳什的石子博弈_柴靖涵yoyo

创建时间：2016-12-09 浏览数：2596

这一次的作业而是约翰纳什的石子博奕，石子博弈的游戏我虽然听老师说了，但是我还想在更加了解一下，下面是我从百度搜来的资料:
博弈论——取石子问题

分类：算法导论/数据结构

取石子是一种很有意思的游戏，就是有物体若干堆，可以是火柴棍或是围棋子等等均可。两个人轮流从堆中取物

体若干，规定最后取光物体者取胜。这是我国民间很古老的一个游戏，别看这游戏极其简单，却蕴含着深刻的数学原理。下面我们来分析一下要如何才能够取胜。

（一）巴什博弈（Bash Game，同余理论）：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。

显然，如果n=m 1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次

拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果n=（m 1）r s，（r为任意自然数，s

≤m),那么先取者要拿走s个物品，如果后取者拿走k（≤m)个，那么先取者再拿走m 1-k个，结果剩下

（m 1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m 1）的倍

数，就能最后获胜。

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

者胜。

（二）威佐夫博弈（Wythoff Game，黄金分割）：有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。这种情况下是颇为复杂的。我们用（ak，bk）（ak ≤ bk ,k=0，1，2，...,n)表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12

，20）。

可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而 bk= ak k，奇异局势有

如下三条性质：

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

由于ak是未在前面出现过的最小自然数，所以有ak > ak-1 ，而 bk= ak k > ak-1 k-1 = bk-1

> ak-1 。所以性质1。成立。

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

事实上，若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其他奇异局势中，所

以必然是非奇异局势。如果使（ak，bk）的两个分量同时减少，则由于其差不变，且不可能是其他奇异局

势的差，因此也是非奇异局势。

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

假设面对的局势是（a,b），若 b = a，则同时从两堆中取走 a 个物体，就变为了奇异局势（0，0）

；如果a = ak ，b > bk，那么，取走b - bk个物体，即变为奇异局势；如果 a = ak ， b < bk ,则同

时从两堆中拿走 ak - ab - ak个物体,变为奇异局势（ ab - ak , ab - ak b - ak）；如果a > ak ，

b= ak k,则从第一堆中拿走多余的数量a - ak 即可；如果a < ak ，b= ak k,分两种情况，第一种，

a=aj （j < k）,从第二堆里面拿走 b - bj 即可；第二种，a=bj （j < k）,从第二堆里面拿走 b - aj

即可。

从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者

取胜。

那么任给一个局势（a，b），怎样判断它是不是奇异局势呢？我们有如下公式：

ak =[k（1 √5）/2]，bk= ak k （k=0，1，2，...,n 方括号表示取整函数)

奇妙的是其中出现了黄金分割数（1 √5）/2 = 1。618...,因此,由ak，bk组成的矩形近似为黄金矩形，

由于2/（1 √5）=（√5-1）/2，可以先求出j=[a（√5-1）/2]，若a=[j（1 √5）/2]，那么a = aj，bj

= aj j，若不等于，那么a = aj 1，bj 1 = aj 1 j 1，若都不是，那么就不是奇异局势。然后再按

照上述法则进行，一定会遇到奇异局势。

（三）尼姆博弈（Nim Game，异或理论）：有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

这种情况最有意思，它与二进制有密切关系，我们用（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加的结果：

1 =二进制01

2 =二进制10

3 =二进制11 （）

———————

0 =二进制00 （注意不进位）

对于奇异局势（0，n，n）也一样，结果也是0。

任何奇异局势（a，b，c）都有a（）b（）c =0。

如果我们面对的是一个非奇异局势（a，b，c），要如何变为奇异局势呢？假设 a < b< c,我们只要将 c

变为 a（）b,即可,因为有如下的运算结果: a（）b（）(a（）b)=(a（）a)（）(b（）b)=0（）

0=0。要将c 变为a（）b，只要从 c中减去 c-（a（）b）即可。

例1。（14，21，39），14（）21=27，39-27=12，所以从39中拿走12个物体即可达到奇异局势（14

，21，27）。

例2。（55，81，121），55（）81=102，121-102=19，所以从121中拿走19个物品就形成了奇异局势

（55，81，102）。

例3。（29，45，58），29（）45=48，58-48=10，从58中拿走10个，变为（29，45，48）。

例4。我们来实际进行一盘比赛看看：

甲:(7,8,9)->(1,8,9)奇异局势

乙:(1,8,9)->(1,8,4)

甲:(1,8,4)->(1,5,4)奇异局势

乙:(1,5,4)->(1,4,4)

甲:(1,4,4)->(0,4,4)奇异局势

乙:(0,4,4)->(0,4,2)

甲:(0.4,2)->(0,2,2)奇异局势

乙:(0,2,2)->(0,2,1)

甲:(0,2,1)->(0,1,1)奇异局势

乙:(0,1,1)->(0,1,0)

甲:(0,1,0)->(0,0,0)奇异局势

甲胜。

上面就是所有的资料了，下面我们开始正式做题，根据上面的资料我们也了解到了一些信息，所以坐骑就更好做了！

我首先做了一个大概的ppt，让大家先了解一下这些主要信息，然后再是excel，然后下来是手绘，文字。

ppt:

上面是我做的一个PPT，模板是用手绘黑板报完成的，里面的一些装饰物是我通过百度来下载的，我做的ppt，的软件试用wps office完成的，下面是我用wps office，做的excel表格。
excel表格: 001954a853fb042236.jpg?6.4.01

上面是我用excel做的，我放大了应该比较清晰，两次都是我赢，下面的这个是我手绘的。
手绘图: 010311fe5907486367.jpg?6.4.01

这是我画的手绘图，有些不清晰，光线太暗，请见谅！
文字:本次的作业是石子博弈，这个游戏可以让人理清思路，这个游戏我和妈妈玩了两次，因为我课上学的比较多，所以两次都赢了，下面是具体过程，就拿钻石当石子吧！
????????????
第一次石头剪刀布我赢了，我先拿石子，然后妈妈再拿！
我:?1
妈妈:???4
我:??6
妈妈:???9
我:??11
妈妈:?12
第一局妈妈输了，因为妈妈一直以为拿最多的就可以赢！刚好我告诉她了应该拿第三个，第七个，我真后悔，但我随机应变赢了妈妈！
下来是第二局，这一次用足球来代替石子！第二次石头剪刀布，一局平，二局妈妈赢，所以这次妈妈先拿石子！
⚽⚽⚽⚽⚽⚽⚽⚽⚽⚽⚽⚽
妈妈:⚽⚽⚽3
我:⚽4
妈妈:⚽⚽6
我:⚽7(哈哈我终于拿到第七个啦)
妈妈:⚽⚽9
我:⚽⚽11(哈哈，我又赢了)
妈妈:⚽12
第二局妈妈懂得了真正的规则，有一会儿分心，所以我又赢了，本来妈妈是赢的，我本来想试下用妈妈的重复必败战术试一下，后来在第二次尝到了甜头，但是妈妈接下来在一弄，我就害怕，然后我开始认真了，又随机应变打败了妈妈！
下面是妈妈和我要写的东西:
153627baf598672389.jpg?6.4.01