Asymmetrische KOTH: Catch the Cat (Fangfaden)

17

Asymmetrische KOTH: Fangen Sie die Katze

UPDATE : Die Gist-Dateien werden aktualisiert (einschließlich neuer Untermischungen), da die Controller.java keine Ausnahmen abfängt (nur Fehler). Es werden nun Fehler und Ausnahmen abgefangen und auch gedruckt.

Diese Herausforderung besteht aus zwei Fäden, dies ist der Fadenfänger ist, kann die Katze Thread gefunden werden hier .

Der Controller kann hier heruntergeladen werden .

Dies ist eine asymmetrische KOTH: Jede Vorlage ist entweder eine Katze oder ein Fänger . Es gibt Spiele zwischen jedem Paar einer Katze und einem Fänger. Die Katzen und die Fänger haben getrennte Ranglisten.

Fänger

Es gibt eine Katze auf einem sechseckigen Gitter. Ihre Aufgabe ist es, es so schnell wie möglich zu fangen. In jeder Runde können Sie einen Wassereimer auf eine Gitterzelle stellen, um zu verhindern, dass die Katze dorthin kann. Aber die Katze ist (vielleicht) nicht so dumm, und wenn Sie einen Eimer platzieren, bewegt sich die Katze in eine andere Gitterzelle. Da das Gitter sechseckig ist, kann die Katze in 6 verschiedene Richtungen gehen. Ihr Ziel ist es, die Katze mit Wassereimern zu umgeben, je schneller desto besser.

Katze

Sie wissen, dass der Fänger Sie fangen möchte, indem er Wassereimer um Sie herum stellt. Natürlich versuchst du auszuweichen, aber da du eine faule Katze bist (so wie Katzen), machst du genau einen Schritt nach dem anderen. Dies bedeutet, dass Sie nicht an dem Ort bleiben können, an dem Sie sich befinden, sondern an einem der sechs umliegenden Orte. Immer wenn Sie sehen, dass der Fänger einen neuen Wassereimer aufgestellt hat, gehen Sie in eine andere Zelle. Natürlich versuchen Sie, so lange wie möglich auszuweichen.

Gitter

Das Gitter ist hexagonal, aber da wir keine hexagonalen Datenstrukturen haben, nehmen wir ein 11 x 11quadratisches 2D-Array und ahmen das hexagonale "Verhalten" nach, das die Katze nur in 6 Richtungen bewegen kann:

Bildbeschreibung hier eingeben

Die Topologie ist toroidal, dh wenn Sie eine Zelle außerhalb des Arrays betreten, werden Sie nur in die entsprechende Zelle auf der anderen Seite des Arrays übertragen.

Spiel

Die Katze startet an einer bestimmten Position im Gitter. Der Fänger kann den ersten Zug machen, dann bewegen sich die Katze und ihr Fänger abwechselnd, bis die Katze gefangen ist. Die Anzahl der Schritte ist die Punktzahl für dieses Spiel. Die Katze versucht eine möglichst hohe Punktzahl zu erzielen, der Fänger versucht eine möglichst niedrige Punktzahl zu erzielen. Die durchschnittliche Summe aller Spiele, an denen Sie teilgenommen haben, ist die Punktzahl Ihrer Einreichung. Es gibt zwei separate Ranglisten, eine für die Katze und eine für die Fänger.

Regler

Der angegebene Controller ist in Java geschrieben. Als Fänger oder Katze müssen Sie jeweils eine Java-Klasse komplett implementieren (es gibt bereits einige primitive Beispiele) und diese in die platzierenplayers Paket einfügen (und die Liste der Katzen / Fänger in der Controller-Klasse aktualisieren). Sie können jedoch auch schreiben zusätzliche Funktionen innerhalb dieser Klasse. Der Controller wird mit jeweils zwei Arbeitsbeispielen für einfache Katzen- / Fängerklassen geliefert.

Das Feld ist ein 11 x 112D- intArray, das die Werte der aktuellen Zustände der Zellen speichert. Wenn eine Zelle leer ist, hat sie einen Wert 0, wenn es eine Katze gibt, hat sie einen Wert -1und wenn es einen Eimer gibt, gibt es einen 1.

Es gibt ein paar bestimmten Funktionen , die Sie verwenden können: isValidMove()/ isValidPosition()sind zu überprüfen , ob Ihr Zug (cat) / Position (Fänger) gültig ist.

Jedes Mal, wenn Sie an der Reihe sind, wird Ihre Funktion takeTurn()aufgerufen. Das Argument enthält eine Kopie des aktuellen Rasters und verfügt über Methoden read(i,j)zum Lesen der Zelle (i,j)unter sowie zum isValidMove()/ isValidPosition()Überprüfen der Gültigkeit Ihrer Antwort. Hiermit wird auch das Umbrechen der Toroid-Topologie verwaltet. Das bedeutet, dass Sie auch dann auf die Zelle (-5,13) zugreifen können, wenn das Raster nur 11 x 11 ist.

Die Methode sollte ein intArray von zwei Elementen zurückgeben, die mögliche Bewegungen darstellen. Für die Katzen sind {-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}dies die relativen Positionen, in die die Katze gehen möchte, und die Fänger geben die absoluten Koordinaten zurück, in die sie einen Eimer stellen möchten {i,j}.

Wenn Ihre Methode einen ungültigen Zug ergibt, wird Ihr Beitrag disqualifiziert. Der Umzug gilt als ungültig, wenn sich an Ihrem Ziel bereits ein Eimer befindet oder der Umzug nicht erlaubt / das Ziel bereits belegt ist (als Katze) oder wenn sich bereits ein Eimer / eine Katze (als Fänger) befindet. Das können Sie vorher mit den angegebenen Funktionen überprüfen.

Ihre Einreichung sollte relativ schnell funktionieren. Wenn Ihre Methode für jeden Schritt länger als 200 ms dauert, wird sie ebenfalls disqualifiziert. (Am liebsten viel weniger ...)

Die Programme dürfen Informationen zwischen den Schritten speichern.

Einreichungen

  • Sie können so viele Beiträge einreichen, wie Sie möchten.
  • Bitte ändern Sie Ihre bereits eingereichten Beiträge nicht wesentlich.
  • Bitte jede Einsendung in einer neuen Antwort.
  • Jeder Beitrag sollte vorzugsweise einen eindeutigen Namen haben.
  • Die Einreichung sollte aus dem Code Ihrer Klasse sowie einer Beschreibung bestehen, aus der hervorgeht, wie Ihre Einreichung funktioniert.
  • Sie können die Zeile <!-- language: lang-java -->vor Ihrem Quellcode schreiben , um eine automatische Hervorhebung der Syntax zu erhalten.

Wertung

Alle Katzen treten gleich oft gegen alle Fänger an. Ich werde versuchen, die aktuellen Ergebnisse regelmäßig zu aktualisieren. Die Gewinner werden ermittelt, wenn die Aktivität abgenommen hat.

Diese Herausforderung ist von diesem alten Flash-Spiel inspiriert

Vielen Dank an @PhiNotPi für das Testen und das konstruktive Feedback.

Aktuelle Ergebnisse (100 Spiele pro Paarung)

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
fehlerhaft
quelle
Welches Programm macht die Animationen?
MegaTom
Die Animation ist nur die GUI (beim Start des Controllers müssen Sie PRINT_STEPS = truegenauere Einstellungen in der Datei vornehmen MyFrame.java). Dann habe ich das mit LICEcap aufgenommen und mit GIMP bearbeitet . Bei weiteren Fragen einfach fragen!
Fehler
Wenn Sie dem Controller Benutzereingaben hinzufügen, kann dies zu einer guten Software mit der GUI und den bereits geschriebenen Bots führen. Es wäre auch interessant zu sehen, wie viel Menschen die spezifischen Bot-Strategien knacken / missbrauchen können.
Randomra
Kann mein Bot auch Informationen aus dem vorherigen Spiel behalten, um zu versuchen, eine bessere Bewegungssequenz für denselben Bot zu finden? Ich nehme nicht an, weil es umso besser wird, je mehr Runden du machst. Es müsste auch erraten werden, ob es gegen einen neuen Bot spielt, daher wäre auch die laufende Reihenfolge von Bedeutung.
Randomra
1
Warum sind die Punktzahlen der Katzen ungeordnet?
Spikatrix

Antworten:

6

Achilles

Achilles ist nicht zu hell, aber er ist rücksichtslos effizient. Zuerst hindert er die Katze daran, das Brett zu umwickeln, dann teilt er das Brett in zwei Teile. Dann teilt er den Teil des Brettes, in dem sich die Katze befindet, in zwei Hälften, bis die Katze gefangen ist.

Demonstration RandCat gegen Achilles

Randcat gegen 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
quelle
Nun, welches ist es jetzt, Achilles oder Hector? (Oder jemand mit einer dissoziativen Identitätsstörung? =)
Fehler
@flawr Achilles, lol Ich habe den Namen in der Mitte geändert (es ist besser, den Catcher Achilles und die Katze Hector zu nennen), aber ich habe vergessen, den Java zu ändern - das passiert, wenn du nach dem Tee programmierst :(
euanjt
Aber Hector wäre lieber ein Hundename =) Danke, dass dein Beitrag super funktioniert. Ich hoffe es macht Ihnen nichts aus, dass ich auch die 'Präambel' in Ihren Code einbinde.
Fehler
Ja, kein Problem. Hector klingt wie ein
Hundename
Ich habe gerade eine Simulation durchgeführt (10000 Spiele für jedes Paar) und Achilles wurde aufgrund wiederholter StackOverflowError disqualifiziert. Ich denke , die Rekursion noch nicht zu Ende: pastebin.com/9n6SQQnd
flawr
5

Agamemnon

Agamemnon teilt den Katzenbereich mit einer vertikalen Linie in zwei Hälften, bis die Katze nur noch einen Streifen mit der Breite 2 zum Einziehen hat. An diesem Punkt fängt er die Katze ein.

Agamemnon vs RandCat:

Bildbeschreibung hier eingeben

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

Dieser Fänger schlägt sich durchweg besser als Achilles, und ich denke, er ist anders genug, um eine neue Antwort zu rechtfertigen.

euanjt
quelle
Sehr schöne Lösung, ich war mir sicher, dass Achilles fast optimal war, aber jetzt denke ich, dass sogar Agamemnon leicht verbessert werden könnte =)
fehlerhaft
Ja, Agamemnon hat einen viel besseren Algorithmus für das
Beenden von
@flawr sehr kleiner Tweak hinzugefügt, um das Fangen in einigen speziellen Fällen zu beschleunigen, dies hat keinen Einfluss auf die Animation hier (obwohl ich denke, dass es die Animation von SpiralCat beeinflussen könnte)
Euanjt
Frage! Was passiert, wenn Sie eine Linie schließen wollen, die Katze aber an der letzten Stelle steht?
Mr. Llama
@ Mr.Llama es beginnt die nächste Zeile zu machen, als ob diese Zeile gefüllt wäre (dh die Katze war in der Tat ein Eimer) - nicht der effektivste Einsatz einer Runde, aber es kommt sehr selten vor, dass es nicht wirklich wichtig ist - die Die Katze muss dann in ihrem nächsten Zug weg, damit ich meinen Eimer dort platzieren kann
Dienstag,
5

HexCatcher

Wenn der Fänger die Katze in das Innere eines großen Sechsecks mit 3 Seiteneinheiten bringen kann, in denen die Ecken des Sechsecks bereits mit Eimern belegt sind, kann der Fänger die Katze in diesem Bereich halten und fangen. Das Sechseck sieht so aus:

Bildbeschreibung hier eingeben

Dies versucht HexCatcher zu erreichen. Es deckt das Feld mental mit diesen großen Sechsecken so ab, dass jede Eckzelle Teil von drei großen Sechsecken ist.

Wenn es eine Chance gibt, die Katze im aktuellen Bereich zu halten, indem zwei Ecken neben der Katze verbunden werden, wird der Bot dies tun. (ZB im Bild, wenn die Katze bei 7,5 ist, wählen wir 7,6, auch wenn nur die 6,6- und 8,5-Zellen noch belegt sind.)

Wenn die vorherige Option nicht verfügbar ist, spielen wir eine Ecke, die Teil des Bereichs ist, in dem sich die Katze befindet. Wenn alle diese Ecken bereits ausgewählt sind (wie im Bild), wählen wir eine Zelle neben der Katze aus.

Es sind mehrere kleine Verbesserungen möglich, z. B. eine bessere Handhabung des Umlaufs (die Kacheln brechen dort ab) oder die optimalen Bewegungen des letzten Paares. Ich könnte einige davon machen. Wenn es nicht erlaubt ist, füge ich es nur (außer Konkurrenz) für die Interessierten hinzu.

DijkstrasCat vs HexCatcher:

Bildbeschreibung hier eingeben

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
quelle
3

CloseCatcher

Wählt eine der Positionen, an denen die Katze im nächsten Schritt treten könnte. Es wird derjenige ausgewählt, der nach 3 Schritten für die Katze die bestmöglichen Pfade ergibt, wenn sie sich dorthin bewegt und sich das Feld nicht ändert.

Der Code ist fast identisch mit meinem Cat-Eintrag FreeCat , der die Richtung auf sehr ähnliche Weise auswählt.

SpiralCat vs CloseCatcher:

SpiralCat gegen 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
quelle
Nizza +1. CloseCatcher erfasst StraightCat
Spikatrix am
3

Dijkstra

Er mag Katzen nicht sehr (:v{ >

FreeCat vs Dijkstra (muss aktualisiert werden) :

Bildbeschreibung hier eingeben

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

Wie er versucht, die Katze zu fangen:

Er analysiert alle Felder der Tafel und versucht, das Feld zu finden, das die Offenheit der Tafel minimiert, und maximiert, wie stark die Tafel gespannt ist. in Bezug auf die Katze. Die Offenheit und Stringiness eines Boards werden mit einer Modifikation seines berühmten Algorithmus berechnet .

Offenheit:

Die Offenheit eines Boards in Bezug auf eine Position ist die Anzahl der von dieser Position aus erreichbaren Positionen.

Stringiness:

Die Fadenzahl eines Brettes relativ zu einer Position ist die Summe der Abstände zwischen den erreichbaren Positionen und der Position.

Mit dem letzten Update:

Jetzt ist er viel besser darin, FreeCat und seine eigene Katze alle Katzen zu fangen .Leider ist er auch viel schlechter darin, die verrückten, nicht kooperativen Katzen zu fangen. Er könnte verbessert werden, indem er erkennt, ob die Katze zu den Verrückten gehört, und dann als CloseCatcher auftritt.

Fehler behoben.

Die Nummer eins
quelle
Kann bestätigen, dass es soweit funktioniert, aber bei weitem das langsamste, aber eines der besten, die ich bisher denke. Benötigt 134 Sekunden für 100 Spiele gegen RandCat bei insgesamt nur 4406 Zügen! Ich glaube, ich muss meinen PC in den nächsten Tagen über Nacht laufen lassen ... Kannst du uns ein bisschen mehr darüber erzählen, wie es funktioniert?
Fehler
@flawr Beschreibung hinzugefügt.
TheNumberOne
Funktioniert immer noch nicht für mich. Gibt mir einen Fehler: error: cannot infer type arguments for PriorityQueue<>in dieser Zeile PriorityQueue<int[]> open = new PriorityQueue<>(new Comparator<int[]>() {.
Spikatrix
@CoolGuy Verwenden Sie Java 6? Ich denke, Sie müssen Ihr JDK aktualisieren.
TheNumberOne
@CoolGuy Sie können auch einen int[]zwischen die beiden leeren Diamanten setzen PriorityQueue.
TheNumberOne
2

ForwordCatcher

Stellen Sie einen Eimer vor die Katze oder stellen Sie ihn dahinter, wenn Sie ihn nehmen.

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
quelle
1
Es gibt einige Fehler, die mich zu der Annahme führen, dass Sie Ihr Programm nicht getestet haben. Bitte reparieren Sie diese ...
Fehler
@flawr behoben. Entschuldigung für die Fehler. Ich habe es nicht getestet und mein Java ist nicht zu gut.
MegaTom
Nizza, soweit läuft alles reibungslos, aber ich bin mir immer noch unsicher, ob es immer gültige Züge bringen wird =)
flawr
1
@flawr Der Raum hinter einer Katze ist für den Fänger immer leer :)
TheNumberOne
2

ChoiceCatcher

Verwendet den gleichen Bewertungsmechanismus wie mein ChoiceCat-Eintrag . Es gibt eine kleine Modifikation, die hilft, relevante Zellen in den ersten Schritten auszuwählen, da ChoiceCat sich nicht um die ersten Eimer kümmert, da es sie nicht als Bedrohung ansieht.

ChoiceCatcher scheint deutlich besser zu punkten als die aktuellen Catcher.

ChoiceCat vs ChoiceCatcher:

ChoiceCat gegen 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
quelle
1

RandCatcher

Dies wurde nur zum Testen des Controllers gemacht und platziert die Eimer zufällig (sehr ineffizient).

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

}
fehlerhaft
quelle
1

DummerFillCatcher

Dies wurde nur zum Testen des Controllers gemacht. Es füllt sich nur Spalte für Spalte, bis die Katze gefangen wird.

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

}
fehlerhaft
quelle