Der letzte freiesMagazin-Programmierwettbewerb ist bereits zwei Jahre her. Eine Abstimmung im September 2013 zeigte, dass die Leser und potentiellen Wettbewerbsteilnehmer das meiste Interesse daran hatten, den Film „Tron“ bzw. das Lightcycle-Rennen darin umzusetzen. 2013 ergab es sich leider nicht, aber dieses Jahr ist es wieder so weit: Der siebte freiesMagazin-Programmierwettbewerb kann beginnen.

Aufgabe

Die Aufgabe ist sehr simpel: In einer Arena treten zwei Bots gegeneinander an. Jede Runde können sie sich entscheiden, nichts zu tun oder sich um 90 Grad nach rechts oder nach links zu drehen. Danach bewegen sie sich automatisch ein Feld vorwärts. Hierbei besetzt jeder Bot das Feld, das er gerade verlässt, welches dadurch für jeden unpassierbar bleibt (auch für den Bot selbst). Wer bei einer Bewegung gegen eine Wand bzw. gegen ein besetztes Feld läuft/fährt, scheidet aus.

Die Idee des Spiels ist nicht neu und leitet sich von dem Film „Tron“ ab, der 1980 aufgrund seiner technischen Raffinesse für Aufsehen gesorgt hatte. In dem Film treten Computerprogramme in Lightcycle-Rennen gegeneinander an und versuchen sich gegenseitig den Weg abzuschneiden. Zu diesem Prinzip gab es auch schon einige Implementierungen. Als Solo-Variante mit leichter Variation ist vielen das Spiel unter dem Namen „Snake“ bekannt.

Kommunikation

Wie in den letzten Programmierwettbewerben soll die Teilnahme möglichst vielen Personen ermöglicht werden. Aus dem Grund wird auf ein Client-Server-Konzept gesetzt, über das das Spiel läuft. Die Teilnehmer müssen nur einen Bot programmieren, der die Server-Befehle von der Standardeingabe (STDIN) liest und eine Antwort auf der Standardausgabe (STDOUT) ausgibt. Durch einen Pipe-Mechanismus (um den sich der Client aber nicht kümmern muss) kann der Server so direkt mit jedem Client kommunizieren.

Der Kommunikationsablauf eines Spiels ist dabei wie folgt (ein > ist dabei ein Kommando vom Server an den Client, ein < die Antwort vom Client an den Server; beides dient nur der Illustration und ist nicht Teil der echten Kommunikation):

Jeder Befehl vom Server bzw. an den Server ist durch ein Zeilenende (\n) abgeschlossen.

Spielbrettübertragung

Am Anfang wird die Arena (das Spielbrett) vom Server an alle Clients (Bots) übertragen:

• GAMEBOARDSTART n,m – Dies startet die Spielbrettübertragung mit Breite n und Höhe m. Das heißt, es werden m Zeilen mit jeweils n Zeichen übertragen.
• .....#.... – Eine Zeile des Spielbretts. Leere Felder sind durch einen Punkt dargestellt, besetzte Felder durch eine Raute #.
• GAMEBOARDEND – Ende der Spielbrettübertragung.

Setzen der Teilnehmernummer

Vor Beginn des eigentlichen Spiels wird jedem Bot die eigene Teilnehmernummer übergeben:

• SET p – Teilt einem Client mit, dass er die Nummer p hat, wobei
  p bei 1 anfängt.

Im Wettbewerb selbst wird es nur die Nummer 1 und 2 geben, die Bots sollten aber so programmiert sein, dass sie auch mit mehr Teilnehmern umgehen können.

Wiederholter Rundenablauf

In jeder Runde wird zuerst allen noch nicht ausgeschiedenen Bots die Position aller anderen noch nicht ausgeschiedenen Bots mitgeteilt:

• POS p n,m DIR – Legt die Position eines Bots auf dem Spielbrett fest.
  p ist dabei die Botnummer, die bei 1 beginnt. n und m ist die Position auf dem Spielbrett in horizontaler bzw. vertikaler Richtung, die ebenfalls bei 1 beginnt. DIR gibt die Richtung an, in die der Bot gerade schaut und kann die Himmelsrichtungen NORTH, EAST, SOUTH und WEST annehmen.

Noch einmal der Hinweis: Die Position ausgeschiedener Bots wird nicht übertragen! Zusätzlich enthält p natürlich auch die eigene Spielernummer. Dies ist für die Startposition wichtig. Zusätzlich kann ein Client damit die eigene Position und Blickrichtung abgleichen.

Danach erfolgt der Befehl an den Client, eine Entscheidung zu treffen, was der Bot tun soll:

• ROUND r – Startet die Runde r. Der Wert r muss nicht ausgewertet werden.

Der Server erwartet nun vom Client eine Antwort. Ausgeschiedene Bots bekommen diesen Befehl natürlich nicht mehr zugesendet und müssen daher auch nicht antworten.

Client-Bewegung des Bots

Der Client hat drei Befehle zur Auswahl, wie er auf ein ROUND antworten kann:

• RIGHT – Dreht den Bot um 90 Grad nach rechts.
• LEFT – Dreht den Bot um 90 Grad nach links.
• AHEAD – Dreht den Bot nicht.

Nach der Übertragung des Befehls dreht der Server den Bot entsprechend und bewegt ihn ein Feld vorwärts.

Achtung: Es wird erst gedreht und danach die Bewegung ausgeführt!

Ausscheiden eines Bots

Fährt ein Bot gegen eine Wand bzw. ein besetztes Feld, scheidet er aus. Dieses Ausscheiden wird allen noch nicht ausgeschiedenen Bots (mit Ausnahme des gerade ausgeschiedenen) mitgeteilt:

• OUT p – Ein Bot ist ausgeschieden. p ist dabei die Botnummer und startet bei 1.

Nach dem Ausscheiden eines Bots werden an ihn keine Botpositionen und auch kein Rundenstart mehr gesendet.

Wichtige Änderung 02.11.2014: Ein Client darf sich nach dem Ausscheiden des eigenen Bots noch nicht direkt beenden, da dies die Server-Kommunikation durcheinanderbringt. Das heißt, der Bot muss korrekt auf den Spielende-Befehl (siehe unten) warten.

Spielende

Wenn ein Bot ausgeschieden ist, können sich alle noch nicht ausgeschiedenen Bots weiter auf dem Spielfeld bewegen. Das heißt, das Spiel ist nicht vorbei, wenn es nur noch einen nicht ausgeschiedenen Bot gibt. Der letzte Bot darf sich auch weiterhin solange auf dem Feld ungestört bewegen, wie es möglich ist (siehe Auswertung unten).

Sobald auch der letzte Bot ausgeschieden ist, überträgt der Server den Ende-Befehl an alle Clients (auch an die zuvor ausgeschiedenen):

• END – Spielende.

Jetzt sollten die Clients sich beenden. Der Server bricht die Verbindung hiernach ab und das Spiel endet.

Implementierung

Der Server ist in C++ geschrieben, sodass man zur Übersetzung einen C++-Compiler benötigt. Hat man diesen installiert, kann man den Servercode herunterladen und entpacken

Danach muss man noch Code kompilieren:

Jetzt kann man den eigenen Bot testen und beispielsweise gegen den Dummybot (siehe unten) antreten lassen:

bots/eigenerbot/bot ist dabei der Pfad zum eigenen Bot und kann ein beliebiges ausführbares Programm oder Skript sein, welches STDIN auslesen bzw. auf STDOUT schreiben kann.

Dummybot

Für alle Teilnehmer, die C++ beherrschen und sich mehr auf die Strategie als das Drumherum konzentrieren wollen, gibt es im Verzeichnis bots/dummybot eine Dummy-Implementierung in C++. Diesen Dummybot kann man als Vorlage (Dabei bitte die Lizenz beachten!) und/oder als Sparring-Partner für den einen eigenen Bot nutzen.

Den Dummybot kompiliert man über:

GUI zur Analyse

Zur Analyse des Botverhaltens kann man die gespielte Sitzung als Logfile ausschreiben lassen und speichern:

Das Logfile kann man danach mit der GUI einlesen und den Ablauf sichtbar machen.

Zum Kompilieren der GUI wird ein C++-Compiler und die Qt4-Entwicklungsbibliotheken benötigt:

• g++
• libqt4-dev
• qt4-qmake

Danach kann man die GUI übersetzen:

Die GUI startet mit

GUI zur Anzeige der Botbewegung.

Eigene Spielfelder

Man kann eigene Spielfelder erstellen und für den Wettbewerb einreichen. Die Syntax ist dabei identisch zu den übertragenen Spielbrettdaten (siehe oben) inkl. GAMEBOARDSTART und GAMEBOARDEND. Zusätzlich kann man noch die Startposition der Spieler am Ende der Datei festlegen. Die Syntax ist dabei identisch zur Positionsübertragung jede Runde.

Ob diese Spielfelder genutzt werden, obliegt der freiesMagazin-Redaktion.

Auswertung

Im Wettbewerb treten jeweils immer zwei Bots gegeneinander an. Es wird dabei immer zwei Spiele geben, damit jeder Bot einmal die andere Startposition hat. Der Bot, der am längsten überlebt, erhält 3 Punkte. Sollten beide Bots gleichzeitig ausscheiden, gibt dies für beide 1 Punkt. Der Bot, der zuerst ausscheidet, erhält 0 Punkte (Dreipunkteregel). Dies wird für alle vorhandenen Spielfelder wiederholt.

Nachdem jeder Bot gegen alle anderen auf allen Spielfeldern angetreten ist, werden die Punkte summiert und der Bot mit den meisten Punkten gewinnt den Wettbewerb. Ein Bot tritt nicht gegen sich selbst an.

An der Stelle noch einmal der Hinweis, dass man seinen Bot dennoch so programmieren sollte, dass er auch mit mehr als einem Gegner zurecht kommt. Dies ist vor allem für Tests (und die Leser später) interessant.

Zusätzlich werden in jedem Spiel die Anzahl der Runden gezählt, bis ein Bot ausscheidet. Diese Anzahl wird dann als Tie-Breaker benutzt, sollten zwei Bots am Ende des Wettbewerbs die gleiche Punktezahl haben.

Hinweis: Sollte es Bots mit Zufallselementen geben, werden mehrere Einzelspiele durchgeführt und der mathematisch gerundete Mittelwert des Ergebnisses genutzt.

Preise

Damit es neben der eigentlichen kreativen Anregung noch einen weiteren Anreiz gibt, am Wettbewerb teilzunehmen, wird es auch Preise geben:

• Der Gewinner des Wettbewerbs erhält ein Buch eigener Wahl im Wert von maximal 35 Euro.
• Der Zweitplatzierte erhält ein Buch eigener Wahl im Wert von maximal 20 Euro.
• Der Drittplatzierte erhält den Film „Tron“ (von 1986) auf DVD, auf dem die Idee des Wettbewerbs basiert.

Zusätzlich gibt es für alle anderen Teilnehmer den Doppel-CD-Sampler des Free!Music!Contest 2014 als Trostpreis, falls gewünscht und solange der Vorrat reicht.

Teilnahmebedingungen

Die Teilnahme am Wettbewerb ist für jeden offen. Ausgeschlossen sind nur die Mitarbeiter der freiesMagazin-Redaktion. Es ist auch erlaubt im Team zu arbeiten, man muss sich dann die Preise aber teilen. Als Programmiersprache kann jede benutzt werden, die die Standardeingabe auslesen bzw. auf die Standardausgabe schreiben kann.

Folgende Bedingungen gibt es:

• Der Bot muss im Quellcode mit einer Kompilierungsanleitung (falls notwendig) vorliegen. Vorkompilierte Binärdateien werden nicht akzeptiert!
• Der Quellcode muss unter einer freien Lizenz vorliegen. Wir helfen gerne bei der Auswahl einer passenden Lizenz, wenn es hierzu Fragen gibt.
• Jeder Teilnehmer darf nur mit einem Bot teilnehmen, darf diesen aber gerne mehrfach verbessern und einsenden.
• Durch die Einsendung des Quellcodes stimmt jeder Teilnehmer der Veröffentlichung des Codes auf der freiesMagazin-Webseite am Ende des Wettbewerbes zu.
• Die Laufzeit der Bot-Programme (inkl. Server-Ausführung) sollte so gering wie möglich sein. Für die Teilnahme sollte pro Runde maximal 1 Sekunde benötigt werden, da der Wettbewerb sonst zu lange dauert.

Der Wettbewerb läuft vom 1. Oktober 2014 bis zum 20. Dezember 2014. Die Auswertung findet über die Weihnachtsfeiertage statt. Der Gewinner wird dann am 1. Januar 2015 bekannt gegeben.

Bis zum 20. Dezember 2014 können die Teilnehmer ihren Bot an senden. Jeder Teilnehmer darf auch gerne eigene Spielfelder zusenden, die dann ggf. für den Wettbewerb benutzt werden.

Hinweis: Die vergangenen Wettbewerbe haben gezeigt, dass es sinnvoll ist, seinen Bot frühzeitig einzureichen, damit dieser getestet werden kann. Nicht lauffähige Bots können nicht am Wettbewerb teilnehmen! Die Redaktion gibt gerne Hilfestellung zur Implementierung, falls dies möglich ist. Hinweise zu einer guten Strategie werden natürlich nicht gegeben.

Download: Quellcode zur Teilnahme

Wir wünschen allen Teilnehmern viel Erfolg und freuen uns auf zahlreiche Zusendungen.

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!

FAQ

FAQ zum siebten Programmierwettbewerb