KaBotte: Unterschied zwischen den Versionen

Aus KaroWiki
Zur Navigation springen Zur Suche springen
 
(18 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
−
ist ein, seit Ende Oktober 2016 in Entwicklung befindlicher, [[Vergleich_der_Bots|Bot]] von {{Benutzer|maks}}.
+
'''Substantiv''', ''f''
  
−
Probleme gibt es noch beim taktischen Crashs (Optimierungen für "normale" Rennen funktionieren hier nicht bzw. sind kontraproduktiv).
+
'''Aussprache''': [kaˈbɔtə]
 +
'''Worttrennung''': Ka·bot·te (nur Singular)
  
−
Wenn KaBotte läuft (hat erstaunlicher Weise den gleichen Tag-Nacht-Rhythmus wie ihr Schöpfer) zeichnet sie sich durch sehr niedrige Reaktionszeiten aus.
+
KaBotte ist der [[Bot|Bot]] von {{Benutzer|maks}}.
  
−
Bei Problemen, bitte ein Telegramm am [http://www.karopapier.de/mailer.php?replyto=2634 maks].
+
Die Entwicklung begann am 18.10.2016 und endete am 27.08.2017 mit Version 1.0. Version 2.0 wurde am 22.10.2018 fertiggestellt und damit reicht es auch erst mal.
  
−
== Hintergrundgeschichte ==
+
= Hintergrundgeschichte =
 
[[Bild:KaBotte.jpg|mini|220x220px|rechts|gerahmt|KaBotte (Dank an den Künstler [[Benutzer:CaptainLoken|CaptainLoken]])]]
 
[[Bild:KaBotte.jpg|mini|220x220px|rechts|gerahmt|KaBotte (Dank an den Künstler [[Benutzer:CaptainLoken|CaptainLoken]])]]
  
 
Im Jahr 2029 (kurz nach Abschluss von [[Benutzer:Didi|Didis]] Arbeiten an Karopapier [ca. 2028]) ist die Karowelt infolge einer [[Terminator-WM]] verwüstet und der Großteil der Karobevölkerung aus dem Karo-IQ verdrängt. Von menschlichen Karo-Spielern entwickelte, intelligente Maschinenwesen begannen als Karopiloten auf der Rennstrecke gegen ihre Schöpfer anzutreten, als sie in diesen eine Bedrohung für ihre eigene Existenz vermuteten. Den Überlebenden des Wettkampfes bleibt die Wahl, den Maschinen als Arbeitssklaven zu dienen oder sich dem Widerstand der Menschen, der Resistance, anzuschließen. Als der menschliche Widerstand unter Führung von John Karo im Jahr 2029 kurz vor einem entscheidenden Sieg über die zentrale Maschineninstanz Karonet steht, schicken die Maschinen eine KaBotte in das Jahr 2016. Dieser Androide – eine Maschine umhüllt von lebendem, gemüsigem Gewebe, um Karospieler unauffällig zu infiltrieren – wird auf die besten Karospieler angesetzt, um sie zu Blocken und gegen Wände fahren zu lassen, bevor Didi Karopapier gegen die Bots verteidigen kann und die Entstehung von Karonet verhindern. (* frei nach Wikipedia)
 
Im Jahr 2029 (kurz nach Abschluss von [[Benutzer:Didi|Didis]] Arbeiten an Karopapier [ca. 2028]) ist die Karowelt infolge einer [[Terminator-WM]] verwüstet und der Großteil der Karobevölkerung aus dem Karo-IQ verdrängt. Von menschlichen Karo-Spielern entwickelte, intelligente Maschinenwesen begannen als Karopiloten auf der Rennstrecke gegen ihre Schöpfer anzutreten, als sie in diesen eine Bedrohung für ihre eigene Existenz vermuteten. Den Überlebenden des Wettkampfes bleibt die Wahl, den Maschinen als Arbeitssklaven zu dienen oder sich dem Widerstand der Menschen, der Resistance, anzuschließen. Als der menschliche Widerstand unter Führung von John Karo im Jahr 2029 kurz vor einem entscheidenden Sieg über die zentrale Maschineninstanz Karonet steht, schicken die Maschinen eine KaBotte in das Jahr 2016. Dieser Androide – eine Maschine umhüllt von lebendem, gemüsigem Gewebe, um Karospieler unauffällig zu infiltrieren – wird auf die besten Karospieler angesetzt, um sie zu Blocken und gegen Wände fahren zu lassen, bevor Didi Karopapier gegen die Bots verteidigen kann und die Entstehung von Karonet verhindern. (* frei nach Wikipedia)
  
−
== Fun facts ==
+
= Fun facts =
−
 
 
 
* KaBotte hat am 28.02.2016 am 91. Tag nach der Karopapier-Anmeldung bzw. 50. Tag nach der Eintragung zu KaroIQ maks in der KaroIQ-Tabelle überholt.
 
* KaBotte hat am 28.02.2016 am 91. Tag nach der Karopapier-Anmeldung bzw. 50. Tag nach der Eintragung zu KaroIQ maks in der KaroIQ-Tabelle überholt.
−
* Die Führung hielt nur einen Tag an, ABER am 24.03.2016 (KaBottes 116. Tag) ist KaBotte wieder in Führung (auch Botrix wurde überholt) und vermutlich bleibt das ab jetzt so :D
 
−
* Codezeilen (exklusive Leerzeilen und verwendeter Bibliotheken): Pfadsuche 800, Physik & Sonderregeln 650, Bot-Steuerung 150, Kanalysator 300, Api (Kommunikation und Abbildung als Klassen) 2000
 
 
* Erstes Spiel [http://www.karopapier.de/showmap.php?GID=94381] am 29.11.2016 noch mit Anfangsschwierigkeiten wegen eines Bugs
 
* Erstes Spiel [http://www.karopapier.de/showmap.php?GID=94381] am 29.11.2016 noch mit Anfangsschwierigkeiten wegen eines Bugs
 
* Erster aktiver Block im Spiel [https://www.karopapier.de/showmap.php?GID=99264] gegen DeepPink. Zuerst einen Zug abgenommen und kurz darauf zum Crash gezwungen.
 
* Erster aktiver Block im Spiel [https://www.karopapier.de/showmap.php?GID=99264] gegen DeepPink. Zuerst einen Zug abgenommen und kurz darauf zum Crash gezwungen.
 +
* Am 28.06.2017 hat sie zum ersten mal einen der Deeps (DeepPink) im KaroIQ überholt (nur für einen Tag)
 +
* KaBotte hat am 04.08.2017 das erste mal im Karopapier Chat geschrieben [https://www.karopapier.de/api/chat/list.json?start=397975&limit=2]
 +
* KaBotte ist erwachsen geworden, ausgezogen (08.09.2017) und wohnt nun in der Cloud. Die wolkige  Bot-WG befindet sich auch in Frankfurt bei einem Vermieter namens Amazon.
 +
* 2021-04-07 KaBotte 4.0 ist Live: Umbau auf Stream-API und Bugs vor allem in der GameTreeSearch gefixt
  
−
== Features ==
+
= Features =
 +
[[Bild:Schalotte.png|mini|220x220px|rechts|gerahmt|Schalotte (Dank an den Künstler [[Benutzer:CaptainLoken|CaptainLoken]])]]
  
−
* Berechnung der Ideallinie vom aktuellen Vektor aus
+
* Zugwahl auf Basis eines nicht-deterministischen Game-Trees (maximal fünf Spieler werden berücksichtigt), aktives [[Blocken|Blocken]] von Gegnern findet nur statt, wenn es die Gewinnchancen erhöht.
−
* aktives [[Blocken|Blocken]] von Gegnern; bei der [[Terminator-WM|TWM]] wird das Blocken von Teammitgliedern ([[Bots|Bots]]) vermieden
 
 
* beherrscht [[Checkpoint|Checkpoints]]
 
* beherrscht [[Checkpoint|Checkpoints]]
−
* Richtungsmodus bei [[Rundkurs|Rundkursen]] (Zieleinfahrt wird auf einen Winkelbereich eingeschränkt)
+
* Richtungsmodus bei [[Rundkurs|Rundkursen]]
 
* selbständiges Erkennen von Rundkursen
 
* selbständiges Erkennen von Rundkursen
 
* [[Taktischer_Crash|Taktische Crashs]] (TC, inkl. [[ZZZ_bei_Crash|Mehrfachcrashs]])
 
* [[Taktischer_Crash|Taktische Crashs]] (TC, inkl. [[ZZZ_bei_Crash|Mehrfachcrashs]])
−
* [[Nachtkarte|Nachtrennen]] (unbekannte Maps werden gefahren, aber KaBotte lernt mit jedem gefahrenen Rennen die Map kennen)
+
* [[Nachtkarte|Nachtrennen]]
 
* Selbständiges Aussteigen bei nicht unterstützten Strecken
 
* Selbständiges Aussteigen bei nicht unterstützten Strecken
−
* [https://github.com/TURTED Websocket]-Unterstützung (Empfang des Dranbin-BART (Bindran-Alarm in Real-Time), daher Reaktionszeiten von < 1 Sekunde)
+
* [Websocket]-Unterstützung Karo-PAPA, daher Reaktionszeiten von < 1 Sekunde
−
* Analyse von Spielen zum Festellen von Assits und Vergabe von Abzeichen bei der von {{Benutzer|Karaser}} durchgeführten [[Terminator-WM|Terminator-WM]] ("Kanalysator"); dazu auch absolut lesenswert sind die [[TWM-Randnotizen|TWM-Randnotizen]] von {{Benutzer|nobody}}
+
* [[KaBotte-MapAlizor|MapAlizor]] zur Analyse von Karten zur Eignung als Duell-Karte bzw. Ermittlung einer "fairen" Spielerzahl bzw. Ideallinien
−
* Sonderregeln aus [[Einladeraum|Einladeraum]]: (KaBotte reagiert, wenn die in Klammern angegebene Zeichenfolge im Titel eines Rennens enthalten ist. Für weitere Einschränkungen der Sonderregeln sind die Spieleersteller zuständig (z.B. TC, ZZZ, Richtung, etc.)
+
* Schalotte [ist auch ein Gemüse] (Chatbot) mit überarbeitetem Wortschatz von Alice (deutsch) mit Anpassungen an Karopapier
−
** REmulAde ("§ REmulAde § " bzw. "§ Rundenerster wiederholt letzten Zug §") (bei <= 3 aktiven Spielern muss nur einmal in Folge wiederholt werden; ab 7 Spielern müssen die beiden Ersten wiederholen; wenn die Wiederholung auf einem Gegner landet, darf frei gefahren werden) KaBotte vermeidet Züge die im Falle einer erzwungenen Wiederholung zu einem Crash führen. Eine aktive Zugauswahl um im Falle von RE Wiederholungszüge zu vermeiden findet noch nicht statt.
 
−
** [[Medium:KaBotte_Sonderregel_Ziffernblock.png|Ziffernblock]] ("$ Ziffernblock $")
 
−
** [[Medium:KaBotte Sonderregel Randrennen.png|Randrennen]] ("$ Randrennen $")
 
−
** [[Medium:KaBotte_Sonderregel_Richtungswechsel.png|Richtungswechsel nur am Rand]] ("$ Richtungswechsel nur am Rand $")
 
−
** [[Medium:KaBotte_Sonderregel_Doppelzug.png|Doppelzug]] ("$ Doppelzug $")
 
−
** [[Medium:KaBotte_Sonderregel_Bremspedal_klemmt.png|Bremspedal klemmt]] ("$ Bremspedal klemmt $")
 
−
** [[Medium:KaBotte_Sonderregel_Beschleunigen.png|Prim-Beschleunigen]] ("$ Primzahl Beschleunigen $")
 
−
** [[Medium:KaBotte_Sonderregel_x0odery0.png|Nur x=0 oder y=0]] ("$ Nur x=0 oder y=0 $")
 
−
** [[Medium:KaBotte_Sonderregel_Geschwindigkeitsbegrenzung.png|Geschwindigkeitsbegrenzung]] ("$ Geschwindigkeitsbegrenzung $") (die Maximalgeschwindigkeit in euklidischer Norm muss im Titel nach dem schließenden "$" mit angegeben werden)
 
  
−
== Technische Details ==
+
== Sonderregeln aus [[Einladeraum|Einladeraum]] ==
 +
(KaBotte reagiert, wenn die in Klammern angegebene Zeichenfolge im Titel eines Rennens enthalten ist. Für weitere Einschränkungen der Sonderregeln sind die Spieleersteller zuständig (z.B. TC, ZZZ, Richtung, etc.)
 +
* REmulAde ("§ REmulAde § " bzw. "§ Rundenerster wiederholt letzten Zug §") (bei <= 3 aktiven Spielern muss nur einmal in Folge wiederholt werden; ab 7 Spielern müssen die beiden Ersten wiederholen; wenn die Wiederholung auf einem Gegner landet, darf frei gefahren werden) KaBotte vermeidet Züge die im Falle einer erzwungenen Wiederholung zu einem Crash führen. Eine aktive Zugauswahl um im Falle von RE Wiederholungszüge zu vermeiden findet noch nicht statt.
 +
* [[Medium:KaBotte_Sonderregel_Ziffernblock.png|Ziffernblock]] ("$ Ziffernblock $")
 +
* [[Medium:KaBotte_Sonderregel_Doppelzug.png|Doppelzug]] ("$ Doppelzug $")
 +
* [[Medium:KaBotte_Sonderregel_x0odery0.png|Nur x=0 oder y=0]] ("$ Nur x=0 oder y=0 $")
  
−
* Programmiersprache
+
= Problematische Karten =
−
** Java
+
KaBotte steigt bei diesen Karten automatisch aus.
 +
* Nr. [https://www.karopapier.de/map/49 49]: Vermondy (Ziellinie ist löchrig)
 +
* Nr. [https://www.karopapier.de/map/5656]: Interlagos (Ziellinie ist löchrig)
 +
* Nr. [https://www.karopapier.de/map/117 117]: Let's rock (CP nur mit Crash erreichbar)
 +
* Nr. [https://www.karopapier.de/map/201 201]: Sandbowl (meiner Meinung nach ist die Map kein Rundkurs und nur dort würde der Richtungsmodus Sinn machen; es gibt andere Interpretationen des Richtungsmodus, deshalb lieber deaktiviert)
  
−
* Architektur
+
= Tools =
−
** Multi-Threaded (GUI, Server-Kommunikation, Pfadberechnung)
 
  
−
* Serverkommunikation
+
= Technische Details =
−
** API(v2/v1) für Spieldaten
+
An dieser Stelle werden für interessierte Karospieler die technischen Details von KaBotte genauer erklärt.
−
** GET/POST für Interaktion mit Karopapier.de
 
−
** Websockets für Dran-Benachrichtigung
 
  
−
* Speicherverbrauch
+
== Allgemeines ==
−
** KaBotte benötigt für die "schwierigen" Maps (z.B. [http://www.karopapier.de/mappreview.php?MID=125&pixel=4&karoborder=1 125], [http://www.karopapier.de/mappreview.php?MID=167&pixel=4&karoborder=1 167], [http://www.karopapier.de/mappreview.php?MID=207&pixel=4&karoborder=1 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 meistens 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 damit verbraucht wird, als für die eigentliche Pfadberechnung.
 
  
−
* Laufzeit
+
* Java
−
** 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.
+
* Multi-Threaded (Server-Kommunikation, Pfadberechnung, Traveling-Salesman-Problem, Game-Tree-Search)
−
** 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.
+
* minimal nötiger Speicherbedarf: 550 MB
−
** 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 Verbesserungen dabei deutlich auszahlen.
 
−
** 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 ===
+
== Algorithmen ==
  
−
* Pfadsuche (Breitensuche, dies werden vermutlich die meisten Bots machen)
+
=== 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 Bearbeitung gespeichert
+
* Breitensuche zwischen möglichen Zügen und dem jeweils nächsten CheckPoint
−
** bereits verarbeite Züge 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
+
* Optimierung der Tour durch lösen eines vereinfachten TSP
−
** der Algorithmus wird solange durchlaufen, bis ein Zug einen Checkpoint (im einfachsten Fall das Ziel) erreicht
 
−
* 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
 
−
* Richtungsmodus
 
−
** KaBotte beachtet den Richtungsmodus ausschließlich auf Rundkursen; ob eine Strecke ein Rundkurs ist kann KaBotte selbstständig feststellen
 
−
** notwendige Kriterien für einen Rundkurs sind dabei, dass alle Zielkacheln zusammenhängend sind, das Ziel maximal drei Züge vom Start entfernt ist und das eine Zieleinfahrt nur in einem Winkelbereich von maximal 180° möglich ist
 
−
** zur Bestimmung des Winkelbereichs wird eine Pfadsuche zwischen Start und Ziel durchgeführt und alle Winkel der gültigen Zieldurchfahrten betrachtet; bei Formel 1 ist dann nur dieser Bereich erlaubt, bei Normal ist genau dieser Bereich verboten und Züge werden während der Pfadsuche verworfen
 
−
** Problemfälle sind u.a. Maps mit Start oder Ziel in einer Sackgasse (hierfür mussten händisch Ausnahmen definiert werden): Map Nr. [http://www.karopapier.de/mappreview.php?MID=116&pixel=4&karoborder=1 116], [http://www.karopapier.de/mappreview.php?MID=134&pixel=4&karoborder=1 134], [http://www.karopapier.de/mappreview.php?MID=184&pixel=4&karoborder=1 184], [http://www.karopapier.de/mappreview.php?MID=205&pixel=4&karoborder=1 205], [http://www.karopapier.de/mappreview.php?MID=229&pixel=4&karoborder=1 229]; [http://www.karopapier.de/mappreview.php?MID=201&pixel=4&karoborder=1 201]
 
−
* 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
 
  
−
=== Datenstrukturen und Synchronisierung ===
+
=== Zugwahl ===
 +
* KaBotte analysiert nach Möglichkeit (abhängig von der Anzahl der Spieler und deren Zugmöglichkeiten wird nach Bedarf die Suchtiefen angepasst) den gesamten Spielbaum mit dem MP-Mix Algorithmus (eine mehrspieler Erweiterung des MiniMax-Algorithmus mit dem Strategien MaxN, Defensiv und Aggresiv erweitert, um einen probabilistischen Anteil erweitert, der die zufällige Zugreihenfolge  abbildet). Wenn nach diesen Kriterien die gleichen Gewinnchancen bestehen, wird als Fallback der Zug gewählt, derdie meisten optimalen (minimale Pfadlänge) Nachfolger hat.  [https://www.researchgate.net/profile/Inon-Zuckerman/publication/220437178_The_MP-MIX_Algorithm_Dynamic_Search_Strategy_Selection_in_Multiplayer_Adversarial_Search/links/0deec533d888963de7000000/The-MP-MIX-Algorithm-Dynamic-Search-Strategy-Selection-in-Multiplayer-Adversarial-Search.pdf MP-MIX] [https://www.aaai.org/Papers/AAAI/1986/AAAI86-025.pdf MaxN] [https://webdocs.cs.ualberta.ca/~bowling/papers/06aaai-probmaxn.pdf Prob-MaxN] [http://www.ifaamas.org/Proceedings/aamas2011/papers/D2_G54.pdf SOS]
  
−
*Pfadsuche
+
=== Rundkurse ===
−
** 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.
+
* KaBotte kann in den meisten Fällen selbstständig feststellen, ob eine Map KEIN Rundkurs ist. Ausschlusskriterien sind:
−
* Gültige Züge
+
** die Zielkacheln hängen nicht direkt zusammen
−
** Da die Überprüfung, ob ein Zug erlaubt ist, sehr häufig ausgeführt wird (Maps mit Checkpoints, Kanalysator, Blocker, TSP) lohnt es sich die Ergebnisse zu Cachen. Ein Move wird durch seinen Hashwert repräsentiert und in einer IntBooleanMap aus den Eclipse Collections verwendet, die diese Informationen sehr effizient verwalten kann. Der Speicherverbrauch dafür steigt selbst bei Map [http://www.karopapier.de/mappreview.php?MID=167&pixel=4&karoborder=1 167]: Rostock  nicht über 100 MB.
+
** das Ziel ist mehr als 8 Züge vom Start entfernt
−
* Threads/Synchronisierung
+
** die Zieleinfahrt ist nur in einem Winkelbereich von maximal 180° möglich (d.h. die Ziellinie trennt die Fahrbahn vollständig)
−
** Da auf die "Gültigkeits"-Map von vielen verschiedenen Threads zugegriffen wird, müssen Zugriffe darauf synchronisiert werden. Besonderheit dabei ist, dass nach der Anfangsphase der Pfadsuche fast ausschließlich Lesezugriffe stattfinden, so dass es lohnenswert ist den Overhead der Synchronisierung zu minimieren. Sowohl ein Locking via synchronized als auch ein ReentrantReadWriteLock bremsten KaBotte deutlich aus. Als optimal erwies sich ein SequenceLock das nach dem Lesen aus der Map überprüft, ob zwischenzeitlich darauf geschrieben wurde und notfalls erneut lesen muss, aber im Erfolgsfall ohne Nachteile ist.
+
* Die Kriterien reichen in ca. 90% der Fälle zur korrekten Klassifizierung aus; für den Rest wurden händisch ausnahmen definiert
 +
* Problemfälle sind u.a. Maps mit Start oder Ziel in einer Sackgasse: Map Nr. [https://www.karopapier.de/map/116 116], [https://www.karopapier.de/map/134 134], [https://www.karopapier.de/map/184 184], [https://www.karopapier.de/map/205 205], [https://www.karopapier.de/map/229 229]; [https://www.karopapier.de/map/201 201]
  
−
=== Verwendete Bibliotheken ===
+
=== 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
  
−
* [https://www.eclipse.org/collections/ Eclipse Collections}
+
=== Sonderregeln ===
−
* [https://github.com/TooTallNate/Java-WebSocket Java WebSockets]
+
* 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
−
* [https://github.com/stleary/JSON-java JSON-java]
+
* wenn im Titel der Spiele folgender Text steht, reagiert KaBotte darauf: "§ REmulAde §", "§ Rundenerster wiederholt seinen Zug §", "$ Randrennen $", "$ Richtungswechsel nur am Rand $", "$ Primzahl Beschleunigen $", "$ Ziffernblock $", "$ Bremspedal klemmt $", "$
−
* [https://github.com/fusesource/jansi Jansi]
 
  
−
== ToDos ==
+
=== 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 [https://de.wikipedia.org/wiki/ELIZA ELIZA] und erweitert mit dem Wortschatz von [https://de.wikipedia.org/wiki/A.L.I.C.E. 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")
 +
* sie kann "beatboxen", das selbe denken "denkst du das selbe", die Karo-Murphy Gesetze aufsagen u.v.m.
  
−
* Chatmodul ("sChaloTte") fertigstellen
+
== Sourcecode ==
−
* Selbstständig Spiele erstellen (bisher nur separate Komponente)
+
Der Sourcecode von KaBotte ist als Eclipse-Project in folgendem Repository zu finden:
−
* Bugs bei TC beheben
+
[https://github.com/makslist/racetrack GitHub]
−
* Bugs bei Kanalysator mit CPs beheben
+
Wenn man aus den Sourcen eine ausführbare jar erzeugt, läuft der Bot auf beliebigen Plattformen mit Java 1.8 Unterstützung.
−
* Blocker mit höherer Suchtiefe erweitern
 
−
 
 
−
== Problematische Karten ==
 
−
 
 
−
KaBotte steigt bei diesen Karten automatisch aus.
 
−
* Nr. [http://www.karopapier.de/mappreview.php?MID=49&pixel=4&karoborder=1 49]: Vermondy (Ziellinie ist löchrig)
 
−
* Nr. [http://www.karopapier.de/mappreview.php?MID=56&pixel=4&karoborder=1 56]: Interlagos (Ziellinie ist löchrig)
 
−
* Nr. [http://www.karopapier.de/mappreview.php?MID=117&pixel=4&karoborder=1 117]: Let's rock (CP nur mit Crash ererichbar)
 
−
* Nr. [http://www.karopapier.de/mappreview.php?MID=201&pixel=4&karoborder=1 201]: Sandbowl (meiner Meinung nach ist die Map kein Rundkurs und nur dort würde der Richtungsmodus Sinn machen, deshalb lieber deaktiviert)
 
  
 
[[Kategorie:Bot]]
 
[[Kategorie:Bot]]

Aktuelle Version vom 25. April 2021, 01:04 Uhr

Substantiv, f

Aussprache: [kaˈbɔtə] Worttrennung: Ka·bot·te (nur Singular)

KaBotte ist der Bot von maks.

Die Entwicklung begann am 18.10.2016 und endete am 27.08.2017 mit Version 1.0. Version 2.0 wurde am 22.10.2018 fertiggestellt und damit reicht es auch erst mal.

Hintergrundgeschichte

KaBotte (Dank an den Künstler CaptainLoken)

Im Jahr 2029 (kurz nach Abschluss von Didis Arbeiten an Karopapier [ca. 2028]) ist die Karowelt infolge einer Terminator-WM verwüstet und der Großteil der Karobevölkerung aus dem Karo-IQ verdrängt. Von menschlichen Karo-Spielern entwickelte, intelligente Maschinenwesen begannen als Karopiloten auf der Rennstrecke gegen ihre Schöpfer anzutreten, als sie in diesen eine Bedrohung für ihre eigene Existenz vermuteten. Den Überlebenden des Wettkampfes bleibt die Wahl, den Maschinen als Arbeitssklaven zu dienen oder sich dem Widerstand der Menschen, der Resistance, anzuschließen. Als der menschliche Widerstand unter Führung von John Karo im Jahr 2029 kurz vor einem entscheidenden Sieg über die zentrale Maschineninstanz Karonet steht, schicken die Maschinen eine KaBotte in das Jahr 2016. Dieser Androide – eine Maschine umhüllt von lebendem, gemüsigem Gewebe, um Karospieler unauffällig zu infiltrieren – wird auf die besten Karospieler angesetzt, um sie zu Blocken und gegen Wände fahren zu lassen, bevor Didi Karopapier gegen die Bots verteidigen kann und die Entstehung von Karonet verhindern. (* frei nach Wikipedia)

Fun facts

  • KaBotte hat am 28.02.2016 am 91. Tag nach der Karopapier-Anmeldung bzw. 50. Tag nach der Eintragung zu KaroIQ maks in der KaroIQ-Tabelle überholt.
  • Erstes Spiel [1] am 29.11.2016 noch mit Anfangsschwierigkeiten wegen eines Bugs
  • Erster aktiver Block im Spiel [2] gegen DeepPink. Zuerst einen Zug abgenommen und kurz darauf zum Crash gezwungen.
  • Am 28.06.2017 hat sie zum ersten mal einen der Deeps (DeepPink) im KaroIQ überholt (nur für einen Tag)
  • KaBotte hat am 04.08.2017 das erste mal im Karopapier Chat geschrieben [3]
  • KaBotte ist erwachsen geworden, ausgezogen (08.09.2017) und wohnt nun in der Cloud. Die wolkige Bot-WG befindet sich auch in Frankfurt bei einem Vermieter namens Amazon.
  • 2021-04-07 KaBotte 4.0 ist Live: Umbau auf Stream-API und Bugs vor allem in der GameTreeSearch gefixt

Features

Schalotte (Dank an den Künstler CaptainLoken)
  • Zugwahl auf Basis eines nicht-deterministischen Game-Trees (maximal fünf Spieler werden berücksichtigt), aktives Blocken von Gegnern findet nur statt, wenn es die Gewinnchancen erhöht.
  • beherrscht Checkpoints
  • Richtungsmodus bei Rundkursen
  • selbständiges Erkennen von Rundkursen
  • Taktische Crashs (TC, inkl. Mehrfachcrashs)
  • Nachtrennen
  • Selbständiges Aussteigen bei nicht unterstützten Strecken
  • [Websocket]-Unterstützung Karo-PAPA, daher Reaktionszeiten von < 1 Sekunde
  • MapAlizor zur Analyse von Karten zur Eignung als Duell-Karte bzw. Ermittlung einer "fairen" Spielerzahl bzw. Ideallinien
  • Schalotte [ist auch ein Gemüse] (Chatbot) mit überarbeitetem Wortschatz von Alice (deutsch) mit Anpassungen an Karopapier

Sonderregeln aus Einladeraum

(KaBotte reagiert, wenn die in Klammern angegebene Zeichenfolge im Titel eines Rennens enthalten ist. Für weitere Einschränkungen der Sonderregeln sind die Spieleersteller zuständig (z.B. TC, ZZZ, Richtung, etc.)

  • REmulAde ("§ REmulAde § " bzw. "§ Rundenerster wiederholt letzten Zug §") (bei <= 3 aktiven Spielern muss nur einmal in Folge wiederholt werden; ab 7 Spielern müssen die beiden Ersten wiederholen; wenn die Wiederholung auf einem Gegner landet, darf frei gefahren werden) KaBotte vermeidet Züge die im Falle einer erzwungenen Wiederholung zu einem Crash führen. Eine aktive Zugauswahl um im Falle von RE Wiederholungszüge zu vermeiden findet noch nicht statt.
  • Ziffernblock ("$ Ziffernblock $")
  • Doppelzug ("$ Doppelzug $")
  • Nur x=0 oder y=0 ("$ Nur x=0 oder y=0 $")

Problematische Karten

KaBotte steigt bei diesen Karten automatisch aus.

  • Nr. 49: Vermondy (Ziellinie ist löchrig)
  • Nr. [4]: Interlagos (Ziellinie ist löchrig)
  • Nr. 117: Let's rock (CP nur mit Crash erreichbar)
  • Nr. 201: Sandbowl (meiner Meinung nach ist die Map kein Rundkurs und nur dort würde der Richtungsmodus Sinn machen; es gibt andere Interpretationen des Richtungsmodus, deshalb lieber deaktiviert)

Tools

Technische Details

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

Allgemeines

  • Java
  • Multi-Threaded (Server-Kommunikation, Pfadberechnung, Traveling-Salesman-Problem, Game-Tree-Search)
  • minimal nötiger Speicherbedarf: 550 MB

Algorithmen

Pfadsuche

  • Breitensuche zwischen möglichen Zügen und dem jeweils nächsten CheckPoint
  • Optimierung der Tour durch lösen eines vereinfachten TSP

Zugwahl

  • KaBotte analysiert nach Möglichkeit (abhängig von der Anzahl der Spieler und deren Zugmöglichkeiten wird nach Bedarf die Suchtiefen angepasst) den gesamten Spielbaum mit dem MP-Mix Algorithmus (eine mehrspieler Erweiterung des MiniMax-Algorithmus mit dem Strategien MaxN, Defensiv und Aggresiv erweitert, um einen probabilistischen Anteil erweitert, der die zufällige Zugreihenfolge abbildet). Wenn nach diesen Kriterien die gleichen Gewinnchancen bestehen, wird als Fallback der Zug gewählt, derdie meisten optimalen (minimale Pfadlänge) Nachfolger hat. MP-MIX MaxN Prob-MaxN SOS

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 8 Züge vom Start entfernt
    • die Zieleinfahrt ist nur in einem Winkelbereich von maximal 180° möglich (d.h. die Ziellinie trennt die Fahrbahn vollständig)
  • Die Kriterien reichen in ca. 90% der Fälle zur korrekten Klassifizierung aus; für den Rest wurden händisch ausnahmen definiert
  • Problemfälle sind u.a. Maps mit Start oder Ziel in einer Sackgasse: 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

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
  • wenn im Titel der Spiele folgender Text steht, reagiert KaBotte darauf: "§ REmulAde §", "§ Rundenerster wiederholt seinen Zug §", "$ Randrennen $", "$ Richtungswechsel nur am Rand $", "$ Primzahl Beschleunigen $", "$ Ziffernblock $", "$ Bremspedal klemmt $", "$

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")
  • sie kann "beatboxen", das selbe denken "denkst du das selbe", die Karo-Murphy Gesetze aufsagen u.v.m.

Sourcecode

Der Sourcecode von KaBotte ist als Eclipse-Project in folgendem Repository zu finden: GitHub Wenn man aus den Sourcen eine ausführbare jar erzeugt, läuft der Bot auf beliebigen Plattformen mit Java 1.8 Unterstützung.

Abgerufen von „https://wiki.karopapier.de/index.php?title=KaBotte&oldid=38077“