KaBotte Motorraum

An dieser Stelle werden für interessierte Karospieler die technischen Details von KaBotte genauer erklärt.

Allgemeines

• Programmiersprache
  • Java

• Architektur
  • Multi-Threaded (GUI, Server-Kommunikation, Pfadberechnung)

• Speicherverbrauch
  • KaBotte benötigt für die "schwierigen" Maps (z.B. 125, 167, 207) trotz paralleler Berechnung durch mehrere Threads maximal 550 MB. Die Laufzeit gewinnt aber deutlich, wenn viel Speicher (~3GB) zur Verfügung stehen, da zur Pfadberechnung sehr schnell, sehr viele Objekte erzeugt werden und die Meisten vom Algorithmus schon nach kurzer Zeit verworfen werden, so dass bei zu wenig Speicher der Garbage Collector sehr häufig laufen muss und dann mehr Zeit für die Speicherbereinigung verbraucht wird, als für die eigentliche Pfadberechnung.

• Laufzeit
  • Die Laufzeit hängt stark von der zu berechnenden Map ab, aber bis auf die schon beim Speicherverbrauch genannt Maps liegen die Antwortzeiten von KaBotte meist bei wenigen Millisekunden, so dass die Antworten zum Server künstlich begrenzt werden, um diesen nicht zu überlasten, was besonders bei einem frischen Start von KaBotte passieren kann, wenn sie viele Spiele blockt.
  • Wenn KaBottes mögliche Züge die von Gegenspielern kreuzen, wird für jede dabei mögliche Zugsituation eine eigene Pfadsuche ausgeführt, was z.B. bei Massenstarts die Laufzeit bis zur endgültigen Zugauswahl vervielfacht.
  • Viele der Optimierungen sind Folgen der Arbeiten am Kanalysator, da dafür pro zu analysierendem Spiel bis zu 1000 einzelne Spielsituationen berechnet werden müssen und sich jede Verbesserung hinsichtlich Speicherverbrauch und Laufzeit dabei deutlich auszahlt.
  • Eine Pfadberechnung für Rostock ab dem Start benötigt mittlerweile ca. 50 Sekunden. Vor den neusten Optimierungen stellte die Karte den Worst-Case dar und die gleiche Berechnung dauerte ca. 30 Minuten.

Algorithmen

Gültige Züge

• Für jeden Nachfolgezug wird überprüft, ob dieser entsprechend der Karo-Physik (Überfahren von Gras usw.) gültig ist.
• Bei Spielen mit Sonderregeln wird zusätzlich noch das Einhalten der entsprechenden Regel überprüft (z.B. Randrennen) und ein Folgezug gegebenenfalls verworfen.
• KaBottes Laufzeit hängt stark von dieser einzelnen Berechnung ab, da die Überprüfung sehr häufig (auch für bereits betrachtete Züge) durchgeführt wird
• Das Cachen der Ergebnisse führt zu deutlichen Performance-Verbesserungen (insb. beim Kanalysator, da dort mehrere hundert Rennsituationen auf einer einzelnen Map berechnet werden)
• Als Cache wird eine IntBooleanMap verwendet; dort wird für jeden Zug ein Hashwert aus dessen vier Komponenten gebildet und das zugehörige Ergebnis als Boolean gespeichert. Selbst bei Map 167: Rostock werden dafür weniger als 100 MB benötigt
• Die Zugriffe durch viele Threads (Kanalysator, Rennen mit Checkpoints, Blocker) auf die Map werden über ein optimistic Lock synchronisiert; nach der Initialisierungsphase (bis die meisten Züge auf einer Map überprüft wurden) dominieren Lesezugriffe

Pfadsuche

• von jedem möglichen Zug werden alle neun Nachfolgezüge betrachtet und überprüft, ob sie den Karo-Regeln entsprechen. Gültige Züge werden in einer Queue zur weiteren Bearbeitung gespeichert
• bereits verarbeite Züge (x,y,xv,yv) werden nur einmal betrachtet (insbesondere Züge mit größerer Pfadlänge werden ignoriert), allerdings wird die Information gespeichert, ob man auf verschieden (gleich langen) Wegen zu diesem Zug gelangt und diese dann als äquivalent angesehen
• der Algorithmus wird solange durchlaufen, bis ein Zug einen Checkpoint (im einfachsten Fall das Ziel) erreicht
• Zentrale Datenstruktur für die Pfadsuche ist eine Queue. Durch die Art, wie KaBotte die Pfadsuche mit Checkpoints behandelt ist eine PriorityQueue notwendig. Die dabei benötigten Sortieroperationen dominierten die Ausführungszeit, so dass die Standard PriorityQueue durch eine Eigenentwicklung ersetzt wurde. Für jede Zuglänge wird verwaltet eine eigene Queues die möglichen Züge. Zugriffe auf das erste Element der Gesamtqueue und auch das sortierte Einfügen finden in konstanter Zeit O(1) statt.

Rundkurse

• KaBotte kann in den meisten Fällen selbstständig feststellen, ob eine Map KEIN Rundkurs ist. Ausschlusskriterien sind:
  • die Zielkacheln hängen nicht direkt zusammen
  • das Ziel ist mehr als 3 Züge vom Start entfernt
  • die Zieleinfahrt ist nur in einem Winkelbereich von maximal 180° möglich (zur Bestimmung des Winkelbereichs wird eine Pfadsuche zwischen Start und Ziel durchgeführt und alle Winkel der gültigen Zieldurchfahrten betrachtet)
• Die Kriterien reichen in ca. 90% der Fälle zur korrekten Klassifizierung aus; für den Rest wurden händisch Sonderregeln definiert
• Problemfälle sind u.a. Maps mit Start oder Ziel in einer Sackgasse (hierfür mussten händisch Ausnahmen definiert werden): Map Nr. 116, 134, 184, 205, 229; 201

Richtungsmodus

• bei Formel 1 ist eine Zieleinfahrt nur im (bei der Rundkursberechnung ermittelten) Winkelbereich erlaubt; für die Pfadberechnung wird eine einmalige Überfahrt über ein Zielfeld erzwungen
• bei Classic Spielen werden Züge mit oben genannter Winkelbereich bei der Zielüberquerung ausgefiltert

Checkpoints

• für Checkpoints wird der obige Algorithmus für die Pfadsuche für jeweils eine Tour (alle offene CPs und zuletzt für das Ziel nacheinander) ausgeführt
• um den Suchraum zu verkleinern, werden nur die besten Kandidaten für die kürzeste Tour betrachtet, dazu wird die Karo-Distanz (die Zuganzahl) der CPs untereinander betrachtet und das TSP gelöst

Sonderregeln

• hierfür werden bei der standardmäßigen Überprüfung auf Gültigkeit von Zügen ebenfalls auf die Sonderregeln hin überprüft; die eigentliche Pfadsuche funktioniert weiterhin ohne spezielle Anpassungen
• für den RE-Modus ist grundsätzlich nicht genau bekannt weiche Züge möglich sind, bzw. ob wiederholt werden muss, deshalb wird ausgehen von der Wahrscheinlichkeit zu wiederholen (Anzahl der Spieler) für jeden Nachfolgezug die Wahrscheinlichkeit berechnet mit der KaBotte zu einem Crash gezwungen wird
• Züge mit Crash-Wahrscheinlichkeiten über einem Grenzwert werden als ungültig verworfen

Verwendete Bibliotheken

• Eclipse Collections
• Java WebSockets
• JSON-java