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

yuange1975

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

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

mathe

二维棋盘情况，那么对于任意两个同行或同列的棋子之间可以连一条边，构成一个图，我们只需要分析图中任意一个连通分支的状态。
只是连通分支还是很复杂。
很显然，交换棋盘任意两行或任意两列都不改变棋盘性质。
从简单到复杂，最简单的就是只有一行的情况，那么一行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

然后计算机计算了一下，非常可惜，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

而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

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

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

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

yuange1975

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

yuange1975

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

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

mathe

使用计算机计算，发现两行情况的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[a][c%32]表示我们期望nim(a;1;c)=a+c+2+D[a][c%32].

1. D[4][3]=-8;
   
2. D[4][11]=-8;
   
3. D[4][19]=-8;
   
4. D[4][27]=-8;
   
5. D[5][3]=-8;
   
6. D[5][11]=-8;
   
7. D[5][19]=-8;
   
8. D[5][27]=-8;
   
9. D[8][7]=-15;
   
10. D[8][8]=-15;
    
11. D[8][9]=-15;
    
12. D[8][10]=-15;
    
13. D[8][11]=-4;
    
14. D[8][23]=-15;
    
15. D[8][24]=-15;
    
16. D[8][25]=-15;
    
17. D[8][26]=-15;
    
18. D[8][27]=-4;
    
19. D[9][7]=-13;
    
20. D[9][8]=-13;
    
21. D[9][9]=-1;
    
22. D[9][10]=-1;
    
23. D[9][11]=-4;
    
24. D[9][23]=-13;
    
25. D[9][24]=-13;
    
26. D[9][25]=-1;
    
27. D[9][26]=-1;
    
28. D[9][27]=-4;
    
29. D[10][7]=-12;
    
30. D[10][8]=-1;
    
31. D[10][9]=-1;
    
32. D[10][10]=-1;
    
33. D[10][11]=-1;
    
34. D[10][23]=-12;
    
35. D[10][24]=-1;
    
36. D[10][25]=-1;
    
37. D[10][26]=-1;
    
38. D[10][27]=-1;
    
39. D[12][3]=-8;
    
40. D[12][7]=-4;
    
41. D[12][9]=-2;
    
42. D[12][11]=-2;
    
43. D[12][19]=-8;
    
44. D[12][23]=-4;
    
45. D[12][25]=-2;
    
46. D[12][27]=-2;
    
47. D[16][15]=-30;
    
48. D[16][16]=-25;
    
49. D[16][17]=-25;
    
50. D[16][18]=-23;
    
51. D[16][19]=-4;
    
52. D[16][23]=-7;
    
53. D[16][24]=-6;
    
54. D[16][27]=-8;
    
55. D[17][15]=-30;
    
56. D[17][16]=-25;
    
57. D[17][17]=-25;
    
58. D[17][18]=-23;
    
59. D[17][19]=-1;
    
60. D[17][23]=-7;
    
61. D[17][24]=-9;
    
62. D[17][26]=-7;
    
63. D[17][27]=-1;
    
64. D[18][15]=-23;
    
65. D[18][16]=-21;
    
66. D[18][17]=-2;
    
67. D[18][18]=-2;
    
68. D[18][19]=-1;
    
69. D[18][23]=-6;
    
70. D[18][24]=-1;
    
71. D[18][25]=-6;
    
72. D[18][26]=-1;
    
73. D[18][27]=-1;
    
74. D[20][3]=-8;
    
75. D[20][11]=-8;
    
76. D[20][15]=-4;
    
77. D[20][17]=-2;
    
78. D[20][19]=-2;
    
79. D[20][23]=-4;
    
80. D[20][25]=-2;
    
81. D[20][27]=-2;
    
82. D[23][8]=-13;
    
83. D[23][11]=-3;
    
84. D[23][16]=-5;
    
85. D[23][19]=-3;
    
86. D[23][24]=-5;
    
87. D[23][27]=-3;
    
88. D[24][7]=-15;
    
89. D[24][8]=-1;
    
90. D[24][15]=-7;
    
91. D[24][16]=-1;
    
92. D[24][23]=-7;
    
93. D[24][24]=-1;
    
94. D[31][31]=-58;

复制代码

然后所有不符合规律的结果在文件 nim.tgz (9.63 KB, 下载次数: 0)

5 天前 上传

点击文件名下载附件

可以看出a=31结果已经不符合规律了，应该是一方面，不规律的数据范围又扩大了，另外一方面周期也可能需要放大。

mathe

两行情况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内所有不符合规律的数。
nim3.tgz (440.7 KB, 下载次数: 0)

4 天前 上传

点击文件名下载附件

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