Choosing the Best Matrix

Question

I am given X matrices of size Ni*Mi where 1<=N<=4 and 1<=M<=4, for all 1 <= i <= X

The game consists of choosing any rectangle (submatrix) from one of the given X matrices and removing this submatrix.

For Example: we have 1 matrix of size 4x4. Player 1 can choose a submatrix of size 4x4 (the entire matrix in this case) and remove it. Or they can choose a submatrix of 2x2 or 1x1 or 2x3 or any valid submatrix and remove it from the 4x4 matrix and we have the remaining matrix left in the game.

The player who can't make a move loses.

Which player wins?

Both Player Plays optimally.

Answer 1

This problem is solved with the Sprague Grundy theorem, which says that when you xor the nimbers of the individual matrices, then the player to move only loses when the result is 0 (because any move will turn the losing position in a winning position and the other player can then turn the winning position in a losing position again and so on, it's the nature of nim-like games).

The nimbers are calculated recursively, a nimber of a matrix is the mex (minimal exclusive = the smallest non-negative integer not present in the collection) of the nimbers of all reachable states.

All 0s is 0, you don't have a valid move and therefore it is a loss (0).

Exactly one 1 is 1 because the only reachable position is 0 and mex(0) = 1.

For two ones we have to decide whether they are adjacent or not, adjacent = mex(0, 1) = 2, not adjacent = mex(1) = 0... and so on.

Example:

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.

A fast implementation could look like this:

1. Calculate the nimbers for the 16 (10 with symmetries) different cases in advance and store them in an array.

2. Assign result = 0

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

4. Repeat 3. until all matrix dimensions are read

5. if result != 0 then the first player wins else the second player

Example 2: nimber calculation

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.

Answer 2

(Before maraca posted his answer about the Sprague Grundy theorem, I was trying to identify an optimal strategy for the game; I'll describe it below, maybe it can also be used to code a solution.)

The outcome of the game is the result of whether each rectangle is removed in an odd or even number of moves. If the total number of moves is odd, player 1 wins; if it is even, player 2 wins.

Let's take a look at the possible rectangles:

For all "normal" rectangles (except 2x2 and 1x1) the player who first removes part of it can decide whether it is completely removed in an odd number of moves (e.g. by removing it completely in one go) or in an even number of moves; the cells indicated in yellow show a first move which leaves the player in control.

For "thin" rectangles which are only 1 cell wide, the odd/even decision is taken immediately (by either removing the whole rectangle, or leaving 1 cell). For the other "normal" rectangles, the decision is delayed from 1 up to 3 moves, depending on the other player's actions.

The 1x1 rectangle can only be removed in one move (i.e. an odd number of moves). The 2x2 rectangle can be removed in one move, but the player cannot force an even number of moves by removing only part of it; the other player can always decide odd or even.

As you can see from the moves indicated in yellow in the images, a move which creates a symmetrical situation (e.g. dividing the 4x4 square into two 4x1 rectangles) leaves the person who created this situation in control of the outcome for this rectangle. He can e.g. force an even number of moves for this rectangle like this:

This is also true for the whole game: if a player's move results in a symmetrical situation (e.g. two identical L-shapes and four 3x1 rectangles) he can respond to the other player's moves by mirroring them, and then when there is only one rectangles greater than 1x1 left, he can choose to remove it completely or leave one cell (depending on whether the number of single cells left over is odd or even) and win the game.

So the strategy comes down to creating a symmetrical situation, and not giving the other player the opportunity to create a symmetrical situation.

Note: a more complicated symmetry can be created by removing the center of a 3x3, 4x3 or 4x4 rectangle and creating a loop. Instead of mirroring the other player's moves, you then rotate them by 180 degrees (i.e. point-mirroring).

A few game results based on these ideas:

• One rectangle: player 1 wins.
• Two identical rectangles: player 2 wins.
• A 1x1 and a thin rectangle: player 1 wins.
• A 1x1 and a 2x2 rectangle: player 2 wins.
• A 1x1 and a larger rectangle: player 1 wins.
• A 2x2 and a thin rectangle: player 1 wins.
• A 2x2 and a larger rectangle: player 1 wins.
• Three identical rectangles: player 1 wins.
• A 1x1, a 2x2 and any other rectangle: player 1 wins.
• An even number of identical rectangles: player 2 wins.
• An even number of identical and any other rectangle: player 1 wins.
• An odd number of identical rectangles: player 1 wins.

---

Below is an implementation of the Sprague-Grundy theorem, as explained in maraca's answer. It uses a list of pre-calculated nimbers for rectangles up to 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.");

The nimber of any 4x4 matrix can be calculated with the algorithm below. The 4x4 matrices are represented by 16-bit patterns, e.g. 65535 is a matrix filled with ones. A list of all rectangles (possible moves), represented as bit patterns, is pre-calculated.

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

The list of 16-bit patterns representing the rectangles of all sizes, positions and orientations in a 4x4 matrix can be generated like this:

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));