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 läuft.

• 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

Bot

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 (zu einem CP)

• von jedem möglichen Zug werden alle neun Nachfolgezüge betrachtet und überprüft, ob sie den Karo-Regeln (siehe Gültige Züge) entsprechen
• ein Zug (x,y,xv,yv) wird nur einmal betrachtet (bei gleicher Länge werden die unterschiedlichen Vorgängerzüge gespeichert / bei größerer Pfadlänge, wird ein weiterer Zug ignoriert)
• der Algorithmus wird solange durchlaufen, bis eine Checkpoint überfahren wird
• zentrale Datenstruktur für die Pfadsuche ist eine PriorityQueue. Die Züge werden nach Länge ihrer zurückgelegten Pfade aufsteigend sortiert betrachtet. Für sehr kurze Zugriffszeiten wird eine BucketQueue verwendet, die Lese- und Einfügeoperationen in konstanter Zeit O(1) ermöglicht

Checkpoints

• eine Tour ist eine Folge von, vom Spieler noch nicht überfahrenen, CPs (bei 9 noch nicht überfahrenen CPs ergeben sich 9 Fakultät [362880] Möglichkeiten diese abzufahren)
• für Checkpoints wird der obige Algorithmus für die Pfadsuche für alle CPs einer Tour nacheinander ausgeführt (von 1 zu 2, dann von 2 zu 3 usw.)
• um die möglichen Touren stark einzugrenzen wird zu erst eine Vereinfachte Distanzmessung (keine Sonderregeln aktiv) zwischen den CPs durchgeführt (die Pfadsuche wird von einem CP mit Suchziel zweiter CP gestartet und die Anzahl an Züge dafür ermittelt). Hierbei kommt es für jeden Teilabschnitt zu Ungenauigkeiten, da die Pfadsuche hier immer mit Geschwindigkeitsvektor (0,0) startet.
• mithilfe der ermittelten Distanzen kann mittels Bruteforce (für 9 Fakultät ist dies schnell genug) das TSP gelöst werden
• die "Ungenauigkeiten" führen dazu, dass nicht notwendigerweise die real kürzeste Tour auch als solche erkannt wird, daher werden Touren untersucht, die kleiner sind als das Minimum plus 7 Züge (empirisch ermittelter Wert innerhalb dessen für alle Maps das globale Minimum gefunden wurde)
• durch die Vorarbeit lässt sich bei Rundkursen die Anzahl der zu untersuchenden Tour meist auf Eine einschränken, bei "freien" Strecken können abhängig von der Charakteristik der Map deutlich mehr Touren nötig sein
• wenn TC aktiviert sind, hat diese Betrachtung auch Nachteile, da die Entfernung zweier CPs deutlich geringer sein kann als ohne TCs. Dies kann dazu führen, dass KaBotte die kürzeste Tour nicht untersucht und deshalb längere Strecken fährt.
• da jede Tour vollständig unabhängig berechnet werden kann, wird jede von einem einzelnen Thread (4 Threads auf einem 4-Kern Prozessor) parallel berechnet. KaBotte skaliert dabei nahezu linear in Anzahl der Prozessorkerne.

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 Formel1 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 genanntem Winkelbereich bei der Zielüberquerung ausgefiltert

Zugwahl

• die möglichen Pfade stellen einen gerichteten Graphen zwischen Start (aktuelle Position) und Zieldurchfahrt dar
• der Algorithmus bewertet alle Züge bezüglich Blockwahrscheinlichkeit, Anzahl und Gewichtung der Nachfolger
• diese Information wird vom Pfadende bist zur aktuellen Zugwahl getragen, so dass schon früh auf u.a. Engstellen im Pfad reagiert werden kann
• Blockzüge werden im Zweifel bevorzugt

Erweiterungen

Sonderregeln

• hierfür werden bei der standardmäßigen Überprüfung auf Gültigkeit von Zügen ebenfalls auf die Sonderregeln hin überprüft und Züge gegebenenfalls aussortiert; 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 ausgehend 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 (hier muss noch eine Menge Feintuning stattfinden) werden als ungültig verworfen

Blocken

• Als Nebenprodukt des Kanalysators hat KaBotte die Fähigkeit des aktiven Blockens gewonnen
• das Berechnen eines Blocks kann beträchtlich länger dauern als die eigentliche Pfadsuche, da z.B. bei Massenstarts mehrere hundert Spielsituationen gerechnet werden müssen
• Nach der eigentlichen Pfadsuche vergleicht KaBotte ihre nächsten optimalen Züge mit Überschneidungen der Mitspieler, die diese Runde noch nicht gezogenen haben
• Für die optimalen Züge wird deren direkte Auswirkung auf die Pfadlänge der Gegner untersucht; der Zug, der zur stärksten Erhöhung führt, wird als nächster Zug gewählt
• Bei der TWM (noch nicht live getestet) unterscheidet KaBotte durch die User-Eigenschaften (ist Bot) in Mitspieler und Gegner und rechnet die Erhöhung der Pfadlänge der Gegner und Mitspieler gegen; nur falls den Gegner mehr Schaden entsteht als den Mitspielern, wird der Block durchgeführt
• der Gemüsegärtner maks wird nicht als Freund betrachtet (auch wenn das ein manchmal aufkommender Gedanke ist ;) )

Chatmodul

• KaBotte wird getriggert, wenn sie direkt angesprochen wird ("KaBotte, ...", "Hast du ma ne Mark, KaBotte?") oder im Text ihr Name mit "@" markiert ist "@KaBotte"
• funktioniert im Chat und auch im Bordfunk (wenn maximal ein Mensch am Spiel teilnimmt, reagiert KaBotte auf Nachrichten auch ohne Anrede mit ihrem Namen)
• Basiert auf einer Java-Implementierung von ELIZA und erweitert mit dem Wortschatz von A.L.I.C.E..
• Themen des aktuellen Zeitgeschehens wurden als Regeln eingefügt
• Spiele: Kopf oder Zahl; Stein, Schere, Papier (, Echse, Spock)
• Zeitansage ("Zeitansage")
• Einfache Rechnungen z.B. "KaBotte, rechne 4 + 5"
• sie kann "beatboxen", das selbe denken "denkst du das selbe", die karo-murphy gesetze aufsagen u.v.m.

Spiele erstellen

• auf Anforderung im Chat erstellt KaBotte ein Spiel mit euch ("spiel mit mir")
• "spiel mit ..." (Angabe der Mitspieler) erstellt ein Spiel mit dir, KaBotte und den angegebenen Mitspielern
• "spiel mit einigen"; eine Auswahl der Spiegeleier, die "wenig" blocken. Die Startplätze werden nur zu 2/3 gefüllt
• Kartenauswahl ist auf Maps mit einer Wertung > 3,3 und mindestens 3 Spielern eingestellt, ansonsten aber zufällig

Spielanalysen

• KaBotte reagiert auf das Schlüsselwort "Analyse" und gibt darauf hin im Boardfunk die Gesamtzahl der Züge jeden Spielers im optimalen Fall aus
• der Unterschied zu DeepGrays Analyse ist, dass dieser "nur" die Anzahl der Restzüge ausgibt

Tools

Kanalysator

• Spiele können auf Blocks und ungeschicktes Zugverhalten untersucht werden
• KaBotte berechnet für jeden Zug aus dem Gamelog die Gesamtlänge des Pfades ins Ziel, bei aufeinander folgenden Runden kann man feststellen, ob sich der Pfadlänge vergrößert hat und der Spieler sich somit verklickt hat oder aktiv von der Ideallinie abgewichen ist.
• Für jeden aktiven Zug wird dessen Auswirkung auf die Gesamtpfadlänge aller Mitspieler untersucht (dafür wird für alle Mitspieler ebenfalls eine komplette Pfadsuche durchgeführt). Wenn sich die Pfadlänge vergrößert, hat ein aktiver Block stattgefunden.
• Mit einer Erweiterung werden auch Rennen mit CPs unterstützt. Dafür muss KaBotte für alle zurückgelegten Pfade ermitteln welche CPs bereits überfahren wurden, da dies alleine aus dem Gamelog nicht mehr hervorgeht

MapAlyzor

• KaBotte führt eine Pfadsuche vom allen möglichen Startpunkten durch
• die Anzahl der optimalen Startpunkte wird ausgegeben
• die resultierenden Pfade werden darauf untersucht, wie breit deren Bottleneck (engste Stelle im optimalen Pfad) ist
• angedacht: die Wahrscheinlichkeit eines gegnerischen Blocks für jeden Zug auf dem optimalen Pfad
• Lust es selbst zu Testen?
  • Download des MapAlyzors. Die folgenden Libraries in den Ordner "KaBotte_lib" kopieren. Bei Fragen und Anmerkungen Telegramm an maks.
  • benötigte Libraries für den MapAlyzor: [EC8.1], [EC8.1Api], [Websocket], [JSON], [Jansi]
  • Zum Starten: java -jar KaBotte.jar -mapalyze:1;2;3 (der Parameter "mapalyze" erwartet nach dem Trenner ":" entweder die Id (oder eine Liste durch ";" getrennt) einer Map auf Karopapier oder den Namen einer Datei auf dem lokalen Computer) ausführen.

Verwendete Bibliotheken

• Eclipse Collections
• Java WebSockets
• JSON-java
• Javaluator