Juegos óptimos de Tic Tac Torus

31

Este desafío es sobre el juego Tic Tac Toe, pero se juega en un toro.

Cómo jugar

Para crear el tablero de juego necesario, comienzas con un tablero de juego Tic Tac Toe normal. Primero dóblelo en un cilindro uniendo el borde izquierdo y el derecho. Luego dóblalo en toro uniendo los bordes superior e inferior. Aquí hay una visualización simple de tal tablero de juego con algunos movimientos jugados (¡habilidades de pintura enferma!).

Tic Tac Torus

Las reglas de Tic Tac Toe en un toro son las mismas que las de Tic Tac Toe normal. Cada jugador coloca alternando Xs y Os. El primero con 3 símbolos iguales en una fila, una columna o una diagonal gana.

Dado que un toro es bastante difícil de visualizar, simplemente proyectamos el tablero nuevamente en un papel. Ahora podemos jugar el juego como Tic Tac Toe normal. La única diferencia es que también puedes ganar con 3 símbolos iguales en una diagonal rota. Por ejemplo, el Jugador 1 (X) gana el siguiente tablero. Puede ver esto fácilmente cambiando un poco la vista del toro.

El jugador 1 (X) gana debido a 3 X en una diagonal rota

Si estás interesado, puedes jugar a Tic Tac Toe en un Torus en Torus Games . Hay una versión para Windows, Mac y Android.

Juegos óptimos

En este desafío estaban interesados ​​en juegos óptimos. Un juego óptimo es un juego, donde ambos jugadores juegan una estrategia óptima. En un tablero regular de Tic Tac Toe, los juegos óptimos siempre terminan en empate. Fascinantemente en un tablero de toro siempre gana el primer jugador. De hecho, un juego en un tablero de toro nunca puede terminar en un empate (también si los jugadores juegan de manera no óptima).

La estrategia óptima es realmente fácil:

  • Si puedes ganar colocando tu símbolo, hazlo.
  • De lo contrario, si su oponente tiene dos símbolos en una fila / columna / giagonal, intente bloquearlo. De lo contrario, haz lo que quieras.
  • De lo contrario, haz lo que quieras.

Cada juego óptimo consta de exactamente 7 movimientos y estos movimientos se pueden describir de la siguiente manera:

  1. El jugador 1 coloca una X en cualquier lugar del tablero (9 opciones)
  2. El jugador 2 coloca una O en cualquier lugar del tablero (8 opciones)
  3. El jugador 1 coloca una X en cualquier lugar del tablero (7 opciones)
  4. El movimiento del jugador 2 puede ser forzado (1 opción), si no, coloca el O en cualquier lugar (6 opciones)
  5. El movimiento del jugador 1 es forzado (1 opción)
  6. El jugador 2 está atrapado en una bifurcación (el jugador 1 puede ganar de dos maneras diferentes), por lo que el jugador 2 tiene que bloquear al jugador 1 de una manera (2 opciones)
  7. El jugador 1 coloca su último movimiento y gana (1 opción)

Hay 9 * 8 * 1 * 6 * 1 * 2 * 1 + 9 * 8 * 6 * 1 * 1 * 2 * 1 = 1728 juegos óptimos diferentes en nuestro tablero proyectado. Aquí puedes ver un juego óptimo típico:

Ejemplo de un juego óptimo

Si etiquetamos cada celda del tablero con los dígitos 0-8, podemos describir este juego por los dígitos 3518207 . Primero, una X se coloca en la celda 3 (fila central, columna izquierda), que una O en la celda 5 (fila central, columna derecha), que una X en la celda 1 (fila superior, columna central), ...

Usando esta notación de dígitos generamos automáticamente un pedido. Ahora podemos ordenar todos los juegos óptimos de 1728 y obtenemos la lista:

Game 0000: 0123845
Game 0001: 0123854
Game 0002: 0124735
Game 0003: 0124753
Game 0004: 0125634
   ...
Game 0674: 3518207
   ...
Game 1000: 5167423
Game 1001: 5167432
Game 1002: 5168304
   ...
Game 1726: 8765034
Game 1727: 8765043

Reto

Esta lista es parte de tu trabajo. Recibirá un número kentre 0 y 1727 y deberá devolver el kjuego en notación de dígitos de esa lista ordenada.

Escribe una función o un programa, que recibe el número k(entero) calcula el juego correspondiente. Puede leer la entrada a través de STDIN, argumento de línea de comando, argumento de solicitud o función e imprimir el resultado (7 dígitos) en un formato legible (p. Ej. 0123845O [0, 1, 2, 3, 8, 4, 5]) o devolverlo usando una cadena (formato legible por humanos) o un entero (que contiene todos dígitos en base 10), o en cualquier formato de matriz / lista.

El tipo de desafío es el código de golf. Por lo tanto, el código más corto gana.

Jakube
fuente
¿Por qué el primer movimiento del jugador 2 tiene que estar en la misma fila o columna que el primer movimiento del jugador 1? He jugado algunos juegos en mi cabeza donde el primer movimiento del jugador 2 es en una de las mismas diagonales y siguen el mismo patrón de juego óptimo. Me parece que uno de los aspectos del tablero toroidal es que las filas, columnas y diagonales tienen efectos simétricos en el juego.
Runer112
@ Runer112 Simplificó mucho la estrategia óptima. La única regla ahora es bloquear a tu oponente si puedes, de lo contrario haz lo que quieras.
Jakube
77
Solo un comentario secundario: en realidad, hay muchos menos juegos únicos posibles aquí. La simetría traslacional hace que la posición del primer movimiento sea irrelevante (porque siempre puedes centrar tu vista), así que divide entre 9 ... y la rotación del tablero solo hace 2 segundos movimientos diferentes (diagonal o cuadrado adyacente) ... así que en La mayoría de los 48 juegos distintos. Si tiene en cuenta la simetría de reflexión, disminuye aún más. Esta versión de toro es mucho más aburrida que la normal. Golf de distancia.
orion
@orion En realidad, el hecho de que el toro se envuelva no nos prohíbe pensar en '0' como el 'primer' rect en el tablero del toro y distinguir los nueve campos en general ... Sin embargo, estamos de acuerdo en que el "meridiano 0" está en Greenwich , mientras que en el lado opuesto de la Tierra podemos tener una pierna en el lugar donde es jueves, una pierna en el lugar es miércoles (¡diferencia de 24 horas en la hora local!), y todo a pesar del hecho de que la Tierra es redonda y no tiene un "punto de partida" ...
pawel.boczarski
@Rodney No, es un uno, no un siete. Intenta calcularlo.
Jakube

Respuestas:

6

JavaScript (ES6), 266308 317 334 341

Una función que devuelve una cadena. Editar Se encontró una solución aritmética para la función M (¡por fin!)

F=(n,x=[],M=(a,b,t=-a-b)=>(a-b)%3?a<3&b<3?3+t:a>5&b>5?21+t:12+t:9+t+a%3*3)=>
[for(a of z='012345678')for(b of z)for(c of z)for(d of z) 
a-b&&c-a&&c-b&&(b-(y=M(a,c))?d==y:d-a&&d-b&&d-c)&&(
f=M(c,e=M(b,d)),g=M(a,e),g<f?[f,g]=[g,f]:0,r=a+b+c+d+e,x.push(r+f+g,r+g+f))]
&&x[n]

Muy ingenuo , se puede acortar de muchas maneras . Simplemente enumera todos los valores legales posibles y devuelve lo que encuentra en el lugar n. La función M devuelve la posición entre dos celdas, que es el movimiento obligatorio para bloquear a un jugador opuesto.

Más legible

F=(n,x=[],
  M=(a,b,t=-a-b)=>(a-b)%3? 
     a<3&b<3?
       3+t // first row
       :a>5&b>5?
          21+t // last row
          :12+t // middle row and diags
     :9+t+a%3*3 // columns
  )=>
  [for(a of z='012345678') // enumerate the first 4 moves
     for(b of z)
       for(c of z)
         for(d of z) 
           a-b&&c-a&&c-b // avoid duplicates
           &&(b-(y=M(a,c))?d==y:d-a&&d-b&&d-c) // and check if d must block a-c or it's free
           &&(
             e=M(b,d), // forced to block b-d
             f=M(c,e),g=M(a,e),g<f?[f,g]=[g,f]:0, // f and g could be in the wrong order
             r=a+b+c+d+e, // start building a return string
             x.push(r+f+g,r+g+f) // store all values in x
  )]&&x[n] // return value at requested position
edc65
fuente
3

Octava, 467369363309297 caracteres

297:

global t=0*(1:9)m=dec2bin([15;113;897;1170;1316;1608;2370;2216;2580])-48 a;
function g(s,p)global a t m;
if nnz(s)<8&&any((t==1)*m>2)a=[a;s];return;end;q=t==3-p;
(r=sort(~q.*(1:9)*m(:,find([3 1]*([q;t==p]*m)==6)')))||(r=find(~t));
for i=r t(i)=p;g([s i+47],3-p);t(i)=0;end;end;g('',1);f=@(n)a(n+1,:);

El único cambio relevante es que nunca verificamos si el jugador actual puede ganar, solo verificamos la posibilidad del oponente de ganar el próximo turno . Como el único turno que puede ganar el jugador 1 es el turno 7 , este es el único lugar donde el algoritmo produciría un juego que no es óptimo, pero es muy fácil filtrar esa situación. Simplemente verificamos cada juego generado si lo ganó el jugador 1; si no lo fue, el movimiento en el turno 7 fue incorrecto, por lo que no agregamos este juego a la mesa de juegos óptima.

(Exactamente la mitad de los juegos generados por esta regla son falsos, es decir. en el séptimo turno, el jugador 1 siempre tiene dos posibilidades para bloquear al jugador dos, pero solo uno lo hará ganar instantáneamente).

Utilizar:

$ octave
octave:1>> source script.m
octave:2>> f(634)
ans = 3270148

El código sin golf parece:

 global t=0*(1:9);
 global m=dec2bin([15;113;897;1170;1316;1608;2370;2216;2580])-48;
 global allgames;
 allgames=[];

 function r=canbewon(by)
  global t m
  q=[t==by;t==(3-by)]*m;
  g=(find([3 1]*q==6))';
  r=sort((~(t==by).*(1:9)) * m(:,g));
 end

 function games_starting_with(s)
 global allgames t;
 if 7==numel(s) && any((t==1)*m==3) # it's 7th move and first player won
  allgames=[allgames;s];
  return;
 end;
 poss=(find(~t));                  # for now all free slots are possible
 player=1+mod(numel(s),2);
 moves = canbewon(3-player);
 if numel(moves) poss=moves; end;  # ... no, we must block the other player
 for i=poss
  t(i)=player;
  games_starting_with([s char(i+47)]);
  t(i)=0;
 end
end

games_starting_with('');
f=@(n)(allgames(n+1,:));
pawel.boczarski
fuente
1
pequeña sugerencia: puede cortar versiones antiguas si usan la misma lógica, ya que estas se almacenan en el historial de edición para que aún estén disponibles
masterX244