KOTH asimétrico: atrapa al gato
ACTUALIZACIÓN : Los archivos gist se actualizan (incluidas las nuevas sumisiones) ya que Controller.java no detectó Excepciones (solo errores). Ahora detecta errores y excepciones y también los imprime.
Este desafío consta de dos hilos, este es el hilo del gato, el hilo del receptor se puede encontrar aquí .
El controlador se puede descargar aquí. .
Este es un KOTH asimétrico: cada presentación es un gato o un receptor . Hay juegos entre cada par de cada un gato y un receptor. Los gatos y los receptores tienen clasificaciones separadas.
Receptor
Hay un gato en una cuadrícula hexagonal. Su tarea es atraparlo lo más rápido posible. Cada turno, puede colocar un cubo de agua en una celda de la rejilla para evitar que el gato pueda ir allí. Pero el gato no es (tal vez) tan tonto, y cada vez que coloca un cubo, el gato se moverá a otra celda de la cuadrícula. Como la cuadrícula es hexagonal, el gato puede ir en 6 direcciones diferentes. Su objetivo es rodear al gato con cubos de agua, cuanto más rápido mejor.
Gato
Sabes que el receptor quiere atraparte colocando cubos de agua a tu alrededor. Por supuesto que tratas de evadir, pero como eres un gato perezoso (como lo son los gatos) exactamente das un paso a la vez. Esto significa que no puede permanecer en el mismo lugar que usted, pero debe moverse a uno de los seis lugares circundantes. Cada vez que veas que el receptor colocó un nuevo cubo de agua, vas a otra celda. Por supuesto, intenta evadir el mayor tiempo posible.
Cuadrícula
La cuadrícula es hexagonal, pero como no tenemos estructuras de datos hexagonales, tomamos una 11 x 11
matriz cuadrada en 2d e imitamos el 'comportamiento' hexagonal que el gato solo puede mover en 6 direcciones:
La topología es toroidal, eso significa que si pisa una celda 'fuera' de la matriz, simplemente será transferido a la celda correspondiente en el otro lado de la matriz.
Juego
El gato comienza en la posición dada en la cuadrícula. El receptor puede hacer el primer movimiento, luego el gato y su receptor se mueven alternativamente hasta que el gato es atrapado. El número de pasos es la puntuación para ese juego. El gato intenta obtener una puntuación lo más alta posible, el receptor intenta obtener una puntuación lo más baja posible. La suma promedio de todos los juegos en los que participó será el puntaje de su presentación. Hay dos clasificaciones separadas, una para el gato y otra para los receptores.
Controlador
El controlador dado está escrito en Java. Como catcher o cat, cada uno tiene que completar cada uno implementar una clase Java (ya hay algunos ejemplos primitivos) y colocarla en elplayers
paquete (y actualizar la lista de gatos / catchers en la clase Controller), pero también puede escribir funciones adicionales dentro de esa clase. El controlador viene con cada dos ejemplos funcionales de clases simples de gatos / receptores.
El campo es una matriz 11 x 11
2D int
que almacena los valores de los estados actuales de las celdas. Si una celda está vacía, tiene valor 0
, si hay un gato tiene valor -1
y si hay un depósito hay un 1
.
Hay algunas funciones que puede usar: isValidMove()
/isValidPosition()
son para verificar si su movimiento (cat) / posición (catcher) es válido.
Cada vez que es tu turno, takeTurn()
se llama a tu función . El argumento contiene una copia de la cuadrícula actual y tiene métodos como read(i,j)
para leer la celda (i,j)
, así comoisValidMove()/ isValidPosition()
que verifica la validez de su respuesta. Esto también gestiona el ajuste de la topología toroidal, lo que significa que incluso si la cuadrícula es solo 11 x 11, aún puede acceder a la celda (-5,13).
El método debe devolver una int
matriz de dos elementos, que representan posibles movimientos. Para los gatos, estos son los {-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}
que representan la posición relativa de dónde quiere ir el gato, y los receptores devuelven las coordenadas absolutas de dónde quieren colocar un balde {i,j}
.
Si su método produce un movimiento no válido, su envío será descalificado. El movimiento se considera no válido, si en su destino ya hay un cubo o el movimiento no está permitido / el destino ya está ocupado (como un gato), o si ya hay un cubo / gato (como un receptor). Puede verificar eso de antemano con las funciones dadas.
Su envío debe funcionar razonablemente rápido. Si su método demora más de 200 ms para cada paso, también será descalificado. (Preferiblemente mucho menos ...)
Los programas pueden almacenar información entre los pasos.
Envíos
- Puede realizar tantos envíos como desee.
- No modifique significativamente las presentaciones que ya ha enviado.
- Por favor, cada presentación en una nueva respuesta.
- Cada presentación debe tener preferiblemente su nombre único.
- La presentación debe consistir en el código de su clase, así como una descripción que nos diga cómo funciona su presentación.
- Puede escribir la línea
<!-- language: lang-java -->
antes de su código fuente para obtener un resaltado automático de sintaxis.
Puntuación
Todos los gatos competirán contra todos los receptores el mismo número de veces. Intentaré actualizar los puntajes actuales con frecuencia, los ganadores se determinarán cuando la actividad haya disminuido.
Este desafío está inspirado en este viejo juego flash
Gracias @PhiNotPi por probar y dar algunos comentarios constructivos.
Puntajes actuales (100 juegos por emparejamiento)
Name Score Rank Author
RandCatcher 191962 8 flawr
StupidFill 212688 9 flawr
Achilles 77214 6 The E
Agamemnon 74896 5 The E
CloseCatcher 54776 4 randomra
ForwordCatcher 93814 7 MegaTom
Dijkstra 47558 2 TheNumberOne
HexCatcher 48644 3 randomra
ChoiceCatcher 43834 1 randomra
RandCat 77490 9 flawr
StupidRightCat 81566 6 flawr
SpiralCat 93384 5 CoolGuy
StraightCat 80930 7 CoolGuy
FreeCat 106294 3 randomra
RabidCat 78616 8 cain
Dijkstra's Cat 115094 1 TheNumberOne
MaxCat 98400 4 Manu
ChoiceCat 113612 2 randomra
main.Controller
, llamengetCatchers()
y simulen / saboteen las respuestas de los receptores a través de sustakeTurn
métodos?Respuestas:
FreeCat
Elige el movimiento que le daría la mayor cantidad de caminos posibles después de 3 pasos si el campo no cambiara.
FreeCat vs Aquiles:
fuente
Gato de Dijkstra
Aprendió y aplica el algoritmo maestro de su maestro. Tenga en cuenta que depende de algunos de los métodos en la clase de su receptor correspondiente.
Dijkstra's Cat vs Hexcatcher (necesita actualizarse):
Cómo trabaja:
Intenta encontrar el movimiento que minimiza la fibrosidad del tablero en relación con él mismo. Para obtener más información, consulte la publicación del receptor correspondiente.
Con actualización:
Ahora evita las extrañas formas geométricas que a veces forman los cubos de agua.
fuente
MaxCat
Intenté implementar el algoritmo Minimax. Sin embargo, no funciona muy bien debido al tiempo limitado.Editar: ahora usa subprocesos múltiples, pero (al menos en mi computadora) no puedo establecer la profundidad más. De lo contrario, se produce un tiempo de espera. Usando una PC con 6 o más núcleos, esta presentación sería mucho mejor :)
MaxCat vs Dijkstra:
fuente
Field
público el constructor . Lamento no haber actualizado los archivos todavía, ¡pero lo discutimos antes!SpiralCat
Se mueve en espiral. Eso
SpiralCat vs Agamenón:
fuente
turns[i]
paraturns[i%6]
evitar fuera de los límites (que NO debería ocurrir en esta situación).turns[i%6]
? Quiero decir,takeTurn
no se llamará si el gato está bloqueado, ¿verdad?i>=6
nunca debería suceder.RabidCat
RabidCat tiene hidrofobia, por lo que le tiene miedo a los baldes de agua. Encuentra el más cercano y corre en la dirección opuesta.
RabidCat vs ForwordCatcher:
fuente
ChoiceCat
Para cada posible nueva posición de gato, verificamos su bondad y elegimos la mejor. La bondad es la función de las dos mejores celdas vecinas que están más lejos de la posición del gato que la posición cuyo puntaje calculamos. Usamos solo dos celdas porque una puede ser bloqueada y el gato solo necesita una más para escapar. Nuestra función prefiere dos celdas bastante buenas que una grande y una mala. Las posiciones con cubos tienen una puntuación de 0 y las celdas libres más lejanas tienen una puntuación de 1.
ChoiceCat parece tener una mejor puntuación que los gatos actuales.
ChoiceCat vs ChoiceCatcher:
fuente
StupidRightCat
Esto se hizo solo para probar el controlador. El gato se mueve hacia la derecha siempre que sea posible, de lo contrario se mueve en una dirección aleatoria.
fuente
RandCat
Esto se hizo solo para probar el controlador. El gato solo se mueve al azar.
fuente
StraightCat
Este gato se mueve derecho.
Al principio, elige una dirección aleatoria y sigue moviéndose en esta dirección hasta que no pueda, en cuyo caso, cambia la dirección en sentido horario a la siguiente dirección válida y repite este proceso.
StraightCat vs Agamenón:
fuente