棋子游戏

Thu, 24th October 2019Edit on Githubgamechess

medie2005提出了一个问题:

在一条直线上连续地放有n个棋子, 甲乙两人轮流每次拿走1个或者相邻的2个棋子(拿走后两边的棋子就不相邻了) 不允许把棋子拿光, 不允许不拿. 谁不能行动就输了.

问n为多少时先拿的输?

这个问题咋一看就是一个典型的Nim游戏。事实上,如果我们把"不允许把棋子拿光"这个限制去掉,问题马上转化为 一个非常简单的Nim游戏。先手只要拿走最中间的一个或两个棋子,接下去只要选择和对手上一轮选择的对称方案即可 保证胜利(拿走最后一颗棋子)。

而这个不允许把棋子拿光的游戏的最终结果也非常奇怪,当且仅当n为1,4,9,12,20之一时先手输。

详细内容

这个问题的复杂之处在于每次每人经过一次选择以后,会把一段连续的棋子分成两段,这使得游戏进行过程中,问题逐步由一段连续的棋子变为多段连续的棋子,而每一次我们都只能从其中一段中选择1个或2个相邻的棋子。

如果我们先考察允许把棋子拿光的情况,那么就是一个典型的Nim游戏。而[Mim游戏]之所以容易解决是在于我们可以对于最简单的状态(n个连续棋子)定义一个状态函数sns_n。于是对于复合状态:也就是存在k段长度分别为(n1,n2,...,nk)(n_1,n_2,...,n_k)的连续棋子的状态,其对应的状态函数值就是sn1sn2snks_{n_1}\oplus s_{n_2}\oplus\dots\oplus s_{n_k}, 其中\oplus代表按二进制比特位进行异或运算。 而一个状态只有在它对应的状态函数取值为0时才先手输,不然先手总可以做出一种选择使得留给对手的局面状态函数取值为0.

而允许取光棋子情况对应的Nim游戏状态函数取值如下

s[1]=1
s[2]=2
s[3]=3
s[4]=1
s[5]=4
s[6]=3
s[7]=2
s[8]=1
s[9]=4
s[10]=2
s[11]=6
s[12]=4
s[13]=1
s[14]=2
s[15]=7
s[16]=1
s[17]=4
s[18]=3
s[19]=2
s[20]=1
s[21]=4
s[22]=6
s[23]=7
s[24]=4
s[25]=1
s[26]=2
s[27]=8
s[28]=5
s[29]=4
s[30]=7
s[31]=2
s[32]=1
s[33]=8
s[34]=6
s[35]=7
s[36]=4
s[37]=1
s[38]=2
s[39]=3
s[40]=1
s[41]=4
s[42]=7
s[43]=2
s[44]=1
s[45]=8
s[46]=2
s[47]=7
s[48]=4
s[49]=1
s[50]=2

于是即使对于存在多条线的复合初始状态,如果允许取光棋子,我们还是可以非常容易的判断出先手能否取胜,以及如何取胜。

对于不允许取光棋子的情况,使用计算机统计各种局面下两种模型下的胜负情况,发现大部分局面竟然胜负情况是相同,胜负不同的局面只占了极小的部分。 如果我们能够把所有胜负情况不同的局面都找出来,那么就可以很好的解决本题。

为了描述对于两种模型胜负不同的局面,我们先定义一些符号描述一些局面集合。 我们分别用字母A,E,O代表任意非负整数,非负偶数和非负奇数。 于是我们就可以使用3+O13+O*1代表正好包含一个长度为3的线和奇数个长度为1的线的状态。 同样用E(1+4+9)E*(1+4+9)代表长度为1、4或9的线的总数是偶数但是不包含其它长度的线的状态(包含全空的状态) 同样用A5+O(4+1)A*5+O*(4+1)代表可以包含任意多个长度为5的线以及长度为1或4的线的总数是奇数但是不包含其它长度的线的状态。

而最终通过半人工半计算机分析得出两种模型不同的所有状态如下:

O*9+E*(4+1)
12+E*(4+1)
O*5+O*(4+1)
E*5+A*(4+1)
A*20+E*(17+12+9)+A*(4+1)
25+O*(20+4+1)+E*(17+12+9)
25+O*9+O*(4+1)

而由于对于允许取走最后一个棋子的模型,开始只有一行的情况总是先手赢的。利用上面表格容易得出,对于开始只有一行的局面,只有长度为1、4、9、12、20的局面才会先手输。

Github