¿Determinar el ganador de un tablero de dedo del pie tic tac con una expresión de matriz único?

Question

Asumir un tic-tac-dedo del pie de la junta de estado se almacena en una matriz. $$ S=\begin{bmatrix} -1 & 0 & 1 \\ 1 & -1 & 0 \\ 1 & 0 & -1 \\ \end{bmatrix} $$

Aquí, $X$ se asigna a $1$, $O$ se asigna a $-1$ y un vacío de estado se asigna a cero, pero cualquier otro numérico mapeo va a hacer si hay uno más adecuado para resolver el problema. Es posible crear una sola expresión que implique la matriz $S$ que se indique si el consejo está en una ganancia de estado? Para el de arriba de la matriz, la expresión debe mostrar una victoria para $O$.

Reconozco que hay más directa de los enfoques programáticos para esto, así que esto es más una cuestión académica.

Edit: me han preguntado qué hacer si la junta muestra dos ganadores. Usted podría:

1. Se supone que solo válida de la junta de los estados. Desde que el juego iba a parar después de que una vez que el bando que gane, no es posible tener una junta con los dos ganadores.
2. Como alternativa (o, equivalentemente?), su expresión podría arbitrariamente escoger un ganador en una tabla que tiene dos.

Answer 1

Seguro, aquí hay una manera de hacerlo con lineal álgebra de primitivas. Definir vectores columna $e_1=(1,0,0)^T$, $e_2=(0,1,0)^T$, $e_3=(0,0,1)^T$, y un vector de fila $a=(1,1,1)$.

• Usted puede detectar si una fila o columna de $S$ es un ganador de la prueba de $a S e_i$$a S^T e_i$$\pm 3$. (Ejercicio: expresión Que detecta ganar filas y que detecta la ganancia de columnas?)
• Usted puede detectar si la diagonal principal es un ganador de la prueba de la traza de $S$.
• Por último, vamos a $R$ ser la matriz que permutes filas $1$$3$; a continuación, puede detectar si la otra diagonal es un ganador de la prueba de la traza de $RS$.

Con el fin de combinar todos los ocho pruebas en una sola expresión, tendrás que especificar lo que desea hacer en caso de una sobre-determinado de la matriz. Por ejemplo, si una fila se muestra una victoria para $+$ y otra fila muestra un triunfo para $-$, ¿cuál es el comportamiento deseado?

Edit: Bueno, suponiendo que sólo válida de la junta de los estados, no es demasiado duro. Vamos a introducir un poco de notación. Definir un poco arbitrario de la función $$ \max^*(a,b)=\begin{cases} a& \text{if } |a| \geq |b|\\ b& \text{otherwise } \end{casos} $$ A continuación, $\max^*$ es una operación asociativa, por lo que podemos extender de forma iterativa a cualquier número de argumentos, y el ganador del juego es $$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$$ donde $\lfloor x\rceil$ es la ronda-hacia-la función cero, de modo que $w(S)=0$ significa que nadie gana.

(Si $S$ es un estado no válido en el que ambos jugadores "ganar", $w(S)$ escogerá el ganador del primer premio, de acuerdo con el orden de las expresiones probado.)

Edit 2: he Aquí un enfoque teórico que técnicamente sólo utiliza la multiplicación de la matriz en $S$... pero entonces cambia todo el trabajo por un escalar.

Deje $a=(1,3,3^2)$$b=(1,3^3, 3^6)^T=(1,27,729)^T$. A continuación, $aSb$ es un número entero que codifica $S$, y tiene valor absoluto $\leq (3^9-1)/2=9841$. De modo que existe un polinomio $p$ grado $\leq 3^9=19683$ tal que $w(S)=p(aSb)$.

De hecho, podemos elegir el que incluso los coeficientes de $p$ a cero. El extraño coeficientes son un poco más difíciles de calcular. :)

Answer 2

Solo un comentario sobre el hecho de que la más oscura de las soluciones puede existir, que son más fáciles de calcular. Que fue capaz de construir uno para el $2\times 2$ tic-tac-toe. Vamos \begin{align} \mathbf{Z}_1 = \left[\begin{array}{cc}2.3049 & -2.2506 \\ -2.2310 & 2.2420 \end{array}\right] \end{align} y \begin{align} \mathbf{Z}_2 =\left[\begin{array}{cc} -0.2072 & 0.2190 \\ 0.3336 & -0.0792\end{array}\right] \end{align} Deje que el tic-tac-toe matriz de $\mathbf{Z}$ con entradas $0$, $1$ o $-1$ en la misma manera como se define en la pregunta. Vamos \begin{align} \chi \triangleq \det(\mathbf{Z}_1+\mathbf{Z})|\det(\mathbf{Z}_2+\mathbf{Z})| \end{align} Entonces, a menos $\mathbf{Z}$ especifica un ilegales de la junta en la que ambas partes han ganado, $\chi \geq 1.5 \iff $ usuario $1$ ha ganado, $-1 < \chi < 1.5\iff$ el juego no ha terminado todavía, y $\chi \leq -1$ si $-1$ ha ganado. Por ejemplo, para \begin{align} \mathbf{Z} = \left[\begin{array}{cc} 1 & 1 \\ -1 & 0\end{array}\right] \end{align} obviamente el usuario $1$ ha ganado, y de hecho tenemos $\chi = 2.5252$.

El de arriba se encuentra el uso de un algoritmo genético y la experimentación con diferentes $\chi$ formas.