Juega un juego perfecto de 4x4 Hex

10

Antecedentes

Hex es un juego de estrategia abstracta para dos jugadores que se juega en un K×Krombo de fichas hexagonales. Dos lados opuestos del rombo son de color blanco, y los otros dos negros, y los dos jugadores, blanco y negro, se turnan para colocar una ficha de su color en una ficha desocupada. El jugador que primero logra construir un camino entre los lados opuestos de su color es el ganador. Se sabe que el juego no puede terminar en un empate, y que el primer jugador tiene una estrategia ganadora sin importar el tamaño del tablero (ver la página de Wikipedia para más detalles).

La tarea

En este desafío, fijamos el tamaño del tablero en K = 4y representamos el tablero como la siguiente cuadrícula. Las líneas gruesas denotan fichas adyacentes.

Una cuadrícula de 4x4.

Su tarea es producir una estrategia ganadora para el primer jugador, que puede elegir para ser negro o blanco. Esto significa que cualesquiera movimientos legales que haga el jugador contrario, su juego debe resultar en una victoria. Su entrada es una posición de juego (la disposición de fichas en el tablero), y su salida es un movimiento legal, en el formato especificado a continuación. Si quieres encontrar una estrategia ganadora tú mismo, no leas este spoiler:

Esquema de una posible estrategia ganadora, suponiendo que las blancas vayan primero. Primero seleccione 5. Después de eso, si tiene una ruta desde 5 hasta la fila inferior O el negro selecciona 0 o 1 en cualquier punto, responda seleccionando el 0 o 1 que esté vacante. Si el negro selecciona 9 o 13, seleccione 10 y luego cualquiera de los 14 o 15 está vacante. Si el negro no selecciona 9, 13 o 14, entonces seleccione 9 y el siguiente, el 13 o 14 está vacante. Si el negro selecciona 14, responda seleccionando 15. A continuación, seleccione 10 si está vacante; si las negras seleccionan 10, responda con 11. Si las negras seleccionan 6, responda con 7, y luego lo que sea 2 o 3 esté vacante. Si el negro no selecciona 6, selecciónelo, de modo que tenga una ruta desde 5 hasta la fila inferior.

Entrada y salida

Su entrada es una cadena de 16 caracteres WBE, que significa blanco, negro y vacío. Representan los mosaicos del tablero, como se enumeró anteriormente. Puede elegir el método de entrada (que también determina su método de salida) entre los siguientes:

  1. Entrada de STDIN, salida a STDOUT.
  2. Entrada como un argumento de línea de comando, salida a STDOUT.
  3. Ingrese como 16 argumentos de línea de comando de un solo carácter, salida a STDOUT.
  4. Entrada como argumento de función nombrada, salida como valor de retorno.

Su salida representa el mosaico en el que coloca su próxima ficha, ya que es su turno de moverse. Puede elegir entre los siguientes formatos de salida:

  1. Un índice de base cero (como se usa en la imagen de arriba).
  2. Un índice de una base.
  3. La cadena de entrada con una Ereemplazada por la que elija Wo Bpara su reproductor.

Reglas

Tu estrategia debe ser determinista. No es necesario que manejes correctamente las posiciones de juego que son inalcanzables desde el tablero vacío usando tu estrategia, o las posiciones que ya están ganando para cualquiera de los jugadores, y puedes chocar contra ellas. Por el contrario, en los tableros a los que se puede acceder utilizando su estrategia, debe devolver un movimiento legal.

Este es el código de golf, por lo que gana el conteo de bytes más bajo. Las lagunas estándar no están permitidas.

Pruebas

He escrito un controlador Python 3 para validar entradas, ya que sería extremadamente tedioso hacerlo a mano. Lo puedes encontrar aquí . Admite los primeros tres formatos de entrada y las funciones de Python 3 (las funciones en otros idiomas deben incluirse en los programas), los tres formatos de salida y ambos reproductores. Si una estrategia no está ganando, generará un juego perdedor que encontró, para que pueda modificar su programa.

Zgarb
fuente
Este desafío me recuerda a tratar de comprimir una IA de tic tac toe cuando estaba escribiendo programas de calculadora. ticalc.org/archives/files/fileinfo/354/35408.html
Sparr
2
Incorrect response 'WWWWWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.Debería haber ganado hace mucho tiempo, ¿o me equivoco?
Sebastian Höffner
@ SebastianHöffner Eso parece un error en el controlador. Intentaré arreglarlo cuando tenga tiempo.
Zgarb
@ SebastianHöffner El error ahora debería corregirse.
Zgarb

Respuestas:

6

Marbelous, 973b

Esta es una implementación ingenua de la estrategia insinuada en la pregunta. Espera que el tablero se proporcione como 16 parámetros de línea de comandos / placa base como hex.mbl B W E E E W E E E B E E E E E Ey generará la posición de índice cero del próximo movimiento de las blancas.

00 }1 }0
&G B? W!
&0 &G &G
!!
00 }0 }1
&H B? W!
&1 &H &H
!!
.. }D .. }9 }9 }D }E }A }D }9 }A .. }E }F }5
}9 B! }E E? W? E? .. E? B? B? W? .. E? .. E?
B! ?0 B! &M &N &O E? &I \\ .. &J .. &K E? &5
?0 ++ ?0 &9 .. &D &P &A &I /\ &J .. &E &L !!
++ .. ++ !! .. !! &E !! \/ &L /\ &K !! &F
\\ .. // .. .. .. !! .. .. \/ .. \/ .. !!
.. =3 \/
&M /\ &N
\/ &O /\ &P
}0 }1 }6 .. }6 .. }7 &7 }2 }3 }A }A }B }E }F
..
..
..
..
..
..
..
..
..
.. .. .. .. .. .. .. .. .. .. .. .. .. B? W!
.. .. .. .. .. .. .. .. .. .. .. .. .. &Q &Q
.. .. .. .. B? .. E? W? E? .. E? B? E? &F \/
.. .. .. &S /\ &T &S &T &U E? &A &R &R !!
.. .. .. &7 .. .. \/ .. &2 &V !! &B \/
.. .. .. !! .. .. &U /\ &V &3 .. !!
.. .. .. .. .. .. .. .. .. !!
.. .. ..
.. .. E?
E? .. &6
&X E? !!
!! &Y
.. !!
}4 }8 }C
\/ \/ \/
30 30 31 31 32 33 35 36 37 39 31 30 31 31 31 33 31 34 31 35
&0 &X &1 &Y &2 &3 &5 &6 &7 &9 &A &A &B &B &D &D &E &E &F &F
:W?
}0
^4
=1
{0
:B?
}0
^0
=0
{0
:E?
}0
^1
=0
{0
:W!
}0
^4
=0
{0
:B!
}0
^0
>0
{0

Creo que probablemente pueda jugar unos 200 caracteres con una mejor ramificación y eliminación de la reutilización del código.

Sparr
fuente
Agregué la opción para el argumento de la línea de comandos 16 y actualicé el script del verificador, para que esta solución se pueda probar.
Zgarb
Marbelous +1 (PPCG cree que agregar estos caracteres mejoró el comentario)
Rohan Jhunjhunwala
1

Python 3, 100b

b=input()
i=b.find('B')
if b[i]in'BW'and'E'in b:i-=1+(b[i-1]is'W')*4
print((b[:i]+'B'+b[i+1:])[:16])
  • Jugador: NEGRO
  • Método: STDIN / STDOUT, MODIFIED_BOARD

La estrategia es buscar primero un Ben el tablero. Si no hay ninguno, esto devuelve -1, que en python es el mismo que last index. Por lo tanto, en un tablero vacío, mi primer índice será index=-1, que es donde empiezo a moverme.

Si el campo a mi izquierda ( index-1) está libre, mi próximo movimiento va allí. Si se toma, subo a la izquierda. Nunca tengo que subir: si lo hago, pierdo el ritmo y perderé el juego.

En una pensión completa (no en ningún Elado) no hago ningún movimiento.

Al printprincipio parece un poco extraño: tengo que construir el nuevo tablero (que hago a través de un corte) pero luego necesito cortar 16 caracteres. Esto es una reliquia ya que trabajo con índices negativos y b[i+1:], por lo tanto, devolveré el tablero de agujeros y el resto que espero, por lo que es importante cortar el resto. Otra forma hubiera sido trabajar con índices positivos, por ejemplo (b.find('B')+16)%16, tomando , pero (+16)%16es un byte más que ()[:16].

Sin golf:

board = input()
index = board.find('B')
if board[index] in 'BW' and 'E' in board:
    index -= 1 + (board[index-1] is 'W') * 4
print((board[:index] + 'B' + board[index+1:])[:16])

Prueba

Al ejecutar la suite de prueba del controlador hexadecimal, encontré un comportamiento extraño:

OUT: EEEEEEEEEEEEEEEB
OUT: WEEEEEEEEEEEEEBB
OUT: WWEEEEEEEEEEEBBB
OUT: WWWEEEEEEEEEBBBB
OUT: WWWWEEEEEEEBBBBB
OUT: WWWWWEEEEEBBBBBB
OUT: WWWWWWEEEBBBBBBB
OUT: WWWWWWWEBBBBBBBB
OUT: WWWWWWWWBBBBBBBB

Incorrect response 'WWWWWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.

Creo que debería haber ganado después del cuarto turno o responder con el mismo tablero a un tablero completo debería ser una respuesta correcta. No estoy seguro de lo que sale mal, no profundicé mucho más, solo quería comprobar si cubría todos los casos "especiales". Pero como no tengo que encubrir situaciones en las que alguien comienza en el espacio 4, no importa de todos modos.

85b

Sin embargo, si me permito no comprobar si hay una placa completa (es decir, omitirla, 'E' in bpuedo simplificar aún más el código para usar solo 85 bytes:

b=input();i=b.find('B')
if i!=-1:i-=1+(b[i-1]is'W')*4
print((b[:i]+'B'+b[i+1:])[:16])

Sin embargo, esto llevará a lo siguiente:

Incorrect response 'WWWBWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.

Esto podría o no contarse, y como descubrí que no era un movimiento válido, decidí ir por la respuesta más larga pero más correcta.

Sebastian Höffner
fuente