KaBotte: Unterschied zwischen den Versionen

Aus KaroWiki
Zur Navigation springen Zur Suche springen
Zeile 31: Zeile 31:
 
Aus den möglichen Zügen wird immer einer gewählt, der zu einer minimalen Pfadlänge führt.
 
Aus den möglichen Zügen wird immer einer gewählt, der zu einer minimalen Pfadlänge führt.
  
2016-12-11: Ein Bug mit dem Richtungsmodus wurde behoben (Information, ob Rundkurs, muss manuell erfasst werden)
+
2016-12-11: Ein Bug mit dem Richtungsmodus wurde behoben (Information, ob es sich um einen Rundkurs, muss manuell erfasst werden)
  
 
2016-12-14: Rudimentäre GUI zur besseren Erfassung von Infos (z.B. Rundkurs)
 
2016-12-14: Rudimentäre GUI zur besseren Erfassung von Infos (z.B. Rundkurs)
  
2016-12-16: Implementierung eines genetischen Algorithmus zur Lösung des [https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden TSP] bei großen Karten
+
2016-12-16: Implementierung eines Algorithmus zur Lösung des [https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden TSP] bei großen Karten
 +
 
 +
2017-01-03: Cachen von nicht möglichen Zügen -> immenser SpeedUp bei Karten mit vielen CPs (einzige Ausnahme: Map [http://www.karopapier.de/mappreview.php?MID=167&pixel=4&karoborder=1 167]
 +
 
 +
2017-01-04: Defensive Strategie zur Zugwahl, um nicht zu Crashs gezwungen zu werden (erste Ergebnisse sind nicht so viel versprechend, wie erwartet)
 +
 
 +
2017-01-05: Ausbau des Multithreadings: Alle Einzelbestandteile werden in eizelnen Threads ausgeführt
 +
 
 +
2017-01-06: Websocket Unterstützung. KaBotte erhält die gleichen Nachrichten wie im Chat 2.1 und reagiert sofort darauf. Direkte Abfragen der offenen Spiele werden nur noch als Backup ausgeführt, falls der Websocket fehlschlägt.
  
 
== ToDos ==
 
== ToDos ==
  
Ausbau des Multi-Threadings bei bei der Pfadsuche zwischen den CPs
 
 
Caching bereits berechneter Pfade pro Spiel (im Augenblick wird jeder Zug komplett neu berechnet)
 
Caching bereits berechneter Pfade pro Spiel (im Augenblick wird jeder Zug komplett neu berechnet)
 
Heuristik zur Bestimmung des nächsten Zuges bzgl. Position der Gegner
 
Heuristik zur Bestimmung des nächsten Zuges bzgl. Position der Gegner
 +
Tests, ob KaBotte auf einem Android-Handy (wahrscheinlich deutlich Leistungsfähiger als das angedachte NAS) lauffähig ist
 +
Automatisches Aussteigen bei nicht unterstützten Maps oder Richtungsmodi-Kombinationen
  
 
[[Kategorie:Bot]]
 
[[Kategorie:Bot]]

Version vom 6. Januar 2017, 22:31 Uhr

ist ein, seit Ende Oktober 2016 in Entwicklung befindlicher, Bot von maks. Erklärtes Ziel von KaBotte ist es, Re-Rennen fahren zu können (das kann noch ein wenig dauern) und performant genug zu sein, um auf einem Synology-NAS (DS213j) zu laufen.

Problematische Karten

Nr. 117: ohne TCs

Nr. 167: die Größe des Suchbaums (9 Fakultät)

Funktionsweise

KaBotte bestimmt zu einem gegebenen Move die möglichen (nach Karo-Physik) Folgezüge. Die neuen Züge werden in einer Queue gespeichert, für den jeweils ersten Zug in der Queue wird dieser Vorgang solange wiederholt bis der gesuchte Checkpoint gefunden wurde oder die Queue leer ist. Wenn ein Checkpoint erreicht ist, wurde er in der minimal möglichen Anzahl der Zügen erreicht. siehe Breitensuche.

Richtungsmodus: Bei Rundkursen bestimmt KaBotte den möglichen Winkel-Bereich mit denen das Ziel überfahren werden kann und sperrt diesen bei Zielüberfahrten.

später mehr...

Facts

Programmiersprache: Java

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

Pfadberechnung: Breitensuche (Wege zwischen CPs), Tiefensuche (Suche des optimalen Pfades durch alle CPs zum Ziel)

aktueller Stand

Zur Zeit ist KaBotte in einer intensiven Testphase (läuft nur tagsüber) mit meinem Arbeitskollegen, die vollkommen freiwillig als Gegner für KaBotte herhalten müssen.

Der Bot beherrscht CPs (integraler Bestandteil) und TCs (kann zu sehr langer Laufzeit bei "großem" ZZZ führen). Aus den möglichen Zügen wird immer einer gewählt, der zu einer minimalen Pfadlänge führt.

2016-12-11: Ein Bug mit dem Richtungsmodus wurde behoben (Information, ob es sich um einen Rundkurs, muss manuell erfasst werden)

2016-12-14: Rudimentäre GUI zur besseren Erfassung von Infos (z.B. Rundkurs)

2016-12-16: Implementierung eines Algorithmus zur Lösung des TSP bei großen Karten

2017-01-03: Cachen von nicht möglichen Zügen -> immenser SpeedUp bei Karten mit vielen CPs (einzige Ausnahme: Map 167

2017-01-04: Defensive Strategie zur Zugwahl, um nicht zu Crashs gezwungen zu werden (erste Ergebnisse sind nicht so viel versprechend, wie erwartet)

2017-01-05: Ausbau des Multithreadings: Alle Einzelbestandteile werden in eizelnen Threads ausgeführt

2017-01-06: Websocket Unterstützung. KaBotte erhält die gleichen Nachrichten wie im Chat 2.1 und reagiert sofort darauf. Direkte Abfragen der offenen Spiele werden nur noch als Backup ausgeführt, falls der Websocket fehlschlägt.

ToDos

Caching bereits berechneter Pfade pro Spiel (im Augenblick wird jeder Zug komplett neu berechnet) Heuristik zur Bestimmung des nächsten Zuges bzgl. Position der Gegner Tests, ob KaBotte auf einem Android-Handy (wahrscheinlich deutlich Leistungsfähiger als das angedachte NAS) lauffähig ist Automatisches Aussteigen bei nicht unterstützten Maps oder Richtungsmodi-Kombinationen