[Math] Matrix tic tac toe

game theorylinear algebrarecreational-mathematics

So we have a 3×3 matrix and two players, a player that only puts in ones and a player that only puts in zeros. A coin flip is used to decide which player goes first. The first move is always to fill the upper left entry with the player's number, whoever won the coin flip. Then the players take turns filling in ones and zeros. Once the matrix is full, the winner is decided by the determinant of the matrix. If the determinant of the matrix is non-zero (an invertible matrix), the player who filled in ones wins. If the determinant of the matrix is zero (non-invertible matrix), the player who filled in zeros wins.

The question is:
Is one of the players always going to win if both players employ optimal strategies? Who wins if 1-player goes first? Who wins if 0-player goes first? Does it even depend on who goes first?

Best Answer

0 always wins (regardless of 1's strategy). This is because any configuration with (a) 0s all in one row or (b) 0s all in one column or (c) 0s all in a 2x2 minor will win.

For the case 1 goes first, let 0 play in the center square. After which up to symmetry there are only four cases that need to be considered after 4 moves

11.      1.1     1..    1..
.00      .0.     .01    .00
...      .0.     .0.    ..1

(this being 0's strategy). It is easy to see that either 1 allows 0 to make a line in the 6th move, or 1 allows a block of the form

.0
00.

to form after the 6th move which guarantees win for 0.

When 0 goes first she wins faster.

Related Question