Determine the winner of a tic tac toe board with a single matrix expression?

Solution 1:

Sure, here's one way to do it with linear-algebra primitives. Define column vectors $e_1=(1,0,0)^T$, $e_2=(0,1,0)^T$, $e_3=(0,0,1)^T$, and a row vector $a=(1,1,1)$.

• You can detect if a row or column of $S$ is a winner by testing $a S e_i$ and $a S^T e_i$ for $\pm 3$. (Exercise: Which expression detects winning rows and which detects winning columns?)
• You can detect if the main diagonal is a winner by testing the trace of $S$.
• Finally, let $R$ be the matrix that permutes rows $1$ and $3$; then you can detect if the other diagonal is a winner by testing the trace of $RS$.

In order to combine all eight tests into a single expression, you'll have to specify what you want to do in case of an over-determined matrix. For example, if one row shows a win for $+$ and another row shows a win for $-$, what's the desired behavior?

Edit: Okay, assuming only valid board states, it's not too hard. We're just going to have to introduce some unusual notation. Define a slightly arbitrary function $$ \max^*(a,b)=\begin{cases} a& \text{if } |a| \geq |b|\\ b& \text{otherwise } \end{cases} $$ Then $\max^*$ is an associative operation, so we can extend it iteratively to any number of arguments, and the winner of the game is $$w(S)=\left\lfloor\frac13\max^*\left(\max^*_i(a S e_i), \max^*_i(a S^T e_i), \mathrm{tr}(S),\mathrm{tr}(RS)\right)\right\rceil$$ where $\lfloor x\rceil$ is the round-towards-zero function, so that $w(S)=0$ means nobody wins.

(If $S$ is an invalid state in which both players "win", $w(S)$ will pick the first winner according to the order of expressions tested.)

Edit 2: Here's a theoretical approach that technically uses only matrix multiplication on $S$... but then shifts all the work to a scalar.

Let $a=(1,3,3^2)$ and $b=(1,3^3, 3^6)^T=(1,27,729)^T$. Then $aSb$ is an integer which encodes $S$, and it has absolute value $\leq (3^9-1)/2=9841$. So there exists a polynomial $p$ of degree $\leq 3^9=19683$ such that $w(S)=p(aSb)$.

In fact, we can choose the even coefficients of $p$ to be zero. The odd coefficients are slightly harder to compute. :)

Solution 2:

Just a comment on the fact that more obscure solutions may exist that are easier to compute. I was able to construct one for the $2\times 2$ tic-tac-toe. Let \begin{align} \mathbf{Z}_1 = \left[\begin{array}{cc}2.3049 & -2.2506 \\ -2.2310 & 2.2420 \end{array}\right] \end{align} and \begin{align} \mathbf{Z}_2 =\left[\begin{array}{cc} -0.2072 & 0.2190 \\ 0.3336 & -0.0792\end{array}\right] \end{align} Let the tic-tac-toe matrix be $\mathbf{Z}$ with entries $0$, $1$ or $-1$ in the same manner as defined in the question. Let \begin{align} \chi \triangleq \det(\mathbf{Z}_1+\mathbf{Z})|\det(\mathbf{Z}_2+\mathbf{Z})| \end{align} Then, unless $\mathbf{Z}$ specifies an illegal board where both sides have won, $\chi \geq 1.5 \iff $ user $1$ has won, $-1 < \chi < 1.5\iff$ the game has not ended yet, and $\chi \leq -1$ if user $-1$ has won. For example, for \begin{align} \mathbf{Z} = \left[\begin{array}{cc} 1 & 1 \\ -1 & 0\end{array}\right] \end{align} obviously user $1$ has won, and indeed we have $\chi = 2.5252$.

The above was found using a genetic algorithm and experimenting with different $\chi$ forms.