¿Cuál es tu próximo movimiento?

18

Este desafío es escribir una función minimax en el idioma que elija, para obtener el siguiente mejor movimiento en un juego de NxN de tic-tac-toe dado el estado actual del tablero . La entrada de la placa se puede aceptar como una matriz, una colección 2D o cualquier otra cosa que tenga sentido para usted, pero que cumpla con las reglas . La salida es el siguiente mejor movimiento para quien sea el turno en este momento , donde se considera que X ha comenzado .

Antecedentes rápidos sobre el algoritmo Minimax

La idea básica del algoritmo minimax es enumerar todos los resultados posibles como un DAG y luego ponderarlos por el beneficio que la secuencia de movimientos tiene para el jugador, clave por el primer movimiento realizado. Todos los resultados posibles se `` agrupan '' en el primer movimiento y se puntúan en función de la suma de todos los resultados (-1 para una pérdida, 0 para un empate y un 1 para una victoria). En implementaciones que requieren que jueguen varios jugadores, enumeras todos los movimientos posibles del jugador y todas las respuestas posibles de los oponentes también. Por ejemplo, en un juego de tic-tac-toe (después del primer movimiento) hay 8 posibles primeros movimientos que puedes hacer, y todos pueden parecer iguales cuando solo analizas el siguiente turno. Pero al iterar a través de todos los resultados posibles para cada conjunto posible de movimientos que resultan en un resultado final y resumirlos todos,

Para obtener un resumen mejor, más profundo y contextual del algoritmo mini-max en términos de tic-tac-toe, lea más aquí: http://neverstopbuilding.com/minimax

XKCD (solo solución 3x3)

Todos los movimientos posibles para un juego 3x3 de tic-tac-toe.

Las normas

  • Se puede usar cualquier idioma, pero no se permiten bibliotecas externas de minimax.
  • La salida puede ser una coordenada (0-n, 0-n) o un número (1-n * n) indicativo del mejor próximo movimiento.
    • Además de esto, debe poder identificar cuándo el mejor de los casos es una pérdida o un empate en lugar de una victoria.
    • La forma en que denota una pérdida o un empate depende, una vez más, de usted.
  • La entrada debe usar las X y O tradicionales, y debe asumir que X se mueve primero; los espacios en blanco se pueden representar por cualquier cosa.
  • Puede suponer que las entradas que entran en su programa tienen n O y n + 1 X, en otras palabras, puede suponer que está obteniendo una placa bien formada.
  • El estado actual de la placa debe ser la única entrada a su programa, si está utilizando recursividad, se deben realizar métodos auxiliares para facilitar los requisitos de entrada. Consulte /codegolf//a/92851/59376 para obtener una aclaración.
  • Cualquier valor de 10> = n> = 1 debe ser compatible; si su programa "agota el tiempo de espera" para n> 10, también me parece aceptable, ya que algunos idiomas tienen un poder de procesamiento significativamente menor (especialmente usando consolas orientadas a la web).

Juzgar

  • Este es el código de golf, por lo que el conteo de bytes más bajo del programa gana y las lagunas estándar se rechazan universalmente.
  • En caso de empate, ganará el programa que admita la 'n' más grande.

Entradas de ejemplo

2x2

[[X,O]
 [-,-]]

Salida: 2 o [0,1] (3 o [1,1] también sería posiblemente correcto) (alguna forma de indicación de la ubicación, arbitraria siempre que pueda explicar fácilmente el formato que utilizó)


3x3

[[X,O,X]
 [O,X,-]
 [-,-,-]]

Salida: -1 (pérdida)


Una vez más, se permite cualquier formato de entrada que desee, pero se deben usar X y O, los ejemplos proporcionados no estaban destinados a restringir a ese formato, solo a inspirar.

Urna de pulpo mágico
fuente
Lo siento DJMCMayhem, en realidad intenté etiquetar esas cosas pero no pude, ya que soy nuevo aquí.
Urna de pulpo mágico
La bonificación también se eliminó, no se agregó más que tedio
Urna de pulpo mágico
¿Se permite el siguiente formato de salida: un diagrama de la posición del tablero con en cada espacio originalmente vacío un carácter único que indica si jugar allí conduce a una victoria / pérdida / empate (por ejemplo, W, L y D)
Ton Hospel
1
En el ejemplo 3x3, O debería perder sin importar lo que juegue, pero usted dice que la salida debería ser [2,1], ¿por qué es eso?
Dada
Editado, buena captura. No sé lo que estaba pensando, ese fue el ejemplo negativo.
Magic Octopus Urn

Respuestas:

8

Perl, 101 98 bytes

Incluye +4para-0p

Ejecutar con la entrada en STDIN

tictactoe.pl
OXO
---
--X
^D

La salida es el mismo diagrama, pero con cada movimiento actualizado con su estado, 1representa una victoria, 2un empate y 3una pérdida. Para este caso eso sería

OXO
223
21X

entonces 3 movimientos empatan, 1 gana y 1 pierde (actualizaré la solución si este formato de salida es inaceptable, pero el código básico seguirá siendo el mismo)

tictactoe.pl:

#!/usr/bin/perl -0p
m%@{[map"O.{$_}"x"@-"."O|",1-/.(
)(.)/,@-]}Z%sx||s%-%$_="$`X$'";y/XO/OX/;do$0%eg?/1/?3:1+/2/:2

Esto ya es dolorosamente lento y usa mucha memoria para la placa vacía de 3 * 3 (por qué, en realidad, la recursión no es tan profunda. Debe haber alguna pérdida de memoria). Agregar memorando cuesta 6 bytes pero es mucho más sensato:

#!/usr/bin/perl -0p
$$_||=m%@{[map"O.{$_}"x"@-"."O|",1-/.(\n)(.)/,@-]}Z%sx||s%-%$_="$`X$'";y/XO/OX/;do$0%eg?/1/?3:1+/2/:2
Ton Hospel
fuente
Wow, pasando por alto que es pl y probablemente no funcionaría para n = 10 con muchos vacíos ... Hiciste las dos cosas que esperaba ver a alguien hacer. Una entrada de cadena y un mapeo del resultado para todos los movimientos, no solo el mejor. Bravo.
Urna de pulpo mágico
Si una función recursiva 'fuga', ¿cómo puede estar bien? Un lenguaje demasiado alto hace que no vea el registro de 32 bits en la CPU (o algo así como la simple instrucción)
RosLuP
La fuga de @RosLup en este contexto no significa necesariamente una pérdida de memoria inalcanzable. Perl es bastante peculiar cuando libera memoria, a menudo lo hace más tarde de lo esperado y, por lo tanto, usa mucha más memoria de la que esperaría. También tiende a asignar más de lo que se necesita directamente con la expectativa de que hará crecer sus estructuras de datos. En este caso, usar una recursión "normal" con una función en lugar del abuso de do$0usaría 10 veces menos memoria. Eso sí, este caso es tan extremo que en realidad podría ser una pérdida de memoria real.
Ton Hospel
No solo uno no ve los registros o las instrucciones básicas (de las instrucciones hlls) sino que pierde el control del uso de la memoria ... Para mí no escalan ...
RosLuP
Ha pasado bastante tiempo, ganaste a mi hombre, triste pero no tuvimos más intentos.
Urna de pulpo mágico
2

Javascript (ES6), 320 294 bytes

(b,p,d,M,S=-2)=>(T=(p,q,r,s)=>b[p][q]==(n=b[r][s|0])&&n!='-',w=0,b.map((r,y)=>(l=r.length-1,m=15,r.map((c,x)=>(m&=8*T(l-x,x,l)+4*T(x,x,0)+2*T(x,y,0,y)+T(y,x,y))),w|=m)),w?-1:(b.map((r,y)=>r.map((c,x)=>S<1&&c=='-'&&(r[x]='O.X'[p+1],(s=-f(b,-p,1))>S&&(S=s,M=[x,y]),r[x]=c))),S=S+2?S:0,d?S:[M,S]))

Entrada

1) Un conjunto de caracteres que describe el tablero actual, como:

[['X', '-'], ['-', 'O']]

2) Un entero que describe el turno actual: 1 = X, -1 =O

Salida

Una matriz hecha de:

  • una matriz que describe el mejor movimiento en [x, y]formato
  • El resultado del juego como un entero: 1 = victoria, -1 = pérdida, 0 = empate

Ejemplo

En el siguiente ejemplo, Xse garantiza que ganará jugando [1, 2].

let f =
(b,p,d,M,S=-2)=>(T=(p,q,r,s)=>b[p][q]==(n=b[r][s|0])&&n!='-',w=0,b.map((r,y)=>(l=r.length-1,m=15,r.map((c,x)=>(m&=8*T(l-x,x,l)+4*T(x,x,0)+2*T(x,y,0,y)+T(y,x,y))),w|=m)),w?-1:(b.map((r,y)=>r.map((c,x)=>S<1&&c=='-'&&(r[x]='O.X'[p+1],(s=-f(b,-p,1))>S&&(S=s,M=[x,y]),r[x]=c))),S=S+2?S:0,d?S:[M,S]))

console.log(JSON.stringify(f(
  [['O','X','O'],
   ['-','-','-'],
   ['-','-','X']],
  1
)));

Un juego extraño. EL ÚNICO MOVIMIENTO GANADOR NO ES JUGAR.
¿Qué tal un buen juego de ajedrez?

Arnauld
fuente
Bien hecho, buena primera entrada. Solo las observaciones que tengo son posibles para guardar bytes con la información dada 'X siempre se moverá primero'. ¿Y has intentado con una placa que no sea 3x3;)?
Urna de pulpo mágico
@carusocomputing: no estoy seguro de entender lo que tiene en mente con 'X siempre se moverá primero'. Podría usarse para deducir qué lado está en movimiento dada la placa solo, pero la computación que realmente costaría más bytes; así que supongo que estás hablando de otra cosa. Responda sí, hice algunas pruebas con tablas un poco más grandes. Eso debería funcionar como se espera mientras ... err ... no haya demasiadas posiciones vacías. :-)
Arnauld
El desafío dice The current state of the board must be the only input to your program. Su código necesita dos entradas, lo que rompe esta regla.
Dada
1
@Dada: me preguntaba sobre eso, pero asumí que el color activo es parte del estado del tablero (al igual que una posición de ajedrez siempre viene con color activo + cuadrado pasante + disponibilidad de enroque). Así que supongo que el OP debería aclarar ese punto. (Y si tienes razón, eso suena como una dificultad adicional innecesaria, en mi humilde opinión).
Arnauld
1
Mmm .. me gusta mucho la explicación del estado del tablero en su respuesta. Pensando en ello, algunos lanagues solo pueden usar cadenas como entrada, tener una placa como XXOOXO-OO sería difícil de descifrar en recuentos de bytes bajos sin información adicional como las dimensiones de la placa. Permitiré cualquier entrada adicional que contribuya al estado de la placa, aunque sigo pensando que la información "suponga que X se mueve primero" es diferente de "dado quién gira". Algunos idiomas se aprovecharán de eso como una suposición;).
Magic Octopus Urn