Assume a tic-tac-toe board's state is stored in a matrix. $$ S=\begin{bmatrix} -1 & 0 & 1 \\ 1 & -1 & 0 \\ 1 & 0 & -1 \\ \end{bmatrix} $$

Here, $X$ is mapped to $1$, $O$ is mapped to $-1$ and an empty state is mapped to zero, but any other numeric mapping will do if there is one more suitable for solving the problem. Is it possible to create some single expression involving the matrix $S$ which will indicate whether the board is in a winning state? For the above matrix, the expression should show a win for $O$.

I recognize that there are more direct programmatic approaches to this, so this is more of an academic question.

Edit: I have been asked what to do if the board shows two winners. You could either:

  1. Assume only valid board states. Since gameplay would stop after once side wins, it is not possible to have a board with two winners.
  2. Alternatively (or equivalently?), your expression could arbitrarily pick a winner in a board that has two.
  • 2
    $\begingroup$ In some ways this question involves the mixing of how the visualization of the matrix "appears" with what its values are. By this, I mean that you might treat the matrix as the graph of a function $z = f(x, y)$. The function is taken modulo $3$ (letting $2$ be displayed as $-1$). Taking this approach and letting the coordinate system be "$x$ increasing to the right, $y$ increasing downwards", it is clear that there is a line along $x=y$ having $-1$ as the value of each entry. But this approach is also mostly academic. $\endgroup$ – abiessu Aug 14 '13 at 21:05
  • 1
    $\begingroup$ Do you want to exclude cases where you have eg a column of $-1$ and another column of $1$ - is it possible for these to occur, or not? $\endgroup$ – Mark Bennet Aug 14 '13 at 21:19
  • $\begingroup$ @Mark Bennet You can assume only valid board states. Since gameplay would stop after one side wins, it is not possible for that to occur. $\endgroup$ – killdash9 Aug 14 '13 at 21:24

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. :)

| cite | improve this answer | |
  • 1
    $\begingroup$ You can assume only valid board states. Since gameplay would stop after once side wins, it is not possible for this to occur. Alternatively, if it makes it easier to express, your expression could arbitrarily pick a winner in a board that has two. $\endgroup$ – killdash9 Aug 14 '13 at 21:37
  • 1
    $\begingroup$ This looks correct to me. This is a very direct approach to the problem of testing for each of the 4 types of wins. I have been wondering if there is some more general, probably more obscure, way of doing this purely with matrix multiplication. $\endgroup$ – killdash9 Aug 14 '13 at 22:40

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.

| cite | improve this answer | |
  • $\begingroup$ This is interesting. How hard would it be to extend this idea to a 3x3? $\endgroup$ – killdash9 Aug 15 '13 at 0:12
  • $\begingroup$ @russ I guess you just need a good computer, more patience and some luck. $\endgroup$ – Lord Soth Aug 15 '13 at 0:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.