找回密码
 欢迎注册
楼主: medie2005

[转载] 一维反Nim游戏

[复制链接]
发表于 2008-9-17 10:04:25 | 显示全部楼层
请问一下楼主这个问题的出处
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-17 10:07:19 | 显示全部楼层
呵呵,我是在pongba(刘未鹏)的TopLanguage讨论组上看到的,TopLanguage上的发贴人是在张志强的阅微堂看到这个题的,所以,原始出处我就不知道了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-17 16:30:24 | 显示全部楼层
原帖由 mathe 于 2008-9-14 14:53 发表 这个代码只是一个临时用于过滤一些数据的小程序,我从一个比较复杂的代码上修改过来,大部分代码没有用处(除了main函数),每找到一个规律,我就添加一个条件语句,所以比较乱: 现在已经分析出$n
对于上面46#结果,突然想到对于所有非零的状态数,其实其具体值是没有什么意义的,所以只要两个方案中结果都是0或都是非0,我们应该都可以认为是匹配的,也就是说,这样可以大大简化结果.等有空我再看看这样是不是可以完全手工将结果解出来(编程解还是挺复杂的,最好能够手工方法解出)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-17 21:47:31 | 显示全部楼层
非常期待 另外,我倾向于存在无数的先手负连续序列局面
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-17 22:22:21 | 显示全部楼层
类似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数组值的异或来计算)来确定是先手胜还是先手负。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-17 22:23:19 | 显示全部楼层
原帖由 无心人 于 2008-9-17 21:47 发表 非常期待 另外,我倾向于存在无数的先手负连续序列局面
什么叫“先手负连续序列局面”,主要这个连续如何解释?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-18 15:18:41 | 显示全部楼层
就是局面 (9)的写法的局面
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-18 22:30:00 | 显示全部楼层
现在我找到这个题目一种比较好的表达方式了,采用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的所有局面也满足要求,说明这个规律可信度已经非常之高了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-18 22:31:23 | 显示全部楼层
通过上面的方法,对于任意一个给定的局面,我们就非常容易判断是否先手负的局面。而如果是先手胜的局面,也将非常容易找出致胜的方案。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-18 22:44:17 | 显示全部楼层
而计算数列s的代码可以采用算法
  1. int st[MAX];
  2. s[0]=0;s[1]=1,s[2]=2;
  3. for(i=3;i<MAX;i++){
  4. for(j=0;j<MAX;j++)st[j]=0;
  5. st[s[i-1]]=1,st[s[i-2]]=1;
  6. for(j=1;j<=(i-1)/2;j++){
  7. int k=i-1-j;
  8. st[s[j]^s[k]]=1;
  9. k=i-2-j;
  10. st[s[j]^s[k]]=1;
  11. }
  12. for(j=0;j<MAX;j++)if(st[j]==0)break;
  13. s[i]=j;
  14. }
复制代码
还有根据上面的特殊局面的分布,可以看出shshsh的那个关于所有局面都只需要看各个数字奇偶性的方案只有对 12+E*(4+1) 25+O*(20+4+1)+E*(17+12+9) 25+O*9+O*(4+1) 中的数字12和25例外
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-12-4 01:25 , Processed in 0.025552 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表