一维反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的代码可以采用算法

1. 
   
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例外