Tic tac neutral

Question

Escuché este rompecabezas de Bob Koca. Supongamos que jugamos al tres en raya en el que ambos jugadores son X. ¿Quién gana?

Ese rompecabezas en particular es fácil de resolver, pero en general, tiene $n \times n$ ¿se ha estudiado antes el tic tac imparcial, tanto en su forma normal como en la misere?

---

EDIT: El documento de Thane Plambeck, mencionado al final de su respuesta más abajo, acuñó el término Notakto para este juego. Ese nombre parece haberse puesto de moda; por ejemplo, ahora existe un Artículo de Wikipedia sobre Notakto .

Answer 1

Bien, consideremos primero un tablero igualado y un robo de estrategia sencillo en el que el segundo jugador gira 180 grados las jugadas del primero en torno al centro del tablero. Esto funciona bien para las líneas horizontales y verticales, ya que si el segundo jugador completa una línea de este tipo, entonces el primer jugador debe haber completado la rotación de 180 grados de esa línea en el movimiento anterior. Sin embargo, tiene problemas con las diagonales.

El problema es que si giras una diagonal 180 grados obtienes la misma diagonal, por lo que la prueba anterior de que la estrategia funciona se viene abajo.

¿Qué podemos hacer al respecto? Una idea es intentar robar una estrategia un poco más complicada. Nos gustaría elegir una transformación que lleve líneas a líneas de tal forma que ninguna línea sea invariante. Todas las transformaciones obvias de orden 2 -- reflexiones y medias vueltas -- tienen líneas invariantes. Así que podríamos intentar una rotación de 90 grados. Por desgracia, esto no funciona, ya que, denotando esta rotación por R, si el primer jugador juega el punto x y luego el punto R^{-1}x, el jugador 2 no puede jugar R(R^{-1}(x)).

Pero al menos podríamos particionar todos los puntos del tablero en cuádruples de la forma {x,Rx,R^2x,R^3x} e intentar utilizar esta partición. ¿Qué ocurre si el segundo jugador juega Rx si es posible y R^{-1}x si no es posible jugar Rx? (Es fácil comprobar que esta estrategia se puede poner en práctica).

Un lema sencillo es que siempre que el jugador 2 juega un punto y, R^{-1}y ya está en el tablero. He aquí la prueba. Si el jugador 2 juega y, entonces o bien el jugador 1 acaba de jugar R^{-1}y, o bien el jugador 1 acaba de jugar Ry y el punto R^2y ya estaba jugado. Ahora bien, si el punto R^2y ya estaba jugado, entonces o bien lo jugó el jugador 1, en cuyo caso el jugador 2 habría jugado R^3y (a menos que ya estuviera jugado, pero eso también está bien y probablemente no sea posible -- no hace falta comprobarlo), o bien lo jugó el jugador 2, lo que de nuevo sólo podría haber ocurrido si el jugador 1 hubiera jugado R^3y.

Déjame intentarlo de nuevo con una prueba mucho más agradable. ¿Cómo se llenan los cuádruplos de la forma {x,Rx,R^2x,R^3x}? Sin pérdida de generalidad el primer punto a rellenar es x. Entonces el siguiente punto tiene que ser Rx. Después de eso, cuando el jugador 2 juega un punto en el cuádruple se juegan los cuatro puntos. Hecho.

Por lo tanto, si el jugador 2 completa una línea ... maldita sea, esto no funciona.

Permítanme terminar mostrando que toda esa estrategia fracasa, ya que aunque no responde a la pregunta proporciona algunas pruebas de que robar estrategias no va a funcionar. Si el jugador 1 sabe que el jugador 2 va a adoptar el robo de estrategia de 90 grados, entonces el jugador 1 puede llenar la fila superior, empezando por la izquierda. Entonces el jugador 2 llenará la columna de la derecha, empezando por arriba. Esto continúa hasta que el jugador 1 es bloqueado por la esquina superior derecha. A continuación, el jugador 1 rellena la esquina inferior izquierda y el jugador 2 completa una línea.

Obviamente, no es sorprendente que fracasara, ya que era una idea bastante improbable en primer lugar.

Un enfoque mejor

He aquí otra idea. Supongamos que tenemos un tablero de 4 m de ancho. Consideremos la transformación que añade 2m a las coordenadas x e y, mod 4m. Esto lleva las líneas horizontales a líneas horizontales y las líneas verticales a líneas verticales. También lleva las diagonales a diagonales y es autoinversa. Por desgracia, las dos diagonales siguen siendo invariantes.

Podemos remediar este último problema reflejando en una línea vertical a través del centro del tablero. Y si no me equivoco mucho, el resultado es una nueva transformación que sigue siendo autoinversa, lleva líneas a líneas y no tiene líneas invariantes. (Para esa última propiedad necesitaba que la anchura fuera múltiplo de 4).

Así que, después de todo, podemos hacerlo robando estrategias, al menos en este caso.

Observación adicional: la transformación que defino más arriba puede describirse del siguiente modo. Toma la mitad izquierda y la mitad derecha del tablero y refleja cada una de ellas alrededor de una línea vertical que pase por su centro. A continuación, traslada todo el tablero verticalmente 2m (mod 4m). El resultado es enviar todas las líneas verticales/horizontales a diferentes líneas verticales/horizontales e intercambiar las dos diagonales. Es fácil ver que haciendo esta transformación dos veces se obtiene la identidad.

Answer 2

Es posible dar una teoría completa de sumas disyuntivas tic-tac-toe de 3x3 misere "sólo X" introduciendo el monoide conmutativo de 18 elementos $Q$ dada por la presentación

$Q = \langle\ a,b,c,d\ | \ a^2=1,\ b^3=b,\ b^2c=c,\ c^3=ac^2,\ b^2d=d,\ cd=ad,\ d^2=c^2 \rangle\ $ .

Este juego "disyuntivo" del tres en raya neutro de 3x3 se juega no sólo con un tablero de tres en raya (como ya se ha comentado en este hilo), sino más generalmente con un número arbitrario (finito) de tales tableros formando la posición inicial. En el movimiento de un jugador, él o ella selecciona uno de los tableros, y hace una X en él (un tablero que ya tiene una configuración de tres en una fila de X's se considera fuera de juego). El juego termina cuando todos los tableros tienen una configuración de tres en raya, y el jugador que completa el último tres en raya en el último tablero disponible es el perdedor.

El juego analizado ya en este hilo corresponde a jugar en un tablero sencillo de 3x3.

El monoide Q surge como cociente misere del juego imparcial

G = 4 + {2+,0}

{2+,0} es la forma canónica de la posición de inicio del tablero sencillo 3x3, y "4" es el montón nim de tamaño 4, que también ocurre como posición en este juego. Estoy usando la notación de John Conway's On Numbers and Games, en la página 141, Figura 32.

Una forma de pensar en Q es que captura el análogo misere de los "nimbers" y la "adición de nim" que se utilizan en los análisis de juegos imparciales disyuntivos de juego normal, localizados al juego de este juego imparcial en particular, el tres en raya neutro 3x3.

Realicé estos cálculos en parte con Mathematica y en parte con el programa "MisereSolver" de Aaron N. Siegel.

Ver también

http://arxiv.org/abs/math/0501315

http://arxiv.org/abs/math/0609825

http://arxiv.org/abs/0705.2404

http://www.miseregames.org

Es posible construir un diccionario que asigne un elemento de Q a cada una de las 102 posiciones no isomórficas concebibles en el tres en raya neutral de un tablero de 3x3. (Me refiero a "no isomórficas" bajo un reflejo o rotación del tablero. Al hacer este recuento, estoy incluyendo posiciones a las que no se podría llegar en la realidad porque tienen demasiadas filas de X completadas, pero eso no importa ya que a todos esos elementos se les asigna el elemento de identidad de Q). Para determinar el resultado de una posición en varios tableros (es decir, si la posición es una posición N - el siguiente jugador en mover gana en la mejor jugada, o alternativamente, una posición P - el segundo jugador en mover gana), lo que una persona hace es multiplicar los elementos correspondientes de Q del diccionario juntos, y reducirlos a través de las relaciones en la presentación Q con la que empecé más arriba, llegando a una palabra en el alfabeto a,b,c,d.

Si esa palabra acaba siendo una de las cuatro palabras {a, b^2, bc, c^2 }, la posición es una posición P; de lo contrario, es una posición N.

Supongo que el juego 4x4 no tiene un cociente misere finito, pero no estoy seguro.

Si la gente quiere más detalles, estaré encantado de enviárselos. Busca mi nombre en Google para ver mi dirección de correo electrónico.

Mis mejores deseos

Thane Plambeck

Posdata (añadida el 8 de enero de 2013) He aquí un artículo http://arxiv.org/abs/1301.1672 Acabo de poner en el arXiv que tiene más detalles.

Answer 3

Por si te sirve de algo, aquí tienes un resumen de las respuestas hasta ahora para el juego Misere:

1x1: victoria P2 (cáliz envenenado)

2x2: P1 gana (P1 hace un movimiento arbitrario)

3x3: P1 gana (P1 juega en el centro, y su 2ª jugada es un movimiento de caballo lejos de la primera jugada de P2, y luego resuelve a mano: ver la respuesta de Kristal Cantwell).

4x4 y más generalmente 4n x 4n: P2 gana (robo de estrategia: ver el "mejor enfoque" de gowers)

5x5: P1 ganar (TonyK fuerza bruta de búsqueda por ordenador)

Answer 4

Actualizado para el caso 4m+2 x 4m+2

A riesgo de decir lo obvio, las estrategias descritas aquí para los juegos 3x3 y 4n x 4n pueden describirse mediante simples emparejamientos. Por ejemplo, el emparejamiento 4x4 es:

a b c d
e f g h
b a d c
f e h g

Cualquier movimiento que haga P1, P2 lo hace con la misma letra.

El emparejamiento 3x3 es:

a b c
c * d
d a b

P1 juega en el punto central *, y luego sigue la misma regla que P2 en el juego 4x4.

¿Cuándo un emparejamiento de este tipo conduce a una estrategia ganadora? Exigimos que siempre que se forme una línea jugando al emparejamiento de un punto de la cuadrícula, ya debe haber una línea en la cuadrícula en algún lugar (de modo que el otro jugador ya haya perdido). El emparejamiento debe satisfacer la siguiente condición:

Sea L una línea cualquiera de la cuadrícula (fila, columna o diagonal). Marca todos los puntos de L con una X, y marca también todos los emparejamientos de esos puntos. Si n es impar, marca el punto central * (primer movimiento de P1). Entonces, para cada punto de L (que no sea el punto central *), si lo borramos de la cuadrícula, ésta debe seguir conteniendo una línea de X.

Esto es siempre cierto si los emparejamientos de L forman otra línea, disjunta de L; tal es el caso de los emparejamientos 4n x 4n resultantes del Mejor Enfoque de Gowers. Pero también es cierto para el emparejamiento 3x3 dado anteriormente, como se puede comprobar por sí mismos con bastante facilidad.

¡Pero no existe tal emparejamiento en el tablero 5x5! Esto es bastante lioso, así que puede que me salte algunos detalles. No dudes en pedir aclaraciones. Aquí el "mapa" de una línea L es el conjunto de emparejamientos de los puntos de L; el punto central * se considera emparejado consigo mismo.

Reclamación 1: Ninguna línea L puede contener a la vez un punto y su emparejamiento. Porque entonces sólo habría como máximo tres puntos emparejados fuera de L, junto con el punto central *; y estos cuatro puntos no pueden ser suficientes para formar una recta cada vez que se borra un punto de L.

Reclamación 2: Toda recta L que pase por el punto central * debe corresponder a una recta que también pase por . Para los pares de los cuatro no puntos de L no serían suficientes para formar una línea cada vez que se borrara un punto no* de L. Por lo tanto, si llamamos a la unión de la fila 3, la columna 3 y las dos diagonales el conjunto de asteriscos, entonces los puntos en (resp. fuera de) el conjunto de asteriscos deben emparejarse con puntos en (resp. fuera de) el conjunto de asteriscos.

Reclamación 3: Cualquier línea L que no pase por * debe mapear a una línea disjunta (y por tanto paralela). Porque hay como máximo 6 X fuera de la línea; si cuatro de ellos forman una línea K, intersecando L en el punto p, digamos, entonces borrar el punto p dejará la cuadrícula sin línea (porque los dos puntos restantes, junto con como máximo un punto de L y un punto de K, no son suficientes para formar una línea).

Reclamación 4: Toda recta L que no pase por * debe corresponder a una recta paralela disjunta que no pase por *. Porque la afirmación 2 nos dice que las rectas que pasan por * se corresponden con rectas que pasan por *, y la función de emparejamiento es su propia inversa.

Consideremos ahora la fila 1 y la fila a la que corresponde según el emparejamiento: Fila r, digamos. La bisectriz vertical de la cuadrícula (Columna 3) interseca estas filas en los puntos p1 y pr, digamos. Los puntos de la fila 1 que no son iguales a p1 se emparejan con puntos de la fila r que no son iguales a pr; por tanto, p1 debe corresponder a pr. Esto contradice la afirmación 1. Así que no puede haber tal emparejamiento. QED

Esta prueba funciona para cualquier impar n >= 5. No funciona para n=3, porque la afirmación 3 falla: los dos puntos restantes, junto con a lo sumo un punto de L y un punto de K, son suficientes para formar una recta.

Bueno, ¡pero un jugador tiene que tener una estrategia ganadora! ¿Cuál? Podemos responder a esta pregunta con bastante facilidad para n=5, mediante una búsqueda de fuerza bruta por ordenador, trabajando hacia atrás desde el tablero lleno marcando todas las posiciones como ganadoras o perdedoras. Sólo hay $2^25$ posiciones a tener en cuenta, y la búsqueda lleva unos 30 segundos en mi portátil. Resulta que el tablero 5x5 es una victoria para P1, que puede hacer cualquier movimiento inicial. (En cambio, en el tablero de 3x3 la única jugada ganadora es el punto central *.) Esto nos dice dos cosas: (i) P1 gana; (ii) la estrategia ganadora no es un simple emparejamiento.

Actualización El caso n x n, con n = 4m + 2

Tampoco en este caso hay una estrategia de emparejamiento sencilla. El análisis es más sencillo para los tamaños de cuadrícula pares. Sólo necesitamos

Reclamación 1: Ninguna línea L puede contener a la vez un punto y su emparejamiento. Porque entonces sólo habría a lo sumo n-2 puntos emparejados fuera de L; y estos puntos no pueden ser suficientes para formar una recta cada vez que se borra un punto de L.

Reclamación 2: Cada línea L debe corresponder a una línea disjunta. Si n-1 de ellas forman una línea K que interseca a L en el punto p, por ejemplo, al borrar el punto p la cuadrícula se quedará sin línea (porque los puntos restantes, junto con un punto de L y un punto de K, como máximo, no son suficientes para formar una línea).

Esto significa que las filas coinciden con las filas, las columnas con las columnas y las dos diagonales entre sí.

Consideremos ahora el punto (a,a) de la diagonal principal. Supongamos que la fila a corresponde a la fila b, y que la columna a corresponde a la columna c. Entonces el punto (a,a) debe estar emparejado con el punto (b,c), y este punto (b,c) debe estar en la diagonal final: b+c = n+1. Por tanto, la columna a debe estar en la diagonal final. Por lo tanto, la columna a corresponde a la columna c = n+1-b. Así tenemos la siguiente implicación:

Fila a corresponde a Fila b => Columna a corresponde a Columna n+1-b

Podemos intercambiar filas y columnas en esta implicación, de modo que

La columna n+1-b corresponde a la columna a => La fila n+1-b corresponde a la fila n+1-a

Combinándolos:

La fila a corresponde a la fila b => La fila n+1-b corresponde a la fila n+1-a

Ahora bien, a no puede ser igual a n+1-a, porque n es par. Y si a es igual a n+1-b, entonces la columna a corresponde a la columna a, lo que no está permitido. Así que podemos dividir las n filas en grupos de la forma (a, b, n+1-b, n+1-a). Pero esto es claramente imposible si n no es múltiplo de 4. QED

Answer 5

En misere tic tac toe en un tablero de 3x3 con cada jugador siendo x el primer jugador ganará. el primer jugador jugará (2,2) entonces WLOG el segundo jugador jugará (1,1) o (2,3) entonces si el segundo jugador ha jugado (1,1) el primero jugará (2,3). Y si el segundo jugador ha jugado (2,3) el primero jugará (1,1). Ahora hay cuatro casillas en las que el segundo jugador puede moverse sin perder: (1,2),(1,3),(3,2) y (3,1). Si el segundo jugador juega (1,2) el primer jugador juega (3,1) y en el siguiente movimiento el segundo jugador debe formar una línea de tres y el primer jugador gana. Si el segundo jugador juega (3,1) el primer jugador juega (1,2) y en el siguiente movimiento el segundo jugador debe formar una línea de tres y gana el primer jugador. Si el segundo jugador juega (1,3) el primer jugador juega (3,2) y en el siguiente movimiento el segundo jugador debe formar una línea de tres y gana el primer jugador. Si el segundo jugador juega (3,2) el primer jugador juega (1,2) y en el siguiente movimiento el segundo jugador debe formar una línea de tres y el primer jugador gana. Pero esto agota todos los casos por lo que el primer jugador debe ganar en este juego.