NOTA: Este desafío está muerto actualmente, ya que no puedo instalar los idiomas necesarios para ejecutar una coincidencia. Si alguien más tiene el tiempo y el interés para hacerlo, no me opongo.
Vea la parte inferior de la publicación para una tabla de clasificación
Este es un desafío semi-cooperativo del rey de la colina, donde los bots construyen caminos a través de un gráfico de cuadrícula bidimensional. El bot que controla los nodos con más tráfico es el ganador. Sin embargo, se necesitan más de un recurso de bot para construir una ruta de conexión, por lo que los bots tendrán que trabajar juntos, hasta cierto punto.
Jugabilidad
A continuación, se indica N > 0
el número de bots en juego.
La cuadrícula
El juego se juega en una cuadrícula de tamaño entero bidimensional , cuya coordenada inferior izquierda está en . Cada coordenada con tiene bordes salientes a las tres coordenadas , y por encima de ella, donde las coordenadas x se toman módulo . Esto significa que la cuadrícula se envuelve en los bordes este y oeste. Cada coordenada inferior es una fuente , y cada coordenada superior es un sumidero .⌊4/3N2⌋ × ⌊4/3N2⌋
(0,0)
(x,y)
0 ≤ y < ⌊4/3N2⌋-1
(x-1,y+1)
(x,y+1)
(x+1,y+1)
x
⌊4/3N2⌋
(x,0)
(x,⌊4/3N2⌋-1)
La siguiente imagen muestra una 8 × 8
cuadrícula.
Cada vértice del gráfico está inactivo , activo o roto . Todos los vértices comienzan inactivos, y pueden ser activados por bots, que luego serán sus dueños. Además, los bots pueden romper vértices y no pueden repararse.
Orden de giro
Un turno consiste en una fase de destrucción y una fase de activación . En la fase de destrucción, cada bot puede romper un vértice inactivo. Ese vértice se rompe desde entonces y no puede ser activado por nadie. En la fase de activación, cada bot puede activar un vértice inactivo. A partir de ese momento, poseen ese vértice y nadie más puede reactivarlo. Varios bots pueden poseer un solo vértice, si todos lo activan en el mismo turno. En cada fase, las selecciones de vértices se realizan simultáneamente.
Tanteo
Una ronda dura exactamente turnos. Después de esto, la ronda se puntúa de la siguiente manera. Desde cada vértice fuente activo, realizamos una búsqueda aleatoria de profundidad primero a lo largo de los vértices activos (lo que significa que los hijos de cada vértice se visitan en un orden aleatorio). Si se encuentra una ruta desde la fuente hasta un sumidero, entonces, para todos los vértices a lo largo de esa ruta, cada propietario del vértice obtiene un punto.N2
N
El juego completo dura 100 rondas, y el bot con más puntos en general es el ganador. Puedo aumentar este número, si la varianza de los puntajes es demasiado alta.
Reglas Adicionales
- No te metas con el controlador u otras presentaciones.
- Como máximo una presentación por concursante.
- Ningún recurso externo, excepto un archivo de texto privado, se limpió al comienzo del juego.
- No diseñes tu bot para vencer o apoyar a oponentes específicos.
- Proporcione comandos para compilar y ejecutar su bot. Cualquier compilador / intérprete que esté disponible gratuitamente para Debian Linux es aceptable.
El controlador
El controlador está escrito en Python 3 y se puede encontrar en GitHub . Consulte el archivo README para obtener instrucciones detalladas. Aquí hay una API para comenzar:
- Los bots se inician al comienzo de cada ronda y persisten hasta el final de la ronda. Se comunican con el controlador a través de STDIN y STDOUT, utilizando mensajes terminados en nueva línea.
BEGIN [num-of-bots] [num-of-turns] [side-length]
es entrada al principio.DESTROY [turn]
es entrada al comienzo de cada fase de destrucción. Su bot responderá conVERTEX x,y
elegir un vértice oNONE
.BROKEN [turn] [your-choice] [other-choices]
es entrada al final de cada fase de destrucción. El orden de los otros bots se aleatoriza al comienzo de cada juego, pero permanece fijo durante el mismo. Las opciones se presentan comox,y
oN
.ACTIVATE [turn]
yOWNED [turn] [your-choice] [other-choices]
son los equivalentes de lo anterior para la fase de activación, y tienen la misma semántica.SCORE [your-score] [other-scores]
es entrada al final del juego.- Su bot tiene 1 segundo para analizar los resultados de una fase y elegir el siguiente vértice, y 1 segundo para abandonar después de obtener la puntuación. Probaré las presentaciones en mi computadora portátil relativamente vieja, por lo que es mejor dejar un margen aquí.
Recuerde lavar su búfer de salida.No hacerlo puede colgar el controlador en algunos entornos.
Tabla de clasificación
Actualizado 13/03/2015
Peacemaker está en funcionamiento y Funnelweb también recibió una actualización. Los puntajes aumentaron en un orden de magnitud. El conector excedió el límite de tiempo en dos juegos.
Funnelweb: 30911
Connector: 18431
Watermelon: 3488
Annoyance: 1552
Explorer: 735
Checkpoint: 720
Random Builder: 535
FaucetBot: 236
Peacemaker: 80
El registro completo con gráficos artísticos ASCII se puede encontrar en el repositorio del controlador, en graphical_log.txt
.
Algunas observaciones
- El conector se puede detener fácilmente rompiendo un solo vértice frente a él. Sospecho que la molestia con frecuencia hace esto. Sin embargo, actualmente tiene poco sentido porque solo Connector puede construir una ruta.
- La sandía puede obtener una puntuación decente simplemente por estar en una ruta de conexión (ya que es muy probable que el DFS use sus vértices).
- A Explorer le gusta cultivar vides de las sandías.
- El Funnelweb actualizado obtiene puntajes realmente buenos, ya que Connector generalmente se engancha en la mitad inferior de la cuadrícula.
- Los juegos se están haciendo bastante largos, la ronda promedio toma alrededor de 25 segundos en mi máquina.
4/3*N^2
, e incluso allí, los bots tuvieron problemas para formar rutas válidas. Sin embargo, Connector fue descalificado temporalmente debido a un error, y ahora que se ha solucionado, espero que los juegos sean más interesantes. Correré otro lote esta noche.Respuestas:
Conector (Java)
Intenta crear una ruta en una posición aleatoria. Debido a que no puede crear una ruta por sí solo, busca celdas activas y las usa. El crédito va a Geobits, de quien robé un código. Además, este envío aún no ha finalizado, ya que simplemente deja de hacer nada tan pronto como se construye la ruta.
Editar: si se crea una ruta, Connector intenta crear varias rutas a lo largo de la existente.
fuente
java.lang.ArrayIndexOutOfBoundsException: -1 at Connector.findExtendingPathPoint(Connector.java:166)
.Funnelweb, Python 2
versión 1.2 - Mejor código de unión, nueva animación agregada
Lleva el nombre de una de las arañas menos amigables de Australia. Este bot primero construye un nido en forma de embudo en las filas superiores, luego atrae a otros bots a crear caminos para el tráfico hacia el nido.
Aquí hay una nueva animación de un juego de 6 bots en un tablero 4 / 3N ^ 2 que muestra el embudo y algunos bots más simples:
El código Python de funnelweb:
La araña se ejecuta con
python funnelweb.py
.fuente
Punto de control, Java
Este bot intenta crear puntos de control para que cualquier ruta válida pase por uno de mis vértices. Dado que hay N 2 vueltas y el tablero tiene 2N 2 de ancho, puedo activar / romper cada nodo en una sola línea horizontal (suponiendo que esté allí primero). Haga esto en un patrón alterno (
x
está roto,o
es mío):Si desea hacer un camino, debe pasar por mis puntos de control :)
Ahora, hay varios problemas que esto podría enfrentar. Primero, no le irá muy bien a menos que haya muchos caminos. Como él mismo no hace ningún camino productivo, realmente depende totalmente de que haya algunos competidores. Incluso un par de competidores que se combinan para hacer un solo camino no ayudarán mucho, ya que solo obtiene un lugar por cada camino encontrado. Lo que necesita para brillar es probablemente unos cuantos bots que hacen bastantes caminos diferentes. Incluso entonces, podría no tener una puntuación muy alta, pero fue una idea que tuve en el chat, así que ...
Si uno de los espacios en la línea ya está bloqueado / reclamado, solo busco un lugar cercano que pueda usar (preferiblemente en la misma
x
línea, simplemente desplazado verticalmente).Para compilar, es
javac Checkpoint.java
. Para ejecutar,java Checkpoint
. Querrá agregar / cambiar la ruta para reflejar donde sea que esté.fuente
Sandía, Java
Intenta dibujar sandías en la cuadrícula.
fuente
FaucetBot (en R)
Crea un cuello de botella en la segunda línea y activa nodos en la ruta detrás de ella.
Si no me equivoqué, la configuración final debería ser algo como:
Comando es
Rscript FaucetBot.R
.fuente
Pacificador, Java
Basado en el código de Manu.
Peacemaker busca zonas de conflicto (es decir, la mayoría de la concentración de vértices ROTOS o ACTIVOS) y activa un vértice aleatorio cercano.
fuente
while
bucle delactivate
método. Detiene la búsqueda una vez que encuentra un vértice que no es suyo ni está roto, pero podría ser propiedad de otra persona, por lo que no puede activarlo.Generador aleatorio, Python 3
Este es un estúpido ejemplo de bot que nunca destruye nada e intenta activar un vértice aleatorio cada turno. Tenga en cuenta que no es necesario verificar si el vértice está inactivo; el controlador se encarga de eso.
Corre con el comando
Es posible que tenga que sustituir
python3
porpython
dependiendo de su instalación de Python. Para hacer esto, solo edite elbots.txt
archivo. Actualicé el controlador, y ya no hay necesidad de meterse con las rutas de archivo.fuente
sys.stdout.flush()
hacerlo, solo puedes hacerloflush=True
como argumento paraprint
.Explorer, Python 3
Estrategia de activación:
Crea un mapa de calor basado en el estado de cada nodo (activo / inactivo / roto) y elige el nodo que tendría el mayor valor de mapa de calor esperado por persona si eligiera ese.
Estrategia de destrucción:
Nunca destruye nada, ya que eso no ayuda mucho al bot.
fuente
Molestia, Bash
Intenté hacer que el resultado se vea más interesante.
Corre con
bash annoyance.sh
.fuente
Hombre medio
Vi que algunos robots se construyeron desde arriba y otros desde abajo. Este es el primero (creo) que comienza en el medio y sube y baja.
(no se prueba con el controlador, por lo que si la dosis no funciona, avíseme).
fuente