当前位置: 华文星空 > 财经

双人回合制智力竞技游戏是否都存在先手优势?

2017-10-25财经
@morpheus

说的动态博弈我并没有专门学过,而

@龙洋

所说的,应该是 Finite Impartial Two-player Strategy Game of Perfect Information ,对此我有过一些了解,我来大致说一下。首先,先来解释一下这个这么长的词是什么意思:

Finite:这是指,游戏是在 有限 步数之内可以分出胜负的,比如Nim游戏。Nim游戏我稍后会介绍。

Impartial:这个意思是,对于同一个游戏局面,下一步无论谁走,可做出的移动是 一样的 。这是什么意思呢?比如

@龙洋

所说的游戏,现在如果已经数到了3,无论接下来轮到红方还是蓝方,他们都可以选择查4或4,5。那什么游戏是不是Impartial的呢?比如象棋。在同一个局面下,考查下一步。一方只能动红子,一方只能动黑子。也就是说, 一方能做出的移动另一方做不了 ,所以象棋不是Impartial的。

Two-player:这个很容易理解,就是两个人之间玩的游戏。

Strategy Game:这也就是题主所说的『智力竞技游戏』的意思,而不是靠运气。

of:唔,这是个介词。

Perfect Information:译为完全信息。这是指每个参与者都可以了解到其他参与者的 一切信息 ,还用

@龙洋

的例子,对于每一个局面,玩家都可以知道对方接下来所有可能的移动,所以这个游戏是完全信息的。而很多扑克牌游戏并不是完全信息,因为每个玩家 不知道其他玩家手上有什么牌

好的,接下来介绍一个典型的Finite Impartial Two-player Strategy Game of Perfect Information,那就是 Nim游戏 。Nim游戏很类似与

@龙洋

的例子,不过我这里介绍原版:

有若干堆有限数量的石子,两人轮流取,每次必须且只能从其中一堆石子里取走若干(至少取一个,最多可以把整堆全部拿走),拿走最后一个石子的人获胜。

这是不是很有小学奥数的即视感!

先上结论:

如果两个知道Nim游戏策略的人要一起玩这个游戏,那么他们只需要看一下桌上石子摆放的状态,就可以知道谁会赢谁会输了。

接下来介绍几个名词:

Position :Position是指游戏目前的局面(State),并通过最精简的语言叙述出来。

P position :走上一步的玩家 可以确保胜利 的局面。(P指Previous)

N position :走下一步的玩家 可以确保胜利 的局面。(N指Next)

所以, 玩家都希望把游戏变为P position ,这样自己对于P position来说,就是走了上一步的玩家。

注意,在Finite Impartial Two-player Strategy Game of Perfect Information中, 每一个position要么是P position,要么是N position

P position和N position有这么几个性质:

1. The winning position (or final position) is a P position.

2. Every P position can not be transferred from another P position within one move.

3. Every N position can be transferred into a P position within one move.

本想偷懒,直接把课上的内容搬上来……还是来翻译一下吧。

1. 游戏最后的局面是一个P position ,因为上一个玩家把最后一个石子拿走了,上一个玩家赢了。

2. 每一个P position在一步之内无法转换为另一个P position 。这个也很好理解,如果我拿完石子之后是个P position,那么我应该可以保证游戏的胜利,如果你走完下一步,又变成了P position,那么你也可以保证胜利。不可能两方同时取胜,矛盾,哼唧。

3. 每个N position都可以在一步之内变为P position 。这也不难理解,因为如果现在是N position,就意味着走下一步的玩家可以保证获胜,怎么保证获胜呢?就是把游戏变为P position。所以只要是N position,那么它都可以在一步之内变为P position。

这么说有些抽象,我们来看一个具体的Nim游戏的例子。比如一开始桌上有两堆石子,一堆14个,一堆57个,记为(14,57),玩家是你和我。其中,我对Nim游戏有了解,而你没有,所以,嘿嘿。【各位先看,游戏结束之后再分析为什么。】

我一看(14,57),呀,这是个N position,我得先走,把它变成一个P position。于是我提出要先走,你很大度地点了点头。

我从57个石子的那一堆中拿走了43个石子,还剩下14个石子。于是现在的position是(14,14),P position。

你完全不知道该怎么办,嗯,反正都是14个,我随便选一堆拿走一半好了。于是变为(7,14)。

我一看,嗯,果不其然是N position,好,我从另一堆里也拿7个。(7,7),P position。

你打算矜持一点,拿走了一个,变为(6,7)。

我从另一堆里拿了一个,变为(6,6)。

你拿走三个,(3,6)。

我拿走三个,(3,3)。

你大喊:「你干嘛学我!」一气之下把一堆全拿光了,(0,3)。

我大喊:「我就学你!」一气之下把另一堆也拿光了,(0,0)。【这不是颜文字啊!这是数学啊数学!!】

我赢了,yay~!

各位应该已经发现了,我一开始把两堆石子变成一样多,然后只需要学你就行了,这样就可以一直保证我拿完之后两堆一样多,直到(0,0)。

所以,在这个游戏中, (n,n)是P position,其余都是N position

那如果一开始有三堆棋子怎么办呢?n堆呢?美国数学家Charles L. Bouton发明了Nim游戏的通解。

1.把每一堆石子的数量都换成二进制。

2.把这些二进制数字 不进位地竖式相加 (其实是 异或 ,这里为了通俗易懂一点),比如1+1=0,1+1+1=1,得到一个新的数m。如果这个数是0,那么目前的游戏处于P Position。若不是0,继续。

3.把m 从左数第一位不是0的数位 (是1)圈出来,然后在 竖式中的这一列 数字中找一个1。一定有1,否则最后加起来是0,而不是1。

4.找到1之后,把1改为0,然后把包含这个改动的数记为s。

5.接下来, 只要m的其中一个数位上是1,就把s对应数位的数字改掉 ,即0改为1或者1改为0。

6.把二进制换回十进制,按照结果取石子。

好的,我知道这个很抽象,我们来举例子。

比如一开始的position是(27,25,12),那么我接下来要做这样的事情。

11011 (27)

11001 (25)

+1100 (12)

----------(不进位的竖式加法)

01110 (m)

m 从左数第一位不是0的数 是1。噗,废话。是从左数第二位上的那个1啦。

好的,我们在那个1所在的一列(第二列)中找一个1。哎?都是1。那就随便找一个,比如第一行第二列的1。并且把第一个数记为s。

11011 (s)

11001 (25)

+1100 (12)

----------(不进位的竖式加法)

01110 (m)

把第一行第二列的1改为0,并且 把s的每一个m是1的数位都改掉 。这个例子中,m的第2、3、4位是1,所以把s的2、3、4位改掉。

10101 (s)

11001 (25)

+1100 (12)

----------

01110 (m)

把s换回十进制,得21。所以,我下一步要把(27,25,12)变为(21,25,12)。

接下来无论你怎么走,我都用这个方法,就 可以确保胜利 了。

回过头看两堆石子的情况,其实也是如此。因为两个一样的数换为二进制后,进行不进位的加法,0+0=0,1+1=0,得到的就是0。所以(n,n)对应了每一个P position。

好的,现在大家都是Nim游戏小王子了!

那对于其他类似的游戏,我们怎么来找P position和N position呢?方法如下:

1.找 已知最小的 P position。(正如之前所说,胜利的position一定是P position)

2.把每一个能 一步走到 这个P position的position都列出来,这些都是N position。

3.没有列出来的 最小的 position就是一个P position。

4.返回1。

其实这就是利用了之前所说的P position和N position的性质。

空说无凭,我们再来看看

@龙洋

所使用的例子。方便起见,我换一个规则:

两人轮流报数,从28开始依次递减,每人每次最少报1个数,最多报4个数,报到0的人获胜。

最小的P position是0,因为报到了0的那个人获胜。

所有能报到0的局面是1,2,3,4。没有列出来的最小的数是5,所以5是下一个P position。

所有能报到5的局面是6,7,8,9。没有列出来的最小的数是10,所以10是下一个P position。

…………

可以看出,所有5的倍数都是P position。所以在游戏中,我只需要不断把数报到5的倍数,就可以确保胜利了。

现在增加一点难度,其他规则不变,但每次每个人只能报1个、2个或4个数呢?方法一样。

最小的P position是0,因为报到了0的那个人获胜。

所有能报到0的局面是1,2,4。没有列出来的最小的数是3,所以3是下一个P position。

所有能报到3的局面是4,5,7。没有列出来的最小的数是6,所以6是下一个P position。

所有能报到6的局面是7,8,10。没有列出来的最小的数是9,所以9是下一个P position。

…………

这回,P position是3n。

当然,P position不会每次都如此工整,但都是 有规律可循的

好的,我们再增加一点难度,其他规则不变,即,两人轮流报数,每人每次最少报1个数,最多报4个数。但我们有两个数,16和28,每次只能选择一个数,报完之后两个数都为0的人获胜。

等一下,是不是有种 似曾相识 的感觉?对了! Nim游戏! 但是又不完全一样,因为Nim游戏从一堆里拿石子的个数是没有限制的。 也就是说,这个游戏里的(16,28)与Nim游戏里的(16,28)是不一样的。

那有没有什么办法让它们变得等价呢?有!这就牵涉到一个新的概念, Nimber 。嗯,我没拼错,Nimber。这是个合成词,Nim+Number,是不是很萌!

这个游戏中,每一个5的倍数的Nimber都是0,以此类推:(5n+1)的Nimber是1,(5n+2)的Nimber是2,(5n+3)的Nimber是3,(5n+4)的Nimber是4。

于是,(16,28)的Nimber就是(1,3)。

此时,这个游戏里的(16,28)与Nim游戏里的(1,3)是等价的!

别激动,听我说。当Nim游戏的position是(1,3)的时候,我应该把其变为(1,1),对吧?那(1,1)在这个游戏中对应的是啥呢?是(5n+1,5n+1)。其中能从(16,28)一步转化的position是(16,26)。所以,我应该选择28,然后报到26。

注意,当这个游戏的Nimber是(0,0)的时候, 并不意味着已经获胜 。比如(15,25)。此时,对手随便走一步,都会使得游戏的Nimber变为(0,n)或者(n,0),此时依然按照我们的Nim策略,再把position变回(0,0)就可以了。

其实这就相当于一个可以往回放石子的Nim。就是说,有若干堆有限数量的石子,每次必须且只能从其中一堆石子里取走若干石子, 或者放入若干自己之前取走的石子 。拿走最后一个石子的人获胜。

这个游戏叫 Poker Nim ,策略与Nim完全一样。当然了,如果引入负数,那么这两个游戏实际上就是同一个游戏了。

接下来我来介绍一个非常牛逼的定理:

每一个Finite Impartial Two-player Strategy Game of Perfect Information都等价于Nim或者Poker Nim。

这就是 Sprague-Grundy Theorem ,是由R. P. Sprague和P. M. Carmelo Grundy两位数学家分别独立发现的。

这个定理,也许能够部分回答题主的问题。

当然了,为了保证答案的可读性,我的表述不是很严谨。有兴趣的可以看

Sprague-Grundy Theorem

关于计算Nimber的方法,有一个 Minimum-Excluded Rule ,简称 MEx Rule ,可以看

Nimber

MEx (mathematics)

嗯,早就想写关于Nim的文章了,一直拖啊拖,这回直接写知乎里了。希望对题主有所帮助。