Zweiter Platz in der Mini AI Cup 4: Paper IO

Ich heiße Igor Volkov. Ich arbeite in einem Beratungsunternehmen als Java-Entwickler, Architekt, Teamleiter und technischer Manager. Unterschiedliche Rollen je nach den aktuellen Anforderungen des Projekts. Er machte lange Zeit auf Wettbewerbe von mail.ru aufmerksam, aber es stellte sich heraus, dass er nur bei Paper IO aktiv teilnahm.

Diesmal schlugen die Organisatoren vor, eine Bot-Management-Strategie basierend auf dem beliebten Spiel zu implementieren. Lesen Sie hier mehr über die Regeln. Den Code meiner Strategie und Beispiele für Spiele finden Sie auf der Website der Meisterschaft .

Zu Beginn des Wettbewerbs war, wie mir schien, die häufigste Idee für die Popup-Implementierung die Verwendung von MCTS . Daher habe ich ein wenig Zeit damit verbracht, mit diesem Algorithmus zu experimentieren. Und ohne herausgefunden zu haben, wie man es effektiv zur Lösung des Problems einsetzt, habe ich mich entschlossen, zunächst viele rechteckige Routen (mit zwei und dann mit drei Umdrehungen) und deren anschließende Bewertung zu generieren.

Strategiealgorithmus

Der übergeordnete Algorithmus der Strategie kann durch die folgenden 6 Punkte dargestellt werden:

1. Lesen Sie den Zustand der Welt
2. Konvertieren Sie Nachrichtenobjekte in Arbeitsobjekte
3. Bilden Sie eine Reihe rechteckiger Routen
4. Bewerten Sie jede der generierten Routen
5. Wählen Sie die beste Route
6. Team senden

Dieser Algorithmus hat sich während des Wettbewerbs nicht geändert. Nur die Methode zur Bildung von Bot-Routen und deren Bewertung wurden geändert.

Die SimpleStrategy- Klasse enthält die ursprüngliche Version der Strategie, und die BestStrategy- Klasse ist eine verbesserte Version, die im Wettbewerb den 2. Platz belegte.

Den Zustand der Welt lesen

Der Zustand der Welt wird als JSON- Objekt über STDIN übertragen . Ich habe in pom.xml gesehen, dass Sie die Gson- Bibliothek verwenden können und die Aufgabe, den Zustand der Welt zu lesen, wurde stark vereinfacht. Deserialisierte mithilfe der Gson- Bibliothek die aus dem Standardeingabestream gelesene JSON- Zeichenfolge in eine Instanz der Message- Klasse. Der Code befindet sich in Main.java (Zeilen 44-49) .

Arbeitsobjekte erstellen

Die Verwendung von Transportobjekten im Hauptprogrammcode ist normalerweise nicht sehr bequem und architektonisch falsch. Beispielsweise können die Organisatoren aus dem einen oder anderen Grund das Format von Nachrichten ändern. Daher ist es notwendig, Transportobjekte in Worker umzuwandeln, die im Hauptprogrammcode verwendet werden. Die Klassen Player und PlayerState behalten den Status des Bots bei, und die Dienstprogrammklasse MessagePlayer2PlayerConverter hilft beim Erstellen dieser Klassen basierend auf Daten aus der Transportnachricht. Die Bonusklasse enthält Informationen über den Bonus einer Zelle im Spielfeld. Der Code zum Erstellen von Arbeitsobjekten befindet sich in Main.java (Zeilen 61-74) .

Routenbildung

In den ersten Versionen der Strategie ( SimpleStrategy ) wurde der Pfad mithilfe der Klassen MovePlanWithScore und Move festgelegt . Move legt die Bewegungsrichtung und die Anzahl der Zellen fest, die der Bot in diese Richtung bewegen soll. MovePlanWithScore enthält die vom Move- Array angegebene Route und eine Schätzung dieser Route. Ein Array kann ein bis vier Verschiebungsobjekte enthalten . Trotz der Tatsache, dass nur rechteckige Routen mit nicht mehr als drei Kurven berücksichtigt werden, wird die Route des Bots tatsächlich in Form einer unterbrochenen Linie erhalten. Dies wird erreicht, indem in jeder Runde eine neue beste rechteckige Route ausgewählt wird. Die Routengenerierungsfunktion , die als verschachtelte Schleifen implementiert ist, bildet eine Liste von MovePlanWithScore zur weiteren Auswertung.

Eine solche Bildung der Flugbahnen des Bots war im Hinblick auf die Leistung der nachfolgenden Bewertung nicht sehr effektiv, da es notwendig war, dieselben Flugbahnen mehrmals zu berechnen, aber sie war sehr nützlich, um die Mechanik des Spiels zu verstehen.

In späteren Versionen der Strategie begann BestStrategy , den Routenbaum zu verwenden. Die MoveNode- Klasse spiegelt den Knoten dieses Baums wider. Der Baum ist zu Beginn der Strategie vollständig gebildet. Beachten Sie die init- Methode der MoveNode-Klasse . Es ist dem Generieren von Routen aus der SimpleStrategy- Klasse sehr ähnlich. Grundsätzlich unterscheidet sich die fragliche Route nicht wesentlich von der ersten Version.

Ich denke, die Bildung von Routen hätte durch eine weitere Wendung etwas verbessert werden können. Es blieb jedoch nicht genügend Zeit für die Optimierung.

Routenbewertung

Wo immer sich der Bot befand, wurde für ihn immer die beste Route gewählt, die auf seinem Territorium endet. Um die Route zu bewerten, habe ich zwei Indikatoren eingeführt: Punktzahl und Risiko. Punktzahl - spiegelt ungefähr die Anzahl der pro Tick des Pfades erzielten Punkte und das Risiko wider - die Anzahl der Ticks, die nicht ausreichen, um den Pfad zu vervollständigen (z. B. aufgrund der Tatsache, dass der Gegner am Schwanz greifen kann). Das Risiko trat nicht sofort auf. Wenn der Bot in der ersten Version plötzlich in der Mitte des Pfades feststellte, dass er keine Zeit hatte, die Route abzuschließen, wurde er „verrückt“, da alle gefährlichen Pfade gleichermaßen schlecht für ihn waren. Von allen betrachteten Routen wird die „sicherste“ mit der maximalen Anzahl von Punkten pro Tick des Pfades ausgewählt.

Um die Sicherheit der Route zu beurteilen, berechne ich die Erreichbarkeitsmatrix: Für jede Zelle des Spielfelds finde ich ein Häkchen, auf dem der Bot des Gegners erscheinen kann. Zuerst nur ein Häkchen und später eine Schwanzlängenberechnung. Boni, die auf dem Weg abgeholt werden können, wurden in den ersten Versionen der Strategie ebenfalls nicht berücksichtigt. Die TimeMatrixBuilder- Klasse berechnet Matrizen von Ticks und Schwanzlängen von konkurrierenden Bots. Diese Matrizen werden dann zur Risikobewertung verwendet. Befindet sich mein Bot zum Zeitpunkt der Berechnung des nächsten Zuges auf seinem Territorium - das maximale Risiko wird gefährlichen Routen zugewiesen. Wenn der Bot bereits in einem fremden oder neutralen Territorium unterwegs war, wird das Risiko als Differenz zwischen den Zecken der Fertigstellung des Pfades (der Bot kam in sein Territorium) und der Zecke bewertet, wenn dies möglich ist Gefahr drohen (zum Beispiel kann der Bot eines anderen auf den Schwanz treten).

In den ersten Versionen der Strategie wurde die Punktzahl nur auf der Grundlage des eroberten Gebiets berücksichtigt und die Boni wurden geringfügig berücksichtigt. Um die erfassten Zellen zu finden, verwende ich einen rekursiven Algorithmus . Viele Teilnehmer beklagten sich über die Seltsamkeit und den übermäßigen Rechenaufwand des von den Organisatoren von Local Runner verwendeten Algorithmus. Ich gehe davon aus, dass dies absichtlich gemacht wurde, um den Teilnehmern des Wettbewerbs keine vorgefertigten Lösungen zu geben.

Seltsam, aber trotz der Primitivität der ersten Versionen der Strategie zeigte es sich recht gut: 10. Platz im Sandkasten. Zwar begann er in der Vorrunde schnell zu sinken: Andere Teilnehmer verbesserten ihre Strategien.

Mein Bot ist oft gestorben. Zuallererst aufgrund der Tatsache, dass eine Route zu dem Gebiet gebaut wurde, das von rivalisierenden Bots erobert wurde. Der Weg verlängerte sich unerwartet und mein Bot wurde vom Schwanz gefangen. Oft gestorben aufgrund einer falschen Vorhersage der Länge des Schwanzes und der Geschwindigkeit des Bot des Gegners. Zum Beispiel war es gefährlich, wenn der Bot eines Gegners langsamer wurde, da die Strategie ungefähr voraussetzte, dass er die Zelle bereits hätte verlassen sollen und immer noch da war. Um diese Probleme zu bekämpfen, begann ich, eine größere Anzahl von Indikatoren für jede Zelle des Spielfelds zu berechnen (Klassen AnalyticsBuilder und CellDetails ).

Zellen des Spielfeldes zählen

1. Häkchen, bei dem der Bot des Gegners den Käfig besetzen kann (Häkchen am Schwanz)
2. Kreuzen Sie an, bei dem der Bot des Gegners die Zelle betreten kann
3. Die Länge des Schwanzes beim Betreten des Käfigs
4. Häkchen, bei dem der Bot des Gegners den Käfig verlassen kann
5. Schwanzlänge beim Verlassen des Käfigs
6. Häkchen, bei dem eine Zelle vom Bot eines Gegners erfasst werden kann
7. Häkchen, bei dem die Zelle das Ziel für die Erfassung des Territoriums sein kann
8. Häkchen, auf das die Zelle mit einer Säge geschlagen werden kann

Die Analysetiefe ist auf 10 Züge begrenzt. Ich denke, es war möglich, eine größere Tiefe zu erreichen, indem man sich weigerte, einzelne Rivalen zu zählen oder eine schwebende Tiefe einzuführen, aber es gab nicht genug Zeit für die Optimierung. Zusätzlich zu AnalyticsBuilder begann er mit der Verwendung von SimpleTickMatrixBuilder, wenn es an Rendering-Tiefe für AnalyticsBuilder mangelte. Analyseergebnisse werden von BestStrategy verwendet .

Die Bewertungsfunktion hat sich ebenfalls leicht verbessert:

1. Ich fing an, Boni zu berücksichtigen: eine Strafe für einen Verzögerungsbonus und einen Bonus für Beschleunigungs- und Sägeboni. Infolgedessen begann der Bot, schlechte Boni erfolgreich zu vermeiden und sammelte dabei gute.
2. Er begann das Aufeinandertreffen der Köpfe zu berücksichtigen. Es wurden einige Punkte für den Sieg hinzugefügt. Je weiter eine mögliche Kollision entfernt ist, desto weniger Punkte.
3. Um die Wahrscheinlichkeit der Umgebung zu verringern, fügte er einige Punkte hinzu, um die Grenzzellen des Gegners zu übernehmen.
4. Der Wert leerer Zellen am Rand wurde verringert: Je weiter von der Mitte entfernt, desto niedriger ist der Wert. Als ich mir die Kämpfe des Finales ansah, kam ich zu dem Schluss, dass es für die Tatsache, eine leere Zelle zu erobern, überhaupt keine Notwendigkeit gab, Punkte zu sammeln. Der Wert einer leeren Zelle sollte von der Nähe zu großen Gruppen feindlicher Zellen abhängen. Leider war es im Finale nicht mehr möglich, die Strategie zu bearbeiten.
5. Es wurden Punkte hinzugefügt, um den Bot-Kopf des Gegners zu umgeben. Ich bin mir nicht sicher, ob das irgendwie geholfen hat. Vielleicht mit den einfachsten Strategien.
6. Er fügte Punkte hinzu, selbst wenn er vergeblich am Schwanz packte (der Bot des Gegners schaffte es, das Gebiet mit demselben Tick zu erobern, in dem mein Bot auf seinen Schwanz trat). Ich bin mir definitiv nicht sicher, aber ich denke, dass dies die Bots des Gegners daran gehindert hat, das Territorium eines anderen zu erobern, und sie mussten oft zu ihrem eigenen zurückkehren.
7. Im Falle der Entdeckung eines möglichen Todes durch Gefangennahme erhöhten sich die Kosten für die Grenzzellen des gegnerischen Territoriums erheblich.

Strategie-Debugging

Die ersten Versionen der Strategie enthielten eine große Anzahl von Tippfehlern und Fehlern: anscheinend das Ergebnis nächtlicher Programmierung. In der Cell- Klasse wurde der Index beispielsweise falsch berücksichtigt: Anstelle von this.index = x * Game.sizeY + y war this.index = x * Game.width + y . Zuerst habe ich versucht, mich nur auf Tests zu verlassen, aber meine Intuition deutete darauf hin, dass es ohne Visualisierung und ohne zuvor gespielte Spiele schwierig sein würde, Fehler im Code zu finden und die Gründe für fehlerhafte Entscheidungen zu analysieren. Als Ergebnis wurde der DebugWindow- Visualizer angezeigt , in dem Sie zuvor gespielte Spiele Schritt für Schritt anzeigen und mit dem Debuggen des gewünschten Häkchens beginnen können. Der Code ist nicht sehr schön, in Eile geschrieben, aber er hat mir beim Debuggen sehr geholfen. Beispielsweise wurde bei einer falschen Berechnung des Zellenindex sofort ein Fehler festgestellt. Viele Teilnehmer zeigten Debugging-Informationen in der Konsole an, aber es schien mir nicht genug.

Optimierung

Um keine Zeit mit dem Erstellen von Objekten und dem Ausführen des GC zu verschwenden, habe ich versucht, einige Objekte im Voraus zu erstellen. Dies sind die Zellen des Spielfeldes ( Zellklasse ). Zusätzlich für jede Zelle identifizierte Nachbarn. Erstellt im Voraus einen Baum möglicher Pfade (Klasse MoveNode ).

Ich ging davon aus, dass viele Szenarien simuliert werden müssten und sich dabei der aktuelle Zustand verschlechtern und jedes Mal wiederhergestellt werden müsste. Um den Zustand der Welt zu erhalten, habe ich versucht, so viele gepackte Strukturen wie möglich zu verwenden. So speichern Sie das besetzte Gebiet - BitSet (Klasse PlayerTerritory ). Jede Zelle des Spielfelds ist nummeriert und die Zellennummer entspricht der Bitnummer in BitSet. Um den Schwanz zu speichern, habe ich BitSet zusammen mit ArrayDeque (Klasse PlayerTail ) verwendet.

Es stimmt, ich habe aus Zeitmangel nicht verschiedene Szenarien gespielt. Und da die Hauptfunktion der Berechnung des Pfades rekursiv wurde und der gesamte Status auf dem Stapel gespeichert werden konnte, waren die neuesten Optimierungen für mich nicht sehr nützlich.

Nicht realisierte Ideen

Bei der Beurteilung des Routenrisikos meines Bots habe ich jeden Gegner unabhängig berücksichtigt. Tatsächlich hat jeder der Rivalen auch Angst zu sterben. Daher lohnt es sich, dies bei einer Risikobewertung zu berücksichtigen. Zumindest musste dies bei den Endspielen unbedingt berücksichtigt werden.

Berücksichtigung des zukünftigen Todes eines Gegners. Manchmal kam es vor, dass der Bot das Territorium des Gegners einnimmt und der Gegner unerwartet stirbt. Es ist eine Schande, weil Sie daher nur leere Zellen erfassen.

Berücksichtigung leerer Zellen, die in naher Zukunft als Bewertungsfunktion erfasst werden.

Empfehlungen und danke

Ich empfehle allen Entwicklern, aktiv an AI Cups-Wettbewerben teilzunehmen. Dies entwickelt das Denken und hilft im Spiel, neue Algorithmen zu lernen. Und wie meine Erfahrung gezeigt hat, reicht ein wenig Eifer aus, um einen Preisplatz einzunehmen, und selbst ein einfacher und nicht sehr optimaler Code kann Ergebnisse bringen.

Vielen Dank an die Organisatoren. Trotz einiger technischer Probleme erwies sich der Wettbewerb als interessant. Ich freue mich auf den nächsten!