选择最佳矩阵

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

（在maraca发布他关于Sprague Grundy定理的答案之前，我正在尝试确定游戏的最佳策略；我将在下面描述它，也许它也可以用来编写一个解决方案。）

游戏的结果是每个矩形是奇数次还是偶数次移动的结果。如果总步数为奇数，则玩家 1 获胜；如果是偶数，则玩家 2 获胜。

让我们看看可能的矩形：

对于所有 "normal" 个矩形（2x2 和 1x1 除外），首先移除部分矩形的玩家可以决定是否在奇数次移动中将其完全移除（例如，一次将其完全移除）或偶数步；以黄色表示的单元格显示让玩家控制的第一步。

对于只有 1 个单元格宽的 "thin" 矩形，odd/even 会立即做出决定（通过删除整个矩形或留下 1 个单元格）。对于其他 "normal" 个矩形，决定从 1 步延迟到 3 步，具体取决于其他玩家的动作。

1x1 矩形只能在一次移动中移除（即奇数次移动）。 2x2 的矩形可以一次移除，但是玩家不能通过只移除它的一部分来强制进行偶数次移动；另一位玩家总是可以决定奇数或偶数。

正如您从图中黄色指示的动作中看到的那样，创造对称情况的动作（例如将 4x4 正方形分成两个 4x1 矩形）让创造这种情况的人控制结果这个矩形。他可以，例如像这样为这个矩形强制移动偶数次：

整个游戏也是如此：如果玩家的移动导致对称情况（例如两个相同的 L 形和四个 3x1 矩形），他可以通过镜像来响应其他玩家的移动，然后当只剩下一个大于 1x1 的矩形，他可以选择完全删除它或留下一个单元格（取决于剩下的单个单元格的数量是奇数还是偶数）并赢得比赛。

所以策略归结为创造一个对称的局面，而不是让其他玩家有机会创造一个对称的局面。

注意：可以通过移除 3x3、4x3 或 4x4 矩形的中心并创建一个环来创建更复杂的对称。不是镜像其他玩家的移动，而是将它们旋转 180 度（即点镜像）。

基于这些想法的一些游戏结果：

一个矩形：玩家 1 获胜。
两个相同的矩形：玩家 2 获胜。
一个 1x1 和一个细矩形：玩家 1 获胜。
一个 1x1 和一个 2x2 的矩形：玩家 2 获胜。
一个 1x1 和一个更大的矩形：玩家 1 获胜。
一个 2x2 和一个细矩形：玩家 1 获胜。
一个 2x2 和更大的矩形：玩家 1 获胜。
三个相同的矩形：玩家 1 获胜。
一个 1x1、一个 2x2 和任何其他矩形：玩家 1 获胜。
偶数个相同的矩形：玩家 2 获胜。
偶数个相同和任何其他矩形：玩家 1 获胜。
奇数个相同的矩形：玩家 1 获胜。

下面是 Sprague-Grundy 定理的实现，如 maraca 的回答中所述。它为最大 4x4 的矩形使用预先计算的数字列表。

function outcome(rectangles) {
    var n = 0, nimbers = [[1,2,3,4],[2,1,5,8],[3,5,4,7],[4,8,7,3]];
    for (var i = 0; i < rectangles.length; i++) {
        n ^= nimbers[rectangles[i][0] - 1][rectangles[i][1] - 1];
    }
    return n > 0 ? 1 : 2;
}
document.write("Player " + outcome([[3,3],[3,4],[4,4]]) + " wins.<br>");
document.write("Player " + outcome([[1,1],[2,2],[3,3],[4,4]]) + " wins.");

可以使用以下算法计算任何 4x4 矩阵的数量。 4x4 矩阵由 16 位模式表示，例如65535 是一个由 1 填充的矩阵。所有矩形（可能的移动）的列表，表示为位模式，是预先计算的。

function nimber(matrix) {
    var rect = [   1,    2,    3,    4,    6,    7,    8,   12,   14,   15,
                  16,   17,   32,   34,   48,   51,   64,   68,   96,  102,
                 112,  119,  128,  136,  192,  204,  224,  238,  240,  255,
                 256,  272,  273,  512,  544,  546,  768,  816,  819, 1024,
                1088, 1092, 1536, 1632, 1638, 1792, 1904, 1911, 2048, 2176,
                2184, 3072, 3264, 3276, 3584, 3808, 3822, 3840, 4080, 4095,
                4096, 4352, 4368, 4369, 8192, 8704, 8736, 8738,12288,13056,
               13104,13107,16384,17408,17472,17476,24576,26112,26208,26214,
               28672,30464,30576,30583,32768,34816,34944,34952,49152,52224,
               52416,52428,57344,60928,61152,61166,61440,65280,65520,65535];
    var memo = [0];                                    // nimber of empty matrix is 0
    return nim(matrix);

    function nim(current) {
        if (memo.hasOwnProperty(current)) return memo[current]; // use memoized value
        var exclude = [];                       // set of nimbers of reachable states
        for (var i = 0; i < rect.length; i++) {
            if ((current & rect[i]) == rect[i]) {   // this rectangle is a valid move
                var next = current & ~rect[i];                    // remove rectangle
                exclude[nim(next)] = true;           // recurse and add nimber to set
            }
        }
        return (memo[current] = mex(exclude));                 // memoize this nimber
    }
    function mex(n) {                              // minimum excludant of nimber set
        var m = 0;
        while (n[m]) ++m;
        return m;
    }
}

document.write(nimber(65535));   // 0b1111111111111111 represents a filled 4x4 matrix

代表 4x4 矩阵中所有大小、位置和方向的矩形的 16 位模式列表可以像这样生成：

function rectangles(width, height) {
    var rect = [], line = (1 << width) - 1;
    for (var y = 0; y < height; y++) {
        for (var x = 0; x < width; x++) {
            for (var h = 1; h <= height - y; h++) {
                for (var w = 1; w <= width - x; w++) {
                    var bits = ((line >> (width - w)) << (width - x - w)) << (y * width)
                    for (var row = 1; row < h; row++) {
                        bits |= (bits << width);
                    }
                    rect.push(bits);
                }
            }
        }
    }
    return rect;
}
document.write(rectangles(4,4));

Answer 2

这个问题用 Sprague Grundy theorem 解决了，它说当你对单个矩阵的数字进行异或时，只有当结果为 0 时，要移动的玩家才会输（因为任何移动都会使输位置处于获胜位置，然后另一个玩家可以再次将获胜位置变为失败位置，依此类推，这是类似 nim 游戏的本质。

数是递归计算的，矩阵的数是所有可达状态的数的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.

快速实现可能如下所示：

预先计算出16个（10个对称）不同情况的数字，并将它们存储在一个数组中。
赋值结果=0
result = 结果 xor nimbers[readRowCount()][readColCount()]
重复3.直到读取所有矩阵维度
if result != 0 then the first player wins else the second player

示例2：数字计算

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.

选择最佳矩阵

Choosing the Best Matrix

algorithm

matrix

game-theory

nim-game