正确答案是这样的:
对于NIM游戏(即:拿到最后一个石头的人赢)的话,必胜策略如2楼所说,每堆数量求NIM和以后为0的局面是后手必胜局(NIM和这个东西按照计算机的说法就是按位异或,比如说(1,2,3)是必胜局),也就是说对于所有不满足这个条件的局面,先手一定能给转化成满足这个条件的局面,从而必胜。
对于misere的NIM游戏,也就是拿到最后一个石头的人输的情况,其实和普通NIM游戏差不多。唯一的区别在于,如果所有堆都只剩下1颗石子,那么有奇数堆的时候后手必胜(这和普通NIM不同)。其他情况下仍然按照NIM和来判断是否为后手必胜局。因此,misere NIM的策略是这样的:
按照普通NIM的必胜策略来进行。但是如果某一步会造成“所有堆都只剩下1颗石子”的局面的话,调整策略使得剩下的堆数为奇数
打个比方,从(1,2,4)开始。这是一个先手必胜局
普通NIM:(1,2,4)->(1,2,3)
如果(1,2,3)->(2,3),则(2,3)->(2,2);如果(1,2,3)->(1,1,3),则(1,1,3)->(1,1)
misere NIM:
(1,2,4)->(1,2,3)
如果(1,2,3)->(2,3),则(2,3)->(2,2);如果(1,2,3)->(1,1,3),则(1,1,3)->(1, 1, 1)
其他的情况可以自行推导