一维反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 的帖子