algorithmmatrixgame-theorynim-game

Choosing the Best Matrix

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.

Solution

  • (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:

    all 10 types of 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:

    force even in 4x4

    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:

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