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.

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:

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:

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.

Spiel starten

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

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

kompilieren.

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

Danach kann man die GUI über

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.

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:

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:

• das Computerspiel „Ankh – Herz des Osiris“ für Linux
• das Computerspiel „Jack Keane“ für Linux
• das Solo-Brettspiel „Pinguintanz“

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

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 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!