数学研发论坛

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

[转载] 棋子游戏

[复制链接]
发表于 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, 2019-6-20 01:04 , Processed in 0.055864 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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