Sechster Programmierwettbewerb

Gestrandet auf einer Insel und kein Entkommen. Nirgends gibt es eine Axt, um Bäume für ein Floß zu fällen. Und auch Essen gibt es hier nicht üppig. Immerhin nerven keine Kannibalen, aber dafür scheint der Meeresspiegel immer weiter zu steigen. Wer hält am längsten den Kopf über Wasser?

Spielidee

Die Idee für den diesjährigen freiesMagazin-Programmierwettbewerb stammt von dem Spiel „Die verbotene Insel“, wobei die Regeln etwas angepasst wurden.

Man schlüpft im Wettbewerb in die Rolle eines auf einer einsamen Insel gestrandeten Menschen. Auf der Insel kann man sich bewegen und auch überflutete Inselfelder trockenlegen. Die Flut steigt im Laufe des Spiels aber immer höher, sodass viele Teile der Insel unwiederbringlich untergehen und verloren sind. Wenn man sich auf so ein untergegangenes Feld bewegt bzw. das Feld, auf dem man steht, untergeht, wird man von den Fluten erfasst und das Spiel ist vorbei.

Im Gegensatz zur Spielvorlage gibt es keine anderen Spieler zur Interaktion und es müssen auch keine Schätze geborgen werden.

Das Spiel im Detail

Jede Runde des Spiels läuft immer gleich ab. Zuerst hat der Spieler/Bot drei Aktionen, die er beliebig aus folgenden Aktionen wählen kann:

  • Man kann sich auf ein Nachbarfeld bewegen oder stehen bleiben. Die Bewegung darf dabei nur horizontal oder vertikal erfolgen, man darf nicht diagonal laufen. Es ist erlaubt, überflutete Felder zu betreten. Untergegangene Felder sollten nicht betreten werden.
  • Man kann ein Nachbarfeld oder das eigene Feld trockenlegen. Auch hier darf man nicht diagonal trockenlegen. Ein überflutetes Feld ist dann wieder trocken. Untergegangene Felder können nicht trocken gelegt werden.

Danacht steigt gegebenenfalls die Flut. Es gibt 10 Flutkarten, wovon nur 2 die Flut steigen lassen. Von diesen Karten wird jede Runde zufällig eine gezogen und beiseite gelegt. Ist es eine der beiden Flut-steigt-Karten, erhöht sich die Anzahl der zu überflutenden Inselfelder ab der aktuellen Runde um eins (siehe unten). Wenn also eine Flut-steigt-Karte gezogen wird, wird ab dieser Runde ein Inselfeld mehr überflutet.

Wird eine Flut-steigt-Karte gezogen, werden zusätzlich die bereits überfluteten Felder auf dem Ablagestapel gemischt und oben auf den Auswahlstapel gelegt (siehe unten). Das heißt, dass kürzlich überflutete Felder sehr schnell erneut überflutet werden. Untergegangene Felder werden nicht wieder hinzugefügt.

Es wird auf diese Art jede Runde eine neue Karte gezogen, bis der Flutkarten-Stapel leer ist. Dann werden die zehn Karten zusammengemischt und neu gezogen. Das heißt, alle 10 Runden wird neu gemischt und in den 10 Runden ist die Flut immer um zwei Level gestiegen.

Wichtige Änderung 02.01.2013: Das Flutlevel erreicht bei dem Wert 7 sein Maximum. Das heißt, in den ersten Runden steigt sieben Mal die Flut und danach bis zum Ende des Spiels nicht mehr. Somit werden pro Runde auch maximal 7 Felder überflutet.

Nach der Flut, wird eine bestimmte Anzahl von Feldern vom Auswahlstapel gezogen. Die Anzahl ist am Anfang des Spiels 0, steigt aber immer weiter durch gezogene Flutkarten (siehe oben). Der Auswahlstapel besteht am Spielanfang aus allen nicht untergegangenen Feldern. Wird ein Feld gezogen, wird es überflutet und auf den Ablagestapel gelegt. Ein trockenes Feld wird in dem Fall einfach nur überflutet, ein überflutetes Feld geht unwiederbringlich verloren. Da neu zu überflutende Felder nur vom Auswahlstapel gezogen werden und nicht vom Ablagestapel, wird ein überflutetes Feld nicht mehr überflutet, bis die Flut steigt (siehe oben). Ausnahme: Müssen mehr Felder überflutet werden als noch im Auswahlstapel verfügbar sind bzw. ist der Auswahlstapel leer, wird nach dem Ziehen der Ablagestapel gemischt und weiter gezogen. Dies kann dazu führen, dass ein Feld zweimal pro Runde überflutet wird.

Am Schluss wird noch geprüft, ob der Spieler/Bot auf einem nun untergegangenem Feld steht. Falls ja, ist das Spiel vorbei, ansonsten beginnt eine neue Runde.

Kommunikation für eigenen Bot

Die Kommunikation geschieht wie schon beim letzten Wettbewerb über die Standardeingabe und -ausgabe. Das heißt, der eigene Bot muss über STDIN die Befehle des Server entgegennehmen und entsprechend seine Antwort auf STDOUT schreiben.

Folgende Kommandos müssen vom Bot verstanden werden:

GAMEBOARDSTART X,Y
Es wird ein neues Spielbrett mit X Spalten und Y Zeilen übertragen.
...oo##oo#..
So in der Art kann eine übertragene Zeile des Spielbretts aussehen. Die Symbole bedeuten:
.
Wasser  /  untergegangenes Feld
o
geflutetes Feld
#
Land  /  trockenes Feld

Es werden Y Zeilen übertragen und jede Zeile enthält X Zeichen.

GAMEBOARDEND
Die Spielbrettübertragung ist zu Ende.
ROUND Z X,Y
Runde Z beginnt. Der Bot steht aktuell auf Feld (X,Y). Das Spielbrett beginnt links oben bei (1,1). Nach diesem Befehl erwartet der Server exakt drei Kommandos mit GO/DRY (siehe unten).
INCRFLOOD Z
Die Flut steigt um ein Level Z an, d. h. es werden Z mehr Felder als vorher überflutet. Z darf auch 0 sein.
FLOOD X,Y
Das Feld (X,Y) wird geflutet. War es noch trocken, ist es nun überflutet. War es schon überflutet, ist es nun untergegangen. Das Spielbrett beginnt links oben bei (1,1).
END
Das Spiel ist zu Ende. Der Bot kann/soll sich jetzt beenden.

Folgende Kommandos können vom Bot an den Server gesendet werden:

GO ...
Der Bot geht ein Feld in eine bestimmte Richtung. Erlaubte Richtungen sind:
NORTH
Der Bot geht ein Feld nach oben.
EAST
Der Bot geht ein Feld nach rechts.
SOUTH
Der Bot geht ein Feld nach unten.
WEST
Der Bot geht ein Feld nach links.
CURRENT
Der Bot bleibt auf dem aktuellen Feld stehen.
DRY ...
Der Bot legt ein überflutetes Feld in einer bestimmten Richtung trocken. Erlaubte Richtungen sind:
NORTH
Der Bot legt das Feld oberhalb von ihm trocken.
EAST
Der Bot legt das Feld rechts von ihm trocken.
SOUTH
Der Bot das Feld unterhalb von ihm trocken.
WEST
Der Bot legt das Feld links von ihm trocken.
CURRENT
Der Bot legt das Feld trocken, auf dem er steht.

War das aktuelle Feld überflutet, ist es nun wieder trocken.

Alle Zahlen X, Y und Z bei der Kommunikation sind Ganzzahlen. Die Befehle sollen exakt wie oben beschrieben mit bzw. ohne Leerzeichen und Kommata verstanden bzw. ausgegeben werden.

wettbewerb_kommunikation.png
Die Kommunikation zwischen dem Server und einem Bot in zwei Beispielrunden.

Spiele-Engine und Referenz-Bot

Um seinen eigenen Bot testen zu können, benötigt man die Dateien, die später den Wettbewerb verwalten werden. Das gesamte Paket kann als Tar-Archiv heruntergeladen und muss entpackt werden:

$ tar -xzf freiesmagazin-2012-12-contest.tar.gz
$ cd freiesmagazin-2012-12-contest

Spiele-Engine

Die Dateien der Engine, dass heißt der Verwaltung, die den Bot ausführt und das Lesen der Spieldateien übernimmt, nimmt den größten Teil des Archives ein. Die Engine ist in C++ programmiert, sodass man einen C++-Compiler plus die notwendigen Entwicklungspakete benötigt.

Danach kann man die Engine wie folgt kompilieren:

$ cd src
$ make
$ cd ..

Referenz-Bot

Der Referenz-Bot im Ordner bots/dummybot soll nur grob veranschaulichen, wie man die Bibliotheken der Spiele-Engine nutzen kann, um mit deren Hilfe einen eigenen Bot aufzubauen. Der Bot selbst ist sehr dumm, denn er bleibt einfach stehen, bis er mit dem Inselfeld untergeht. Der Referenz-Bot wird unter der GNU General Public License veröffentlicht.

Den Referenz-Bot kann man wie folgt kompilieren. Zuvor muss die Engine kompiliert worden sein.

$ cd bots/dummybot
$ make
$ cd ../..

Spiel starten

Will man den Dummy-Bot oder seinen eigenen Bot testen, geht dies aus dem Hauptverzeichnis über

$ ./start.sh "fields/simple.txt" "bots/dummybot/bot"

Im Verzeichnis fields befinden sich Testinseln, die aber nicht für den späteren Wettbewerb benutzt werden.

Grafische Oberfläche

Für die Analyse des eigenen Bots (und der Engine), gibt es eine grafische Oberfläche (GUI), welche die Aktionen eines Bots nachspielen kann.

Für die Kompilierung benötigt man Qt4 (Pakete libqt4-dev und qt4-qmake). Danach kann man die GUI über

$ cd gui
$ qmake && make

kompilieren.

Um ein Logfile zu erhalten, muss man die Engine mit der Option --log starten und die Ausgabe in einer Datei speichern:

$ ./start.sh "fields/simple.txt" "bots/dummybot/bot" --log |& tee bot.log

Danach kann man die GUI über

$ ./gui

starten.

GUI bedienen

Nach dem Laden eines Logfiles über den Knopf „Open game file“, kann man den Ablauf wie folgt steuern:

Start
Spiel wird fortgesetzt – oder neu gestartet, wenn man am
Ende steht.
Stop
Spiel wird im Ablauf angehalten.
Go to line
Springt zur aktuell ausgewählten Zeile im Editor. Auf
diese Art kann man bei der Fehlersuche gezielt an eine bestimmte Stelle
springen.
Single step
Ist der Einzelschritt aktiviert, arbeitet ein Start
nur die aktuelle Zeile ab. Der Einzelschritt wirkt nicht auf „Go to
line
“.
Reset
Setzt die Abarbeitung auf den Anfang zurück.

Im Menü gibt es noch den Punkt „Game -> Quit“, um das Spiel zu beenden.

wettbewerb_gui.png
Die GUI kann bereits geführte Spiele anzeigen.

Informationen zum Wettbewerb

Ablauf

Nach Abgabeschluss werden die Bots nacheinander auf verschiedenen, bisher noch nicht näher definierten Inseln ausgesetzt und 1000 Mal ihrem Schicksal überlassen. Aus den 1000 Iterationen wird der Mittelwert der überlebten Rundenanzahl bestimmt, um die Zufallskomponente (das Überfluten der Felder und Ziehen der Flutkarten) auszugleichen. Wir behalten uns vor, die Anzahl der Iterationen noch zu erhöhen, wenn es sinnvoll erscheint.

Danach wird das gemittelte Rundenergebnis aller Inseln addiert und bildet die Endwertung. Ein Bot muss damit nicht auf allen Inseln perfekt agieren, aber im Mittel muss er besser sein als die anderen.

Der Bot mit der höchsten Rundensumme gewinnt den Wettbewerb.

Teilnahmebedingungen

Jeder Teilnehmer darf genau einen Bot einreichen. Mit jeder Einreichung testen wir den Bot auf den vorhandenen Inselfeldern und geben eine Rückmeldung, wie gut der Bot sich in etwa schlägt. Wir versuchen auch auf offensichtliche Fehler hinzuweisen, wenn uns das möglich ist. Es lohnt sich also, einen Bot früh einzureichen. Ein Teilnehmer kann seinen Bot bis zum Abgabeschluss bis zu fünfmal nachbessern. Die Begrenzung soll verhindern, dass wir ein Teilnehmer seinen Bot mit verschiedenen Strategien bei uns austestet.

Es ist erlaubt, im Team zu arbeiten, sodass mehrere Leute einen Bot gemeinsam einreichen. Den Preis muss sich das Team dann aber teilen.

Die Mitglieder der freiesMagazin-Redaktion sind von der Teilnahme ausgeschlossen, weil diese zum einen Zugriff auf alle andere Bots und zum anderen auch viel früher von diesem Wettbewerb erfahren haben.

Programmiersprache

Die benutzte Programmiersprache ist wie immer freigestellt. Das Projekt sollte aber auf einem „Standard-Linux-Rechner“ (d. h. mit einer aktuellen Linux-Distribution, z. B. Ubuntu 12.04) ohne Probleme kompilier- und ausführbar sein. Es ist natürlich nicht verboten, sein Programm unter Windows oder Mac zu entwickeln, solange es am Ende auf einem Linux-Rechner läuft.

Die Programme müssen selbst geschrieben sein und im Quelltext eingereicht werden, der unter einer Open-Source-Lizenz veröffentlicht werden muss. Hier helfen wir gerne bei der Auswahl einer passenden Lizenz weiter, sollten Fragen zu diesem Thema auftauchen. Reine Binärpogramme werden wir nicht annehmen oder testen.

Für die Bots ist es natürlich erlaubt, den Quelltext und die Bibliotheken der Referenz-Implementierung (siehe unten) unter Beachtung der Lizenz zu nutzen, um auf dieser Basis einen eigenen Bot zu erstellen.

Laufzeit

Die Laufzeit der Bot-Programme (inkl. Server-Ausführung) sollte natürlich so gering wie möglich sein. Für die Teilnahme am Wettbewerb sollten pro Runde maximal 0.1 Sekunden benötigt werden, da der Wettbewerb sonst zu lange dauert.

Als Beispiel kann man die Ablaufdauer der Insel island.txt nutzen:

$ /usr/bin/time -f "%e sec" ./start.sh fields/island.txt bots/dummybot/bot
(II) ROUNDS: 77
0.02 sec

Die Ausführung dürfte bei dem Dummy-Bot und der Rundenanzahl also maximal 7.7 Sekunden dauern!

Wichtig: Bash-Nutzer müssen den vollen Pfad zum time-Befehl angeben, damit nicht das eingebaute Shell-Kommando benutzt wird. Man kann von dem eingebauten Shell-Kommando die reale Laufzeit (real) aber auch ablesen.

Preise

Normalerweise vergeben wir Preisgelder bzw. Buchgutscheine, wovon wir dieses Jahr abweichen und trotzdem auf eine rege Teilnahme hoffen.

Für die ersten drei Plätze gibt es folgende Preise:

Der Gewinner darf sich zuerst einen Preis aussuchen, dann der Zweite und zuletzt der Dritte.

wettbewerb_preise.jpg
Diese Preise des diesjährigen Programmierwettbewerbs.

Zusätzlich gibt es für die ersten zehn Plätze (für die Nicht-Gewinner sozusagen als Trostpreis) eine Doppel-CD des diesjährigen Free! Music! Contest 2012.

Wettbewerbsdauer

Der Wettbewerb beginnt am 1. Dezember 2012 und endet am 31. Januar 2013. Die Teilnehmer können so hoffentlich die ggf. freien Tage zwischen den Jahren nutzen, um einen Bot zu programmieren.

Alle Einsendungen sollten per E-Mail unter redaktion ETT freiesmagazin PUNKT de bis zu diesem Stichtag bei der Redaktion eingegangen sein. Programme, die uns später erreichen, können leider nicht mehr berücksichtigt werden.

Insel erstellen

Jeder Wettbewerbsteilnehmer darf zusätzlich eine Insel erstellen und einreichen, die dann auch für den Wettbewerb genutzt wird. Die Größe der Insel ist dabei auf 1000 Felder begrenzt. Zur Erstellung kann man einfach die Insel von simple.txt oder island.txt als Vorlage nehmen und abändern. Die Syntax ist dabei identisch zur Übertragung des Spielfeldes an den Bot:

GAMEBOARDSTART 8,1
...o#...
GAMEBOARDEND
ROUND 1 4,1

Nach GAMEBOARDEND kann man optional auch mittels der ROUND-Angabe bestimmen, wo der Bot in der ersten Runde starten soll. Das zu startende Feld muss dabei valide sein, d.h. auf der Insel liegen und kein untergegangenes Feld sein. Der Start auf einem überflutetem Feld ist erlaubt.

Schlussbemerkungen

Wir wünschen allen Teilnehmern viel Erfolg und freuen uns auf zahlreiche Einsendungen. „Immer schön den Kopf über Wasser halten …“

Quellcode zur Teilnahme

PS: Um immer auf den aktuellen Stand zu sein, was den Wettbewerb angeht, kann man die Kommentare zu dieser Seite per RSS abonnieren. Kommentare können hier aber nur vom freiesMagazin-Team verfasst werden!

Regel-Update 01.12.2012

Regel-Update 01.12.2012

Zitat: „Ein überflutetes Feld wird nicht mehr überflutet, bis die Flut steigt.“

Ergänzung hierzu: „Ausnahme: Müssen mehr Felder überflutet werden als noch verfügbar sind, wird nach dem Ziehen der Ablagestapel gemischt und weiter gezogen. Dies kann dazu führen, dass ein Feld zweimal pro Runde überflutet wird.“

Bugfix 02.12.2012

Bugfix 02.12.2012

Ein Bot konnte sich auf ein untergegangenes Feld bewegen und danach weitere Kommandos ausführen. Es war damit möglich, „übers Wasser zu laufen“. Daneben konnte man ein untergegangenes Feld auch trocken legen, was ebenfalls nicht möglich sein sollte. Der Fehler führte zu einem Endlosprogramm, da das untergegangene Felder nicht mehr zur Auswahl beim Überfluten stand.

Bugfix 03.12.2012

Bugfix 03.12.2012

Der Bot stand in der Datei "start.sh" in Anführungszeichen, was er natürlich nicht darf, da sonst Argumente mit zur ausgeführten Datei zählen.

Skript-Update 06.12.2012

Update 06.12.2012:

Die Skripte wurde etwas aktualisiert, sodass man nun den gesamten Wettbewerb auf allen Feldern starten kann. Zusätzlich wird alles in Logfiles ausgegeben und ausgewertet.

Code-Update 07.12.2012

Code-Update 07.12.2012:

Das Spielbrett (Gameboard) kann nun kopiert werden.

Skript-Update 07.12.2012

Skript-Update 07.12.2012

Es wurde ein neues Skript ./start_single_contest hochgeladen, mit dem man seinen Bot auf allen Inselfeldern testen kann.

Regel-Update 13.12.2012

Regel-Update 13.12.2012

Da die Auswahl der zu überflutenden Felder und die Ablage nicht ganz klar waren, wurde dies näher spezifiziert:

„Wird eine Flut-steigt-Karte gezogen, werden zusätzlich die bereits überfluteten Felder auf dem Ablagestapel gemischt und oben auf den Auswahlstapel gelegt (siehe unten). [...]“

„Nach der Flut, wird eine bestimmte Anzahl von Feldern vom Auswahlstapel gezogen. [...] Der Auswahlstapel besteht am Spielanfang aus allen nicht untergegangenen Feldern. Wird ein Feld gezogen, wird es überflutet und auf den Ablagestapel gelegt. [...] Da neu zu überflutende Felder nur vom Auswahlstapel gezogen werden und nicht vom Ablagestapel, wird ein überflutetes Feld nicht mehr überflutet, bis die Flut steigt (siehe oben). Ausnahme: Müssen mehr Felder überflutet werden als noch im Auswahlstapel verfügbar sind, wird nach dem Ziehen der Ablagestapel gemischt und weiter gezogen. Dies kann dazu führen, dass ein Feld zweimal pro Runde überflutet wird.“

Regel-Update 13.12.2012

Regel-Update 13.12.2012

Sobald der Bot den Befehl END empfängt, ist das Spiel vorbei.

Es wurde nun explizit hinzugefügt, dass der Bot sich dann auch beenden soll.

Update 22.12.2012

Update 22.12.2012:

  • GUI merkt sich Pfad zu zuletzt geöffneter Datei
  • Format der Inselfelder geändert mit GAMEBOARDSTART und GAMEBOARDEND, sodass man diese direkt in der GUI einlesen kann
  • Taste „F5“ zum Neueinlesen einer Datei; erleichtert die Erstellung/Prüfung von Inseln mit Hilfe der GUI

Update 23.12.2012

Update 23.12.2012:

  • Spielerdaten in GUI zurücksetzen, wenn neue Datei geöffnet wird
  • Start-Position in Spieldatei mittels ROUND 1 X,Y setzen

Bugfix 24.12.2012

Bugfix 24.12.2012

Fehlerausgabe, wenn ein untergegangenes Feld trocken gelegt werden soll. Auf die Art sieht man, wenn sich der eigene Bot falsch verhält.

Regel-Update 27.12.2012

Regel-Update 27.12.2012:

Nach einer kurzen Berechnung hat sich gezeigt, dass die vorherige Laufzeitbegrenzung von 1 Sekunde pro Runde etwas zu großzügig bemessen war. Aus dem Grund wird die Laufzeit auf maximal 0.1 Sekunden pro Runde begrenzt. Als Beispiel kann man die Ablaufdauer der Insel island.txt nutzen:

$ /usr/bin/time -f "%e sec" ./start.sh fields/island.txt bots/dummybot/bot
(II) ROUNDS: 77
0.02 sec

Die Ausführung dürfte bei dem Dummy-Bot und der Rundenanzahl also maximal 7.7 Sekunden dauern!

Wichtig: Bash-Nutzer müssen den vollen Pfad zum time-Befehl angeben, damit nicht das eingebaute Shell-Kommando benutzt wird. Man kann von dem eingebauten Shell-Kommando die reale Laufzeit (real) aber auch ablesen.

Code-Update 01.01.2013

Code-Update 01.01.2013:

Es gab zwei Updates: Zum einen wurde das Kommando-Fenster in der GUI etwas breiter gemacht, damit man Debug-Ausgaben besser lesen kann.

Als zweites Update kann man über

$ make GRPOF=Y

eine Laufzeitanalyse erstellen, welche dann mit gprof ausgewertet werden kann. Dies ist für die meisten Teilnehmer nicht relevant, außer sie nutzen die libbot für ihren eigenen Bot und wollen die mitgelieferte Bibliothek analysieren.

Regel-Update 02.01.2013

Regel-Update 02.01.2013

Das Flutlevel erreicht nun bei dem Wert 7 sein Maximum. Das heißt, in den ersten Runden steigt sieben Mal die Flut und danach bis zum Ende des Spiels nicht mehr. Somit werden pro Runde auch maximal 7 Felder überflutet.

Die Änderung hat den Grund, dass im Laufe des Spiels irgendwann eine solche Fülle an Feldern überflutet wurden, dass die Taktik eines Bots eine untergeordneten Rolle spielte. Durch die Begrenzung auf den Wert 7 kann ein Bot länger agieren. Somit liegen die Ergebnisse der bisherigen Teilnehmer weiter auseinander, wobei sich die Reihenfolge nicht verändert hat.

Code-Update 04.01.2013

Code-Update 04.01.2013:

Die Fehlerausgabe vom 24.12.2012 wurde in eine Warnung gewandelt. Damit sieht man eine Ausgabe, wenn ein Bot (gewollt) ein untergagengenes Feld trocken legen will, die Engine bricht aber nicht sofort ab. So kann ein Bot länger überleben. Auf die Warnungen sollte man dennoch schauen!

Code-Update 07.01.2013

Code-Update 07.01.2013:

Wettbewerbsteilnehmer Markus Brenneis hatte die Idee für eine bessere Visualisierung die einzelnen Zeilen in der GUI verschiedenfarbig einzufärben. Dies wurde umgesetzt. Die zyklischen Server-Kommandos sind dabei grau hinterlegt, die zyklischen Bot-Kommandos nur farbig. Debug- und Fehlerausgaben sind zum schnelleren Erfassen sehr bunt markiert.

Code-Update 08.01.2013

Code-Update 08.01.2013:

Das Ausblenden von bestimmten Zeilen wurde in der GUI ermöglicht. So können Debug- und Informationsausgaben ebenso wie Server-Ausgaben ausgeblendet werden. Dies erleichtert mitunter die Übersicht bei der Analyse des eigenen Bots.

Inhalt abgleichen