一维反Nim游戏

mathe

下一个为:
+E*20+E*17+E*12+E*9+1*5+E*4+O*1,其复杂之处在于20,17,12,9都是0时1*5+E*4+O*1同规则匹配。
所以我们需要查看(20+17+12+9)的数目不小于2的情况。这种情况没有规则匹配，对应g值为s[5]^s[1]!=0,所以也是先手胜局面。我们选择将那个20,17,12或9中一个拆分。由于我们知道规则中含5的只能是5最大的，所以变换结果肯定不符合规则，我们只要找出一个变换后g值为0的就可以了。
20的拆分可以变成O*20+E*17+E*12+E*9+1*5+E*4+O*1+11+7,对应g值为s[20]^s[5]^s[1]^s[11]^s[7]=1^4^1^6^2=0,所以通过
17的拆分可以变为E*20+O*17+E*12+E*9+1*5+E*4+O*1+16,对应g值为0通过
12的拆分可以变为E*20+E*17+O*12+E*9+1*5+E*4+O*1+7+3,对应g值为0通过
9的拆分可以变为E*20+E*17+E*12+O*9+1*5+E*4+O*1+8,对应g值为0通过
所以这个模板情况也完全通过

mathe

下一个+E*20+E*17+E*12+O*9+O*4+O*1
挺复杂，需要分别查看20,17,12数目大于0的情况，分别得出用下面变换证明
20=>13+5
O*20+E*17+E*12+O*9+O*4+O*1+13+5
17=>2*8
E*20+O*17+E*12+O*9+O*4+O*1+2*8
12=>2*5
E*20+E*17+O*12+O*9+O*4+O*1+2*5

mathe

再下面一个+E*20+E*17+E*12+E*9+1*5+O*4+E*1同92#的+E*20+E*17+E*12+E*9+1*5+E*4+O*1几乎相同，类似构造就可以了
同样+E*20+E*17+E*12+O*9+E*4+E*1同93#的类似

mathe

同样最后两个
+1*25+E*20+E*17+E*12+O*9+O*4+E*1
+1*25+E*20+E*17+E*12+O*9+E*4+O*1
都是20,17,12数目都是0的情况同规则匹配，所以我们需要验证它们至少一个数目不为0的情况
同样
+1*25+E*20+E*17+E*12+O*9+O*4+E*1
+1*25+E*20+E*17+E*12+O*9+E*4+O*1
20=>13+5
17=>2*8
12=>2*5
都可以达到目的。所以证明都通过了。也就是所有的规则都得到证明了

shshsh_0510

mathe的计算机检验我已经看不明白了，如果真是只有那几个奇异局势，真是很神奇！

我上面那个只需考虑奇偶的猜测我想基本是对的，其原因来源于以下事实：
1、S(N)表示最大不超过N-1的子序列，则局势N+S(N)只依赖于所有S(N)中的奇异局势
2、k*N+S(N)只依赖于所有(k-1)*N+S(N)中的奇异局势
3、k*N+S(N) 和(k-1)*N+S(N)中的奇异局势的奇偶表示必不相同
对于k*N+S(N)中，用奇偶表示的局势总共为3^n-1种，其中在k ODD时为奇异的有X个，在k EVEN时为奇异的有Y个，在两种情况全非异的有Z=3^n-1-X-Y个，由于转换规则有n个，以3^n-1种情况为顶点，以转换关系为边做无向图，则X、Y中的点无边相通，Z中的点与X,Y均相同
我估计Z中的点的数量为一半左右，所以如要穷举所有S(N) 的奇异局势还得是O(3^N)的

medie2005

楼上两位不怕脱发？？
程序员还是要早考虑个人问题，不然以后头发掉光，就困难了。

mathe

的确基本上没有问题，但是对于少数情况不成立。
比如局面12是先手负，但是3*12是先手胜，变成2*12+2*5就可以赢了。（根据前面的规则）

mathe

原帖由 medie2005 于 2008-9-25 16:52 发表
楼上两位不怕脱发？？
程序员还是要早考虑个人问题，不然以后头发掉光，就困难了。

^_^，我们两都不需要考虑这个问题了。就你需要加油了

shshsh_0510

我们再考虑过多就要犯错误了

无心人

mathe的分析有点复杂了
能有一个简单的规则判定体系
只需要比你的那个体系更多的计算量？