Tic-Tac-Latin!

Esta es una historia real, por lo que los nombres han sido alterados.

Mi profesor de latín, el señor Latin, creó su propia variante patentada (no es broma) de tic tac toe. Llamémoslo tic-tac-latin. El juego es simple, es esencialmente un tic tac toe jugado en una cuadrícula cuatro por cuatro.

Declaración de regla formal

Una línea es una fila, columna o diagonal. Hay dos símbolos, 'X' y 'O', pero uno o ambos pueden ser sustituidos por un símbolo diferente.
Obtienes un punto cuando tienes tres de tu símbolo y uno del otro personaje.

Estos arreglos puntúan:

--- O
-O--
XXXO
XOOX

O -XX
- O -
- X -
--- O

Estos no puntúan:

----
XXXX
----
OOOO

----
XXX-
----
OOO-

El juego se gana cuando un jugador tiene más puntos que otro. El juego es un empate solo si el tablero se llena.

Desafío

Resuelve este juego. Su trabajo es proporcionar una forma de garantizar una victoria o un empate, el que sea el resultado óptimo.

Su solución puede elegir comenzar primero o segundo (y, por lo tanto, puede elegir su símbolo). No es obligatorio implementar un juego interactivo donde el usuario ingresa movimientos y la pantalla correspondiente cambia. También puede ser una función o programa que toma la entrada como un estado del juego y genera un nuevo tablero o una descripción de su movimiento . Cualquiera de las opciones debe ejecutarse dentro de aproximadamente diez segundos por movimiento realizado.

---

Jugar a tu jugador contra cualquier secuencia de movimientos debe dar el resultado óptimo. Esto significa que puede asumir que la posición de entrada es una que se puede alcanzar desde el juego con su reproductor. Los envíos deben ser deterministas, y no necesariamente tienen que proporcionar una prueba de optimización, pero si se agrietan (al ser golpeados) sus envíos se considerarán inválidos (puede dejarlos, pero agregarlos (agrietados) en el título).

---

Esta es una tarea no trivial, por lo que cualquier presentación válida es impresionante y merece un tick aceptado, pero haré del código golf el criterio principal para ganar.

El ganador se elige bajando por esta lista hasta que se elija un ganador.

• Implementación resuelta más corta que siempre gana
  
• Implementación más corta
  

Perl, 147 bytes (no compite, toma más de 10 segundos por movimiento)

Incluye +4 para -0p

El programa juega X. Jugará un juego perfecto.

Ingrese la placa en STDIN, por ejemplo:

tictaclatin.pl
-X-O
-X--
X-X-
O--O
^D

La salida será la misma placa con todos Xreemplazados por Oy viceversa. Los espacios vacíos se llenarán con un número que indica el resultado si X jugaría allí, lo que 1significa que el resultado será una victoria, 2un empate y 3una derrota. Un juego terminado solo devuelve la misma posición con los colores invertidos.

En este ejemplo, la salida sería:

1O1X
1O33
O3O3
X33X

Entonces, la posición es una victoria Xsi juega en los 3 lugares a lo largo de la parte superior e izquierda. Todos los demás movimientos pierden.

Este resultado confuso es realmente conveniente si quieres saber cómo continúa el juego después de un movimiento. Como el programa siempre se reproduce, Xdebes intercambiar Xy Over los movimientos O. Aquí, por ejemplo, está bastante claro que Xgana jugando en la parte superior izquierda, pero ¿qué pasa si Xjuega en la tercera posición en la parte superior? Simplemente copie el resultado, coloque un Olugar en el movimiento que seleccione y reemplace todos los demás números de -nuevo, así que aquí:

-OOX
-O--
O-O-
X--X

Resultando en:

3XXO
3X33
X3X3
O33O

Obviamente, cada movimiento Odebe perder, entonces, ¿cómo pierde si juega en la esquina superior izquierda? Nuevamente, haga esto colocando Oen la esquina superior izquierda y reemplazando los dígitos por -:

OXXO
-X--
X-X-
O--O

Dando:

XOOX
1O33
O3O3
X33X

Entonces X solo tiene un camino por recorrer para su victoria:

XOOX
OO--
O-O-
X--X

Dando

OXXO
XX33
X3X3
O33O

La situación para Osigue siendo desesperada. Es fácil ver ahora que cada movimiento permite Xganar de inmediato. Al menos intentemos hacer 3 O seguidas:

OXXO
XX--
X-X-
O-OO

Dando:

XOOX
OO13
O3O3
X3XX

Xjuega el único movimiento ganador (observe que esto se realiza XXXOen la tercera columna:

XOOX
OOO-
O-O-
X-XX

Aquí la salida es:

OXXO
XXX-
X-X-
O-OO

porque el juego ya estaba terminado. Puedes ver la victoria en la tercera columna.

El programa actual tictaclatin.pl:

#!/usr/bin/perl -0p
y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/sx;$@<=>0||s%-%$_="$`O$'";$$_||=2+do$0%eg&&(/1/||/2/-1)

Aplicado al tablero vacío, esto evalúa 9506699 posiciones que toman 30Gb y 41 minutos en mi computadora. El resultado es:

2222
2222
2222
2222

Por lo tanto, cada movimiento inicial se basa. Entonces el juego es un empate.

El uso extremo de la memoria es causado principalmente por el uso recurrente do$0. El uso de esta versión de 154 bytes que utiliza una función simple necesita 3Gb y 11 minutos:

#!/usr/bin/perl -0p
sub f{y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/sx;$@<=>0||s%-%$_="$`O$'";$$_||=2+&f%eeg&&(/1/||/2/-1)}f

que es más soportable (pero aún demasiado, algo debe estar perdiendo memoria).

La combinación de varias aceleraciones conduce a esta versión de 160 bytes (5028168 posiciones, 4 minutos y 800M para el tablero vacío):

#!/usr/bin/perl -0p
sub f{y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/osx;$@<=>0||s%-%$_="$`O$'";$a{$_}//=&f+1or return 1%eeg&&/1/-1}f

El último se usa 0para ganar (no confundir con O), 1para empatar y 2para perder. La salida de este también es más confusa. Completa el movimiento ganador para X en caso de una victoria sin cambio de color, pero si el juego de entrada ya fue ganado, todavía cambia el color y no completa ningún movimiento.

Todas las versiones, por supuesto, se vuelven más rápidas y usan menos memoria a medida que la placa se llena. Las versiones más rápidas deberían generar un movimiento en menos de 10 segundos tan pronto como se hayan realizado 2 o 3 movimientos.

En principio, esta versión de 146 bytes también debería funcionar:

#!/usr/bin/perl -0p
y/XO/OX/,$@=-$@while/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^/sx,--$|;$@<=>0||s%-%$_="$`O$'";$$_||=2+do$0%eg&&(/1/||/2/-1)

pero en mi máquina activa un error perl y vuelca el núcleo.

En principio, todas las versiones seguirán funcionando si $$_||=se elimina el almacenamiento en caché de la posición de 6 bytes, pero eso consume tanto tiempo y memoria que solo funciona para tableros casi llenos. Pero, en teoría, al menos tengo una solución de 140 bytes.

Si coloca $\=(costo: 3 bytes) justo antes de $@<=>0cada placa de salida, le seguirá el estado de toda la placa: 1para Xvictorias, 0para empates y -1para pérdidas.

Aquí hay un controlador interactivo basado en la versión más rápida mencionada anteriormente. El controlador no tiene lógica para cuando finaliza el juego, por lo que debes detenerte. Sin embargo, el código de golf lo sabe. Si el movimiento sugerido regresa sin ser -reemplazado por nada, el juego ha terminado.

#!/usr/bin/perl
sub f{
    if ($p++ % 100000 == 0) {
        local $| = 1;
        print ".";
    }
y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/osx;$@<=>0||s%-%$_="$`O$'";$a{$_}//=&f+1or return 1%eeg&&/1/-1}

# Driver
my $tomove = "X";
my $move = 0;
@board = ("----\n") x 4;
while (1) {
    print "Current board after move $move ($tomove to move):\n  ABCD\n";
    for my $i (1..4) {
        print "$i $board[$i-1]";
    }
    print "Enter a move like B4, PASS (not a valid move, just for setup) or just press enter to let the program make suggestions\n";
    my $input = <> // exit;
    if ($input eq "\n") {
        $_ = join "", @board;
        tr/OX/XO/ if $tomove eq "O";
        $p = 0;
        $@="";
        %a = ();
        my $start = time();
        my $result = f;
        if ($result == 1) {
            tr/OX/XO/ if $tomove eq "O";
            tr/012/-/;
        } else {
            tr/OX/XO/ if $tomove eq "X";
            tr/012/123/;
        }
        $result = -$result if $tomove eq "O";
        my $period = time() - $start;
        print "\nSuggested moves (evaluated $p positions in $period seconds, predicted result for X: $result):\n$_";
        redo;
    } elsif ($input =~ /^pass$/i) {
        # Do nothing
    } elsif (my ($x, $y) = $input =~ /^([A-D])([1-4])$/) {
        $x = ord($x) - ord("A");
        --$y;
        my $ch = substr($board[$y],$x, 1);
        if ($ch ne "-") {
            print "Position already has $ch. Try again\n";
            redo;
        }
        substr($board[$y],$x, 1) = $tomove;
    } else {
        print "Cannot parse move. Try again\n";
        redo;
    }
    $tomove =~ tr/OX/XO/;
    ++$move;
}

JavaScript (ES6) 392 bytes

a=>b=>(c="0ed3b56879a4c21f",r=[],k=f=>r.push([a.filter(f),b.filter(f)]),[0,1,2,3].map(i=>k(n=>n%4==i)+k(n=>(n/4|0)==i)),k(n=>n%5==0),k(n=>n&&n-15&&!(n%3)),g=r.find(o=>(o[0].length==1&&o[1].length==2)||(o[0].length==2&&o[1].length==1)),g?parseInt(c[30-[...g[0],...g[1]].map(i=>parseInt(c[i],16)).reduce((p,c)=>p+c)],16):[...a,...b].indexOf(15-a[0])+1?15-a.find(i=>b.indexOf(15-i)==-1):15-a[0])

Uso

El "bot" jugará segundo.

Dibuja una cuadrícula de 4x4 que esté numerada así:

+----+----+----+----+
|  0 |  1 |  2 |  3 |
+----+----+----+----+
|  4 |  5 |  6 |  7 |
+----+----+----+----+
|  8 |  9 | 10 | 11 |
+----+----+----+----+
| 12 | 13 | 14 | 15 |
+----+----+----+----+

Ejecutemos esto en la consola del navegador: solo ponga f=antes del código

Entonces, si quiero comenzar 1, correría f([1])([])y me daría 14.

Buen movimiento ... ¿Qué pasa si juego 2después? f([2,1])([14]). Se volverá 13.

Déjame intentar rendirte. Jugar 3. f([3,2,1])([14,13]). Oh 0! ¡Me tienes!

Jugar 0? f([0,2,1])([14,13]). 15Ok, sigamos jugando ...

Nota

1. Juega interactivamente. Comenzar con f([your-step])([]).

2. Antepone tu próximo paso. (Ver demo arriba)

3. Ayuda al "bot" a ingresar sus pasos. No le dará buenos resultados si le da una configuración aleatoria. (Al igual f([1,2,4])([14,12])que dará 14- ¡Hey, el bot quería jugar 13en su segundo movimiento!

Resumen breve

Mientras no te rindas, el bot jugará un movimiento espejo.

Gracias @EHTproductions por decirme que leí mal las reglas del juego y los consejos de golf: P

Ahora también detectará si tiene jaque mate. Si es así, ¡bloquéalo!

Sus prioridades: Bloquear> Espejo> (respaldo) buscan formas de reproducir un espejo