KOTH asimétrico: Atrapa al gato (hilo del receptor)

17

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 receptor, el hilo del gato 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 11matriz cuadrada en 2d e imitamos el 'comportamiento' hexagonal que el gato solo puede mover en 6 direcciones:

ingrese la descripción de la imagen aquí

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 sea 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 un receptor o un gato, cada uno debe completar cada uno implementar una clase Java (ya hay algunos ejemplos primitivos) y colocarla en elplayers paquete (y actualizar la lista de gatos / receptores en la clase Controlador), pero también puede escribir funciones adicionales dentro de esa clase. El controlador viene con cada dos ejemplos de trabajo de clases simples de gatos / receptores.

El campo es una matriz 11 x 112D intque 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 -1y 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 intmatriz 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 tarda más de 200 ms en 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       191674     8      flawr   
StupidFill        214246     9      flawr
Achilles          76820      6      The E
Agamemnon         74844      5      The E
CloseCatcher      54920      4      randomra
ForwordCatcher    94246      7      MegaTom  
Dijkstra          46500      2      TheNumberOne
HexCatcher        48832      3      randomra
ChoiceCatcher     43828      1      randomra

RandCat           77928      7      flawr
StupidRightCat    81794      6      flawr
SpiralCat         93868      5      CoolGuy
StraightCat       82452      9      CoolGuy
FreeCat           106304     3      randomra
RabidCat          77770      8      cain
Dijkstra's Cat    114670     1      TheNumberOne
MaxCat            97768      4      Manu
ChoiceCat         113356     2      randomra
falla
fuente
¿Qué programa hace las animaciones?
MegaTom
La animación es solo la interfaz gráfica de usuario (al iniciar el controlador, debe establecer configuraciones PRINT_STEPS = truemás detalladas en el archivo MyFrame.java). Luego grabé esto con LICEcap y lo edité con GIMP . Si tiene más preguntas, ¡solo pregunte!
flawr
Si agrega la entrada del usuario al controlador, podría ser un buen software con la GUI y los bots ya escritos. También sería interesante ver cuánto pueden los humanos descifrar / abusar de las estrategias de bot específicas.
randomra
Además, ¿puede mi bot guardar información de la partida anterior para tratar de encontrar una mejor secuencia de movimiento contra el mismo bot? Supongo que no porque mejore cuanto más rondas hagas. También tendría que adivinar si está jugando contra un nuevo bot, por lo que el orden de ejecución también sería importante.
randomra
1
¿Por qué no se ordenan las puntuaciones de los gatos?
Spikatrix

Respuestas:

6

Aquiles

Aquiles no es demasiado brillante, pero es implacablemente eficiente. Primero evita que el gato use la envoltura del tablero, luego divide el tablero en dos. Luego sigue dividiendo la parte del tablero en la que está el gato por la mitad hasta que queda atrapado.

Demostración RandCat vs Aquiles

randcat vs aquiles

package players;
/**
 * @author The E
 */
import main.*;



public class Achilles implements Catcher
{
    public Achilles() {

    }
    @Override
    public String getName() {

        return "Achilles";
    }

    @Override
    public int[] takeTurn(Field f) {
        try{
        if(f.read(0, f.SIZE-1)!=Field.BUCKET)
        {
            //Make the first line

            for(int j = 0; j<f.SIZE; j++)
            {
                if(f.read(0, j) == Field.EMPTY)
                {
                    return new int[]{0,j};
                }
            }
            return WasteGo(f);

        }
        else if (f.read(f.SIZE-1, 0)!=Field.BUCKET)
        {
            //Make the second line
            for(int i = 0; i<f.SIZE; i++)
            {
                if(f.read(i, 0) == Field.EMPTY)
                {
                    return new int[]{i,0};
                }
            }
            //The cat got in the way
            for(int j = 0; j<f.SIZE; j++)
            {
                if(f.read(1, j) == Field.EMPTY)
                {
                    return new int[]{1,j};
                }
            }
            return WasteGo(f);
        }
        else
        {
            return TrapCat(1,1,f.SIZE-1, f.SIZE-1, false, f);

        }
        }
        catch (Exception e)
        {
            return WasteGo(f);
        }
    }
    private int[] TrapCat(int i1, int j1, int i2, int j2, Boolean direction, Field f) {
        for(int a = 0; a<f.SIZE+10; a++)
        {
            if(direction)
            {

                int height = j2-j1+1;
                int row = j1 + height/2;
                for(int i = i1; i<=i2; i++)
                {
                    if(f.read(i, row)==Field.EMPTY)
                    {
                        return new int[]{i,row};
                    }
                }

                    //Done that Row
                    //Find cat
                    if(f.findCat()[1]>row)
                    {
                        //he's above the line
                        j1 = row+1;
                        direction = !direction;
                        //return TrapCat(i1, row+1, i2, j2, !direction, f);
                    }
                    else
                    {
                        //he's below the line
                        j2 = row - 1;
                        direction = !direction;
                        //return TrapCat(i1, j1, i2, row-1, !direction, f);
                    }


            }
            else
            {
                int bredth = i2-i1+1;
                int column = i1 + bredth/2;
                //Continue making the line
                for(int j = j1; j<=j2; j++)
                {
                    if(f.read(column,j)==Field.EMPTY)
                    {
                        return new int[]{column,j};
                    }
                }

                    //Done that Column
                    //Find cat
                    if(f.findCat()[0]>column)
                    {
                        //he's right of the line
                        i1 = column + 1;
                        direction = !direction;
                        //return TrapCat(column+1, j1, i2, j2, !direction, f);
                    }
                    else
                    {
                        //he's left of the line
                        i2 = column -1;
                        direction = !direction;
                        //return TrapCat(i1, j1, column-1, j2, !direction, f);
                    }

            }
        }
        return WasteGo(f);
    }
    private int[] WasteGo(Field f) {
        for (int i = 0; i<f.SIZE;i++)
        {
            for(int j=0;j<f.SIZE;j++)
            {
                if(f.read(i,j)==Field.EMPTY)
                {
                    return new int[]{i,j};
                }
            }
        }
        //Something drastic happened
        return new int[]{0,0};
    }



}
euanjt
fuente
Bueno, ¿cuál es ahora, Aquiles o Héctor? (¿O alguien con un trastorno de identidad disiociativo? =)
error
@flawr Achilles, jaja. Cambié el nombre a mitad de camino (es más apropiado nombrar al receptor Achilles y al gato Hector) pero olvidé cambiar el java: es lo que sucede cuando programa después del té :(
euanjt
Pero Héctor preferiría ser un nombre de perro =) Gracias por su presentación funciona muy bien. Espero que no le importe que también incluya el 'preámbulo' en su código.
falla
Si no hay problema. Héctor suena como el nombre de un perro ...
euanjt
Acabo de ejecutar una simulación (10000 juegos para cada emparejamiento) y Aquiles fue descalificado, debido a StackOverflowError repetido. Creo que la recursión no terminó: pastebin.com/9n6SQQnd
flawr
5

Agamenón

Agamenón divide el área del gato por la mitad con una línea vertical hasta que el gato solo tiene una franja de ancho 2 para moverse, en cuyo punto atrapa al gato.

Agamenón vs RandCat:

ingrese la descripción de la imagen aquí

package players;
/**
 * @author The E
 */
import main.*;



    public class Agamemnon implements Catcher {
        boolean up = true;
        @Override
        public String getName() {
            return "Agamemnon";
        }

        @Override
        public int[] takeTurn(Field f) {
            //First Make Line in column 1
            for(int j = 0; j<f.SIZE; j++)
            {
                if(f.read(0, j)==Field.EMPTY)
                {
                    return new int[]{0,j};
                }
            }
            //Then in column SIZE/2
            for(int j = 0; j<f.SIZE; j++)
            {
                if(f.read(f.SIZE/2, j)==Field.EMPTY)
                {
                    return new int[]{f.SIZE/2,j};
                }
            }
            //Then work out where the cat is
            int left, right;
            int cati = f.findCat()[0];
            if(cati<f.SIZE/2)
            {
                left = 1;
                right = f.SIZE/2-1;
            }
            else
            {
                left = f.SIZE/2+1;
                right = f.SIZE-1;
            }
            while(right-left>1)
            {
                //If the cat is not in a two width column
                //Split the area the cat is in in half
                int middleColumn = (left+right)/2;
                for(int j = 0; j<f.SIZE; j++)
                {
                    if(f.read(middleColumn, j)==Field.EMPTY)
                    {
                        return new int[]{middleColumn,j};
                    }
                }
                //If we got here we had finished that column
                //So update left and/or right
                if(cati<middleColumn)
                {
                    //he's left of the middle Column
                    right = middleColumn - 1;
                }
                else
                {
                    //he's right of the middle Column
                    left = middleColumn+1;
                }
                //Repeat
            }
            //Otherwise try to trap the cat
            //Make a line up and down on the opposite side of the cat
            int catj = f.findCat()[1];
            if(left!=right){
                if(cati==left)
                {
                    if(f.read(right, catj)==Field.EMPTY)
                    {
                        return new int[]{right, catj};
                    }
                    if(f.read(right, catj-1)==Field.EMPTY)
                    {
                        return new int[]{right, catj-1};
                    }
                    if(f.read(right, catj+1)==Field.EMPTY)
                    {
                        return new int[]{right, catj+1};
                    }


                }
                else
                {
                    if(f.read(left, catj)==Field.EMPTY)
                    {
                        return new int[]{left, catj};
                    }
                    if(f.read(left, catj-1)==Field.EMPTY)
                    {
                        return new int[]{left, catj-1};
                    }
                    if(f.read(left, catj+1)==Field.EMPTY)
                    {
                        return new int[]{left, catj+1};
                    }

                }
            }
            //Alternate between above and below
            if(up)
            {
                up = !up;
                if(f.read(cati, catj+1)==Field.EMPTY)
                {

                    return new int[]{cati, catj+1};
                }
            }
            up = !up;
            if(f.read(cati, catj-1)==Field.EMPTY)
            {

                return new int[]{cati, catj-1};
            }
            return WasteGo(f);
        }

        private int[] WasteGo(Field f) {
            for (int i = 0; i<f.SIZE;i++)
            {
                for(int j=0;j<f.SIZE;j++)
                {
                    if(f.read(i,j)==Field.EMPTY)
                    {
                        return new int[]{i,j};
                    }
                }
            }
            //Something drastic happened
            return new int[]{0,0};
        }
    }

Este receptor es mucho mejor que Aquiles y creo que es lo suficientemente diferente como para justificar una nueva respuesta.

euanjt
fuente
Muy buena solución, estaba seguro de que Aquiles estaba cerca del óptimo, pero ahora creo que incluso Agamenón podría mejorarse ligeramente =)
error
Sí, Agamenón tiene un algoritmo de captura de juego final mucho mejor que Aquiles, pero estoy bastante seguro de que hay algunos ajustes ... Ahora intentaré trabajar en un gato :)
euanjt
@flawr Se agregó un ajuste muy pequeño para acelerar la captura en algunos casos especiales, esto no afecta la animación aquí (aunque creo que podría afectar la animación de SpiralCat)
euanjt
¡Pregunta! ¿Qué sucede si estás a punto de cerrar una línea, pero el gato está parado en el último lugar?
Sr. Llama
@ Mr.Llama comienza a hacer la siguiente línea como si esa línea se hubiera llenado (es decir, el gato era en realidad un balde), no es el uso más efectivo de un giro, pero ocurre muy raramente que realmente no importa. cat tiene que alejarse en su próximo turno para que pueda colocar mi cubo allí
euanjt
5

HexCatcher

Si el receptor puede meter al gato dentro de un gran hexágono con 3 unidades de lados donde las esquinas del hexágono ya están ocupadas por cubos, el receptor puede mantener al gato en esta área y atraparlo. El hexágono se ve así:

ingrese la descripción de la imagen aquí

Esto es lo que HexCatcher intenta lograr. Mentaliza el campo con estos grandes hexágonos de manera que cada celda de la esquina sea parte de 3 grandes hexágonos.

Si existe la posibilidad de mantener al gato en el área actual conectando dos esquinas al lado del gato, el bot lo hará. (Por ejemplo, en la imagen si el gato está en 7,5, elegimos 7,6 incluso si solo las celdas 6,6 y 8,5 están ocupadas todavía).

Si lo anterior no es una opción, elegimos jugar en una esquina que es parte del área donde está el gato. Si todas esas esquinas ya están elegidas (como en la imagen), elegimos una celda al lado del gato.

Son posibles múltiples pequeñas mejoras, como manejar mejor la envoltura (el mosaico se rompe allí) o hacer los últimos dos movimientos de manera óptima. Podría hacer algunos de estos. Si no está permitido, lo agregaré (fuera de competencia) a los interesados.

DijkstrasCat vs HexCatcher:

ingrese la descripción de la imagen aquí

package players;
/**
 * @author randomra
 */
import main.Field;

public class HexCatcher implements Catcher {
    public String getName() {
        return "HexCatcher";
    }

    final int[][] o = { { -1, 1 }, { 0, 1 }, { -1, 0 }, { 1, 0 }, { 0, -1 },
            { 1, -1 } };// all valid moves
    final int[][] t = { { -2, 2 }, { 0, 2 }, { -2, 0 }, { 2, 0 }, { 0, -2 },
            { 2, -2 } };// all valid double moves in one direction
    final int[][] h = { { -1, 2 }, { -2, 1 }, { -1, -1 }, { 1, -2 }, { 2, -1 },
            { 1, 1 } };// all valid moves in not one direction
    int opp = 0;

    public int[] takeTurn(Field f) {
        int[] p = f.findCat();
        // center of the hexagon the cat is in
        int[] c = { ((int) p[0] / 3) * 3 + 1, ((int) p[1] / 3) * 3 + 1 };
        // change priority of catching direction at every turn
        opp = 1 - opp;

        // check missing corner piece next to cat
        for (int i = 0; i < 6; i++) {
            int ind = (i + opp * 3) % 6;
            boolean close = false;
            for (int k = 0; k < 6; k++) {
                if (c[0] + h[ind][0] == p[0] + o[k][0]
                        && c[1] + h[ind][1] == p[1] + o[k][1]) {
                    close = true;
                }
            }
            if (f.read(c[0] + h[ind][0], c[1] + h[ind][1]) == 0 && close) {
                return new int[] { c[0] + h[ind][0], c[1] + h[ind][1] };
            }
        }
        // cut off escape route if needed
        for (int i = 0; i < 6; i++) {
            int ind = (i + opp * 3) % 6;
            if (f.read(c[0] + o[ind][0], c[1] + o[ind][1]) == -1
                    && f.read(c[0] + t[ind][0], c[1] + t[ind][1]) == 0) {
                return new int[] { c[0] + t[ind][0], c[1] + t[ind][1] };
            }
        }
        // check any missing corner piece in the area
        for (int i = 0; i < 6; i++) {
            int ind = (i + opp * 3) % 6;
            if (f.read(c[0] + h[ind][0], c[1] + h[ind][1]) == 0) {
                return new int[] { c[0] + h[ind][0], c[1] + h[ind][1] };
            }
        }
        // choose an empty cell next to the cat
        for (int i = 0; i < 6; i++) {
            int ind = (i + opp * 3) % 6;
            if (f.read(p[0] + o[ind][0], p[1] + o[ind][1]) == 0) {
                return new int[] { p[0] + o[ind][0], p[1] + o[ind][1] };
            }
        }
        return null;
    }
}
randomra
fuente
3

CloseCatcher

Elige una de las posiciones donde el gato podría pisar en el siguiente paso. Elige el que daría la mayor cantidad de caminos posibles después de 3 pasos para el gato si se moviera allí y el campo no cambiara.

El código es casi idéntico a mi entrada Cat, FreeCat , que elige la dirección de una manera muy similar.

SpiralCat vs CloseCatcher:

SpiralCat vs CloseCatcher

package players;
/**
 * @author randomra
 */

import main.Field;
import java.util.Arrays;

public class CloseCatcher implements Catcher {
    public String getName() {
        return "CloseCatcher";
    }

    final int[][] turns = { { -1, 1 }, { 0, 1 }, { -1, 0 }, { 1, 0 },
            { 0, -1 }, { 1, -1 } };// all valid moves
    final int turnCheck = 3;

    public int[] takeTurn(Field f) {

        int[] pos = f.findCat();
        int[] bestMove = { 0, 1 };
        int bestMoveCount = -1;
        for (int[] t : turns) {
            int[] currPos = { pos[0] + t[0], pos[1] + t[1] };
            int moveCount = free_count(currPos, turnCheck, f);
            if (moveCount > bestMoveCount) {
                bestMoveCount = moveCount;
                bestMove = t;
            }
        }
        int[] bestPos = { pos[0] + bestMove[0], pos[1] + bestMove[1] };
        return bestPos;
    }

    private int free_count(int[] pos, int turnsLeft, Field f) {
        if (f.isValidPosition(pos) || Arrays.equals(pos, f.findCat())) {
            if (turnsLeft == 0) {
                return 1;
            }
            int routeCount = 0;
            for (int[] t : turns) {
                int[] currPos = { pos[0] + t[0], pos[1] + t[1] };
                int moveCount = free_count(currPos, turnsLeft - 1, f);
                routeCount += moveCount;
            }
            return routeCount;
        }
        return 0;
    }

}
randomra
fuente
Niza +1. CloseCatcher captura fácilmente StraightCat
Spikatrix
3

Dijkstra

No le gustan mucho los gatos (:v{ >

FreeCat vs Dijkstra (necesidades actualizadas) :

ingrese la descripción de la imagen aquí

package players;

import main.Controller;
import main.Field;

import java.util.*;

/**
 * @author TheNumberOne
 *
 * Catches the cat.
 */

public class Dijkstra implements Catcher{

    private static final int[][][] CACHE;

    static {
        CACHE = new int[Controller.FIELD_SIZE][Controller.FIELD_SIZE][2];
        for (int x = 0; x < Controller.FIELD_SIZE; x++){
            for (int y = 0; y < Controller.FIELD_SIZE; y++){
                CACHE[x][y] = new int[]{x,y};
            }
        }
    }

    private static final int[][] possibleMoves = {{-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}};
    @Override
    public String getName() {
        return "Dijkstra";
    }

    @Override
    public int[] takeTurn(Field f) {
        long startTime = System.nanoTime();

        final int[] theCat = f.findCat();
        int[] bestMove = {-1,1};
        int[] bestOpenness = {Integer.MAX_VALUE, 0};
        List<int[]> possiblePositions = new ArrayList<>();
        for (int x = 0; x < 11; x++){
            for (int y = 0; y < 11; y++){
                int[] pos = {x,y};
                if (f.isValidPosition(pos)){
                    possiblePositions.add(pos);
                }
            }
        }
        Collections.sort(possiblePositions, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return distance(o1, theCat) - distance(o2, theCat);
            }
        });
        for (int i = 0; i < possiblePositions.size() && System.nanoTime() - startTime < Controller.MAX_TURN_TIME/2; i++){
            int[] pos = possiblePositions.get(i);
            int before = f.field[pos[0]][pos[1]];
            f.placeBucket(pos);
            int[] openness = openness(theCat, f, true);
            if (openness[0] < bestOpenness[0] ||
                    (openness[0] == bestOpenness[0] &&
                            (openness[1] > bestOpenness[1])
                    )
                    ){
                bestOpenness = openness;
                bestMove = pos;
            }
            f.field[pos[0]][pos[1]] = before;
        }
        return bestMove;
    }


    /**
     *
     * @param pos The pos to calculate the openness of.
     * @param f The field to use.
     * @return Two integers. The first integer represents the number of reachable hexagons.
     * The second integer represents how strung out the squares are relative to the pos.
     */
    public static int[] openness(int[] pos, Field f, boolean catZeroWeight){
        Map<int[], Integer> lengths = new HashMap<>();
        PriorityQueue<int[]> open = new PriorityQueue<>(10,new Comparator<int[]>() {
            Map<int[], Integer> lengths;
            @Override
            public int compare(int[] o1, int[] o2) {
                return lengths.get(o1) - lengths.get(o2);
            }
            public Comparator<int[]> init(Map<int[], Integer> lengths){
                this.lengths = lengths;
                return this;
            }
        }.init(lengths));
        Set<int[]> closed = new HashSet<>();
        lengths.put(pos, catZeroWeight ? 0 : 6 - pointsAround(pos, f).size());
        open.add(pos);
        while (open.size() > 0){
            int[] top = open.remove();
            if (closed.contains(top)){
                continue;
            }
            closed.add(top);
            int l = lengths.get(top);
            List<int[]> pointsAround = pointsAround(top, f);

            for (ListIterator<int[]> iter = pointsAround.listIterator(); iter.hasNext();){
                int[] point = iter.next();
                if (closed.contains(point)){
                    iter.remove();
                }
            }

            for (int[] p : pointsAround){
                int length = l + 7 - pointsAround(p, f).size();
                if (lengths.containsKey(p)){
                    length = Math.min(length, lengths.get(p));
                }
                lengths.put(p, length);
                open.add(p);
            }
        }
        int sum = 0;
        for (int integer : lengths.values()){
            sum += integer;
        }
        return new int[]{lengths.size(),sum};
    }

    public static int distance(int[] p1, int[] p2){
        p2 = Arrays.copyOf(p2, 2);
        while (p2[0] < p1[0]){
            p2[0] += 11;
        }
        while (p2[1] < p2[0]){
            p2[1] += 11;
        }
        int lowestDistance = 0;
        for (int dx = 0; dx == 0; dx -= 11){
            for (int dy = 0; dy == 0; dy -= 11){
                lowestDistance = Math.min(lowestDistance,Math.min(Math.abs(p1[0]-p2[0]-dx),Math.min(Math.abs(p1[1]-p2[1]-dy),Math.abs(p1[0]+p1[1]-p2[0]-dx-p2[1]-dy))));
            }
        }
        return Math.min(Math.abs(p1[0]-p2[0]),Math.min(Math.abs(p1[1]-p2[1]),Math.abs(p1[0]+p1[1]-p2[0]-p2[1])));
    }

    public static int[] normalize(int[] p){
        return CACHE[(p[0]%11+11)%11][(p[1]%11+11)%11];
    }

    public static List<int[]> pointsAround(int[] p, Field f){
        int[] cat = f.findCat();
        List<int[]> locations = new ArrayList<>();
        for (int[] move : possibleMoves){
            int[] location = normalize(new int[]{p[0]+move[0], p[1] + move[1]});
            if (f.isValidPosition(location) || Arrays.equals(cat, location)){
                locations.add(location);
            }
        }
        return locations;
    }
}

Cómo intenta atrapar al gato:

Analiza todos los cuadrados del tablero y trata de encontrar el cuadrado que minimiza la apertura del tablero y maximiza cuánto está tendido el tablero; en relación con el gato. La apertura y la fibrosidad de un tablero se calculan utilizando una modificación de su famoso algoritmo .

Franqueza:

La apertura de un tablero en relación con una posición es el número de posiciones alcanzables desde esa posición.

Stringiness:

La fibrosidad de un tablero en relación con una posición es la suma de las distancias entre las posiciones alcanzables y la posición.

Con la última actualización:

Ahora, es mucho mejor atrapando a FreeCat y a su propio gato todos los gatos. Desafortunadamente, también es mucho peor al atrapar a los locos gatos que no cooperan. Podría mejorarse al detectar si el gato es uno de los locos y luego actuar como CloseCatcher.

Error corregido.

El numero uno
fuente
Puedo confirmar que funciona hasta ahora, pero creo que es el más lento pero uno de los mejores hasta ahora. ¡Necesita 134 segundos para 100 juegos contra RandCat mientras hace un total de solo 4406 movimientos! Creo que tendré que dejar que mi PC funcione durante la noche en uno de los próximos días ... ¿Puede contarnos un poco más sobre cómo funciona?
flawr
@flawr Se agregó una descripción.
TheNumberOne
Aún no funciona para mí. Me da un error: error: cannot infer type arguments for PriorityQueue<>en esta línea PriorityQueue<int[]> open = new PriorityQueue<>(new Comparator<int[]>() {.
Spikatrix
@CoolGuy ¿Estás usando Java 6? Creo que necesitas actualizar tu JDK.
TheNumberOne
@CoolGuy También puedes poner un int[] entre los dos diamantes vacíos después PriorityQueue.
TheNumberOne
2

ForwordCatcher

Coloca un cubo delante del gato, o si se toma, se coloca detrás.

RabidCat vs ForwordCatcher:

RabidCat vs ForwordCatcher:

package players;

import main.Field;
import java.util.Arrays;

public class ForwordCatcher implements Catcher {
    public String getName() {
        return "ForwordCatcher";
    }

    private int[] lastPos = {0,0};

    public int[] takeTurn(Field f) {
        int[] temp = lastPos;
        int[] pos = f.findCat();
        lastPos = pos;
        int[] Move = {pos[0]*2-temp[0], pos[1]*2-temp[1]};
        if(f.isValidPosition(Move)){return Move;}
        if(f.isValidPosition(temp)){return temp;}
        Move[0] = pos[0];Move[1] = pos[1]+1;
        return Move;
    }
}
MegaTom
fuente
1
Hay bastantes errores, lo que me lleva a suponer que no probó su programa. Por favor arregle esos ...
flawr 01 de
@flawr arreglado. Perdón por los errores. No lo probé y mi Java no es demasiado bueno.
MegaTom
Agradable, hasta ahora todo funciona sin problemas, pero todavía no estoy seguro de si siempre producirá movimientos válidos =)
error
1
@flawr El espacio detrás de un gato siempre estará vacío para el receptor :)
TheNumberOne
2

ChoiceCatcher

Utiliza el mismo mecanismo de puntuación que mi entrada ChoiceCat . Hay una pequeña modificación que ayuda a elegir las celdas relevantes en los primeros pasos, ya que a ChoiceCat no le importan los primeros grupos, ya que no los ve como una amenaza.

ChoiceCatcher parece tener un puntaje considerablemente mejor que los receptores actuales.

ChoiceCat vs ChoiceCatcher:

ChoiceCat vs ChoiceCatcher

package players;
/**
 * @author randomra
 */
import java.util.Arrays;

import main.Field;

public class ChoiceCatcher implements Catcher {

    private class Values {
        public final int size;
        private double[][] f;

        Values(int size) {
            this.size = size;
            f = new double[size][size];
        }

        public double read(int[] p) {
            int i = p[0];
            int j = p[1];
            i = (i % size + size) % size;
            j = (j % size + size) % size;
            return f[i][j];
        }

        private double write(int[] p, double v) {
            int i = p[0];
            int j = p[1];
            i = (i % size + size) % size;
            j = (j % size + size) % size;
            return f[i][j] = v;
        }
    }

    final int[][] turns = { { -1, 1 }, { 0, 1 }, { 1, 0 }, { 1, -1 },
            { 0, -1 }, { -1, 0 } };// all valid moves CW order
    final int stepCheck = 5;

    public String getName() {
        return "ChoiceCatcher";
    }

    @Override
    public int[] takeTurn(Field f) {
        int[] bestPos = null;
        double bestPosValue = Double.MAX_VALUE;
        for (int i = 0; i < f.SIZE; i++) {
            for (int j = 0; j < f.SIZE; j++) {
                if (f.read(i, j) == Field.EMPTY) {
                    Field myField = new Field(f);
                    myField.placeBucket(new int[] { i, j });
                    double posValue = catTurnValue(myField);
                    if (posValue < bestPosValue) {
                        bestPosValue = posValue;
                        bestPos = new int[] { i, j };
                    }
                }
            }
        }
        return bestPos;
    }

    private double catTurnValue(Field f) {

        int[] pos = f.findCat();
        double[] values = new double[6];
        int count=0;
        for (int[] t : turns) {
            int[] currPos = { pos[0] + t[0], pos[1] + t[1] };
            double moveValue = movePosValue(currPos, f);
            values[count++]=moveValue;
        }
        Arrays.sort(values);
        return values[5];
    }

    private double movePosValue(int[] pos, Field f) {

        Values v = new Values(f.SIZE);

        for (int ring = stepCheck; ring >= 0; ring--) {
            for (int phase = 0; phase < 2; phase++) {
                for (int sidepos = 0; sidepos < Math.max(1, ring); sidepos++) {
                    for (int side = 0; side < 6; side++) {
                        int[] evalPos = new int[2];
                        for (int coord = 0; coord < 2; coord++) {
                            evalPos[coord] = pos[coord] + turns[side][coord]
                                    * sidepos + turns[(side + 1) % 6][coord]
                                    * (ring - sidepos);
                        }
                        if (phase == 0) {
                            if (ring == stepCheck) {
                                // on outmost ring, init value
                                v.write(evalPos, -1);
                            } else {
                                v.write(evalPos, posValue(evalPos, v, f));
                            }
                        } else {
                            // finalize position value for next turn
                            v.write(evalPos, -v.read(evalPos));
                        }
                    }
                }
            }
        }

        return -v.read(pos);
    }

    private double posValue(int[] pos, Values v, Field f) {
        if (f.read(pos[0], pos[1]) == Field.BUCKET) {
            return 0;
        }
        int count = 0;
        int maxRoutes = 2;
        double[] product = new double[6];
        for (int[] t : turns) {
            int[] tPos = new int[] { pos[0] + t[0], pos[1] + t[1] };
            if (v.read(tPos) > 0) {
                product[count] = 1 - 1 / (v.read(tPos) + 1);
                count++;
            }
        }
        Arrays.sort(product);
        double fp = 1;
        for (int i = 0; i < Math.min(count, maxRoutes); i++) {
            fp *= product[5 - i];
        }
        double fp2 = 1;
        for (int i = 0; i < Math.min(count, 6); i++) {
            fp2 *= product[5 - i];
        }
        double retValue = Math.min(count, maxRoutes) + fp;
        double retValue2 = Math.min(count, 6) + fp2;
        return -retValue - retValue2 / 1000000;
    }

}
randomra
fuente
1

RandCatcher

Esto se hizo solo para probar el controlador y coloca aleatoriamente los cubos (de manera muy ineficiente).

package players;

import main.Field;

public class RandCatcher implements Catcher {
    public String getName(){
        return "RandCatcher";
    }
    public int[] takeTurn(Field f){
        int[] pos = {0,0};
        do {
            pos[0] = (int) (Math.random()*f.SIZE);
            pos[1] = (int) (Math.random()*f.SIZE);
        } while( f.isValidPosition(pos)==false );
        return pos;
    }

}
falla
fuente
1

StupidFillCatcher

Esto se hizo solo para probar el controlador. Simplemente se llena columna por columna hasta que se atrapa al gato.

package players;

import main.Field;

public class StupidFillCatcher implements Catcher {
    public String getName(){
        return "StupidFillCatcher";
    }
    public int[] takeTurn(Field f){
        for(int i=0; i < f.SIZE; i++){
            for(int j=0; j < f.SIZE; j++){
                if(f.isValidPosition(new int[] {i,j})){
                    return new int[] {i,j};
                }
            }
        }
        return new int[] {0,0};
    }

}
falla
fuente