Asymetryczny KOTH: Catch the Cat

AKTUALIZACJA : Pliki gist są aktualizowane (w tym nowe zgłoszenia), ponieważ plik Controller.java nie wychwytuje wyjątków (tylko błędy). Przechwytuje teraz błędy i wyjątki, a także je drukuje.

To wyzwanie składa się z dwóch wątków, to jest wątek kota, wątek łapacza można znaleźć tutaj .

Kontroler można pobrać tutaj .

Jest to asymetryczna KOTH: Każde zgłoszenie dotyczy kota lub łapacza . Istnieją gry między każdą parą każdego kota i łapacza. Koty i łapacze mają osobne rankingi.

Łapacz

Na sześciokątnej siatce jest kot. Twoim zadaniem jest złapanie go tak szybko, jak to możliwe. W każdej turze możesz postawić wiadro z wodą na jednej komórce siatki, aby kot nie mógł się tam dostać. Ale kot nie jest (może) głupi i za każdym razem, gdy umieścisz wiadro, kot przeniesie się do innej komórki siatki. Ponieważ siatka jest sześciokątna, kot może iść w 6 różnych kierunkach. Twoim celem jest otoczenie kota wiadrami z wodą, im szybciej, tym lepiej.

Kot

Wiesz, że łapacz chce cię złapać, umieszczając wokół ciebie wiadra z wodą. Oczywiście próbujesz uniknąć, ale ponieważ jesteś leniwym kotem (tak jak koty), robisz dokładnie jeden krok naraz. Oznacza to, że nie możesz pozostać w tym samym miejscu, co ty, ale musisz przenieść się do jednego z sześciu okolicznych miejsc. Ilekroć zobaczysz, że łapacz umieścił nowe wiadro z wodą, idziesz do innej celi. Oczywiście starasz się unikać tak długo, jak to możliwe.

Krata

Siatka jest sześciokątna, ale ponieważ nie mamy heksagonalnych struktur danych, bierzemy 11 x 11kwadratową tablicę 2d i naśladujemy sześciokątne „zachowanie”, które kot może poruszać się tylko w 6 kierunkach:

Topologia jest toroidalna, co oznacza, że ​​jeśli wejdziesz na komórkę „na zewnątrz” tablicy, zostaniesz po prostu przeniesiony do odpowiedniej komórki po drugiej stronie tablicy.

Gra

Kot zaczyna od określonej pozycji na siatce. Łapacz może wykonać pierwszy ruch, następnie kot i jego łapacz wykonują naprzemienne ruchy, dopóki kot nie zostanie złapany. Liczba kroków to wynik tej gry. Kot stara się uzyskać jak najlepszy wynik, łapacz stara się uzyskać jak najniższy wynik. Średnia suma wszystkich gier, w których uczestniczyłeś, będzie wynikiem twojego zgłoszenia. Istnieją dwa osobne rankingi, jeden dla kota, drugi dla łapaczy.

Kontroler

Dany kontroler jest napisany w Javie. Jako catcher lub cat każdy z was musi w pełni zaimplementować klasę Java (są już pewne prymitywne przykłady) i umieścić ją w playerspakiecie (i zaktualizować listę kotów / catchers w klasie Controller), ale można także napisać dodatkowe funkcje w tej klasie. Do kontrolera dołączone są dwa robocze przykłady prostych klas cat / catcher.

Pole to tablica 11 x 112D intprzechowująca wartości bieżących stanów komórek. Jeśli komórka jest pusta, ma wartość 0, jeśli jest kot, ma wartość, -1a jeśli jest wiadro, to jest 1.

Istnieje kilka podanych funkcji, których możesz użyć: isValidMove()/ isValidPosition()służą do sprawdzania, czy twój ruch (kot) / pozycja (łapacz) jest prawidłowy.

Za każdym razem, gdy jest twoja kolej, twoja funkcja takeTurn()jest wywoływana. Argument zawiera kopię bieżącej siatki i ma metody takie jak read(i,j)czytanie komórki w (i,j), a także isValidMove()/ isValidPosition()sprawdza poprawność odpowiedzi. To również zarządza zawijaniem toroidalnej topologii, co oznacza, że ​​nawet jeśli siatka ma tylko 11 x 11, nadal możesz uzyskać dostęp do komórki (-5,13).

Metoda powinna zwrócić inttablicę dwóch elementów, które reprezentują możliwe ruchy. Dla kotów {-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}reprezentują one względną pozycję, w której kot chce iść, a łapacze zwracają bezwzględne współrzędne miejsca, w którym chcą umieścić wiadro {i,j}.

Jeśli Twoja metoda spowoduje nieprawidłowy ruch, zgłoszenie zostanie zdyskwalifikowane. Ruch uważa się za nieważny, jeśli w miejscu docelowym znajduje się już wiadro lub ruch jest niedozwolony / miejsce docelowe jest już zajęte (jako kot) lub jeśli jest już wiadro / kot (jako łapacz). Możesz to wcześniej sprawdzić za pomocą podanych funkcji.

Twoje zgłoszenie powinno działać dość szybko. Jeśli twoja metoda trwa dłużej niż 200 ms dla każdego kroku, zostanie również zdyskwalifikowana. (Najlepiej znacznie mniej ...)

Programy mogą przechowywać informacje między krokami.

Zgłoszenia

• Możesz przesłać dowolną liczbę zgłoszeń.
• Nie zmieniaj znacząco przesłanych już zgłoszeń.
• Proszę o każde zgłoszenie w nowej odpowiedzi.
• Każde zgłoszenie powinno mieć swoją unikalną nazwę.
• Zgłoszenie powinno składać się z kodu twojej klasy oraz opisu, który mówi nam, jak działa zgłoszenie.
• Możesz napisać wiersz <!-- language: lang-java -->przed kodem źródłowym, aby uzyskać automatyczne podświetlanie składni.

Punktacja

Wszystkie koty będą rywalizować ze wszystkimi łapaczami tyle samo razy. Spróbuję często aktualizować bieżące wyniki, zwycięzcy zostaną wyłonieni, gdy aktywność spadnie.

To wyzwanie jest inspirowane starą grą flash

Dzięki @PhiNotPi za testowanie i udzielenie konstruktywnej opinii.

Aktualne wyniki (100 gier na parę)

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

Wybiera ruch, który zapewniłby mu możliwie najwięcej ścieżek po 3 krokach, gdyby pole nie uległo zmianie.

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

Kot Dijkstry

Nauczył się i stosuje główny algorytm swojego mistrza. Zauważ, że jest on zależny od niektórych metod w swojej odpowiedniej klasie łapacza.

Dijkstra's Cat vs Hexcatcher (wymaga aktualizacji):

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

Jak on działa:

Próbuje znaleźć ruch, który minimalizuje rygorystyczność planszy w stosunku do siebie. Aby uzyskać więcej informacji, zobacz odpowiedni post łapacza.

Z aktualizacją:

Teraz unika dziwnych geometrycznych kształtów, które czasami tworzą wiadra z wodą.

MaxCat

Próbowałem zaimplementować algorytm Minimax. Jednak nie działa bardzo dobrze z powodu ograniczonego czasu. Edycja: Teraz używa wielowątkowości, ale (przynajmniej na moim komputerze) nie mogę ustawić głębi. W przeciwnym razie nastąpi przekroczenie limitu czasu. Przy użyciu komputera z 6 lub więcej rdzeniami przesyłanie byłoby znacznie lepsze :)

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

Porusza się spiralnie. To

• Próbuje przejść do lewego górnego koła
• Jeśli nie jest to możliwe, próbuje przejść do prawego górnego koła
• Jeśli nie jest to możliwe, próbuje przejść do prawego okręgu
• Jeśli nie jest to możliwe, próbuje przejść do prawego dolnego koła
• Jeśli nie jest to możliwe, próbuje przejść do lewego dolnego okręgu

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 ma hydrofobię, więc boi się wiader z wodą. Znajduje najbliższy i biegnie w przeciwnym kierunku.

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

Dla każdej możliwej nowej pozycji kota sprawdzamy jego dobroć i wybieramy najlepszą. Dobroć jest funkcją dwóch najlepszych sąsiadujących komórek, które są dalej od pozycji kota niż pozycja, której wynik obliczamy. Używamy tylko dwóch komórek, ponieważ jedną można zablokować, a kot potrzebuje tylko jednej, aby uciec. Nasza funkcja preferuje dwie dość dobre komórki niż jedną wielką i jedną złą. Pozycje z segmentami mają wynik 0, a najdalsze wolne komórki mają wynik 1.

ChoiceCat wydaje się osiągać lepsze wyniki niż obecne koty.

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

Zostało to wykonane tylko do testowania kontrolera. Kot porusza się w prawo, gdy tylko jest to możliwe, w przeciwnym razie porusza się w losowym kierunku.

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

Zostało to wykonane tylko do testowania kontrolera. Kot po prostu porusza się losowo.

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

Ten kot porusza się prosto.

Na początku wybiera losowy kierunek i porusza się w tym kierunku, dopóki nie może, w takim przypadku przesuwa kierunek zgodnie z ruchem wskazówek zegara do następnego prawidłowego kierunku i powtarza ten proces.

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