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)

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.

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

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?}