KaBotte: Unterschied zwischen den Versionen
Maks (Diskussion | Beiträge) |
Maks (Diskussion | Beiträge) |
||
Zeile 5: | Zeile 5: | ||
Es ist vollbracht! KaBoote ist feature-complete, aber noch nicht bug-free. | Es ist vollbracht! KaBoote ist feature-complete, aber noch nicht bug-free. | ||
− | |||
− | |||
Bei Problemen, bitte ein direktes Telegramm am [http://www.karopapier.de/mailer.php?replyto=2634 maks]. | Bei Problemen, bitte ein direktes Telegramm am [http://www.karopapier.de/mailer.php?replyto=2634 maks]. | ||
Zeile 17: | Zeile 15: | ||
== 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. 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 :( | + | * 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 :( | ||
== Features == | == Features == | ||
Zeile 30: | Zeile 29: | ||
* [https://github.com/TURTED Websocket]-Unterstützung (Empfang des Dranbin-BART (Bindran-Alarm in Real-Time), daher Reaktionszeiten von < 1 Sekunde) | * [https://github.com/TURTED Websocket]-Unterstützung (Empfang des Dranbin-BART (Bindran-Alarm in Real-Time), daher Reaktionszeiten von < 1 Sekunde) | ||
* 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.) | * 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) | + | ** 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_Ziffernblock.png|Ziffernblock]] ("$ Ziffernblock $") | ||
** [[Medium:KaBotte Sonderregel Randrennen.png|Randrennen]] ("$ Randrennen $") | ** [[Medium:KaBotte Sonderregel Randrennen.png|Randrennen]] ("$ Randrennen $") | ||
Zeile 45: | Zeile 44: | ||
Architektur: Multi-Threaded (GUI, Server-Kommunikation, Pfadberechnung) | Architektur: Multi-Threaded (GUI, Server-Kommunikation, Pfadberechnung) | ||
− | |||
− | |||
Serverkommunikation: API(v2/v1) für Spieldaten, GET/POST für Interaktion mit Karopapier.de, Websockets für Dran-Benachrichtigung | Serverkommunikation: API(v2/v1) für Spieldaten, GET/POST für Interaktion mit Karopapier.de, Websockets für Dran-Benachrichtigung | ||
− | == | + | == Algorithmen == |
− | *Pfadsuche (Breitensuche, dies werden vermutlich die meisten Bots machen) | + | * Pfadsuche (Breitensuche, dies werden vermutlich die meisten Bots machen) |
− | ** von jedem möglichen Zug werden alle neun Nachfolgezüge betrachtet und überprüft, ob sie den | + | ** 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 |
− | ** 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 | + | ** 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 |
− | ** der Algorithmus wird solange durchlaufen, bis ein Zug einen Checkpoint (im einfachsten Fall das Ziel) erreicht | + | ** der Algorithmus wird solange durchlaufen, bis ein Zug einen Checkpoint (im einfachsten Fall das Ziel) erreicht |
− | *Checkpoints | + | * Checkpoints |
− | *Richtungsmodus | + | ** 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 | + | * 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 | ||
== ToDos == | == ToDos == | ||
+ | * Chatmodul fertigstellen | ||
+ | * Analyse von Spielen zum Festellen von Assits bei der TWM | ||
* Verbesserte Heuristik zur Bestimmung des nächsten Zuges (insb. Blocken von Gegnern) | * Verbesserte Heuristik zur Bestimmung des nächsten Zuges (insb. Blocken von Gegnern) | ||
* Selbstständig Spiele erstellen (bisher nur separate Komponente) | * Selbstständig Spiele erstellen (bisher nur separate Komponente) |
Version vom 4. April 2017, 17:36 Uhr
ist ein, seit Ende Oktober 2016 in Entwicklung befindlicher, Bot von maks.
Die Serverkommunikation und Pfadberechnung haben einen stabilen Stand erreicht. Taktische Crash bereiten noch Probleme (erstaunlich kniffliges Problemfeld). Wenn KaBotte läuft (hat erstaunlicher Weise den gleichen Tag-Nacht-Rhythmus wie sein Schöpfer) zeichnet er sich durch sehr niedrige Reaktionszeiten aus.
Es ist vollbracht! KaBoote ist feature-complete, aber noch nicht bug-free.
Bei Problemen, bitte ein direktes Telegramm am maks.
Inhaltsverzeichnis
Hintergrundgeschichte
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.
- 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 :(
Features
- Berechnung der Ideallinie vom aktuellen Vektor aus
- beherrscht Checkpoints
- Richtungsmodus bei Rundkursen (Zieleinfahrt wird auf einen Winkelbereich eingeschränkt)
- selbständiges Erkennen von Rundkursen
- Taktische Crashs (TC, inkl. Mehrfachcrashs)
- Nachtrennen (unbekannte Maps werden gefahren, aber KaBotte lernt mit jedem gefahrenen Rennen)
- Selbständiges Aussteigen bei nicht unterstützten Strecken
- Websocket-Unterstützung (Empfang des Dranbin-BART (Bindran-Alarm in Real-Time), daher Reaktionszeiten von < 1 Sekunde)
- 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 $")
- Randrennen ("$ Randrennen $")
- Richtungswechsel nur am Rand ("$ Richtungswechsel nur am Rand $")
- Doppelzug ("$ Doppelzug $")
- Bremspedal klemmt ("$ Bremspedal klemmt $")
- Prim-Beschleunigen ("$ Primzahl Beschleunigen $")
- Nur x=0 oder y=0 ("$ Nur x=0 oder y=0 $")
- Geschwindigkeitsbegrenzung ("$ Geschwindigkeitsbegrenzung $") (die Maximalgeschwindigkeit in euklidischer Norm muss im Titel nach dem schließenden "$" mit angegeben werden)
Technische Details
Programmiersprache: Java
Architektur: Multi-Threaded (GUI, Server-Kommunikation, Pfadberechnung)
Serverkommunikation: API(v2/v1) für Spieldaten, GET/POST für Interaktion mit Karopapier.de, Websockets für Dran-Benachrichtigung
Algorithmen
- Pfadsuche (Breitensuche, dies werden vermutlich die meisten Bots machen)
- 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
- 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
- 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. 116, 134, 184, 205, 229; 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
ToDos
- Chatmodul fertigstellen
- Analyse von Spielen zum Festellen von Assits bei der TWM
- Verbesserte Heuristik zur Bestimmung des nächsten Zuges (insb. Blocken von Gegnern)
- Selbstständig Spiele erstellen (bisher nur separate Komponente)
Problematische Karten
KaBotte steigt bei diesen Karten automatisch aus.