Aquí hay un problema interesante que pensé el otro día, que involucra fragmentos de código que compiten contra otros bits de código no solo en una propiedad que tiene el código, sino al jugar un juego contra esos otros bits de código.
Su tarea es construir un programa que tome el estado actual de un tablero de Go y determine qué movimiento hacer o aprobar.
Su programa aceptará lo siguiente como entrada:
19 líneas, cada una con 19 caracteres, que representan las piezas actualmente en el tablero Go. Un carácter de
0
representa un cuadrado vacío,1
es negro y2
es blanco.Dos números que representan el número de piezas de prisioneros que tiene cada jugador (negro, luego blanco).
Un número que representa a quién le toca moverse (blanco o negro). Como arriba,
1
es negro y2
es blanco.
y generar uno de los siguientes:
Un par de coordenadas que
a b
representan las coordenadas a las cuales moverse.1 1
es el cuadrado superior izquierdo, y los números primero y segundo representan moverse hacia abajo y hacia la derecha respectivamente.La cadena
pass
, que representa un movimiento para pasar.
Por ejemplo, el programa puede recibir la siguiente entrada:
0000000000000000000
0000000000000000000
0000000000000000000
0001000000000002000
0000000000000000000
0000000000000000000
0001210000000000000
0000100000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0002000000000001000
0000000000000000000
0000000000000000000
0000000000000000000
0 0 1
que representa un juego donde solo se han jugado unos pocos movimientos.
Entonces el programa podría salir 6 5
, lo que significa "poner una piedra negra en el sexto punto desde arriba y el quinto desde la izquierda". Esto capturaría la piedra blanca en 7 5
. El estado de la junta luego cambiaría a:
0000000000000000000
0000000000000000000
0000000000000000000
0001000000000002000
0000000000000000000
0000100000000000000
0001010000000000000
0000100000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0002000000000001000
0000000000000000000
0000000000000000000
0000000000000000000
1 0 2
(Tenga en cuenta que aunque se capturó una piedra blanca, cuenta como prisionero para negro).
Su código debe cumplir adicionalmente las siguientes propiedades:
Si su programa tiene el mismo estado de entrada, siempre debe producir la misma salida. Este es el determinismo de Go AI. No debe tener un componente aleatorio.
Su programa no debe tomar más de aproximadamente 60 segundos para determinar qué movimiento hacer. Esta regla no se aplicará estrictamente debido a las variaciones en el poder de cómputo, pero debe hacer un movimiento en un período de tiempo razonable.
El código fuente de su programa no debe exceder un total de 1 megabyte (1,048,576 bytes).
Su programa siempre debe hacer movimientos legales. Su programa no puede hacer un movimiento donde ya existe una piedra, y no puede colocar una pieza que resultaría en la captura de un grupo de sus propias piedras. (Una excepción a las reglas para los propósitos de este desafío es que un programa puede crear una posición que originalmente estaba allí, ya que solo se le da la posición actual de un tablero, no se puede esperar que almacene los movimientos que se han realizado antes de.)
Su envío se jugará en un torneo de todo contra todos los demás envíos, en un juego de Go donde el estado del tablero comienza como vacío, y cada programa se turna para alimentar la posición del tablero y hacer un movimiento. .
Cada par de presentaciones jugará dos rondas, una ronda con cada jugador negro. Debido a que las IA en este problema son completamente deterministas, dos de las mismas IA que juegan juntas siempre darán como resultado exactamente el mismo juego.
Las condiciones para ganar son las siguientes:
Si su programa juega hasta el final del juego, las reglas de puntuación de Go de China se utilizarán para determinar el ganador. No se aplicará komi.
Si su programa juega hasta el punto en que se alcanza un estado anterior, causando así un bucle infinito, los dos programas se declararán vinculados.
Su envío se puntuará según la cantidad de puntos que obtenga frente a otros envíos. Una victoria vale 1 punto, y un empate vale medio punto. La presentación con más puntos es el ganador general.
Este es un desafío del rey de la colina, en el que cualquiera puede publicar una nueva entrada en cualquier momento, y la clasificación se volverá a evaluar periódicamente cuando esto suceda.
fuente
Respuestas:
Aquí está mi entrada para despegar este desafío. Código de Python:
Según sus reglas, siempre jugar "pasar" es una estrategia válida (aunque mala).
fuente
Java: elige un lugar, cualquier lugar
Simplemente elige puntos en el tablero para probar su validez. Utiliza el PRNG, pero con una semilla establecida, así que eso es determinista. Utiliza diferentes fragmentos del ciclo PRNG dependiendo de cuántos turnos hayan pasado.
Para cada posición de candidato, verifica que sea un movimiento válido (pero no que sea un movimiento inteligente ). Si no lo es, pasa al siguiente candidato. Si no puede encontrar un movimiento válido después de 1000 intentos, pasa.
fuente
Algunos Scala:
Al leer Wikipedia, creo que esto superará la solución actual.
fuente
1 1
ypass
).1 1
, en realidad, ya que el programa siempre se ejecuta de nuevo cada vez que el tablero cambia.Java
Elige el primer espacio vacío. Gana contra cualquiera de las IA al momento de la publicación.
fuente
1 1
sería capturada por el blanco (ahora vacío) y no podría ser jugada por el negro en el siguiente turno.