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 11
quadratisches 2D-Array und ahmen das hexagonale "Verhalten" nach, das die Katze nur in 6 Richtungen bewegen kann:
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 11
2D- int
Array, 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 -1
und 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 int
Array 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
quelle
PRINT_STEPS = true
genauere Einstellungen in der Datei vornehmenMyFrame.java
). Dann habe ich das mit LICEcap aufgenommen und mit GIMP bearbeitet . Bei weiteren Fragen einfach fragen!Antworten:
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
quelle
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:
Dieser Fänger schlägt sich durchweg besser als Achilles, und ich denke, er ist anders genug, um eine neue Antwort zu rechtfertigen.
quelle
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:
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:
quelle
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:
quelle
Dijkstra
Er mag Katzen nicht sehr (:
v{ >
FreeCat vs Dijkstra
(muss aktualisiert werden):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 Katzealle 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.
quelle
error: cannot infer type arguments for PriorityQueue<>
in dieser ZeilePriorityQueue<int[]> open = new PriorityQueue<>(new Comparator<int[]>() {
.int[]
zwischen die beiden leeren Diamanten setzenPriorityQueue
.ForwordCatcher
Stellen Sie einen Eimer vor die Katze oder stellen Sie ihn dahinter, wenn Sie ihn nehmen.
RabidCat vs ForwordCatcher:
quelle
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:
quelle
RandCatcher
Dies wurde nur zum Testen des Controllers gemacht und platziert die Eimer zufällig (sehr ineffizient).
quelle
DummerFillCatcher
Dies wurde nur zum Testen des Controllers gemacht. Es füllt sich nur Spalte für Spalte, bis die Katze gefangen wird.
quelle