Todos se dan cuenta de que Tic Tac Toe es un juego resuelto. Sin embargo, la versión Misère de only-Xs ofrece una alternativa interesante.

En esta versión del juego, ambos jugadores juegan Xs en el tablero e intentan evitar hacer tres seguidos. Si desea ver más sobre esto, Numberphile tiene un buen video sobre este concepto.

Dado un tablero de Misère Crosses, juega un movimiento óptimo.

Un tablero tiene tres líneas de tres caracteres cada una, que son Xo . Así:

X X
X  
 XX

Es un tablero válido. Puede tomar esto en cualquier formato conveniente, siempre que su entrada y salida usen el mismo formato. Los formatos incluyen (pero no se limitan a): una cadena de varias líneas (con una nueva línea final opcional); Una matriz 2D de caracteres que son Xo ; una matriz aplanada 1D de valores booleanos que representan si se ha jugado cada posición.

Un movimiento óptimo es aquel que garantiza que ganará si continúa jugando de manera óptima o prolonga su pérdida el mayor tiempo posible y se define mediante las siguientes reglas:

• Evita hacer tres seguidos.
• Si vas primero, juega en el medio.
• Si el único espacio ocupado es el medio, juega en cualquiera de los espacios restantes.
• Si el cuadrado del medio no está ocupado y un cuadrado exterior sí, juega enfrente de la última jugada de tu oponente.
• Si la casilla del medio está ocupada y una casilla exterior lo está, juega un "movimiento de caballeros" (opuesto, uno encima) lejos de un movimiento anterior que no te haga perder.
• Si no quedan casillas restantes donde no perderás, juega en cualquiera de las casillas restantes.

[NOTA: se ha demostrado que esto no es óptimo en un caso, pero debe usar este algoritmo de todos modos.]

Puede suponer que todos sus movimientos anteriores fueron óptimos. Por lo tanto, la primera placa de ejemplo no es una entrada válida. Los movimientos de tu oponente pueden o no ser óptimos.

Si el juego ha terminado (es decir, se ha hecho un tres en una fila), el comportamiento no está definido.

Como se trata de código de golf , ¡la respuesta más corta en bytes gana!

Un camino posible, que usa solo movimientos óptimos, es este:

[   ]  [   ]  [X  ]  [X  ]  [X  ]  [X  ]  [XX ]
[   ]->[ X ]->[ X ]->[ XX]->[ XX]->[ XX]->[ XX]
[   ]  [   ]  [   ]  [   ]  [ X ]  [XX ]  [XX ]

Aquí hay posibles entradas que se originan del oponente usando movimientos no óptimos:
(Tenga en cuenta que solo los tableros del lado izquierdo en esta lista son entradas válidas).

[X  ]  [X  ]
[   ]->[   ]
[   ]  [  X]

[XX ]  [XX ]
[   ]->[   ]
[  X]  [ XX]

[XX ]  [XX ]
[X  ]->[X X]
[ XX]  [ XX]

Ruby, Rev B 121 bytes

La sumisión es la función anónima, menos la f=. Se muestra en el programa de prueba para ilustrar el uso.

f=->n{["~mK)\7","}uYwQO"][l=n%2].bytes{|t|9.times{|i|(m=n|1<<i)==n||8.times{|j|m/2*257>>j&255==126-t&&t+j%2!=119&&l=m}}}
l}

puts g=f[gets.to_i]
puts
[7,6,5,
 8,0,4,
 1,2,3].each{|i|print g>>i&1; puts if i/3==1}

Se ahorran 2 bytes al hacer que el cuadrado central sea el bit menos significativo en lugar del bit más significativo (eliminar por en /2lugar de %256). Ahorros restantes por una reorganización de la tabla de movimientos aceptables. Organizarse como centro cuadrado libre / ocupado en lugar de por el número total de X permite una prueba más simple. Además, ahora solo hay 2 cadenas en la matriz, por lo que la %w{string1 string2}sintaxis se abandona a favor de la ["string1","string2"]sintaxis. Esto permite \7incluir un carácter no imprimible , que a su vez permite utilizar una codificación más simple: en 126-tlugar de (36-t)%120.

Ruby, Rev A 143 bytes

->n{l=r=("%b"%n).sum%8
%w{$ %5 - I+Wy Q S#}[r].bytes{|t|9.times{|i|(m=n|1<<i)==n||8.times{|j|m%256*257>>j&255==(t-36)%120&&t+j%2!=43&&l=m}}}
l}

Esta es una función anónima. El formato de entrada / salida se dejó abierto, así que elegí un número binario de 9 bits. el bit de 512 representa el centro, con los bits restantes girando en espiral alrededor de él (el bit de 1 se considera una esquina).

Hay muchas más entradas posibles que salidas aceptables, por lo que el algoritmo es probar todos los movimientos y encontrar uno que se ajuste a un patrón de salida aceptable. Los patrones de salida aceptables para cada número de X están codificados.

La información sobre el cuadrado central se elimina y los 8 bits restantes se multiplican por 257 para duplicarlos. Este patrón se gira más allá de los patrones aceptables mediante el desplazamiento de derechos.

El ciclo no sale cuando se encuentra un patrón, por lo que el patrón devuelto será el ÚLTIMO patrón encontrado. Por esta razón, los patrones preferibles (donde hay una preferencia) aparecen más adelante en la lista.

Dada la estrategia de 'Movimiento de los Caballeros', es de poca importancia si un patrón gira 45 grados o no. La versión sin golfista sigue la estrategia de movimiento de los caballeros y, por lo tanto, no necesita diferenciar entre los cuadrados de las esquinas y los cuadrados de los bordes: de todos modos, se debe evitar tres en fila.

Sin embargo, descubrí que esta no siempre es la mejor estrategia, ya que existe el siguiente truco. Si tu oponente va primero y toma el centro, debería ganar. Pero en su segundo movimiento, comete el error de permitirte hacer un cuadrado de 2x2, deberías tomarlo, ya que esto te permite obligarlo a hacer tres seguidos. Esto se implementa en la versión de golf. Se necesita un pequeño código adicional en esta instancia para distinguir entre tres X en una esquina (obligar al oponente a perder) y 3 X a lo largo de un borde (suicidio inmediato).

Sin golf en el programa de prueba

La versión no golfista sigue la lógica expresada en la pregunta.

En la versión de golf, la tabla se modifica ligeramente [[0],[1,17],[9],[37,7,51,85],[45],[47,119]]para implementar un comportamiento ligeramente diferente para el caso r=3. Luego se comprime a ASCII imprimible (que requiere decodificación (t-36)%120). Se requiere un poco de lógica adicional para diferenciar entre tres X en una esquina y tres X a lo largo de un borde en el caso de la entrada de tabla 7:&&t+j%2!=43

f=->n{l=r=("%b"%n).sum%8                                      #convert input to text, take character checksum to count 1's(ASCII 49.) 
                                                              #0 is ASCII 48, so %8 removes unwanted checksum bloat of 48 per char.
                                                              #l must be initialised here for scoping reasons.
  [[0],[1,17],[9],[11,13,37,51,85],[45],[47,119]][r].each{|t| #according to r, find the list of acceptable perimeter bitmaps, and search for a solution.
    9.times{|i|(m=n|1<<i)==n||                                #OR 1<<i with input. if result == n, existing X overwritten, no good.
                                                              #ELSE new X is in vacant square, good. So.. 
      8.times{|j|m%256*257>>j&255==t&&l=m}}                   #%256 to strip off middle square. *257 to duplicate bitmap.
                                                              #rightshift, see if pattern matches t. If so, write to l
  }
l}                                                            #return l (the last acceptable solution found) as the answer.

#call function and pretty print output (not part of submission)
puts g=f[gets.to_i]
puts
[6,7,0,
 5,8,1,
4,3,2].each{|i|print g>>i&1; puts if i<3}

Salida del programa de prueba

Esto es lo que sucede cuando la computadora se juega sola.

C: \ Users \ steve> ruby ​​tictac.rb
0 0
256

000
010
000

C: \ Users \ steve> ruby ​​tictac.rb
256
384

010
010
000

C: \ Users \ steve> ruby ​​tictac.rb
384
400

010
010
100

C: \ Users \ steve> ruby ​​tictac.rb
400
404

010
010
101

C: \ Users \ steve> ruby ​​tictac.rb
404
436

010
110
101

C: \ Users \ steve> ruby ​​tictac.rb
436
444

010
110
111

ANÁLISIS DEL JUEGO JUGANDO PRIMERO

Esto es realmente muy simple y lineal.

Al jugar primero, el cuadro del medio siempre será el primer cuadro ocupado.

r = 0

...  binary representation 0
.X.
...

r = 2

X..  binary representation 1001=9 
.XX
...

r = 4

X.. binary representation 101101=45
.XX
XX.

Solo hay una forma (hasta la simetría) de tener cinco X, incluida la casilla central en el tablero, sin que el juego haya terminado. Hay una X en el cuadrado del medio, una en cada diagonal (a 90 grados entre sí) y una en cada línea central horizontal / vertical (a 90 grados entre sí). Como no se puede ocupar un borde completo, lo anterior es lo único arreglo posible. Otro jugador debe perder en el próximo movimiento.

ANÁLISIS DEL JUEGO JUGANDO SEGUNDO

El juego es bastante diferente dependiendo de si el otro jugador elige la casilla del medio.

r = 1

plaza central ocupada

.X. X..  binary representation 1 
.X. .X.
... ...

plaza media libre

X.. .X. binary representation 10001=17
... ...
..X .X.

r = 3

Casilla central ocupada, si otro jugador juega adyacente a tu última X Jugar la jugada de un caballero como se muestra a continuación es compatible con la versión sin golf

XX. .XX binary representation 1011=11 
.X. XX. or mirror image 1101=13
X.. ...

Sin embargo, lo anterior NO es el mejor movimiento y no es compatible con la versión de golf. El mejor movimiento es el siguiente, forzando una victoria en el siguiente turno:

XX. binary representation 111=7.           XXX
XX. Only to be used where j is odd.        .X.
... Even j would look like image to right. ...

Casilla central ocupada, si otro jugador juega a 90 o 135 grados con respecto a tu última X (juega la jugada del caballero)

X.X .X. binary representation 100101=37 
.X. .XX
.X. X..

Plaza media libre

X.X .X. XX. binary representations:
... X.X ...    1010101=85 (first two)
X.X .X. .XX and 110011=51 (last one)

r = 5

plaza central ocupada. Por las razones indicadas anteriormente en r = 4, hay cuatro movimientos posibles, todos los cuales pierden. solo uno es compatible: 101111 = 47.

plaza media libre. Solo hay una tabla posible hasta la simetría, de la siguiente manera. Otro jugador debe perder en el próximo movimiento, por lo que no hay necesidad de soportar r> 5.

XX. binary representation 1110111=119
X.X
.XX