一维反Nim游戏

shshsh_0510

请问一下楼主这个问题的出处

medie2005

呵呵，我是在pongba（刘未鹏）的TopLanguage讨论组上看到的，TopLanguage上的发贴人是在张志强的阅微堂看到这个题的，所以，原始出处我就不知道了。

mathe

原帖由 mathe 于 2008-9-14 14:53 发表 这个代码只是一个临时用于过滤一些数据的小程序,我从一个比较复杂的代码上修改过来,大部分代码没有用处(除了main函数),每找到一个规律,我就添加一个条件语句,所以比较乱: 现在已经分析出$n

对于上面46#结果,突然想到对于所有非零的状态数,其实其具体值是没有什么意义的,所以只要两个方案中结果都是0或都是非0,我们应该都可以认为是匹配的,也就是说,这样可以大大简化结果.等有空我再看看这样是不是可以完全手工将结果解出来(编程解还是挺复杂的,最好能够手工方法解出)

无心人

非常期待 另外，我倾向于存在无数的先手负连续序列局面

mathe

类似49#过程，我们需要依次找出所有 f(x)=0但是g(x)!=0的状态x以及f(x)!=0但是g(x)=0的状态x 首先我们知道f(O*1)=0,f(E*1)=1但是g(E*1)=0,g(O*1)=1.所以状态O*1和E*1对应的f,g函数不匹配。 所以所有可以到达O*1和E*1的状态都需要重新计算，也就是我们需要重新计算 2+O*1,2+E*1,3+O*1,3+E*1,4+O*1,4+E*1 首先计算f(2)=1,g(2)=2所以两者都不是0，我们认为匹配，同样f(2+1)=2,g(2+1)=3也匹配， 同样f(2+O*1)=2,g(2+O*1)=s(2)^s(1)=3也匹配，f(2+E*1)=3,g(2+E*1)=s(2)=2也匹配（都不是0） 所以我们直接删除状态2+O*1和2+E*1. 同样状态3,3+O*1,3+E*1也不需要继续考虑。 所以只余下状态4+O*1,4+E*1需要考虑 （前面唯一不匹配的规律只有f(O*1)=0,f(E*1)!=0) 我们可以得到f(4+E*1)=0!=g(4+E*1)=s(4)=1,f(4+O*1)=1!=g(4+O*1)=s(4)^s(1)=1 也就是我们需要添加规律f(4+E*1)=0,f(4+O*1)!=0,然后需要继续查看所有可以到达4+E*1,4+O*1的状态。 这些状态有4+2+O*1,4+2+E*1,4+3+O*1,4+3+E*1,2*4+O*1,2*4+E*1,5+E*1,5+O*1,6+E*1,6+O*1,7+E*1,7+O*1 同样可以淘汰4+2+O*1,4+2+E*1,4+3+O*1,4+3+E*1. 然后我们得出f(2*4+O*1)=0!=g(2*4+O*1)=s(1)=1,f(2*4+E*1)=1!=g(2*4+E*1)=0 所以状态2*4+O*1和2*4+E*1也属于不匹配状态，为此我们需要添加所有可以到达2*4+E*1和2*4+O*1的状态，得出 2*4+2+E*1,2*4+2+E*1,2*4+3+O*1,2*4+3+E*1,3*4+O*1,3*4+E*1,5+4+E*1,5+4+O*1,6+4+E*1,6+4+O*1,7+4+E*1,7+4+O*1 同样可以直接淘汰2*4+2+E*1,2*4+2+E*1,2*4+3+O*1,2*4+3+E*1 并且得出3*4+O*1,3*4+E*1不匹配。 进一步我们可以得出所有O*(4+1)和E*(4+1)不匹配，需要添加规则f(O*(4+1))=0,f(E*(4+1))=1 而且我们需要添加需要检查的状态 5+E*(4+1),5+O*(4+1),6+E*(4+1),6+O*(4+1),7+E*(4+1),7+O*(4+1) 前面所有不匹配结果可以写成f(O*(4+1))=0,f(E*(4+1))=1 继续分析下去还是比较复杂的，我们可以让计算产生充分大范围内一些数据，然后查看数据中规律。 可以猜测所有不匹配的数据有 f(O*(9+4+1))=0,f(E*(9+4+1))!=0 f(A*5+O*(4+1))=0,f(E*5+E*(4+1))!=0 f(12+E*(4+1))=0,f(E*(12+9)+O*(4+1))=0,f(E*(12+9)+E*(4+1))!=0 f(E*(20+4+1))!=0,f(O*(20+4+1))=0 f(E*(12+9)+O*(20+4+1))=0,f(E*(12+9)+E*(20+4+1))!=0 f(17+O*(12+9)+O*(20+4+1))=0,f(17+O*(12+9)+O*(20+4+1)!=0 f(2*17+O*(20+4+1))=0,f(2*17+E*(20+4+1))!=0 f(2*17+2*9+E*(20+4+1))!=0,f(2*17+2*9+O*(20+4+1))=0 （上面所有最大数小于等于12的状态基本上可以确定没有错，但是最大数为17和20的，可能需要更多的数据来验证） 而对于所有不在上面的状态，我们可以简单的通过g函数（这个函数通过s数组值的异或来计算）来确定是先手胜还是先手负。

mathe

原帖由 无心人 于 2008-9-17 21:47 发表 非常期待 另外，我倾向于存在无数的先手负连续序列局面

什么叫“先手负连续序列局面”，主要这个连续如何解释？

无心人

就是局面 (9)的写法的局面

mathe

现在我找到这个题目一种比较好的表达方式了，采用46#中的表格s[.] 其中前50项为: 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 其意义就是如果允许拿最后一个棋子，那么对于一个有k行，各行分别有$x_1,x_2,...,x_k$个连续棋子的局面，先手负的充分必要条件为 $g(x)=g(x_1,x_2,...,x_k)=s[x_1]^^s[x_2]^^...^^s[x_k]$ (这里方程右边所有变量之间做异或运算) 数列s的计算相对比较简单，但是其规律我没有找到。 然后对于本问题任何一个局面，我们采用上面提到的记号，比如O*(4+1)+E*9表示这个局面4和1的数目之和为奇数，9的数目为偶数 而A用来表示任意数目（可以是0），那么所有特殊局面都在下面中： 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) 也就是对于任何一个局面，我们首先可以计算出其$g(x)$,然后如果这个局面不在上面列表中，那么g(x)非零表示先手胜的局面，g(x)是零表示是先手负的局面。但是如果在上面列表中，那么相反，g(x)是0表示先手胜的局面，g(x)非零表示先手负的局面。 通过这个方法，我们可以判断非常复杂的局面。 当然现在上面的这个规律我还没有证明，但是我第一次让计算机验证了所有最大数在不超过100，和不超过150的所有局面都满足要求。同样第二次验证了所有最大数不超过60，和不超过300的所有局面也满足要求，说明这个规律可信度已经非常之高了。

mathe

通过上面的方法，对于任意一个给定的局面，我们就非常容易判断是否先手负的局面。而如果是先手胜的局面，也将非常容易找出致胜的方案。

mathe

而计算数列s的代码可以采用算法

2. int st[MAX];
3. s[0]=0;s[1]=1,s[2]=2;
4. for(i=3;i<MAX;i++){
5. for(j=0;j<MAX;j++)st[j]=0;
6. st[s[i-1]]=1,st[s[i-2]]=1;
7. for(j=1;j<=(i-1)/2;j++){
8. int k=i-1-j;
9. st[s[j]^s[k]]=1;
10. k=i-2-j;
11. st[s[j]^s[k]]=1;
12. }
13. for(j=0;j<MAX;j++)if(st[j]==0)break;
14. s[i]=j;
15. }

复制代码

还有根据上面的特殊局面的分布，可以看出shshsh的那个关于所有局面都只需要看各个数字奇偶性的方案只有对 12+E*(4+1) 25+O*(20+4+1)+E*(17+12+9) 25+O*9+O*(4+1) 中的数字12和25例外