Asymetryczny KOTH: Catch the Cat (Catcher Thread)

17

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 łapacza, można znaleźć wątek kota tutaj .

Kontroler można pobrać tutaj .

Jest to asymetryczna KOTH: Każde poddanie jest albo kotem 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 umieścić wiadro z wodą na jednej komórce siatki, aby kot nie mógł tam dotrzeć. 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 komórki. 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:

wprowadź opis zdjęcia tutaj

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 łapacz lub kot, każdy z was musi w pełni zaimplementować klasę Java (istnieją już pewne prymitywne przykłady) i umieścić ją w playerspakiecie (i zaktualizować listę kotów / łapaczy 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 topologii toroidalnej, 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. W przypadku 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, Twoje 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 istnieje 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       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
wada
źródło
Jaki program tworzy animacje?
MegaTom
Animacja to tylko GUI (przy uruchamianiu kontrolera należy ustawić PRINT_STEPS = truebardziej szczegółowe ustawienia w pliku MyFrame.java). Potem nagrałem to za pomocą LICEcap i zredagowałem za pomocą GIMP . Jeśli masz dodatkowe pytania, po prostu zapytaj!
flawr
Jeśli dodasz dane wejściowe użytkownika do kontrolera, może stworzyć fajne oprogramowanie z GUI i botami już napisanymi. Byłoby również interesujące zobaczyć, jak bardzo ludzie mogą złamać / nadużyć określonych strategii botów.
randomra
Czy mój bot może zachować informacje z poprzedniego meczu, aby znaleźć lepszą sekwencję ruchów przeciwko temu samemu botowi? Przypuszczam, że nie, ponieważ im więcej rund zrobisz, tym lepiej. Musiałby również zgadywać, czy gra przeciwko nowemu botowi, więc kolejność działania również miałaby znaczenie.
randomra
1
Dlaczego wyniki kotów są nieporządane?
Spikatrix

Odpowiedzi:

6

Achilles

Achilles nie jest zbyt bystry, ale jest bezwzględnie skuteczny. Najpierw powstrzymuje kota od używania owijania deski, a następnie dzieli deskę na dwie części. Następnie dzieli część deski, na którą kot jest w połowie, dopóki kot nie zostanie uwięziony.

Demonstracja RandCat vs Achilles

randcat vs achilles

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
źródło
Który to teraz jest, Achilles czy Hector? (Lub ktoś z dysocjacyjnym zaburzeniem tożsamości? =)
błąd
@flawr Achilles, lol Zmieniłem nazwę w połowie (lepiej nazwać łapacza Achillesa i kota Hectora), ale zapomniałem zmienić java - tak się dzieje, gdy programujesz po herbacie :(
euanjt
Ale Hector wolałby być psim imieniem =) Dzięki za zgłoszenie działa świetnie. Mam nadzieję, że nie masz nic przeciwko temu, że dołączam również „preambułę” do twojego kodu.
flawr
Tak, nie ma problemu. Hector brzmi jak imię psa ...
euanjt
Właśnie uruchomiłem symulację (10000 gier dla każdej pary) i Achilles został zdyskwalifikowany z powodu powtarzającego się błędu StackOverflowError. Myślę, że rekurencja się nie zakończyła: pastebin.com/9n6SQQnd
flawr
5

Agamemnon

Agamemnon dzieli obszar kota na pół pionową linią, aż kot ma tylko pasek o szerokości 2, w którym może się poruszać, w którym to momencie uwięził kota.

Agamemnon vs RandCat:

wprowadź opis zdjęcia tutaj

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

Ten łapacz jest konsekwentnie lepszy niż Achilles i myślę, że jest na tyle inny, że uzasadnia nową odpowiedź.

euanjt
źródło
Bardzo fajne rozwiązanie, byłem pewien, że Achilles był bliski optymalności, ale teraz myślę, że nawet Agamemnon można by nieco poprawić =)
wada
Tak, Agamemnon ma znacznie lepszy algorytm wychwytywania gier końcowych niż Achilles, ale jestem pewien, że są pewne poprawki ... Teraz spróbuję pracować nad kotem :)
euanjt
@flawr bardzo drobna poprawka dodana w celu przyspieszenia łapania w niektórych specjalnych przypadkach, nie wpływa to na animację tutaj (choć myślę, że może to wpłynąć na animację
SpiralCat
Pytanie! Co się stanie, jeśli masz zamiar zamknąć linię, ale kot stoi w ostatnim miejscu?
Pan Llama,
@ Mr.Lama zaczyna robić następną linię, jakby ta linia była wypełniona (tj. Kot był w rzeczywistości wiadrem) - nie jest to najbardziej efektywne użycie tury, ale zdarza się bardzo rzadko, że to nie ma znaczenia - kot musi odejść w następnym zakręcie, abym mógł tam postawić wiadro
euanjt
5

HexCatcher

Jeśli łapacz może wprowadzić kota do wnętrza dużego sześciokąta z 3 jednostkowymi bokami, w których narożniki sześciokąta są już zajęte przez wiadra, łapacz może zatrzymać kota w tym obszarze i złapać go. Sześciokąt wygląda następująco:

wprowadź opis zdjęcia tutaj

To właśnie próbuje osiągnąć HexCatcher. Mentalnie układa pole tymi dużymi sześciokątami w taki sposób, że każda komórka narożna jest częścią 3 dużych sześciokątów.

Jeśli istnieje szansa na utrzymanie kota w bieżącym obszarze, łącząc dwa rogi obok kota, bot to zrobi. (Np. Na zdjęciu, jeśli kot ma 7,5, wybieramy 7,6, nawet jeśli tylko komórki 6,6 i 8,5 są jeszcze zajęte.)

Jeśli poprzednie nie jest możliwe, wybieramy zagrać w rogu, który jest częścią obszaru, w którym znajduje się kot. Jeśli wszystkie takie rogi są już wybrane (jak na obrazku), wybieramy komórkę obok kota.

Możliwych jest wiele drobnych ulepszeń, takich jak lepsze radzenie sobie z zawijaniem (układanie się tam psuje) lub optymalne wykonywanie ostatnich kilku ruchów. Mógłbym zrobić niektóre z nich. Jeśli nie jest to dozwolone, dołączę go (poza konkurencją) dla zainteresowanych.

DijkstrasCat vs HexCatcher:

wprowadź opis zdjęcia tutaj

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
źródło
3

CloseCatcher

Wybiera jedną z pozycji, w której kot mógłby przejść w następnym kroku. Wybiera tę, która po 3 krokach dałaby kotom możliwie najwięcej ścieżek, gdyby się tam poruszał, a pole nie zmieniłoby się.

Kod jest prawie identyczny z moim wpisem Cat, FreeCat , który wybiera kierunek w bardzo podobny sposób.

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
źródło
Niezły +1. CloseCatcher z łatwością przechwytuje StraightCat
Spikatrix
3

Dijkstra

Nie bardzo lubi koty (:v{ >

FreeCat vs Dijkstra (wymaga aktualizacji) :

wprowadź opis zdjęcia tutaj

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

Jak próbuje złapać kota:

Analizuje wszystkie kwadraty planszy i próbuje znaleźć kwadrat, który minimalizuje otwartość planszy i maksymalizuje, jak bardzo plansza jest wyciągnięta; w stosunku do kota. Otwartość i surowość planszy są obliczane przy użyciu modyfikacji jego słynnego algorytmu .

Otwartość:

Otwartość deski względem pozycji jest liczbą osiągalnych pozycji z tej pozycji.

Surowość:

Sztywność deski względem pozycji jest sumą odległości między dostępnymi pozycjami a pozycją.

Z ostatnią aktualizacją:

Teraz jest znacznie lepszy w łapaniu FreeCat i własnego kota wszystkich kotów.Niestety, jest również znacznie gorszy w łapaniu szalonych, niechętnych do współpracy kotów. Można go poprawić, wykrywając, czy kot jest jednym z szalonych, a następnie działając jako CloseCatcher.

Naprawiono błąd.

Numer jeden
źródło
Potwierdzam, że działa do tej pory, ale myślę, że zdecydowanie najwolniejszy, ale jak dotąd jeden z najlepszych. Potrzebuje 134 sekund na 100 gier przeciwko RandCatowi, wykonując jednocześnie tylko 4406 ruchów! Myślę, że będę musiał pozwolić, aby mój komputer działał przez noc w jednym z następnych dni ... Czy możesz nam powiedzieć nieco więcej o tym, jak to działa?
wada
@flawr Dodano opis.
TheNumberOne
Nadal dla mnie nie działa. Daje mi jeden błąd: error: cannot infer type arguments for PriorityQueue<>w tej linii PriorityQueue<int[]> open = new PriorityQueue<>(new Comparator<int[]>() {.
Spikatrix
@CoolGuy Czy używasz Java 6? Myślę, że musisz zaktualizować swój JDK.
TheNumberOne
@CoolGuy Możesz także umieścić int[]między dwoma pustymi diamentami poPriorityQueue .
TheNumberOne
2

ForwordCatcher

Umieszcza wiadro przed kotem, a jeśli zostanie zabrane, umieszcza się z tyłu.

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
źródło
1
Istnieje sporo błędów, które doprowadziły mnie do założenia, że ​​nie przetestowałeś swojego programu. Napraw te ...
błąd
@flawr naprawiony. przepraszam za błędy. Nie przetestowałem tego, a moja Java nie jest zbyt dobra.
MegaTom
Fajnie, do tej pory wszystko działa płynnie, ale wciąż nie jestem pewien, czy zawsze przyniesie prawidłowe ruchy =)
flawr
1
@flawr Przestrzeń za kotem zawsze będzie pusta dla łapacza :)
TheNumberOne
2

ChoiceCatcher

Używa tego samego mechanizmu oceniania, co mój wpis ChoiceCat . Istnieje niewielka modyfikacja, która pomaga wybrać odpowiednie komórki na pierwszych kilku krokach, ponieważ ChoiceCat nie dba o kilka pierwszych segmentów, ponieważ nie widzi ich jako zagrożenia.

ChoiceCatcher wydaje się osiągać znacznie lepsze wyniki niż obecne łapacze.

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
źródło
1

RandCatcher

Zostało to wykonane tylko do testowania kontrolera i po prostu losowo umieszcza segmenty (bardzo nieefektywnie).

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

}
wada
źródło
1

StupidFillCatcher

Zostało to wykonane tylko do testowania kontrolera. Po prostu wypełnia kolumnę po kolumnie, aż kot zostanie złapany.

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

}
wada
źródło