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

[转载] 一维反Nim游戏

[复制链接]
发表于 2008-9-19 11:21:56 | 显示全部楼层
g函数转f函数的代码如何表示?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-19 14:45:43 | 显示全部楼层
代码同采用的数据结构有关系呀.
其实主要就是判断当前局面是不是上面列出的特殊局面.如果不是,f(x)就等于g(x),如果是上面局面之一,那么f(x)=!g(x),其中!g(x)表示g(x)逻辑取反(有就是非零变0,0变非零)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-20 13:45:05 | 显示全部楼层
另外,非常容易证明对于任意整数x,s[x]不是零,所以我们根据79#的结果,可以得出对于LZ的问题,当且仅当n是1,4,9,12,20时先手输
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-20 16:09:24 | 显示全部楼层
很精妙的结论哦
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-20 16:30:14 | 显示全部楼层
结论是挺不错的,不过还没有证明.还需要写个程序来证明.不过现在公式已经得出,如果公式没有错误,后面用来证明的程序相对来说要容易写很多了.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-23 18:37:24 | 显示全部楼层
关于这个题目,用计算机将这些模板全部拆分成简单模板。
然后又让计算机将所有可以直接到达这些模板的状态计算出来
如附件,分别给出了
Rules: (也就是所有上面的模板)

Check List: (也就是上面两类的并集)
output.zip (7.21 KB, 下载次数: 3)
只要我们能够验证所有在Check List中状态全部符合上面的规律,那么这个结论就没有错了。

初步用计算机分析结果来看应该没有问题,只是两类模板之间匹配的代码有点麻烦,我现在写的程序还不能完全处理。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-25 16:02:29 | 显示全部楼层
弄了个计算机验证的程序,它可以过滤大部分情况的正确性,然后余下一下几个模板需要手工证明其正确性:
+1*9+E*5+E*4+E*1
+1*12+E*5+E*4+E*1
+1*9+E*5+O*4+O*1
+1*12+E*5+O*4+O*1
+E*20+E*17+E*12+E*9+1*5+E*4+O*1
+E*20+E*17+E*12+O*9+O*4+O*1
+E*20+E*17+E*12+E*9+1*5+O*4+E*1
+E*20+E*17+E*12+O*9+E*4+E*1
+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
程序见附件:
scode.zip (2.97 KB, 下载次数: 3)
程序运算过程中对于某些模板可能会输出"Difficult to test the rule ****",
这个表示这些模板过于复杂,这个程序分析不了,如果对于这些模板,最后程序输出fail to check rule ****,那么表示这些模板需要继续手工确认。但是如果某个模板程序没有输出"Difficult to test the rule ***",但是输出了"fail to check rule ****",那么表示模型不成立。
而那些会显示"Difficult to test the rule ****"的是那些它的一部分会同某些规则匹配的情况,比如上面的
+1*9+E*5+E*4+E*1,其中部分1*9+E*4+E*1会同规则O*9+E*4+E*1匹配,对于这些模板,要计算机分析会比较复杂,所以很可能失败。
而对于上面计算机不能验算的部分,可以手工验算

不过现在感觉奇怪的是为什么还有几个规则计算机显示difficult to test,但是通过了。原因还没有细想:
Difficult to test the rule:+E*20+E*17+E*12+O*9+O*4+O*1
Difficult to test the rule:+E*20+E*17+E*12+O*9+E*4+E*1
Difficult to test the rule:+1*25+E*20+E*17+E*12+O*9+O*4+E*1
Difficult to test the rule:+1*25+E*20+E*17+E*12+O*9+E*4+O*1
不过如果将这几个也手工检测一下就更加安全了。
而所有手工检测过程中需要使用规则计算这个对象的胜负情况,然后产生它的所有可以直接到达的状态,也用规则计算胜负情况。
如果结果匹配,就通过。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-25 16:08:24 | 显示全部楼层
mathe不怕脱发?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-25 16:09:36 | 显示全部楼层
比如我们先手工检测
+1*9+E*5+E*4+E*1
其中E*5中5的数目是0的情况被规则O*9+E*(4+1)覆盖,由于这部分已经被计算机检测通过,我们不需要在考虑,所以只要考虑5的数目不小于2的情况。对于这种情况,没有任何模板可以匹配,所以我们直接计算g值得到为s[9]=4!=0,也就是这个应该是先手胜的局面;所以只要找出一种先手败的直接到达局面就可以了。
我们考虑将一个5拆分的局面,可以变成如:
1*9+O*5+O*4+E*1
1*9+O*5+E*4+3+E*1
....
1*9+O*5+E*4+2*2+E*1
...
其中1*9+O*5+E*4+2*2+E*1不能同任何规则匹配,而且其g值为s[9]^s[5]=0,所以是先手败的局面。
也就是+1*9+E*5+E*4+E*1在5的数目不小于的情况检验通过。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-25 16:13:18 | 显示全部楼层
同样对于局面+1*12+E*5+E*4+E*1,我们需要检测5的数目不小于2的情况。也需要证明其先手胜。
由于这个局面可以到达+1*12+O*5+E*4+2*2+E*1,这个是先手败的局面,所以证明通过。

同样对于局面+1*9+E*5+O*4+O*1,我们需要检测5的数目不小于2的情况。也需要证明其先手胜。
由于这个局面可以到达+1*12+O*5+O*4+2*2+O*1,这个是先手败的局面,所以证明通过。

同样对于局面+1*12+E*5+O*4+O*1,由于可以到达+1*12+E*5+O*4+2*2+O*1先手败局面,也通过证明
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 17:14 , Processed in 0.053516 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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