KOTH asymétrique: Attrapez le chat

MISE À JOUR : Les fichiers gist sont mis à jour (y compris les nouvelles submisisons) car Controller.java n'a pas détecté d'exceptions (seulement des erreurs). Il détecte désormais les erreurs et exceptions et les imprime également.

Ce défi consiste en deux threads, c'est le thread cat, le thread catcher peut être trouvé ici .

Le contrôleur peut être téléchargé ici .

Il s'agit d'un KOTH asymétrique: chaque soumission est soit un chat, soit un receveur . Il y a des jeux entre chaque paire de chacun un chat et un receveur. Les chats et les attrapeurs ont des classements séparés.

Catcher

Il y a un chat sur une grille hexagonale. Votre tâche consiste à l'attraper le plus rapidement possible. À chaque tour, vous pouvez placer un seau d'eau sur une cellule de la grille afin d'empêcher le chat d'y aller. Mais le chat n'est pas (peut-être) aussi stupide, et chaque fois que vous placez un seau, le chat se déplace vers une autre cellule de la grille. La grille étant hexagonale, le chat peut aller dans 6 directions différentes. Votre objectif est d'entourer le chat de seaux d'eau, le plus vite sera le mieux.

Chat

Vous savez que le receveur veut vous attraper en plaçant des seaux d'eau autour de vous. Bien sûr, vous essayez de vous soustraire, mais comme vous êtes un chat paresseux (comme les chats), vous faites exactement un pas à la fois. Cela signifie que vous ne pouvez pas rester au même endroit que vous, mais vous devez vous déplacer vers l'un des six endroits environnants. Chaque fois que vous voyez que le receveur a placé un nouveau seau d'eau, vous allez dans une autre cellule. Bien sûr, vous essayez d'éviter le plus longtemps possible.

la grille

La grille est hexagonale, mais comme nous n'avons pas de structures de données hexagonales, nous prenons un 11 x 11tableau carré 2d et imitons le `` comportement '' hexagonal que le chat ne peut déplacer que dans 6 directions:

La topologie est toroïdale, ce qui signifie que si vous marchez sur une cellule «à l'extérieur» de la matrice, vous serez simplement transféré vers la cellule correspondante de l'autre côté de la matrice.

Jeu

Le chat commence à une position donnée dans la grille. Le receveur peut effectuer le premier mouvement, puis le chat et son receveur alternent les mouvements jusqu'à ce que le chat soit attrapé. Le nombre de pas est le score de ce match. Le chat essaie d'obtenir un score aussi élevé que possible, le receveur essaie d'obtenir un score aussi bas que possible. La somme moyenne de tous les jeux auxquels vous avez participé sera le score de votre soumission. Il y a deux classements distincts, un pour le chat, un pour les attrapeurs.

Manette

Le contrôleur donné est écrit en Java. En tant que receveur ou chat, vous devez chacun implémenter une classe Java (il existe déjà quelques exemples primitifs) et la placer dans le playerspackage (et mettre à jour la liste des chats / catchers dans la classe Controller), mais vous pouvez également écrire fonctions supplémentaires au sein de cette classe. Le contrôleur est livré avec chacun deux exemples pratiques de classes simples chats / catcher.

Le champ est un tableau 11 x 112D intqui stocke les valeurs des états actuels des cellules. Si une cellule est vide, elle a de la valeur 0, s'il y a un chat, elle a de la valeur -1et s'il y a un seau, il y en a un 1.

Il y a quelques fonctions données que vous pouvez utiliser: isValidMove()/ isValidPosition()sont pour vérifier si votre mouvement (chat) / position (receveur) est valide.

Chaque fois que c'est votre tour, votre fonction takeTurn()est appelée. L'argument contient une copie de la grille actuelle et des méthodes telles read(i,j)que la lecture de la cellule (i,j), ainsi isValidMove()/ isValidPosition()que la vérification de la validité de votre réponse. Cela gère également le recouvrement de la topologie toroïdale, ce qui signifie que même si la grille n'est que de 11 x 11, vous pouvez toujours accéder à la cellule (-5,13).

La méthode doit renvoyer un inttableau de deux éléments, qui représentent des mouvements possibles. Pour les chats, ce sont ceux {-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}qui représentent la position relative de l'endroit où le chat veut aller, et les capteurs renvoient les coordonnées absolues de l'endroit où ils veulent placer un seau {i,j}.

Si votre méthode produit un mouvement invalide, votre soumission sera disqualifiée. Le déplacement est considéré comme invalide, si à votre destination est déjà un seau ou le déplacement n'est pas autorisé / destination déjà occupée (comme un chat), ou s'il y a déjà un seau / chat (comme un receveur). Vous pouvez vérifier cela à l'avance avec les fonctions données.

Votre soumission devrait fonctionner assez rapidement. Si votre méthode dure plus de 200 ms pour chaque étape, elle sera également disqualifiée. (De préférence beaucoup moins ...)

Les programmes sont autorisés à stocker des informations entre les étapes.

Soumissions

• Vous pouvez faire autant de soumissions que vous le souhaitez.
• Veuillez ne pas modifier de manière significative les soumissions que vous avez déjà soumises.
• Veuillez chaque soumission dans une nouvelle réponse.
• Chaque soumission doit de préférence avoir son nom unique.
• La soumission doit comprendre le code de votre classe ainsi qu'une description qui nous indique comment fonctionne votre soumission.
• Vous pouvez écrire la ligne <!-- language: lang-java -->avant votre code source afin d'obtenir une coloration syntaxique automatique.

Notation

Tous les chats rivaliseront avec tous les attrapeurs le même nombre de fois. J'essaierai de mettre à jour fréquemment les scores actuels, les gagnants seront déterminés lorsque l'activité aura diminué.

Ce défi est inspiré de ce vieux jeu flash

Merci @PhiNotPi pour les tests et les commentaires constructifs.

Scores actuels (100 matchs par paire)

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

FreeCat

Choisit le mouvement qui lui donnerait le plus de chemins possibles après 3 étapes si le champ ne changeait pas.

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

Le chat de Dijkstra

Il a appris et applique l'algorithme maître de son maître. Notez qu'il dépend de certaines des méthodes de sa classe de receveur correspondante.

Cat vs Hexcatcher de Dijkstra (besoins mis à jour):

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

Comment il travaille:

Il essaie de trouver le mouvement qui minimise la rigidité de la planche par rapport à lui-même. Pour plus d'informations, consultez l'article correspondant du receveur.

Avec mise à jour:

Il évite désormais les formes géométriques étranges que les seaux d'eau forment parfois.

MaxCat

J'ai essayé d'implémenter l'algorithme Minimax. Cependant, il ne fonctionne pas très bien en raison du temps limité. Edit: Il utilise maintenant le multithreading, mais (au moins sur mon ordinateur), je ne peux pas régler la profondeur plus haut. Sinon, un délai d'attente se produit. En utilisant un PC avec 6 cœurs ou plus, cette soumission serait bien meilleure :)

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

SpiralCat

Bouge en spirale. Il

• Tente de se déplacer vers le cercle supérieur gauche
• Si ce n'est pas possible, essaie de se déplacer vers le cercle supérieur droit
• Si ce n'est pas possible, essaie de se déplacer vers le cercle de droite
• Si ce n'est pas possible, essaie de se déplacer vers le cercle en bas à droite
• Si ce n'est pas possible, essaie de se déplacer vers le cercle en bas à gauche

SpiralCat vs Agamemnon:

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

RabidCat

RabidCat souffre d'hydrophobie, il a donc peur des seaux d'eau. Il trouve le plus proche et court dans la direction opposée.

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];
}

}

ChoiceCat

Pour chaque nouvelle position de chat possible, nous vérifions sa qualité et choisissons la meilleure. La bonté est la fonction des deux meilleures cellules voisines qui sont plus éloignées de la position du chat que la position dont nous calculons le score. Nous n'utilisons que deux cellules car une peut être bloquée et le chat n'a besoin que d'une autre pour s'enfuir. Notre fonction préfère deux cellules plutôt bonnes qu'une grande et une mauvaise. Les positions avec des seaux ont un score de 0 et les cellules libres les plus éloignées ont un score de 1.

ChoiceCat semble mieux marquer que les chats actuels.

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

StupidRightCat

Cela a été fait juste pour tester le contrôleur. Le chat se déplace à droite autant que possible, sinon se déplace dans une direction aléatoire.

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
        }
    }
}

RandCat

Cela a été fait juste pour tester le contrôleur. Le chat se déplace simplement au hasard.

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
    }
}

StraightCat

Ce chat se déplace tout droit.

Au début, il choisit une direction aléatoire et continue de se déplacer dans cette direction jusqu'à ce qu'il ne puisse pas dans ce cas, il déplace la direction dans le sens des aiguilles d'une montre vers la prochaine direction valide et répète ce processus.

StraightCat vs Agamemnon:

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