一维反Nim游戏

shshsh_0510 · 发表于 2008-9-12 09:16:22

虽然还没证明，但感觉这个问题应该可以只分析类型
既不用分析2*4之类，而直接分析 o4 ,p4 就可以了
也就是说 F(2^n)的向量是所有分划的特征向量，在同特征的等价类中有相同奇异性质

medie2005 · 发表于 2008-9-12 09:17:39

mathe到底是干什么的啊，每天都有时间来给别人解答，天天都这么闲？

mathe · 发表于 2008-9-12 09:21:18

你管的比我老板还宽嘛

工作去了

shshsh_0510 · 发表于 2008-9-12 10:44:11

又想了一下，看来只要O(n^2)就应该可以了

无心人 · 发表于 2008-9-12 11:38:02

mathe
我说了，41＃的可以利用来计算
用字典储存得到结论的状态
没得到结论的，去按规则计算，且储存到字典
应该很快能得出每个状态的值

而你们的方法会遇到很多特例

mathe · 发表于 2008-9-12 14:02:16

41#这种方法当然可行了,只是计算复杂度太高,当然更加不能处理通用的情况.
我一直希望能够找到一种比较通用的方法,不过现在看来这个题目的情况还是太复杂
现在我可以知道先手1,4,9,12,20这几个情况必负看不出什么规律

mathe · 发表于 2008-9-12 14:14:44

计算到50,发现单项的状态值在n>33以后(17个数据)都同取最后一个数赢情况的状态值相同.
也就是如果我前面的猜想成立的话,有可能需要计算到最大数为33的那些状态,其中中间状态自然会非常之多的,不知道通过计算机是否能够处理都是一个问题.而如果能够确认最大数不小于33时两个问题可以使用相同策略,那么我们就可以得出只有n=1,4,9,12,20这几种是先手负的.

无心人 · 发表于 2008-9-12 19:11:01

现在分析到多少了？

mathe · 发表于 2008-9-13 18:12:37

现在分析到最大数不超过9的所有规则了。到这里规则数还不算太多，不过要分析到33还是很难的，必须有计算机辅助才行。
其中很多规则挺有意思，比如得出如果一个局面只有1,4,9那么它们堆数之和是奇数时先手输，偶数先手赢。

无心人 · 发表于 2008-9-13 20:53:14

能写出来么？

账号		自动登录	找回密码
密码			欢迎注册

[转载] 一维反Nim游戏

回复 53# medie2005 的帖子