Während der Corona-Zeit hat auch das digitale Spielen von Brettspielen deutlich zugenommen. Dies ist besonders für Spiele interessant, die stark von Computerunterstützung profitieren oder die eine sehr internationale Fangemeinde haben. Beides trifft auf die 18xx genannte Spielefamilie zu, die in den 70ern von Francis Tresham mit dem Spiel 1829 begründet wurde. Hier handeln SpielerInnen mit Aktien von Eisenbahnfirmen, die jeweils durch den/die SpielerIn mit den meisten Anteilen kontrolliert werden. Ein Aspekt dabei ist es, die Züge der jeweiligen Firma optimal im Schienennetz einzusetzen. Beginnend mit 1829, 1830, 1825, ... gibt es mittlerweile wohl über 200 verschiedene 18xx Spiele.
Die open-source Plattform 18xx.games erlaubt das asynchrone und synchrone Spielen von vielen dieser Spiele. Auch die Berechnung der optimalen Routen für die Züge der aktuellen Firma kann dabei vom Computer übernommen werden. Allerdings ist dies sehr langsam (das zugrundeliegende Problem ist NP-schwer) und es gibt einen festen Timeout an dem der Algorithmus aufgibt, oft sind die Routen dann klar suboptimal.
Ziel des Projekts ist eine Verbesserung des Routings für die 18xx.games Plattform. Teilaspekte davon sind:
* geeignete Modellierung des Schienennetzes als gewichteten Graph
* automatische Konvertierung von Spieldaten in einen gewichteten Graphen
* Vorverarbeitung und heuristische bzw. exakte Algorithmen für das Routing entwerfen und umsetzen
* (optional) Einbau des verbesserten Routings in 18xx.games
- Kursverantwortliche/r: Narek Bojikian