KOTH asimétrico: atrapa al gato (hilo de gato)

14

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 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 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 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 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
falla
fuente
1
Creo que este tipo de desafío es para lo que sirve la etiqueta de policías y ladrones.
SuperJedi224
44
@flawr Estaría a favor de extender la etiqueta CnR a todos los desafíos que involucran dos sub-desafíos adversarios (y usar tanto eso como KotH como etiquetas en esto). El wiki de la etiqueta CnR está muy influenciado por los primeros desafíos que tuvimos en ese género. (Además, tienes a los policías y ladrones al revés.;))
Martin Ender
1
¿Qué impide que los gatos importen main.Controller, llamen getCatchers()y simulen / saboteen las respuestas de los receptores a través de sus takeTurnmétodos?
LegionMammal978
12
@ LegionMammal978 Deportividad.
Martin Ender
2
@feersum ¿ ayuda esto ? (Los puntos negros (resp. Azules) representan la misma celda.)
falla

Respuestas:

5

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:

FreeCat vs Achilles

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

import java.util.Arrays;

import main.Field;

public class FreeCat implements Cat {

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

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

    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;
            }
        }
        return bestMove;
    }

    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
3

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):

ingrese la descripción de la imagen aquí

package players;

import main.Field;
import players.Dijkstra; //Not needed import. Should already be available.

/**
 * @author TheNumberOne
 *
 * Escapes from the catcher.
 * Uses Dijkstras methods.
 */

public class DijkstrasCat implements Cat{

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

    @Override
    public int[] takeTurn(Field f) {
        int[] me = f.findCat();
        int[] bestMove = {-1,1};
        int bestOpenness = Integer.MAX_VALUE;
        for (int[] move : possibleMoves){
            int[] newPos = Dijkstra.normalize(new int[]{me[0]+move[0],me[1]+move[1]});
            if (!f.isValidMove(move)){
                continue;
            }
            int openness = Dijkstra.openness(newPos, f, true)[1];
            if (openness < bestOpenness || (openness == bestOpenness && Math.random() < .5)){
                bestOpenness = openness;
                bestMove = move;
            }
        }
        return bestMove;
    }
}

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.

El numero uno
fuente
3

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:

MaxCat vs Dijkstra

package players;

import java.util.ArrayList;
import java.util.List;

import main.Field;

public class MaxCat implements Cat {
    final int[][] turns = { { -1, 1 }, { 0, 1 }, { -1, 0 }, { 1, 0 }, { 0, -1 }, { 1, -1 } };

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

    public int[] takeTurn(Field f) {
        List<CatThread> threads = new ArrayList<>();
        int[] pos = f.findCat();
        for (int[] turn : turns) {
            if(f.read(pos[0]+turn[0], pos[1]+turn[1]) == Field.EMPTY){
                CatThread thread = new CatThread();
                thread.bestMove = turn;
                thread.field = new Field(f);
                thread.start();
                threads.add(thread);
            }
        }
        for (CatThread thread : threads) {
            try {
                thread.join();
            } catch (InterruptedException e) {}
        }
        int best = Integer.MIN_VALUE;
        int[] bestMove = { -1, 1 };
        for (CatThread thread : threads) {
            if (thread.score > best) {
                best = thread.score;
                bestMove = thread.bestMove;
            }
        }
        return bestMove;
    }

    class CatThread extends Thread {
        private Field field;
        private int[] bestMove;
        private int score;
        private final int DEPTH = 3;

        @Override
        public void run() {
            score = max(DEPTH, Integer.MIN_VALUE, Integer.MAX_VALUE);       
        }

        int max(int depth, int alpha, int beta) {
            int pos[] = field.findCat();
            if (depth == 0 || field.isFinished()) {
                int moveCount = 0;
                for (int[] turn : turns) {
                    if(field.read(pos[0]+turn[0], pos[1]+turn[1]) == Field.EMPTY)
                        moveCount++;
                }
                return DEPTH-depth + moveCount;
            }
            int maxValue = alpha;
            for (int[] turn : turns) {
                if(field.read(pos[0]+turn[0], pos[1]+turn[1]) == Field.EMPTY) {
                    field.executeMove(turn);
                    int value = min(depth-1, maxValue, beta);
                    field.executeMove(new int[]{-turn[0], -turn[1]});
                    if (value > maxValue) {
                        maxValue = value;
                        if (maxValue >= beta)
                            break;
                    }
                }
            }
            return maxValue;
        }

        int min(int depth, int alpha, int beta) {
            if (depth == 0 || field.isFinished()) {
                int moveCount = 0;
                for (int[] turn : turns) {
                    int pos[] = field.findCat();
                    if(field.read(pos[0]+turn[0], pos[1]+turn[1]) == Field.EMPTY)
                        moveCount++;
                }   
                return -depth - moveCount;
            }
            int[][] f = field.field;
            int minValue = beta;
            List<int[]> moves = generateBucketMoves();
            for (int[] move : moves) {
                f[move[0]][move[1]] = Field.BUCKET;
                int value = max(depth-1, alpha, minValue);
                f[move[0]][move[1]] = Field.EMPTY;
                if (value < minValue) {
                    minValue = value;
                    if (minValue <= alpha)
                        break;
                }
            }
            return minValue;
        }

        private List<int[]> generateBucketMoves() {
            int[][] f = field.field;
            List<int[]> list = new ArrayList<>();
            for (int i = 0; i < f.length; i++) {
                for (int j = 0; j < f[i].length; j++) {
                    if (f[i][j] == Field.EMPTY) {
                        list.add(new int[]{i,j});
                    }
                }
            }
            return list;
        }
    }
}
CommonGuy
fuente
En realidad puedes hacer Fieldpúblico el constructor . Lamento no haber actualizado los archivos todavía, ¡pero lo discutimos antes!
flawr
@flawr Oh genial, gracias!
CommonGuy
2

SpiralCat

Se mueve en espiral. Eso

  • Intenta moverse al círculo superior izquierdo
  • Si no es posible, intenta moverse al círculo superior derecho
  • Si no es posible, intenta moverse al círculo derecho
  • Si no es posible, intenta moverse al círculo inferior derecho
  • Si no es posible, intenta moverse al círculo inferior izquierdo

SpiralCat vs Agamenón:

SpiralCat vs Agamenón

package players;
/**
 * @author Cool Guy
 */

import main.Field;

public class SpiralCat implements Cat{
    public String getName(){
        return "SpiralCat";
    }
    public int[] takeTurn(Field f){
        int[][] turns = {{-1,1},{0,1},{1,0},{1,-1},{0,-1},{-1,0}};//all valid moves
        int[] move;
        int i = -1;
        do {
            i++;
            move = turns[i];
        } while(f.isValidMove(move) == false);
        return move;
    }
}
Spikatrix
fuente
¿Sabes qué errores has encontrado? Lo único que cambiaría sería alterar turns[i]para turns[i%6]evitar fuera de los límites (que NO debería ocurrir en esta situación).
falla
@flawr, maldita sea. Mala elección de palabras. Quise decir que este gato no es muy inteligente. A veces, este gato simplemente alterna entre el círculo superior izquierdo y el círculo inferior derecho, incluso cuando hay una salida ...
Spikatrix
@flawr, ¿tengo que usar turns[i%6]? Quiero decir, takeTurnno se llamará si el gato está bloqueado, ¿verdad?
Spikatrix
No, pensé que querías decir que encontraste un error en el programa, así que estaba buscando posibles razones. Pero tienes razón, obviamente (si todo está correcto) i>=6nunca debería suceder.
flawr 01 de
2

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:

rabidcat_vs_forwordcatcher

package players;

import java.util.Random;

import main.Field;

/**
* Run away from water buckets
* @author cain
*
*/

public class RabidCat implements Cat {

public RabidCat() {
}

@Override
public String getName() {
    return "RabidCat";
}

@Override
public int[] takeTurn(Field f) {
    int[][] directions = {{-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}};

    //where am I?
    int[] position = {0,0};
    for(int i = 0; i < 12; i++){
        for(int j = 0; j < 12; j++){
            if(f.read(i,j) == -1){
                position[0] = i;
                position[1] = j;
            }
        }
    }

    //Find the closest water
    int direction = 0;
    for(int d = 0; d < 10; d++){
        if(f.read(position[0] + d, position[1] - d) == 1 && f.isValidMove(directions[0])){
            direction = 1;
            break;
        }
        if(f.read(position[0], position[1] - d) == 1 && f.isValidMove(directions[1])){
            direction = 2;
            break;
        }
        if(f.read(position[0] + d, position[1]) == 1 && f.isValidMove(directions[2])){
            direction = 3;
            break;
        }
        if(f.read(position[0] - d, position[1]) == 1 && f.isValidMove(directions[3])){
            direction = 4;
            break;
        }
        if(f.read(position[0], position[1] + d) == 1 && f.isValidMove(directions[4])){
            direction = 5;
            break;
        }
        if(f.read(position[0] - d, position[1] + d) == 1 && f.isValidMove(directions[5])){
            direction = 6;
            break;
        }
    }

    //If there is no water near, wander
    while(direction == 0){
        Random rand = new Random();
        direction = rand.nextInt(6) + 1;
        if(!f.isValidMove(directions[direction - 1])){
            direction = 0;
        }
    }
    return directions[direction - 1];
}

}
Caín
fuente
Wow, realmente queda destrozado por CloseCatcher sin embargo
Cain
2

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:

ChoiceCat vs ChoiceCatcher

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

import main.Field;

public class ChoiceCat implements Cat {

    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 "ChoiceCat";
    }

    public int[] takeTurn(Field f) {

        int[] pos = f.findCat();
        int[] bestMove = { 0, 1 };
        double bestMoveValue = -1;
        for (int[] t : turns) {
            int[] currPos = { pos[0] + t[0], pos[1] + t[1] };
            double moveValue = movePosValue(currPos, f);
            if (moveValue > bestMoveValue) {
                bestMoveValue = moveValue;
                bestMove = t;
            }
        }
        return bestMove;
    }

    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;
        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,2); i++) {
            fp *= product[5-i];
        }
        double retValue = Math.min(count,2) + fp;
        return -retValue;
    }
}
randomra
fuente
1

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.

package players;

import main.Field;

public class StupidRightCat implements Cat{
    public String getName(){
        return "StupidRightCat";
    }
    public int[] takeTurn(Field f){
        int[][] turns = {{-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}};//all valid moves
        int[] move;

        if(f.isValidMove(turns[3])){
            return turns[3];
        } else {
            do {
                move = turns[(int) (turns.length * Math.random())];
            } while(f.isValidMove(move)==false);
            return move;//chose one at random
        }
    }
}
falla
fuente
1

RandCat

Esto se hizo solo para probar el controlador. El gato solo se mueve al azar.

package players;

import main.Field;

public class RandCat implements Cat{
    public String getName(){
        return "RandCat";
    }
    public int[] takeTurn(Field f){
        int[][] turns = {{-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}};//all valid moves
        int[] move;
        do {
            move = turns[(int) (turns.length * Math.random())];
        } while(f.isValidMove(move)==false);
        return move;//chose one at random
    }
}
falla
fuente
1

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:

StraightCat vs Agamenón

package players;
/**
 * @author Cool Guy
 */

import main.Field;

public class StraightCat implements Cat{

    int lastDirection = -1; //Holds the last direction the cat moved
    public String getName(){
        return "StraightCat";
    }
    public int[] takeTurn(Field f){
        int[][] turns = {{-1,1},{0,1},{1,0},{1,-1},{0,-1},{-1,0}};//all valid moves

        if(lastDirection == -1)
          lastDirection = (int) (turns.length * Math.random());

        int[] move = turns[lastDirection];
        int i = lastDirection;

        while(true)
        {
            if(f.isValidMove(move))
                break;
            i = (i+1)%6;
            lastDirection = i;
            move = turns[i];
        }
        return move;
    }
}
Spikatrix
fuente