论坛 › 难题征解 › 推广的取子nim游戏必胜算法

yuange1975 发表于 2024-11-14 06:26:04

每次只能固定行或者列算1纬。
棋盘行或者列可以自己选算2纬。
立体的长、宽、高，可以任意选一个取子，可以算3纬。
或者还是用二维棋盘，每次取子可以行或者列或者斜线，就是有3个方向或者3个别的什么可选的，就是3唯的。

这个推广后就是n纬的nim取子游戏。1维已经完美解决了，并且发现了神奇的先手优势。

mathe 发表于 2024-11-14 09:01:54

二维棋盘情况，那么对于任意两个同行或同列的棋子之间可以连一条边，构成一个图，我们只需要分析图中任意一个连通分支的状态。
只是连通分支还是很复杂。
很显然，交换棋盘任意两行或任意两列都不改变棋盘性质。
从简单到复杂，最简单的就是只有一行的情况，那么一行n个棋子的nim状态就是n (可以一步到达0~n-1之间所有状态）；这个还是很简单的。
但是两行就已经很复杂了。两行的状态我们可以记为(a;b;c),其中b代表第一行和第二行中共同有棋子的列的数目；而a代表仅第一-行有棋子的列的数目；c代表仅第二行有棋子的列的数目。显然nim(a;0;c)=a^c。
然后再查看(a;1;0), 这个状态可以到达(a+1;0;0),(a-s;0;1),(a-s,1,0); 然后容易归纳证明nim(a;1,0)=a+2。也就是这种情况状态数还是等于棋子数。
然后我们可以发现(1;1;1)无法达到状态1，所以nim(1;1;1)=1.而nim(2;1;1)=5,nim(3;1;1)=6,然后可以得出nim(n;1;1)=n+3 (n>=2)
然后还可以有nim(n;1;2)=n+4; nim(n;1;3)除了nim(3;1;3)=1,nim(3;1;4)=2,nim(3;1;5)=3,nim(3;1;11)=9,nim(3;1;12)=10以外有nim(3;1,n)=n+5.
也就是除了少量状态，大部分状态有nim(a;1;c)=a+c+2 (棋子数目）。

mathe 发表于 2024-11-14 09:32:02

然后计算机计算了一下，非常可惜，nim(a;b;c)的状态规律已经很复杂。
比如b=1,a<=3时，nim(a;b;c)!=a+c+2b的只有
nim(1;1;1)=1
nim(3;1;3)=1
nim(3;1;4)=2
nim(3;1;5)=3
nim(3;1;11)=9
nim(3;1;12)=10
nim(3;1;19)=17

但是a=4时，有出现其它规律了，
首先不规律的有
nim(4;1;4)=3
nim(4;1;5)=10
nim(4;1;11)=11
nim(4;1;12)=17
nim(4;1;19)=18
然后发现
nim(4;1;27)=25
nim(4;1;35)=33
nim(4;1;43)=41
nim(4;1;51)=49
nim(4;1;59)=57
nim(4;1;67)=65
nim(4;1;75)=73
nim(4;1;83)=81
nim(4;1;91)=89
...
也就是
nim(4;1;8k+3)=8k+1 (k>=3)
而a>=5，不规律的有
nim(5;1;5)=1
nim(5;1;12)=11
nim(5;1;19)=19
然后
nim(5;1;8k+3)=8k+2 (k>=3)
而nim(6;1;c)=6+2+c没有例外
nim(7;1;c)例外的有
nim(7;1;7)=1
nim(7;1;8)=2
nim(7;1;9)=3
nim(7;1;10)=4
nim(7;1;11)=5
nim(7;1;12)=6
nim(7;1;13)=7
nim(7;1;23)=17
nim(7;1;24)=18
nim(7;1;25)=19
nim(7;1;26)=20
nim(7;1;27)=21
nim(7;1;28)=22
nim(7;1;39)=33
nim(7;1;40)=34
nim(7;1;41)=35
nim(7;1;42)=36
nim(7;1;43)=37
nim(7;1;55)=49
nim(7;1;56)=50
nim(7;1;57)=51
nim(7;1;58)=52
nim(7;1;59)=65
nim(7;1;71)=66
nim(7;1;72)=67
nim(7;1;73)=68
nim(7;1;75)=81
nim(7;1;87)=82
nim(7;1;88)=84
nim(7;1;91)=97
nim(7;1;103)=100
而nim(8;1;c)的规律就更加奇怪了，首先不规则的有
nim(8;1;8)=3
nim(8;1;9)=4
nim(8;1;10)=5
nim(8;1;11)=6
nim(8;1;12)=7
nim(8;1;13)=22
nim(8;1;23)=18
nim(8;1;24)=19
nim(8;1;25)=20
nim(8;1;26)=21
nim(8;1;27)=23
nim(8;1;28)=37
nim(8;1;39)=34
nim(8;1;40)=35
nim(8;1;41)=36
nim(8;1;42)=38
nim(8;1;43)=49
nim(8;1;55)=50
nim(8;1;56)=51
nim(8;1;57)=52
nim(8;1;58)=53
nim(8;1;59)=66
nim(8;1;71)=65
nim(8;1;72)=68
nim(8;1;73)=67
nim(8;1;74)=69
nim(8;1;75)=82
nim(8;1;87)=81
nim(8;1;88)=83
nim(8;1;89)=84
nim(8;1;90)=85
nim(8;1;91)=98
nim(8;1;103)=97
nim(8;1;104)=99
nim(8;1;105)=100
nim(8;1;106)=101
nim(8;1;107)=113
nim(8;1;119)=114
nim(8;1;120)=115
nim(8;1;121)=116
nim(8;1;122)=117
nim(8;1;123)=129
看起来好像有些规律，但是有经常破坏规律。

mathe 发表于 2024-11-14 09:36:18

而b=2开始出现先手必败的状态（状态数为0），至少再b=2时看到都是a=c的情况，而且看上去当且仅仅a==c时nim(a;2;c)=0
推广计算可以发现对于两行的情况，当且仅当nim(a;2k;a)的情况先手负，也就是两行的情况还是比较简单的，也就是当且仅当通过交换行列后变成中心对称（而且非空的行列数目都是偶数）
当然我们容易得出对于任意行的情况，如果可以通过行列交换变成中心对称（而且非空行列数目都是偶数）的状态，那么必然是先手负的状态。但是可惜还有一些先手负的状态不满足这个条件，比如3*3的格子全部填满状态
nim(0;2;0)=0
nim(0;2;3)=4
nim(1;2;1)=0
nim(2;2;2)=0
nim(2;2;3)=2
nim(2;2;4)=3
nim(2;2;8)=9
nim(2;2;9)=8
nim(2;2;10)=10
nim(2;2;17)=16
nim(3;2;3)=0
nim(3;2;4)=10
nim(3;2;10)=11
nim(4;2;4)=0
nim(5;2;5)=0
nim(6;2;6)=0
nim(6;2;7)=2
nim(6;2;8)=3
nim(6;2;9)=4
nim(6;2;10)=5
nim(6;2;11)=6
nim(6;2;12)=7
nim(6;2;19)=18
nim(6;2;20)=17
nim(6;2;21)=16
nim(6;2;22)=19
nim(6;2;23)=20
nim(6;2;24)=21
nim(6;2;25)=22
nim(6;2;34)=35
nim(6;2;35)=34
nim(6;2;36)=33
nim(6;2;37)=32
nim(7;2;7)=0
nim(7;2;8)=4
nim(7;2;9)=5
nim(7;2;10)=6
nim(7;2;11)=7
nim(7;2;12)=22
nim(7;2;22)=18
nim(7;2;23)=19
nim(7;2;24)=20
nim(7;2;25)=21
nim(7;2;26)=23
nim(7;2;38)=34
nim(7;2;39)=35
nim(7;2;40)=36
nim(7;2;54)=50
nim(7;2;55)=51
nim(7;2;70)=65
nim(7;2;86)=81
nim(7;2;102)=97
nim(8;2;8)=0
nim(8;2;9)=6
nim(8;2;10)=7
nim(8;2;11)=21
nim(8;2;12)=5
nim(8;2;22)=20
nim(8;2;23)=22
nim(8;2;24)=23
nim(8;2;25)=35
nim(8;2;26)=37
nim(8;2;38)=36
nim(8;2;39)=38
nim(8;2;40)=51
nim(8;2;54)=52
nim(8;2;55)=66
nim(8;2;70)=67
nim(8;2;87)=82
nim(9;2;9)=0
nim(9;2;10)=20
nim(9;2;11)=22
nim(9;2;12)=23
nim(9;2;22)=21
nim(9;2;23)=35
nim(9;2;24)=36
nim(9;2;25)=37
nim(9;2;26)=38
nim(9;2;38)=39
nim(9;2;39)=51
nim(9;2;40)=52
nim(10;2;10)=0
nim(10;2;11)=2
nim(10;2;12)=3
nim(10;2;22)=22
nim(10;2;23)=23
nim(10;2;24)=17
nim(10;2;25)=16
nim(10;2;26)=39
nim(10;2;38)=38
nim(10;2;39)=52
nim(10;2;40)=53
nim(10;2;54)=54

yuange1975 发表于 2024-11-16 10:13:38

这个游戏还是很有意思，一纬的情况是1990年左右高中时候接触到独立研究出来了必胜态算法，那时候没有计算机没有网络中能够靠自己独立研究。得力于看过一些课外书，有布尔代数、异或计算等数学基础，很容易就得到了异或等于0的必胜态算法。
后面我推广到多维，太复杂一直没有进展总结不出来必胜态规律算法。这些年也发过几次挑战，这次总算是有大佬愿意研究，有初步的研究发出来，可以看出来确实比较复杂。

这个用图表示可以更直观，除了1唯纬的情况，用图表示就和多少纬没有太大关系。多少纬度也就是一个点最多可以有多少条边。估计这个也可以算图论里面一到经典题目了。

https://bbs.emath.ac.cn/forum.php?mod=viewthread&tid=19760&extra=page%3D1&mobile=2

yuange1975 发表于 2024-11-16 10:22:04

这个游戏简单的一纬的，还可以有象棋残局的表现形式。

yuange1975 发表于 2024-11-16 10:48:01

改动一下炮的位置，可以增加平炮的操作，增加一些变化。这些变化里面也会后手设计的一些陷阱。

比如后手稳输了的情况，后手可以平炮，如果对手被诱惑错误的炮下去将军，反而可能会被动变成输棋。正着是稳赢态的话也跟着平炮就行了。

mathe 发表于 2024-11-16 21:50:55

使用计算机计算，发现两行情况的nim(a;1;c)还是能体现出一定的规律性，只是规律已经比较复杂了。
我们只需要分析$a\le c$的情况，前面我们分析过很多情况状态数就是a+2*b+c=a+c+2.
但是计算后发现对于某些情况经常还是需要有一个常数调整，这个调整值通常依赖于a,然后对于c出现周期性。
比如前面已经发现a=4和a=5时关于c的周期为8，进一步计算发现对于对于a=8,9,10,12关于c有周期16， 对于a=16,17,18,20,23,24关于c有周期32.
另外周期性只对较大的c有效，对于较小的部分c会不符合规律，比如对于$a<=5$,不符合规律的c都不超过19，对于$a<=14$,不符合规律的c都不超过103
对于$a<=30$不符合规律的c都不超过561等。
下面这个表格中D表示我们期望nim(a;1;c)=a+c+2+D.

D=-8;
D=-8;
D=-8;
D=-8;
D=-8;
D=-8;
D=-8;
D=-8;
D=-15;
D=-15;
D=-15;
D=-15;
D=-4;
D=-15;
D=-15;
D=-15;
D=-15;
D=-4;
D=-13;
D=-13;
D=-1;
D=-1;
D=-4;
D=-13;
D=-13;
D=-1;
D=-1;
D=-4;
D=-12;
D=-1;
D=-1;
D=-1;
D=-1;
D=-12;
D=-1;
D=-1;
D=-1;
D=-1;
D=-8;
D=-4;
D=-2;
D=-2;
D=-8;
D=-4;
D=-2;
D=-2;
D=-30;
D=-25;
D=-25;
D=-23;
D=-4;
D=-7;
D=-6;
D=-8;
D=-30;
D=-25;
D=-25;
D=-23;
D=-1;
D=-7;
D=-9;
D=-7;
D=-1;
D=-23;
D=-21;
D=-2;
D=-2;
D=-1;
D=-6;
D=-1;
D=-6;
D=-1;
D=-1;
D=-8;
D=-8;
D=-4;
D=-2;
D=-2;
D=-4;
D=-2;
D=-2;
D=-13;
D=-3;
D=-5;
D=-3;
D=-5;
D=-3;
D=-15;
D=-1;
D=-7;
D=-1;
D=-7;
D=-1;
D=-58;
然后所有不符合规律的结果在文件
可以看出a=31结果已经不符合规律了，应该是一方面，不规律的数据范围又扩大了，另外一方面周期也可能需要放大。

mathe 发表于 2024-11-17 10:19:07

两行情况nim(a : b : c)现在可以有个大概的规律了，但是计算3行以上情况还是会很困难，比如两行我们只需要a,b,c三个数表示即可，而三行将会需要7个数来描述，计算复杂度太高了
对于$a<=c$的情况，记p(a)为大于a的最小2的幂，比如p(8)=p(9)=...=p(15)=16,
那么对于充分大的c会有nim(a : b : c)=nim(a : b : c-2p(a))。
附件中给出了a<=62, b<=19, c<4000-20内所有不符合规律的数。

可以看出不规律数最大范围应该在nim(31:1:2015), 而没有继续计算63以上是因为63的不规律范围会更大，越过4000的边界

查看完整版本: 推广的取子nim游戏必胜算法