Softwareentwickler / Programmierer / Fachinformatiker
InformatiCup Logo

InformatiCup 2021 | Projekt im Rahmen des Studiums

Gemeinsam mit einem Kommilitonen hab ich an der diesjährigen Ausgabe vom InformatiCup der Gesellschaft für Informatik teilgenommen. Hierbei ging es darum, einen Lösungsvorschlag in einer beliebigen Programmiersprache zu entwickeln, die bei dem Spiel spe_ed im Vergleich zu den Lösungen der anderen Teams möglich oft gewinnt.

Die Teilnahme am InformatiCup ist für alle Studierenden in Deutschland möglich. Die Universität Oldenburg unterstützt dabei insofern, als dass eine Anrechnung als Modul im Rahmen des Studiums möglich ist.

Erlernen neuer Technologien

Der Wettbewerb gab uns als Team die Möglichkeit, viele neue Technologien kennenzulernen. Dazu zählt das Erlernen einer neuen Programmiersprache, da wir uns für eine Entwicklung in Python entschieden haben. Darüber hinaus haben wir viele Funktionalitäten von GitHub eingesetzt und auf Pull Requests und automatisierte Builds mit GitHub Actions gesetzt. Zudem haben wir eine umfangreiche Dokumentation in LaTeX verfasst und konnten Docker kennenlernen, da die Abgabe eines Dockerfiles gefordert war.

Unsere Lösungsidee

Aber auch die reine Programmierung war herausfordernd. Die grundsätzlichen Spielregeln sind recht einfach und vergleichbar bspw. mit „Achtung, die Kurve!“ oder „Curvefever“. Eine Spielfigur bewegt sich auf einem rechteckigen Spielfeld und kann in jeder Spielrunde eine 90-Grad-Wendung machen oder die Geschwindigkeit ändern. Dabei zieht die Figur eine Spur hinter sich her, die für alle Spieler ein Hindernis darstellt. Der zuletzt überlebende Spieler gewinnt das Spiel. Da bei der Maximalzahl von sechs Spielern die Anzahl möglicher Spielzüge mit jeder betrachteten Runde sehr stark steigt, ist eine Vorhersage der gegnerischen Spieler sehr schwierig und in der Zeit von maximal 15 Sekunden für einen Spielzug fast unmöglich zu berechnen.

Daher mussten andere Lösungsansätze her. Zuerst stand die Idee im Raum, auf maschinelles Lernen zu Setzen. Diese wurde aber schnell verworfen, da dieser Ansatz eher wenig vielversprechend erschien. Letztendliches besteht unser Lösungsvorschlag für den InformatiCup aus der Kombination von mehreren Ansätzen. Zuerst wählt der Algorithmus ohne Betrachtung der Gegner die Aktionen aus, die den eigenen Spieler auch für die nächsten Runden die Möglichkeit geben, nicht direkt in ein Hindernis zu laufen. Anschließend bestimmt dieser zufällige Punkte auf dem Spielfeld und ein Pathfinding-Algorithmus berechnet, wie viele dieser Punkte nach den vorher gefilterten Aktionen erreichbar sind und entsprechend absteigend sortiert. Dies verhindert, dass die Figur in Sackgassen läuft. Im letzten Schritt werden in einer Baumstruktur alle möglichen Szenarien nur mit den Gegnern in der Nähe für die nächsten 3 Spielrunden simuliert. Das Ergebnis wird mit dem des Pathfinding-Algorithmus verglichen und anhand einer Gewichtung eine Entscheidung für die nächste Aktion getroffen.

Fazit

Insgesamt war die Teilnahme am Wettbewerb eine sehr interessante Erfahrung und ich konnte mich in einige Technologien einarbeiten, für die sonst keine Module an der Universität angeboten werden. Das Endergebnis inklusive der Dokumentation ist in folgendem GitHub-Repository zu finden: jonashellmann/informaticup21-team-chillow

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.