Asymmetrische KOTH: Fangen Sie die Katze
UPDATE : Die GIST-Dateien werden aktualisiert (einschließlich neuer Untermischungen), da die Controller.java keine Ausnahmen (nur Fehler) abfängt. Es werden nun Fehler und Ausnahmen abgefangen und auch gedruckt.
Diese Herausforderung besteht aus zwei Fäden, dies ist der Katzenfaden, den Fängerfaden finden Sie 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 einfügenplayers
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 enthält jeweils zwei Arbeitsbeispiele für einfache Katzen- / Fängerklassen.
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 einige 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 enthält Methoden read(i,j)
zum Lesen der Zelle (i,j)
unter sowieisValidMove()/ 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 a zurückgeben 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 / Ziel bereits belegt ist (als Katze) oder wenn sich bereits ein Eimer / eine Katze befindet (als Fänger). 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 den Code Ihrer Klasse sowie eine Beschreibung enthalten, 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 inspiriert von diesem alten Flash-Spiel
Vielen Dank an @PhiNotPi für das Testen und das konstruktive Feedback.
Aktuelle Ergebnisse (100 Spiele pro Paarung)
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
quelle
main.Controller
, diegetCatchers()
Antworten der Fänger über ihretakeTurn
Methoden zu importieren , anzurufen und zu simulieren / zu sabotieren ?Antworten:
FreeCat
Wählt den Zug, der nach 3 Schritten die bestmöglichen Pfade ergibt, wenn sich das Feld nicht ändert.
FreeCat gegen Achilles:
quelle
Dijkstra's Cat
Er lernte und wendete den Master-Algorithmus seines Masters an. Beachten Sie, dass er von einigen Methoden in der Klasse seines entsprechenden Catchers abhängig ist.
Dijkstra's Cat vs Hexcatcher (muss aktualisiert werden):
Wie er arbeitet:
Er versucht, den Zug zu finden, der die Fadenzahl des Brettes im Verhältnis zu sich selbst minimiert. Weitere Informationen finden Sie im entsprechenden Beitrag des Catchers.
Mit Update:
Er vermeidet jetzt die seltsamen geometrischen Formen, die die Wassereimer manchmal bilden.
quelle
MaxCat
Ich habe versucht, den Minimax-Algorithmus zu implementieren. Es funktioniert jedoch aufgrund der begrenzten Zeit nicht sehr gut. Bearbeiten: Es wird jetzt Multithreading verwendet, aber (zumindest auf meinem Computer) kann ich die Tiefe nicht höher einstellen. Andernfalls tritt eine Zeitüberschreitung auf. Bei Verwendung eines PCs mit 6 oder mehr Kernen wäre diese Einreichung viel besser :)
MaxCat gegen Dijkstra:
quelle
Field
öffentlich machen. Es tut mir leid, dass ich die Dateien noch nicht aktualisiert habe, aber wir haben dies bereits besprochen!SpiralCat
Bewegt sich spiralförmig. Es
SpiralCat gegen Agamemnon:
quelle
turns[i]
,turns[i%6]
um Grenzen zu überschreiten (was in dieser Station NICHT vorkommen sollte).turns[i%6]
? Ich meine,takeTurn
werde nicht angerufen, wenn die Katze blockiert ist, oder?i>=6
sollte nie passieren.RabidCat
RabidCat hat Hydrophobie, deshalb hat er Angst vor den Wassereimern. Er findet den nächsten und rennt in die entgegengesetzte Richtung.
RabidCat vs ForwordCatcher:
quelle
ChoiceCat
Für jede mögliche neue Katzenposition prüfen wir die Güte und wählen die beste aus. Güte ist die Funktion der beiden besten Nachbarzellen, die weiter von der Katzenposition entfernt sind als die Position, deren Punktzahl wir berechnen. Wir verwenden nur zwei Zellen, da eine blockiert werden kann und die Katze nur noch eine benötigt, um zu entkommen. Unsere Funktion bevorzugt zwei ziemlich gute Zellen als eine große und eine schlechte. Positionen mit Eimern haben eine Punktzahl von 0 und die am weitesten entfernten freien Zellen haben eine Punktzahl von 1.
ChoiceCat scheint besser zu punkten als die aktuellen Katzen.
ChoiceCat vs ChoiceCatcher:
quelle
StupidRightCat
Dies wurde nur zum Testen des Controllers gemacht. Die Katze bewegt sich wann immer möglich nach rechts, ansonsten in eine zufällige Richtung.
quelle
RandCat
Dies wurde nur zum Testen des Controllers gemacht. Die Katze bewegt sich nur zufällig.
quelle
StraightCat
Diese Katze bewegt sich gerade.
Zu Beginn wählt es eine zufällige Richtung und bewegt sich so lange in diese Richtung, bis dies nicht mehr möglich ist. In diesem Fall verschiebt es die Richtung im Uhrzeigersinn in die nächste gültige Richtung und wiederholt diesen Vorgang.
StraightCat gegen Agamemnon:
quelle