选择最佳矩阵

Question

我给出的X尺寸的矩阵Ni*Mi,其中1<=N<=4 and 1<=M<=4, for all 1 <= i <= X

游戏包括从给定X矩阵之一中选择任何矩形(子矩阵)并移除该子矩阵.

例如:我们有1个大小的矩阵4x4.玩家1可以选择大小的子矩阵4x4(在这种情况下是整个矩阵)并将其删除.或者他们可以选择子矩阵2x2或1x1或2x3或任何有效的子矩阵,并将其从4x4矩阵中删除,我们在游戏中留下剩余的矩阵.

无法移动的玩家输了.

哪位球员获胜？

两个播放器都以最佳方式播放.

Answer 1

这个问题通过Sprague Grundy定理来解决,该定理说当你对各个矩阵的nimbers进行xorbers时,那么当结果为0时,移动的玩家只会失败(因为任何移动都会将失败的位置变为获胜位置并且然后其他玩家可以将胜利位置再次变为失败位置,依此类推,这就是类似于游戏的游戏的本质.

递归地计算nimbers,矩阵的nimber是所有可达状态的nimber的mex(最小异或=集合中不存在的最小非负整数).

所有0都为0,您没有有效的移动,因此它是一个损失(0).

恰好一个1是1,因为唯一可到达的位置是0而mex(0)= 1.

对于两个,我们必须决定它们是否相邻,相邻= mex(0,1)= 2,不相邻= mex(1)= 0 ......等等.

例:

1 0 0 0     1 1 0     1 1
0 0 1 1     0 0 0     1 1
0 0 1 0     0 0 1
0 0 0 0
   =          =        =
   2    xor   3   xor  1   =   0   => player to move loses.

快速实现可能如下所示:

1. 预先计算16个(10个具有对称性)不同情况的nimbers并将它们存储在一个数组中.

2. 分配结果= 0

3. result = result xor nimbers [readRowCount()] [readColCount()]

4. 重复3.直到读取所有矩阵尺寸

5. 如果结果!= 0则第一个玩家赢得第二个玩家

例2:nimber计算

matrix:
1 1
1 1

valid moves:
0 1*  1 0*  1 1*  1 1*  0 0   1 1+  0 0+  1 0+  0 1+
1 1   1 1   0 1   1 0   0 0   0 0   1 1   1 0   0 1
                         =
                         0 by definition

The other matrices can be grouped into 2 groups * and + because of symmetries.

Reachable positions from *:
0 1   0 1   0 0
0 1   1 0   0 1
 =     =     =
             1 = mex(0), because the only reachable position has a nimber of 0
       0 = mex(1), because the only reachable position has a nimber of 1
 2 = mex(0,1), because the reachable positions have nimbers of 0 and 1

==> the nimber for * is mex(0, 1, 2) = 3.

==> we already know now that the nimber of + is 2.

==> the nimber of the given matrix is mex(0, 2, 3) = 1.