Erstellen eines Bots

Anmerkung: Version 0.1 - hier könnte noch einiges kommen ;)

Auf Bitte von ultimate ein paar Punkte und Hinweise für die Erstellung eines Bots.

Erste Überlegungen

1. Bevor der Bot angefangen wird - Mit welcher Taktik soll er seine Route bestimmen?
   Es ist wesentlich vor dem ersten Zeichen im Botcode festzulegen, welche Methode der Bot verwenden soll um seine Route zu fahren. je nachdem sind andere Punkte bei der Implementierung zu beachten und ändert sich die zu verarbeitende Datenmenge, die durchaus riesig ist.
   Soll er beispielsweise

   • Einfach mal drauflosfahren, wie es ein Mensch tun würde und nur einer groben Richtung folgen?*
   • Seine Route vom Start berechnen?
   • Seine Route vom Ziel berechnen?
   • Nur Zug für Zug denken?

2. In welcher Sprache wird der Bot geschrieben?
   Als Faustregel gilt: je einfacher eine Sprache zu schreiben ist, desto langsamer und Resourcen-hungriger ist der Bot, aber desto schneller wird der Bot seine ersten Züge machen.
   Allerdings ist erfahrungsgemäß ein Bot, der in C++ mit Maps arbeitet aufgrund der Menge an zu verarbeitenden Daten durchaus langsam. Es liegt also auch an der Art der Implementation.
3. Will ich alle Karten spielen können?
   Manche Karten können eine spezielle herausforderung für Bots sein. Beispielsweise Karte 117 "Let's Rock", die einen Crash benötigt um den CP zu durchfahren oder Karte 167 "Rostock", die so viele Wege bietet, dass es ewig dauert, diese zu berechnen. Je nach Ansatz kann - zumindest für den Anfang - hier einiges an Arbeit gespart werden. Zumindest für erstere empfehle ich Spiele dort einfach zu ignorieren. Ansonsten wird sich der Bot wahrscheinlich sehr lange verzögern, außer - und ich mag diesen Ansatz nicht - für den Bot wird hier eine Speziallinie vorgegeben.

Welche Daten brauche ich für den Bot, damit er weis was er tut und wie verarbeite ich sie?

• Didi listet die meisten Hilfsmittel im [KaroApiBrowser] auf.
• Was uns in der API fehlt sind die Aktionen die wir setzen müssen. Login, Ziehen und eventuell im Chat schreiben. Als einfachstes hat es sich herausgestellt dies über die Karo 1.0-Seiten zu tun.
  • Der Login geschieht über http://www.karopapier.de/anmelden.php.
    Ich verwende hier explizit die http-Variante, da wir davon ausgehen müssen, dass wir ggf. fehlerhafterweise irgendwo http statt https nutzen könnten und bei einem Login über https dann unser Keks nicht gilt.
    Der Login verwendet folgende Parameter:
    • ID: Unser Benutzername
    • PWD: Unser Passwort
  • Als Technik hierfür empfehle ich die Unix-Funktion curl, die auch in vielen Programmiersprachen repräsentiert wird, da diese einfach mit Cookies umgehen kann. Mit WGET wird dies wohl ein wenig komplizierter.
    Das Resultat müssen wir nur auf den String "Anmeldung erfolgreich" prüfen. Ist dieser vorhanden war der Login erfolgreich, wir haben einen Keks und können unseren Zug machen.
  • Für den Zug verwenden wir die https://www.karopapier.de/move.php. Alle Parameter müssen hier auch völlig korrekt berechnet sein, ansonsten wird der Zug nicht durchgeführt.
    Folgende Parameter werden hierfür benötigt:
    • GID: Bei welchem Spiel wollen wir überhaupt ziehen?
    • xpos: Was die x-Koordinate unseres Zielpunkts? Der Punkt ganz links hat die Zahl 0, danach geht es immer +1 weiter. Negative Punkte gibt es nicht.
    • ypos: Das selbe mit Y. Ganz oben ist 0, dann folgt 1 und so weiter.
    • xvec: Welchen Vektor fahren wir in x-Richtung?
    • yvec: Welchen Vektor fahren wir in y-Richtung?
    • movemessage(opt.): Sollten wir mal eine Nachricht mitsenden wollen, zum Beispiel weil uns ultimate mal wieder 3 Züge kostet, schicken wir diesen Parameter mit. Ansonsten lassem wir ihn weg.
  • Sollten wir mal Crashen müssen, rufen wir die https://www.karopapier.de/showmap.php nur mit der GID auf. Danach können wir mit dem Spiel ganz normal weiter arbeiten.
• Von der API (JSON-Codiert) benötigen wir folgende Daten:
  • http://www.karopapier.de/api/user/<MEINBOTNAME>/dran.json
    <MEINBOTNAME> wird entweder durch den Namen des Bots oder durch dessen SpielerID ersetzt. Die ID findet sich auch unter json->user->id im JSON-Objekt.
    Ansonsten benötigen wir normalerweise hier:
    • Alle Einträge unter dem Punkt "json->games". Normalerweise interssiert uns hier nur die ID des Spieles, beispielsweise json->games->0->id. Die 0 iterieren wir bis zu n-1 hoch, wobei n für die Anzahl der offenen Spiele steht.
  • http://www.karopapier.de/api/game/<GID>/details.json
    <GID>wird hier natürlich durch die im vorherigen Punkt extrahierte GID ersetzt. Wir benötigen hier:
    • json->map->mapcode
      Die landkarte für unseren Bot.
    • json->game->cps und json->map->cps
      Warum beide? game->cps kann auch true sein, obwohl die map keine CPS hat. Wenn wir wissen wollen, dass keine CPS vorhanden sind (was bedeutet wir dürfen beispielsweise nicht direkt vom Start über das Ziel fahren), müssen wir prüfen, dass json->game->cps false ist ODER json->map->cps leer ist.
      Ein Bot, der ohne CPs direkt ins Ziel fahren will, würde hiermit sonst sehr wirre Kreise vor der Startlinie auf manchen Karten ziehen und auf anderen mit 2 Zügen ins Ziel fahren.
    • json->players-><me>->moves-><last>->x, json->players-><me>->moves-><last>->y, json->players-><me>->moves-><last>->vx und json->players-><me>->moves-><last>->vy
      <me> ist durch den Eintrag definiert, an dem wir uns befinden (hierfür müssen wir alle nach unserem Namen oder unserer ID, je nach Präferenz durchsuchen) und <last> durch den letzten Eintrag im Moves-Array. Ich verwende hier explizit nicht json->players-><me>->lastmove, da sich dieser Eintrag mehrfach als fehlerhaft herausgestellt hat.
    • json->players-><me>->missingCps
      Ja wo müssen wir denn wohl noch durch an CPs?
    • json->players-><me>->dran
      Moment einmal, sollten wir doch sein, wenn wir durch die dran.json gegangen sind? Ja, aber nachdem es leider bei der API immer wieder zu Inkonsistenzen kommt.. besser 2 mal checken als einmal. Erfahrungsgemäß spart das eine Endlosschleife in der Programmierung.
    • json->players-><me>->possibles
      Wo erlaubt uns Didi hinzuziehen? Dankenswerterweise schon ausgerechnet wo wir landen würden. Was wir zur move.php schicken muss mit einer dieser Möglichkeiten übereinstimmen, dmait wir einen gültigen Zug bekommen.
      Ist die Liste leer müssen wir höchstwahrscheinlich crashen. Also: showmap.php aufrufen, eine Sekunde warten und es noch einmal versuchen. Wenns jetzt noch immer nicht klappt: Didi rufen und Spiel aus der Liste nehmen. Dann passt was nicht.

Mein Bot fährt! Aber wie fährt er "richtig"?

(Fast) jeder menschliche Spieler weis bei Betrachtung der Karte sofort, wie er fahren muss um eine komplette Runde zu fahren. Ein Bot kennt dies nicht, er würde (sofern er dabei nicht über den Start fahren muss) ohne CPs direkt ins Ziel gehen oder mit CPs falls es kürzer ist immer im F1-Modus fahren. Als erstes müssen wir den Parameter json->game->dir beachten.

• classic: Wir fahren nicht direkt über das Ziel (wenn es sich vermeiden lässt!)
• egal: fahr wie du willst (solange CPs vorhanden sind, ansonsten darfst du 1. nicht über Start und Ziel gleichzeitig und 2. falls es ein Rundkurs ist erst den Rundkurs fahren)
• formula1: fahr zuerst über das Ziel, dann deine Runde und dann noch einmal über das Ziel (sofern CPs vorhanden sind und es ein Rundkurs ist!)

An den Einschränkungen sieht man schon die Schwierigkeiten der diesbezüglichen Programmierung. Es gibt unendlich viele Möglichkeiten Karten zu bauen und dabei auch unendlich viele möglichkeiten, dass der Bot anders fährt als erwartet, weil wir diese Möglichkeit so nicht bedacht haben. Aus diesem Grund rate ich jedem explizit sich seine eigene Implementation zu überlegen, da mit fremden Ansätzen früher oder später Probleme auftauchen werden, die dann nur mir einem Neuschreiben gelöst werden können. Und wenn man die Implementation nicht genau kennt, wird dies ein schweres Unterfangen. Um ein paar Beispiele diesbezüglich zu nennen:

• Variante erlaubter Zielwinkel: der Bot darf nur von der anderen Seite in das Ziel fahren, als der Start ist:
  • Karte 101: Die Karte bildet einen Kreis, bei dem der Start als Anhang beigehängt ist - der Bot würde am Ziel vorbeifahren, umdrehen und mit einem erlaubten Winkel ins Ziel fahren.
  • Karte 148: Die Spirale: Wir müssen über einen Startpunkt fahren um ins Ziel zu kommen.
  • Karte 95: Moebius: Wir haben auf beiden Seiten des Starts ein Ziel und wir haben einen Rundkurs.
• Variante: Felder zwischen Start und Ziel sperren:
  • Karte 95: Moebius: Wie oben: Wir sind gezwungen über das Ziel zu fahren.
  • Karte 148: Die Spirale: Auch wie oben: wir müssen ein mal die Punkte zw. Start und Ziel überqueren.

Ich habe der Einfachheit halber Karte 148 und 95 bei beiden Beispielen genommen. Es gibt natürlich noch deutlich mehr Beispiele dafür. Ein gutes Beispiel für alle möglichen Probleme - abgesehen von der Größe - ist Karte 167 - "Rostock". Eventuell müssen wir hier die Ziele mit allen möglichen Routen überqueren können, können also diesbezüglich keine Einschränkungen machen. Die Lösung dieser Probleme ist eines der zeitaufwendigsten Projekte beim Bau eines Bots. Selbst die Deeps als älteste Bots, die dies beherrschen fahren die Karten nach menschlichen Maßstäben nicht immer perfekt. Für Slybotone wurde eine Kombination mehrerer Abfragen gewählt, die per Karte die beste Methode zur Sicherung der richtigen Linie wählen soll. Leider stellt sich immer wieder heraus, dass selbst eine Funktion von 100+ Codezeilen und mehreren Stunden Arbeitszeit diesbezüglich Schwachstellen aufweist.

Weiteres zu Bedenken:

• Formula1 sowie egal und eine Karte ohne CPs vertragen sich nicht. Eine Interpretation als Classic diesbezüglich wäre wünschenswert.
  Ich unterscheide derzeit grob 4 Fälle der Karten, in der Reihenfolge der Abfrage:

  1. Keine CPs
  2. Classic
  3. Formula1
  4. egal (Kombination der Routen aus Classic und Formula1)

Wichtige weitere Hinweise

• Es muss mindestens eine Sekunde Zeit zwischen 2 Zügen sein.
  Ansonsten kann es sein, dass Didis API durcheinanderkommt und wir falsche Daten geliefert bekommen. Daher sollte sicherheitshalber ein sleep 1 zwischen zwei Zügen sein.
• Baue Return-Codes für Züge! Wenn der Bot solange durchlaufen soll, bis alle Züge abgearbeitet sind, aber eine Karte aus einem Grund einfach nicht gefahren werden kann, muss diese aus der Liste genommen werden. Ansonsten haben wir eine Endlosschleife, bis das Script abbricht.
• Wenn der Bot öfter starten soll und die maximale Laufzeit des Scripts länger als ein Intervall ist, wäre es zu empfehlen ein Lockfile mit exklusivem Locking zu verwenden.
  Exklusives Locking ist zum Beispiel durch die Linux-Funktion flock zu erreichen und bedeutet, dass wenn ein Prozess einen exklusiven Zugriff auf eine Datei haben möchte, bekommt kein anderer Prozess mehr Zugriff. Wird der Prozess aber - aus welchem Grund auch immer - terminiert, so wird das Lock automatisch frei. Damit müssen wir uns nicht um ein "unlock" oder "was wäre wenn" Gedanken machen. Nur darum, dass der Bot nicht in eine Endlosschleife kommt.

ToDo

Punkte, über die ich noch etwas schreiben möchte:

• Ziel oder nicht Ziel? Wie fahre ich eine Runde, Hindernisse und Einschränkungen ( Karten mit verpflichtender Zieldurchfahrt nach dem start, mauer hinter dem start oder ziel durchfahrbar, mehrere starts und ziele,... Vor- und nachteile der varianten)
• Caching DB vs. File(s), Routenvarianten