Zweiter Programmierwettbewerb

Aufgrund des Erfolges des ersten Programmierwettbewerbes von freiesMagazin im April dieses Jahres, bei dem 13 Teilnehmer eine KI eingereicht haben, haben wir uns entschlossen, erneut einen Programmierwettbewerb zu veranstalten. Dieses Mal wird die Aufgabe etwas anspruchsvoller, aber auch etwas lustiger. Wir hoffen erneut auf eine rege Teilnahme.

Spielidee

Die Idee basiert dieses Mal auf dem Spiel RoboRally von Richard Garfield (Spielidee), Bill McQuillan (Spielentwicklung) und Paul Sottosanti (Spielbrettdesign) aus dem Hause Wizards of the Coast. Man steuert über Spielkarten einen Roboter durch eine Fabrik auf dem Weg zu verschiedenen Zielpunkten. Dabei kommen einem oftmals andere Roboter in die Quere und zusätzlich gibt es in der Fabrik verschiedene Objekte, die die Bewegungen des Roboters beeinflussen können.

Aufgrund der zeitlichen Begrenzung des Wettbewerbs wurde aber auf die Interaktion mit anderen Robotern und auf einige Spielelemente verzichtet. Auf diese Art soll die zu programmierende Künstliche Intelligenz (KI), d.h. das Programm, welches den Roboter steuert, nicht zu komplex werden.

Das Spiel im Detail

Der Roboter

Wie bereits erwähnt, ist es diesmal die Aufgabe der Teilnehmer, eine KI für einen Roboter zu programmieren. Dieser kann durch Spielkarten vorwärts und rückwärts fahren oder sich nach rechts und links drehen. Ziel des Spiels ist es, den Roboter unbeschadet von der Startposition ins Ziel zu führen. Es reicht dabei, wenn der Roboter das Ziel überfährt, er muss nicht exakt darauf stehen bleiben.

Die Spielkarten

Zu Beginn jeder Runde werden acht Karten ausgeteilt, mit denen man den Roboter bewegen oder drehen kann. Von diesen acht wählt man fünf aus, deren Befehle dann sequenziell (also der Reihe nach, so wie sie ausgewählt wurden) abgearbeitet werden.

Es stehen folgende Karten (mit zugehöriger Anzahl im Kartenstapel) zur Auswahl:

Karten
Titel	Anzahl	Wahrscheinlichkeit
Bewegung 3 Felder vorwärts	400	0.071
Bewegung 2 F. vorwärts	800	0.143
Bewegung 1 F. vorwärts	1200	0.214
Bewegung 1 F. rückwärts	400	0.071
Nach links drehen (90 Grad)	1200	0.214
Nach rechts drehen (90 Grad)	1200	0.214
Umdrehen (180 Grad)	400	0.071
Gesamt	5600

Hinweis: Es gibt also keine Karte, mit der ein Roboter einfach nur still stehenbleibt!

Ingesamt heißt das, es wird die erste von den fünf gewählten Karte ausgespielt, der Roboter bewegt sich und bleibt stehen. Dann bewegen ggf. die Elemente auf dem Spielbrett (siehe unten) den Roboter und dann wird die nächste Karte ausgespielt usw.

Die hohe Anzahl der Spielkarten ergibt sich daraus, dass es bei einer zu geringen Zahl zu leicht dazu kommen kann, dass die Karten aufgebraucht sind, bevor der Roboter das Ziel gefunden hat. Mit der obigen Anzahl konnte die Referenz-KI (siehe unten) das Ziel aber jedes Mal erreichen.

Das Spielbrett

Wie erwähnt, gibt es auf dem Spielbrett verschiedene Spielelemente, die den Roboter beeinflussen oder behindern können.

	Boden: Wie langweilig! Ein leeres Fabrikfeld.
	Ziel: Das Zielfeld, zu dem der Roboter geführt werden muss.
	Wände: Wände wirken sehr einschränkend auf die Bewegungsfreiheit des Roboters, denn sie können nicht durchbrochen werden. Fährt ein Roboter gegen die Wand, passiert aber zumindest nichts Schlimmes (außer vielleicht einer kleinen Delle). Nachfolgende Bewegungen wie Drehungen werden aber natürlich weiter ausgeführt, soweit möglich.
	Kiste: Eine Kiste sperrt ein Feld komplett. Man kann nicht anders, als das Hindernis zu umfahren.
	Loch: Wenn ein Roboter dieses Feld aus Versehen betritt oder darauf geschoben wird, verschwindet er auf Nimmerwiedersehen.
	Öl: Besonders glitschig! Wenn ein Roboter dieses betritt oder darauf geschoben wird, rutscht er bis zum nächsten Nichtölfeld weiter oder bis er von einer Wand gestoppt wird. Wenn er sich auf einem Ölfeld dreht, wird die Drehung verdoppelt. Aus einer Links- oder Rechtsdrehung wird zum Beispiel eine Drehung um 180 Grad.
	Drehrad: Drehwurm garantiert. Wenn man auf diesem Feld zum Stehen kommt, wird der Roboter um 90 Grad in die jeweils angezeigte Richtung gedreht.
	Förderband: Nur für Faule! Bleibt man auf einem Förderband stehen, bewegt es den Roboter exakt einen Schritt in die jeweilige Richtung. Aufpassen sollte man hier, wenn am Ende der Abgrund wartet.
	Schieber: Deprimierend, ständig wird man durch die Gegend geschoben. Bleibt man vor dem Schieber stehen, schiebt er den Roboter ein Feld vorwärts. Die Seite, an der der Schieber steht, ist mit einer Wand versehen und kann dort nicht betreten oder verlassen werden.
	Schrottpresse: Zwischen den beiden Schiebern einer Schrottpresse sollte man nicht stehen bleiben, sonst landet man als kleiner zusammengepresster Würfel auf dem Müll. Wie bei Schiebern auch hat die Schrottpresse rechts und links bzw. oben und unten zwei Wände.

Förderbänder haben noch eine Besonderheit, denn sie können, wenn ein Förderband den Roboter auf ein anderes Förderband schiebt, auch die Blickrichtung des Roboters ändern. In allen anderen Fällen bleibt die Blickrichtung des Roboters erhalten.

Als Beispiel: Der Roboter bewegt sich von seiner Startposition drei Schritte nach rechts und wird dann durch das Förderband nur nach oben geschoben, die Blickrichtung bleibt nach rechts.

Fall 1: Der Roboter behält die Blickrichtung bei.

Im anderen Fall bewegt sich der Roboter nur zwei Felder vor und wird dann vom Förderband nach rechts auf das nach oben laufende Förderband geschoben. Dabei wird er auch gedreht, so dass er ebenfalls nach oben blickt.

Fall 2: Der Roboter wird gedreht.

Dies gilt auch, wenn das erste Förderband den Roboter über mehrere Ölfelder auf ein zweites, senkrecht dazu stehendes Förderband rutschen lässt. Dann wird der Roboter auch entsprechend gedreht.

Die Elemente, die den Roboter auf dem Feld bewegen (Drehrad, Förderband, Schieber, Schrottpresse), agieren erst, wenn der Roboter nach einem Kartenzug zum Stillstand kommt. Durch eine Schrottpresse zu fahren, ist also kein Problem. Über ein Loch fahren zu wollen schon eher.

Zusätzlich agieren diese bewegenden Elemente nacheinander und nicht gleichzeitig. Die Reihenfolge ist:

Reihenfolge der Elementaktionen
Reihenfolge	Aktion
1	Die Förderbänder bewegen sich.
2	Der Schieber und die Schrottpresse werden aktiviert.
3	Die Drehräder drehen sich.

Es ist also möglich, dass ein Roboter, der auf einem Förderband steht, von diesem zu einem Schieber geschoben wird, der einen auf ein Drehrad-Feld schiebt und dieses dann den Roboter noch einmal dreht.

Diese Bewegung kann man mit nur einem Schritt erreichen.

Da die späteren Wettbewerbsspielbretter alle von Hand erstellt werden, gibt es auch keine besondere Häufigkeit, mit der ein bestimmtes Feld vorkommt.

Spielumsetzung

Aufgabe der Teilnehmer ist es, eine KI zu programmieren, die aus acht Karten fünf auswählt und diese abspeichert. Als Eingabe muss die KI dafür folgende Dateien auslesen:

board.txt - das Spielbrett mit ASCII-Zeichen
cards.txt - acht Spielkarten zur Auswahl
bot.txt - Roboterposition und -blickrichtung

Die fünf ausgewählten Karten müssen in der Datei ccards.txt (das doppelte „cc“ steht für „choosen cards“) abgespeichert sein.

Die Spielbrettdatei `board.txt`

Die Datei board.txt enthält das Wichtigste überhaupt: das Spielbrett. Dessen Aufbau ist auch am kompliziertesten und muss hier genau erklärt werden.

Das Referenzspielbrett chop.dat sieht so aus:

12 12

V e ev^f eF 

<N<<<<^  DH 

b  k LR    c

>>>O>>>>>>>>

b  Rp    ^ g

  HL  ivf^<<

   i<<<L>>>>

je   H^    c

<<<L bRc    

b  ^  ^DH<<c

   ^  ^   ^ 

  i^k ^i i^Z

In der ersten Zeile findet man zwei durch ein Leerzeichen getrennte Ganzzahlwerte X und Y, die die Breite und die Höhe des Spielbrettes angeben. Danach folgen Y Zeilen mit je X Zeichen für das Spielbrett.

Hinweis: Die linke obere Ecke (in dem Fall also das V) hat immer den Index (0,0).

ASCII-Zeichen der Spielfelder

Es folgt die Bedeutung der einzelnen Zeichen.

Einfache Felder
Zeichen	Feld
Leerzeichen	leerer Boden
H	Loch
O	Öl
S, T, U, V	Startfeld des Roboters (für die KI irrelevant, als leeres Bodenfeld behandeln)
Z	Zielfeld für den Roboter

Drehräder
Zeichen	Feld
L	dreht den Roboter 90° gegen den Uhrzeigersinn
R	dreht den Roboter 90° im Uhrzeigersinn

Förderbänder
Zeichen	Feld
<	Förderband nach links
>	Förderband nach rechts
`^`	Förderband nach oben
v	Förderband nach unten

Schieber/Presse
Zeichen	Feld
C	schiebt den Roboter ein Feld nach links
D	schiebt den Roboter ein Feld nach rechts
E	schiebt den Roboter ein Feld nach oben
F	schiebt den Roboter ein Feld nach unten
M	Links/Rechts-Schrottpresse
N	Oben/Unten Schrottpresse

Wände
Zeichen	Feld
a-p	definiert eine Wand/mehrere Wände pro Feld

Die Definition der Wände ist binärkodiert, dass heißt:

Wand links = 1
Wand rechts = 2
Wand oben = 4
Wand unten = 8

Beispiele:

Beispiele für Wände
Kodierung	Zeichen	Wände
0	a	keine
1	b	links
8	i	unten
7	h	links, rechts und oben
15	p	an allen vier Seiten (entspricht einer Kiste)

Die Wettbewerbsspielbretter werden alle von Hand erstellt und haben voraussichtlich alle eine Größe von 12x12-Feldern, wobei die KI sich natürlich nicht darauf verlassen sollte, dass dem so ist.

Die Kartendatei `cards.txt`

In jeder Zeile der Datei cards.txt steht eine Karte. Es gibt folgende Möglichkeiten:

MF 1 - bewegt den Roboter ein Feld vorwärts (vorwärts ist immer in Blickrichtung des Roboters)
MF 2 - bewegt den Roboter zwei Felder vorwärts
MF 3 - bewegt den Roboter drei Felder vorwärts
MB - bewegt den Roboter ein Feld rückwärts
RL - dreht den Roboter um 90 Grad nach links
RR - dreht den Roboter um 90 Grad nach rechts
RU - dreht den Roboter um 180 Grad

Im gleichen Format speichert man die fünf ausgewählten Karten auch in der Datei ccards.txt ab.

Hinweis: Während das Spiel läuft steht in der Datei cards.txt der komplette Kartenstapel mit allen folgenden Karten. Bevor die KI aufgerufen wird, wird die Datei aber mit den 8 auszuwählenden Karten gefüllt. Man kann also nicht auf den ganzen Kartenstapel zugreifen.

Die Roboterdatei `bot.txt`

Die Datei bot.txt enthält nur eine Zeile mit den durch Leerzeichen getrennten Informationen:

horizontale Position des Roboters (zwischen 0 und Breite des Spielbretts-1)
vertikale Position des Roboters (zwischen 0 und Höhe des Spielbretts-1)
Blickrichtung des Roboters:
- L - nach links
- R - nach rechts
- U - nach oben („up“)
- D - nach unten („down“)

Beispiel:

7 8 D

Der Roboter steht also auf Feld (7,8) und schaut (auf dem Bildschirm) nach unten.

Weitere Dateien

Spielbrett in Großformat

Vor jeder Runde wird das Spielbrett noch in einem etwas schöneren ASCII-Format ascii-board.txt ausgegeben, das sich aber nicht zum Einlesen eignet, da es zu komplex ist. Man kann damit aber schöner nachvollziehen, wo sich der Roboter auf dem Spielbrett gerade befindet und wie die einzelnen Felder aussehen.

Das Spielbrett wird auch im Großformat angezeigt.

Sequenzdateien

Am Ende jeder Runde wird eine Datei sequence.txt erstellt, die die absoluten Bewegungen des Roboters für die fünf von der KI ausgewählten Karten auf dem Spielbrett enthält. Das heißt, es gibt folgende Einträge:

ML - bewegt den Roboter um ein Feld nach links
MR - bewegt den Roboter um ein Feld nach rechts
MU - bewegt den Roboter um ein Feld nach oben
MD - bewegt den Roboter um ein Feld nach unten
RL - dreht den Roboter um 90 Grad nach links
RR - dreht den Roboter um 90 Grad nach rechts
RU - dreht den Roboter um 180 Grad
X - Roboter wurde zerstört, Spiel ist zu Ende
Y - Kartenstapel ist leer, Spiel ist zu Ende
Z - Roboter hat das Ziel erreicht, Spiel ist zu Ende
---- - vier Striche signalisieren die nächste Karte

Am Ende eines Spiels wird noch zusätzlich eine Datei globalseq.txt erstellt, die die gesamten Bewegungen des Roboters enthält. Auf diese Weise kann man genau nachvollziehen, wie der Roboter zum Ziel gefunden hat. Die einzelnen Runden werden dabei in der Datei durch acht Striche -------- voneinander getrennt.

Statistikdatei

Ebenfalls am Ende eines Spiels wird noch eine Statistikdatei stats.txt erzeugt, die alle wichtigen Informationen zu einem Spiel enthält:

Cards: 60

Rounds: 12

Card Moves: 72

Board Moves: 20

Destroyed (X): 0

Cards Out (Y): 0

Finished (Z): 1

Der Wettbewerb

Kategorien

Der Wettbewerb wird in vier Kategorien unterteilt, wobei die ersten drei eine Schwierigkeitsstufe angeben.

Schwierigkeitsstufe leicht

In der einfachsten Stufe kann der Roboter nicht sterben, das heißt, das Spielbrett enthält keine Löcher und auch keine Schrottpresse. Auch die Ölfelder werden entfernt, da deren Auswirkungen recht komplex werden können. Zusätzlich ist das Spielbrett von einer unsichtbaren Wand umgeben, sodass der Roboter nicht herunterfällt.

Schwierigkeitsstufe mittel

In der Standardstufe sind alle Felder wie oben beschrieben vorhanden, d.h. es gibt auch Löcher und Schrottpressen, bei denen der Roboter sterben kann.
Der Roboter kann aber immer noch nicht vom Spielbrettrand fallen.

Schwierigkeitsstufe schwer

In der schwierigsten Stufe muss der Roboter wirklich aufpassen, wo er hintritt, denn die unsichtbare Wand um das Spielbrett herum ist verschwunden. Außerhalb des Spielbretts herrscht gähnende Leere, ein Schritt zu weit und der Roboter verschwindet auf Nimmerwiedersehen.

Sonderpreis: 3-D-Spielbrett

Als kleine Besonderheit fänden wir es schön, wenn es ein 3-D-Spielbrett gäbe, in dem man den Roboter herumlaufen sieht. Als Anforderung muss die GUI neben der Spielbrett- und Roboteranzeige nur das komplette Sequenzskript globalseq.txt (siehe oben) laden und abspielen können.

Hinweis: 3-D schließt in diesem Fall auch die isometrische Darstellung mit ein, die viele Spieler vielleicht aus Action-Rollenspielen wie Diablo oder Sacred kennen.

Wie weit die Funktionalität des Spielbrettes geht, ist dem Programmierer überlassen. Zum Beispiel bieten sich freie Rotationen oder die vier Standardansichten bei isometrischer Perspektive genauso wie verschiedene Zoomstufen an. Das Spielbrett sollte aber nicht auf eine maximale Spielfeldgröße von 12x12 Feldern (wie die Referenz-GUI) beschränkt sein.

Teilnahmebedingungen

Jeder Teilnehmer kann nur in einer der vier Kategorien antreten. Zusätzlich muss es pro Kategorie (außer bei dem 3-D-Spielbrett) mindestens zwei Teilnehmer geben, damit wenigstens etwas Wettbewerb entsteht. Es ist auch erlaubt, dass mehrere Personen zusammen als ein einzelnes Team antreten - diese müssen sich den Preis dann aber natürlich teilen.

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

Wer außer Konkurrenz ein 3-D-Spielbrett programmieren will, aber lieber eine KI einreicht, kann die 3-D-Oberfläche auch zuschicken. Diese wird dann vorgestellt, getestet und bewertet, kann aber natürlich nicht gewinnen.

Qualität

Daneben gibt es noch die Anforderung, dass der Roboter in der jeweiligen Schwierigkeitsstufe, in der man teilnehmen möchte, in mindestens 75% der Testfälle das Ziel erreichen muss. Das heißt, eine schlechte KI, die den Roboter in jedes Loch stolpern lässt und ihn dadurch zerstört, kann nicht gewinnen. Die Einschränkung müssen wir machen, um ein gewisses KI-Niveau im Wettbewerb zu erreichen.

Das 3-D-Spielbrett sollte natürlich korrekt funktionieren und „gut aussehen“.

Programmiersprache

Die benutzte Programmiersprache ist wie immer freigestellt. Das Projekt sollte aber auf einem „Standard-Linux-Rechner“ (d.h. mit einer aktuellen Linux-Distribution) ohne Probleme kompilier- und ausführbar sein. Das gilt auch für die 3-D-Oberfläche. Für diese darf man aber natürlich auf bekannte grafische Bibliotheken wie Mesa (für OpenGL) oder wxWidgets für das Fenstermanagement zurückgreifen.

Die Programme müssen 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.

Für die KIs 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 eine eigene KI zu erstellen.

Sinnvoll ist es, wenn das KI-Programm nach der Ausführung im Erfolgsfall 0 zurückliefert und bei Fehlern einen Wert ungleich 0.

Es ist natürlich erlaubt, dass sich die KI in Form von gespeicherten Dateien Notizen macht, auf die sie dann beim nächsten KI-Aufruf zugreifen kann.

Laufzeit

Die Laufzeit der KI-Programme sollte natürlich so gering wie möglich sein. Für die Teilnahme am Wettbewerb sollten im Schnitt pro Spiel nicht mehr als maximal 6 Sekunden gebraucht werden. Das heißt ein kompletter Testdurchgang mit 100 Kartenstapeln auf einem Spielbrett sollte maximal 10 Minuten dauern.

Preisgelder

Die vier Kategorien sind jeweils mit einem Buchgutschein in folgender Höhe dotiert:

Preisgelder
Stufe	Preisgeld
leicht	10 Euro
normal	20 Euro
schwer	30 Euro
3-D-Spielbrett	50 Euro

Gewinner

Die einzelnen KIs treten auf verschiedenen (bis nach Ende des Wettbewerbs geheimen) Spielbrettern mit zuvor berechneten Kartenstapeln an. In die Bewertung fließt zunächst ein, ob der Roboter das Ziel erreicht hat oder vorher zerstört wurde. Erreicht er das Ziel, fließt noch die Anzahl der Züge bzw. Runden in die Bewertung mit ein. Es ist also sehr positiv, wenn ein Roboter in möglichst wenigen Runden das Ziel sicher findet.

Bei dem 3-D-Spielbrett ist die Wahl des Gewinners etwas schwieriger, da Aussehen immer im Auge des Betrachters liegt. Wir versuchen aber die Einsendungen objektiv zu bewerten. Der Teilnehmer mit dem schönsten 3-D-Spielbrett gewinnt.

Wettbewerbsdauer

Der Wettbewerb begann am 27. September 2009 und endet am 13. Dezember 2009, sodass wir den Gewinnern hoffentlich noch zu Weihnachten ein kleines Geschenk machen können. Alle Einsendungen sollten per E-Mail unter bis zu diesem Stichtag bei der Redaktion
unter eingegangen sein. Programme, die uns später erreichen, können
leider nicht mehr beachtet werden.

Es ist erlaubt, dass ein Teilnehmer seine eingesandte KI mehrfach ausbessert. Wir geben gerne Hinweise auf etwaige Fehler der KI (bezogen auf den Quellcode, nicht auf falsche Entscheidungen). Informationen über die Leistung der eigenen KI im Vergleich zu anderen Teilnehmern werden aber nicht vorab veröffentlicht.

Referenzimplementierung

Um seine eigene KI testen zu können, benötigt man die Dateien, die später den Wettbewerb verwalten werden. Das gesamte Paket kann als Tar-Archiv heruntergeladen werden und muss nach dem Entpacken mit

$ make

kompiliert werden.

Das Paket setzt sich aus verschiedenen Bestandteilen zusammen, wovon ein Großteil in C++ programmiert ist. Das Paket build-essential und dessen Abhängigkeiten sollten auf alle Fälle installiert sein, um die Programme kompilieren zu können.

Spiele-Engine

Die Dateien der Engine, dass heißt der Verwaltung, die die KI ausführt und das Schreiben und Lesen der Spieledateien übernimmt, nimmt den größten Teil des Archives ein.

Im Verzeichnis robots-engine_dir findet man die Bibliotheken in Ordnern, die nach Basis (libbase), Roboter (libbot), Karten (libcards) und Spielfelder (libtiles) aufgeteilt sind.

Der Quellcode unterliegt der GNU Lesser General Public License (LGPL), damit eine Verwendung der erstellten Bibliotheken erlaubt ist, ohne dass man den eigenen Quellcode wieder unter der LGPL veröffentlichen muss. Das heißt, eine KI, die auf libbot zugreift, um die Roboter-Dateien auszulesen, darf beispielsweise unter der BSD-Lizenz vertrieben werden. Würde der Quellcode unter der GPL veröffentlicht werden, hätte das Endprodukt, das die Bibliothek nutzt, auch unter der GPL veröffentlicht werden müssen, was eine zu große Einschränkung wäre.

Wer natürlich Teile des Quellcodes aus der Engine benutzen und abändern oder ergänzen möchte, kann dies auch tun, ist dann aber an eine Veröffentlichung des Gesamtwerkes unter der LGPL gebunden.

Nach der Erstellung mittels make findet man die Datei robots-engine
im Hauptordner, die man wie folgt aufrufen kann:

$ ./robots-engine save DECKNAME

Dies erstellt einen zufälligen Kartenstapel und speichert diesen als Datei DECKNAME ab. Wer gleich mehrere Kartenstapel erstellen möchte, kann dies mit einem einfachen Skript erledigen (dies liegt in leicht abgewandelter Form auch als Datei create_decks vor):

#!/bin/bash
mkdir -p decks
# create decks 0 - 99

for (( I=0; $I <= 99; I++ ))

do
    echo "./robots-engine save decks/carddeck$I.dat"

    ./robots-engine save decks/carddeck$I.dat

    sleep 2

done

In dem Fall wird erst ein Verzeichnis decks erstellt und dann 100 Kartenstapel darin gespeichert. Die zwei Sekunden Wartezeit sind dafür da, dass die Zufallszahlen (die von der Uhrzeit abhängig sind) neu berechnet werden.

Im Ordner gameboards findet man das Referenz-Spielbrett chop.dat. Man kann nun entweder dieses Spielbrett alleine laden, sodass ein zufälliger neuer Kartenstapel erzeugt wird oder man benutzt einen der über obiges Vorgehen gespeicherten Kartenstapel:

$ ./robots-engine load BOARDNAME [easy|normal|hard]

$ ./robots-engine load BOARDNAME DECKNAME [easy|normal|hard]

Als letztes Argument kann man optional (daher die eckigen Klammern) auch die Spielstufe mit angeben. Standardwert ist „normal“. Ein Beispiel:

$ ./robots-engine load gameboards/chop.dat decks/carddeck0.dat easy

Wenn man das Spielbrett und Kartenstapel geladen hat, kann man eine Runde (nicht das gesamte Spiel!) per

$ ./robots-engine start [easy|normal|hard]

laufen lassen. Die Spielstufe sollte dabei am besten mit der bei load angegebenen übereinstimmen.

Nach dem Aufruf wird intern das im Ordner liegende Skript bot-ki gestartet:

#!/bin/bash
# Reference

./KIs/robots-ki-reference $1
retVal=$?
exit $retVal

Dies ruft also einfach nur die jeweilige KI (hier die Referenz-KI) im Ordner KIs auf. Als Argument $1 wird dabei die Spielstufe übergeben. Möchte man mit dem eigenen Bot spielen, passt man einfach die Zeile

./KIs/robots-ki-reference $1

entsprechend den eigenen Wünschen an.

Hat man eine Runde über die Option start ausgeführt, findet man die oben erwähnte Datei sequence.txt im Ordner. In dieser findet man die Bewegungssequenz wieder.

Ein komplettes Spiel kann man durchführen, wenn man die Engine solange startet, bis der Bot am Ziel ist, zerstört wurde oder keine Karten mehr auf dem Kartenstapel liegen.

Referenz-KI

Die Referenz-KI im Ordner KIs/robots-ki_dir soll nur grob veranschaulichen, wie man die Bibliotheken der Spiele-Engine nutzen kann, um mit deren Hilfe eine KI aufzubauen. Die KI selbst ist sehr dumm, denn sie wählt immer nur die ersten fünf der acht zur Auswahl stehenden Karten aus. Das sorgt dafür, dass der Roboter nur per Zufall ins Ziel findet. Die Referenz-KI wird unter der GNU General Public License veröffentlicht.

Es ist aber möglich, innerhalb von wenigen Stunden mit Hilfe der Bibliotheken eine KI zu schreiben, die auch auf der Stufe „schwer“ den Roboter sicher ins Ziel bewegt. Diese zweite Referenz-KI von Dominik Wagenführ wird aber erst nach Beendigung des Wettbwerbs veröffentlicht, sonst wäre die Teilnahme zu einfach.

Wettbewerb starten

Wer den Wettbewerb starten will, kann das Skript start_contest benutzen:

#!/bin/bash
GAMES=$1

DECKS=`find decks -name "*.dat" | sort`

LEVEL=$2
date

for GAME in $GAMES

do
    for DECK in $DECKS

    do

        echo "./robots-contest $GAME $DECK $LEVEL"

        ./robots-contest $GAME $DECK $LEVEL

    done

done

date
exit 0

Der Aufruf ist wie folgt:

$ ./start_contest GAMEBOARDS [easy|normal|hard]

GAMEBOARDS ist dabei eine Auflistung aller Spielbretter, die benutzt werden sollen. Als Kartenstapel werden alle Dateien im Ordner decks benutzt (den zum Beispiel das Skript create_decks zuvor angelegt hat). Ein Beispiel:

$ ./start_contest "gameboards/chop.dat gameboards/board2.dat" hard

Grafische Oberfläche

Da beim letzten Programmierwettbewerb von freiesMagazin im April dieses Jahres einige Nutzer nach einer grafischen Oberfläche (GUI) fragten, um das Geschehen besser verfolgen zu können, hat Dominik Honnef diese für den anstehenden Wettbewerb umgesetzt. Die GUI ist dabei als Programmier- und Visualisierungshilfe gedacht und wird nicht zwingend für eine Teilnahme benötigt.

Anforderungen

Für die Umsetzung wird Ruby, Ruby-Gnome2, RubyGems und die Gosu Game Development Library benutzt. Daher muss man ein paar Ruby-Pakete (und deren Abhängigkeiten) installieren:

ruby bzw. ruby1.8
rubygems
libgtk2-ruby bzw. libgtk2-ruby1.8

Daneben benötigt man noch einige Entwickler-Bibliotheken, um die Gosu GUI kompilieren zu können:

g++
libgl1-mesa-dev
libpango1.0-dev
libboost-dev
libsdl-mixer1.2-dev
ruby1.8-dev

Hinweis: Die Paketbezeichnungen stammen von Debian/Ubuntu und können/werden unter anderen Distributionen variieren. Unter Arch Linux gibt es beispielsweise keine extra dev-Pakete. Hier hilft ein Blick in die offizielle Installationsanleitung weiter.

Nach der Installation der Pakete installiert man die Gosu GUI Library mit Root-Rechten über

# gem install gosu

Falls gefragt wird, welches gosu-Paket installiert werden soll, wählt man am besten gosu 0.7.14 (ruby) aus.
Falls eine Fehlermeldung der Art

ERROR:  While executing gem ... (Gem::GemNotFoundException)

    Could not find gosu (> 0) in any repository

kommt, sollte man die Installation einfach wiederholen, bis das Paket gosu gefunden wird.

Nach der Kompilierung von Gosu kann man die Entwicklerpakete wieder deinstallieren. Ruby und Co. müssen natürlich installiert bleiben.

GUI-Start

Die grafische Oberfläche besteht aus zwei Teilen: zum einen aus der Oberfläche für alle Einstellungen des Spiels „robots-gui-helper“ und zum anderen aus der Oberfläche für das Spielbrett „robots-gui“. Da die „robots-gui“ nie direkt gestartet werden sollte, werden deren Optionen hier nicht näher erläutert. Den GUI-Starter ruft man per

$ ./robots-gui-helper

auf. Im Standardfall kann man nun bereits auf „Spiel starten“ klicken und die Referenz-KI sollte den Roboter bewegen.

Die Einstellungen im Starter sind fast alle selbsterklärend. Es soll hier nur auf die Optionen eingegangen werden, die nicht offensichtlich sind.

Das Hilfsprogramm „GUI-Starter“ zur Vorbereitung der GUI.

Über „Neues Spiel starten“ kann man einstellen, ob der Roboter von seiner letzten Position aus der Datei bot.txt oder von der Startposition auf dem Spielbrett starten soll. Zusätzlich wird das Spielfeld und der Kartenstapel nicht neu eingelesen, wenn der Haken nicht gesetzt ist. Auf diese Art kann man unterbrochene Spiele fortsetzen.

Entfernt man den Haken bei „Spiel animieren“, läuft der Roboter nicht über das Spielfeld, sondern das Spiel wird bis zum Ende berechnet, der Roboter also das Ziel gefunden hat oder zerstört wurde. Erst dann wird die Anzeige freigeschaltet und man sieht den Roboter an der Endposition.

Mit „Spiel starten“ startet man das Spiel und kann dem Roboter bei der Bewegung zuschauen. Dieser hinterlässt eine transparente grüne Spur (Nein, er verliert kein Öl!), mit der man sehen kann, welche Felder er wie häufig betreten hat. Mit den Tasten „+“ und „-“ kann man die Bewegungsgeschwindigkeit des Roboters verändern.

Ein Testlauf mitsamt Spur des Roboters.

Eine gute KI würde wohl eher diesen Weg wählen.

Über einen Klick auf den Eintrag „Pause“ kann man das Spiel kurz unterbrechen, „Neustart“ startet das Spiel von vorne (bei einem zufälligem Kartenstapel wird ein neuer zufälliger ausgewählt). Mit „Beenden“ verlässt man die GUI und landet wieder im GUI-Starter.

Hinweis: Die GUI hat eine Größe von 1024x768 Pixeln. Das heißt, um sie sinnvoll nutzen zu können, sollte die Bildschirmauflösung größer als 1024x768 sein oder man muss im GUI-Starter einstellen, dass das Programm im „Vollbildmodus“ starten soll. Dann werden die Grafiken auf eine kleinere Auflösung herunterskaliert.

Die Spielbrett-Themen

In der GUI gibt es (derzeit) zwei Themen zur Auswahl.

Das Standardthema im Ordner images/new wurde von Arne Weinberg erstellt. Die Bilder unterliegen der GFDL.

Alternativ gibt es noch eine handgemalte Version im Ordner images/pen. Diese wurde von Dominik Wagenführ erstellt. Die Bilder unterliegen der CreativeCommons-Lizenz „Namensnennung-Weitergabe unter gleichen Bedingungen 3.0 Deutschland“.

Die beiden vorinstallierten Themen.

Erweiterungen

Da der Wettbewerb so offen wie möglich gehalten wird, kann natürlich auch jeder Nicht-Teilnehmer etwas beitragen, wenn er möchte. Es werden hier einige Möglichkeiten vorgestellt, wie man etwas beitragen kann.

Themen

Im Ordner images findet man die Themen, die für die Spielbrettanzeige genutzt werden können. Wer selbst ein neues Thema erstellen möchte, legt einfach ein neues Verzeichnis in diesem Ordner an und speichert die selbst erstellten Bilder der 31 Felder plus jeweils ein Bild für den Roboter und den Cursor dort ab. Die Felder müssen dabei eine Größe von 64x64 Pixeln haben. Der Roboter und der Cursor müssen einen transparenten Hintergrund haben.

Das neue Thema wird automatisch vom GUI-Starter erkannt und kann dort ausgewählt werden.

Spielbretter

Es ist relativ leicht, neue Spielbretter zu erstellen. Einfach eine Textdatei anlegen, in die erste Zeile die Breite und Höhe des Spielbretts eintragen und darunter dann die einzelnen Spielfelder mit obigem ASCII-Code angeben. Bis auf die Wände sind die Codes für alle Felder ziemlich leicht zu erlernen.

Ein Spielbrett sollte (für die GUI-Anzeige) nicht größer als 12x12 Felder sein, da die GUI auf diese Größe beschränkt ist.

Spielbrett-Editor

Wer Lust hat, kann auf Basis der Ruby-GUI oder als Eigenentwicklung einen Spielbrett-Editor schreiben, in welchem man per Drag & Drop die Felder auf ein Spielbrett setzen kann und dieser das Ergebnis dann als ASCII-Datei nach obigem Schema abspeichert.

Es gibt bereits einen Spielfeldeditor für das Originalspiel RoboRally, der aber für Windows geschrieben wurde. Damit lassen sich aber auch über Wine neue Spielfelder erstellen und ausdrucken.

Eine Schnittstelle für den Wettbewerb gibt es aber nicht und der Editor ist auch nicht Open Source.

Spielfelder

Neben den obigen Spielfeldern kann man sich natürlich noch zahlreiche neue Felder ausdenken, deren Funktion man in die Engine einprogrammieren müsste. Als Beispiele seien genannt:

Teleporter: Teleportiert einen Roboter von einem Feld zu einem anderen.
Fallgrube: Öffnet zu bestimmten Zeiten (z.B. jede 2 und 4 Phase einer Runde) ein Loch im Boden.
Schiebetür: Öffnet und schließt sich nur zu bestimmten Phasen.
Laser: Wie im Originalspiel RoboRally nimmt ein Roboter Schaden, wenn er im Strahl eines Lasers stehen bleibt.
Reparaturkit: Wie im Originalspiel, auf dem der Roboter wieder repariert wird.
Einbahnstraße: Der Roboter kann nur in diese Richtung ein Feld betreten und verlassen.

Der Phantasie sind keine Grenzen gesetzt.

Eine sehr gute Auflistung weiterer Spielfelder findet man auf den Seiten WarpZone und RoboFactory. Dort sind auch gleich zahlreiche Spielbretter abgelegt, die diese neuen Elemente nutzen.

Schlussbemerkungen

Wir wünschen allen Teilnehmern viel Erfolg und freuen uns auf zahlreiche Einsendungen. „Let the games begin ...“

Quellcode zur Teilnahme: per FTP oder per HTTP.