一维反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的分析有点复杂了 能有一个简单的规则判定体系 只需要比你的那个体系更多的计算量？