尼姆游戏问题

Question

好吧,我必须制作一个nim游戏并尝试找到总是通过以下nim游戏获胜的策略:

21场比赛,每场比赛1和2每场比赛需要1,2,3,4或5场比赛,并且一场比赛不能获得前一场比赛所需的相同数量的比赛.如果/当他们参加最后一场比赛时,电子竞技者将获胜.

我必须为此编程,但我甚至不明白是要开始.如何通过这种类型的nim游戏找到获胜策略？

编辑:

所以我认为当你仍然处于中间的7场比赛时你将永远获胜.另一个可以拿2-5,最多可以加7个.当另一个取1时,你拿3(另一个不能取3)然后必须选择1或2,在这种情况下你将获得一个并获胜.

然而,从21到7对我来说是一个难题,我无法弄清楚你如何能够永远成为7人.

编辑2:确定没有规则,你不能采取与以前的播放器相同,我认为这很简单.

你得到k = 5 + 1 = 6.然后你应该进行第一次移动,使得匹配剩下那么%6 = 0.所以在这种情况下先取3然后再填充其他玩家的移动到6但是在这种情况下不会起作用,因为其他玩家可以拿3,之后你不能拿3来填补6.所以有我的问题.有任何想法吗？

EDIT3:

好的,所以你说我可以强迫7场比赛.但是假设我对14-7比赛步骤采取相同的想法.(然后是另一个)

那么有两个场景:1:他拿到2-5然后我把它填满七个让7在那里我赢了.2:他拿1分,所以剩下13分.当我在(7-0)步骤中取3时,它变为10.然后他取5,我不能再拿5来完成,我会松开.

这就是问题所在,方案2在(7-0)步骤中没有问题.我该如何解决这个问题？

是的,解决方案:

顺便说一下,na speler 1意味着:在玩家1轮之后等(我是荷兰人).

好的,所以我尝试了一些东西,我想我有解决方案.你必须先将1场比赛作为第一名球员.然后其他人可以参加2-5场比赛.你匹配(双关语)他的金额最多为7,所以你总共会有(21-1-7 =)13场比赛.然后又是玩家2的回合,并且有两种情况:玩家2需要1,2,4或者5场比赛,在这种情况下,您将获得尽可能多的匹配,左侧将有7个.(正如之前所说的那样,当你进行比赛时,剩下7分,你总会获胜).第二种情况是,玩家2需要3场比赛,在这种情况下,当轮到你时,中间有10场比赛.你不能拿3来制作7,因为你不能拿2倍相同的金额.所以你拿5分,剩下5分.玩家2然后可以'

这是我猜的解决方案.我不知何故来到它,因为我注意到了这一点:

正常Nim游戏与modulo等:

P2  1  2  3  4  5  
P1  5  4  3  2  1  
------------------
    6  6  6  6  6 

但是你不能在这里做3,3所以这是骗子:

p2 1  2  3  4  5 
p1    5  4  3  2  1
---------------------
      7  7  7  7 

所以你每次都可以做7次,1次是特例.我不知道为什么,但我直觉地把1作为起点,因为你觉得你需要主动控制对方的动作.(一个不能做两次1,所以另一个必须采取2-5,这使你控制)

无论如何,感谢所有的帮助.也为整个程序编写.我无法使用它,因为它不会编译为缺乏良好的Java技能:)我也想自己解决它.

无论如何,我看到这是一个维基,祝未来人们试图解决这个问题!

Answer 1

在这样的游戏中,你需要保持在获胜位置的不变性(如果你已经在一个位置).所以你需要知道如何从一个胜利的位置开始,然后无论你的对手做了什么动作再回到它.

以下是三个提示:

1. 你的移动组和对手的移动组是相同的:参加1,2,3,4或5场比赛.
2. 这个游戏,当你开始它,是一个添加游戏.是的,您正在减去匹配,但在制定策略时,仍然需要考虑添加.
3. 从这开始:对于任何对手移动X(其中X是1,2,3,4或5),你可以采取什么措施来"取消"移出？

我想要的概念在模块化算法的概念中得到解释,如果有帮助的话.

编辑:虽然没有采取相同数量的比赛的限制使事情变得有趣.我们将不得不在以后作为一个角落案例解决这个问题,但让我们首先看看你是如何看到我到目前为止所说的.请随时评论.

编辑2:你对第二次编辑是正确的(如果不存在重复移动的规则,我的意思是).但是你的第一次编辑是在正确的轨道上:你可以让事情在7年代起作用.

只是不断质疑和回答自己:

问:如何通过让AI进行最后一场比赛来可靠地强制获胜？
答:强制AI留下7场比赛,然后用你的策略迫使AI拿下第7个.这是因为您可以强制减去7个匹配项.
问:那么如何通过确保AI进行最后一场比赛(但是七场)来强制赢得AI？

不要过度思考它.拿你已经知道的东西 - 你已经可以做AI的事情 - 并尽可能多地应用这个步骤.

编辑3:这只是我想到的一个小问题,可能有助于您处理在第三次编辑中提到的问题.

如果,对于移动组中的所有X(1,2,3,4,5),当AI轮到时,仍然会有2X个匹配,那么你可以通过X匹配来强制获胜.(您在第三次编辑中详细说明了除了其他玩家之外的情况)

不幸的是,这不是你可以强迫的,因为我说的是在AI轮到之前有2X的比赛,而其他战略获胜条件取决于AI轮到之后的位置,因此AI的移动可以迫使它.

同样,你要避免让AI的移动结果为任何一个X的2X匹配.