Antecedentes
Hex es un juego de estrategia abstracta para dos jugadores que se juega en un K×K
rombo 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 = 4
y representamos el tablero como la siguiente cuadrícula. Las líneas gruesas denotan fichas adyacentes.
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:
- Entrada de STDIN, salida a STDOUT.
- Entrada como un argumento de línea de comando, salida a STDOUT.
- Ingrese como 16 argumentos de línea de comando de un solo carácter, salida a STDOUT.
- 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:
- Un índice de base cero (como se usa en la imagen de arriba).
- Un índice de una base.
- La cadena de entrada con una
E
reemplazada por la que elijaW
oB
para 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.
Incorrect response 'WWWWWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.
Debería haber ganado hace mucho tiempo, ¿o me equivoco?Respuestas:
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 E
y generará la posición de índice cero del próximo movimiento de las blancas.Creo que probablemente pueda jugar unos 200 caracteres con una mejor ramificación y eliminación de la reutilización del código.
fuente
Python 3, 100b
La estrategia es buscar primero un
B
en el tablero. Si no hay ninguno, esto devuelve-1
, que en python es el mismo quelast 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
E
lado) no hago ningún movimiento.Al
print
principio 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 yb[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)%16
es un byte más que()[:16]
.Sin golf:
Prueba
Al ejecutar la suite de prueba del controlador hexadecimal, encontré un comportamiento extraño:
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 b
puedo simplificar aún más el código para usar solo 85 bytes:Sin embargo, esto llevará a lo siguiente:
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.
fuente