推广的取子nim游戏必胜算法

yuange1975

我来出一道我推广的nim游戏，看谁能解出来。

围棋棋盘上随机分布的一些棋子，可以拿具体围棋比赛或者残局图来做数据。两人轮流从棋盘里取子，只能从某一行或者列取子，每次最少取一子。取到棋盘上最后一子的算赢或者输，求必胜算法。




补充内容 (2024-11-14 05:49):
推广的取子nim游戏必胜算法

我来出一道我推广的nim游戏，看谁能解出来。

围棋棋盘上随机分布的一些棋子，可以拿具体围棋比赛或者残局图来做数...

lihpb00

同一行或者列里面是不是每次只能取连续相邻的棋子，是否允许隔空取子，如果允许隔空取子，问题就直接简化多了

yuange1975

只说了同一行或者列，肯定是可以隔开取呀。

dxn13533

这应该没有必胜算法 这是双方博弈的过程

dxn13533

或者说如果双方都没有失误 那最开始的棋子分布可能就已经注定了结局

yuange1975

这个就是要的必胜算法呀，大多数时候是先手必胜，很少数时候是后手必胜。

mathe

好像n*n的棋盘布满棋子后手赢（取光的人赢）

yuange1975

对于n*n堆满，取完算赢。

哈哈，你考虑少了1*1，先手直接取完赢。
别的对称性，好像确实后手稳赢。

对于n*n堆满，取完算输，是先手稳输吗？

yuange1975

推广的取子nim游戏必胜算法

我来出一道我推广的nim游戏，看谁能解出来。

围棋棋盘上随机分布的一些棋子，可以拿具体围棋比赛或者残局图来做数据。两人轮流从棋盘里取子，只能从某一行或者列取子，每次最少取一子。取到棋盘上最后一子的算赢或者输，求必胜算法。

这个要是解出来了必胜算法，还是非常牛逼的，可以用来类似残局摆局了。

也可以用象棋残局来作为数据，别人摆街头象棋残局你就用他的残局然后用这个游戏去挑战他。


原来这个NIM游戏是一纬的，就是每次取子固定了只能从行或者列中某一个取。
这个原来的NIM游戏必胜算法就比较简单，这里也不多说了，很多人都会。但是就是这个很多人都会的NIM游戏，其实很多人还是没有玩透。

一般是固定好了取到最后一子算赢或者输，这种NIM游戏先取的一般绝大多数情况都是先行者有巨大的先行优势。
但是这个游戏先行优势有多大呢？这个NIM游戏里，大多数时候先行者可以让后面一个人在多少步内再确认取最后一子算赢还是输。一般来说怎么算输赢肯定是决定胜负的关键，可是这个NIM游戏先行着可以在还没有确认输赢条件下（相反结果的两个选一个）最后多少步内都稳操胜券。

yuange1975

对于1纬的比较简单。

如果取完算赢，所有an异或=0的状态为必胜态。用异或的性质很好证明。所以大多数情况先手稳赢，如果已经是必胜态，那么先手稳输了。

如果取完算输，必胜态并不是上面取完算赢的取反。绝大多数的时候上面的必胜态也是取完算输的必胜态。
这时候，只有剩下的所有都是1的时候，就是n个1的时候，必胜态才是取反了，其它时候还是所有数异或=0的时候是必胜态。
取胜秘诀仍然是按照异或=0操作，只需要发现如果取完后都是1的时候，就改为剩下单数个1就行了。


⚠️这样就出现了绝大多数人没有注意的神奇的先手优势。
先手取完后，只要不是直到了所有数都是1的情况，所有an异或=0的状态的必胜态，后手再来决定取完算赢或者输，先手都能稳赢。