Die Programmieraufgabe ist prinzipiell sehr einfach gestrickt. Es geht darum, für ein sehr simples Zwei-Personen-Spiel die künstliche Intelligenz (KI), d.h. den computergesteuerten Spieler, zu erstellen. Diese soll nach Übergabe einiger Daten die (in den Augen des Programmierers) beste Zugmöglichkeit herausfinden. Auf diese Art spielen zwei künstliche Intelligenzen gegeneinander. Der Programmierer mit der besten, d.h. dominierensten KI (siehe unten für genaue Kriterien), gewinnt den Wettbewerb.

Das Spiel

Zuerst soll das Spielprinzip erklärt werden. Die Idee ist dabei nicht von uns entwickelt, sondern stammt aus dem Spiel „Bejeweled“, welches derzeit mit der Neuauflage „Puzzle-Quest“ wieder auflebt. Auf einem 10x10-Spielfeld befinden sich verschiedenfarbige Steine und Bomben. Durch das Tauschen zweier benachbarter Steine muss man mindestens drei gleichartige in eine Reihe bringen, sodass diese verschwinden und Punkte bringen. Sind diese Punktekonten weit genug aufgefüllt, erleidet der Gegner Schaden. Durch die Aneinandereihung von Bomben kann man auch direkten Schaden verursachen.

Wurden zwei Steine getauscht, werden alle gleichartigen Steine mit einer zusammenhängenden Länge (waagerecht oder senkrecht) von mindestens drei Steinen vom Spielfeld entfernt, und einem Spieler gut geschrieben oder verursachen Schaden. In den Spalten, in denen es nun freie Stellen gibt, rutschen alle Steine nach unten. Danach fallen von oben neue Steine herab und füllen das Spielfeld wieder auf.

Die Spielsteine

Wie erwähnt, gibt es verschiedenfarbige Spielsteine: grün, gelb, rot, blau und lila. Diese haben die folgende Bedeutung:

Beim „Einlösen“ der Steine verschwinden diese wieder vom Konto eines Spielers.

Zusätzlich gibt es noch Bomben mit den Werten 1-5. Reiht man von diesen mindestens drei aneinander (die Zahlwerte müssen nicht identisch sein), erleidet der Gegner Schaden in Höhe der Summe aller Werte der zusammengefügten Bomben.

Die Spielsteine erscheinen dabei nicht komplett zufällig auf dem Spielfeld, sondern werden mit folgenden Wahrscheinlichkeiten berechnet:

Das heißt, dass überhaupt eine Bombe auf einem Feld erscheint, hat eine Wahrscheinlichkeit von 0.1 und ist damit fast halb so wahrscheinlich wie bei einem farbigen Stein.

Die Spieler

Jeder der beiden Spieler hat eine bestimmte Anzahl von Lebenspunkten (Standard: 30) und einen Schild (Standard: 15). Erleidet der Spieler durch gegnerische Angriffe Schaden, wird zuerst der Schild reduziert. Wenn dieser auf 0 gesunken ist, werden die Lebenspunkte abgezogen. Erreichen diese 0, hat der Spieler verloren. Durch das Aneinanderreihen blauer Steine kann man den Schild aber bis zur Maximalzahl 15 wieder aufladen.

Dazu hat jeder Spieler ein Konto für rote, gelbe und grüne Steine. Ab einem bestimmten Wert (Standard: 15) werden diese automatisch in gegnerischen Schaden umgesetzt und verschwinden wieder vom Konto.

In der Regel sind die zwei Spieler immer abwechselnd an der Reihe. Sammelt ein Spieler aber eine bestimmte Anzahl lilafarbener Steine (Standard: 15), ist er erneut am Zug.

Beste Taktik

Zu entscheiden, was die beste Taktik ist, ist Ihre Aufgabe. Die Referenzimplementierung (siehe unten) stellt eine sehr simple KI zur Verfügung. Diese tauscht einfach so lange Steine, bis gleichartige nebeneinander liegen und sieht das als günstigen bzw. gültigen Zug an. Dieses Vorgehen ist natürlich sehr dumm.

Ein erster Fortschritt wäre es, wenn aus allen gültigen Tauschmöglichkeiten die ausgewählt wird, die dem Spieler den meisten Gewinn beziehungsweise dem Gegenspieler den meisten Schaden bringt. Oder anders: Bomben vorrangig zu sammeln ist meist sehr sinnvoll. ;)

Daneben gibt es noch andere taktische Möglichkeiten, die Sie aber selbst ausknobeln dürfen.

Beispiel

Um das Spielprinzip besser zu verdeutlichen, soll ein Beispielzug durchgeführt werden. Die Ausgangsbasis ist dabei das folgende Spielfeld:

Die Zählung der Spielfeldindizes beginnt typisch für C++ (Referenzimplementierung) bei 0, sodass die x- und y-Werte von 0 bis 9 laufen.

Der Spieler, der an der Reihe ist, hat verschiedene Möglichkeiten, einen gültigen Zug durchzuführen. Er kann z. B. Feld (0,8) mit (0,9) tauschen, was drei blaue Steine horizontal zusammenfügt, oder (6,7) mit (5,7), was drei rote Steine vertikal aneinanderreiht. Die Referenz-KI tauscht aber die Felder (1,0) mit (1,1), um drei lilafarbene Steine zusammenzufügen.

Die drei lilafarbenen Steine werden seinem Konto gut geschrieben und verschwinden.
Alle darüberliegenden Steine rutschen ein Feld nach unten, was oben eine Lücke entstehen lässt, welche durch neue Steine aufgefüllt wird:

Im nächsten Zug böte es sich für den zweiten Spieler an, Feld (2,2) mit (3,2) zu tauschen, damit der erste Spieler 10 Punkte (5 + 4 + 1) Schaden erleidet.

Referenzimplementierung

Damit niemand denkt, der Sieger würde später im Geheimen von uns gekürt, wird die eigentliche Spielmechanik unter der GPLv3 veröffentlicht:

Quellcode: per FTP oder per HTTP

Die Implementierung geschah dabei mittels C++ und befindet sich im Verzeichnis fm-game.

Daneben wurde auch, wie oben bereits erwähnt, eine einfache KI programmiert, die sich im Ordner fm-ai befindet („ai“ steht für den englischen Ausdruck „artificial intelligence“).

Möchte man das Spiel und die KI kompilieren, benötigt man einen C++-Compiler, den man am einfachsten über das Paket build-essential installiert. Danach kann man aus dem entpackten Verzeichnis wettbewerb einfach ein

make

aufrufen, was alle C++-Dateien in Binärcode umwandelt.

Wettbewerb starten

Um einen neuen Wettbewerb zu starten, müssen zwei KIs fm-ai1.bin und fm-ai2.bin im Ordner (gegebenenfalls auch nur als Link) existieren. Dazu benötigt man noch ein vorberechnetes Spielfeld (hier: beispielfeld.dat).

Hinweis: Das Beispiel umfasst dabei ein Spielfeld der Größe 10x1000, relevant, also spielbar, sind die letzten 10 Zeilen. Die Größe von 1000 Zeilen sorgt aber dafür, dass das Spielfeld in jedem Spieldurchgang nicht mit zufälligen Steinen von oben aufgefüllt wird, sondern vorberechnete Steine benutzt werden. So hat jede KI die gleichen Chancen.

Die zwei KIs lässt man per

./fm-game.bin beispielfeld.dat

gegeneinander antreten. In einem Programmdurchlauf gibt es zwei Partien mit dem gleichen Startspielfeld. Zuerst hat KI 1 den ersten Zug. Nachdem das Ergebnis der ersten Partie auf dem Bildschirm ausgeben wird, musst der Benutzer eine Taste drücken. Dann startet die zweite Partie, wobei KI 2 den ersten Zug hat.

Hinweis: Startet man das Spiel mit der gleichen KI für KI 1 und KI 2, sollte sich bei einem deterministischem Algorithmus, d. h. keine Zufallsentscheidungen, ein symmetrisches Ergebnis ergeben. Sprich, wenn Spieler 1 im ersten Spiel gewinnt, muss Spieler 2 im zweiten Spiel gewinnen und umgekehrt.

Wer sich selbst ein Spielfeld generieren möchte, kann dies über

./fm-game.bin DATEINAME create

erzeugen und dann das Spiel per

./fm-game.bin DATEINAME

mit diesem Feld starten.

Teilnahmebedingungen

Sprache

Welche Programmier- oder Skriptsprache für die KI benutzt wird, ist egal. Das Skript bzw. das Programm sollte sich aber relativ einfach auf einem „normalen“ Linux-System (genauer Ubuntu 8.10) ausführen bzw. kompilieren lassen. Es wird zwingend vorausgesetzt, dass der Code (gegebenenfalls mit einer kleinen Anleitung zum Übersetzen), und nicht nur eine Binärdatei eingereicht wird. Der Quellcode muss dabei einer freien Lizenz unterliegen.

Hinweis: Wer möchte, kann auch gerne den Code der Referenz-KI benutzen und erweitern. Damit fällt der Einstieg vielleicht etwas leichter.

Welche Sprache (also Deutsch oder Englisch) im Programm selbst für Kommentare und Bezeichnungen benutzt wird, ist dem Programmierer überlassen. Kommentare sollte es aber geben. ;)

Schnittstelle

Um eine einfache Schnittstelle zu gewährleisten, werden die Daten zwischen Spielmechanik und KI über Dateien ausgetauscht. Die Spielmechanik schreibt dabei die folgenden Dateien:

• player.dat enthält die Daten des Spielers. In jeder Zeile steht je ein Wert mit der folgenden Bedeutung:
  • Lebenspunkte
  • Schild
  • rote Punkte
  • gelbe Punkte
  • grüne Punkte
  • lilafarbene Punkte
• opponent.dat enthält die Daten des Gegners, auf die man gerne zugreifen kann. Der Dateinhalt ist dabei identisch zu oben.
• gamefield.dat enthält das 10x10 Spielfeld, wobei nur die ersten hundert Zeichen (der Art „R“, „Y“, „G“, „B“, „L“, „1“ - „5“) relevant sind. (Natürlich sollten in der Datei exakt 100 Zeichen drinstehen. ;)) Der erste Wert (linke obere Ecke) hat dabei den Index (0,9), der zweite (1,9) etc. bis hin zum letzten Wert (untere rechte Ecke) mit dem Index (9,0).

Das oben dargestellte erste Beispielfeld würde daher im Textformat so aussehen:

R B B 3 G G 5 B 1 G
B G Y Y L Y L G R L
L B L R L 1 R G G B
G L G L R R Y B R B
G Y R Y B R G L B G
B B Y Y G B R Y B Y
5 R 5 B R 2 R Y G R
Y G Y G B R L 3 R B
3 L R 4 R G B R G B
L B L 1 L 1 B G R L

Im Normalfall sollte das KI-Programm 0 als Wert zurückgeben, im Fehlerfall irgendetwas ungleich 0. Zusätzlich muss das Programm eine Datei result.dat mit den Daten der zu tauschenden Felder enthalten:

FELD_1_X FELD_1_Y FELD_2_X FELD_2_Y

So würde zum Beispiel der Inhalt

1 0 1 1

das Feld (1,0) mit dem Feld (1,1) tauschen. Felder müssen dabei immer benachbart sein und auch der Index 9 sollte nicht überschritten werden. Sollte also eine Sprache benutzt werden, die bei 1 anfängt zu zählen, sollte beim Schreiben der Datei daran gedacht werden.

Laufzeit

Die Laufzeit der KI sollte eine Minute pro Zug nicht überschreiten. Da das Spiel aber sehr einfach gehalten ist und durch die „Zufallskomponente“ nicht unendlich weit in die Zukunft berechnet werden kann, sollte die Laufzeit eigentlich gering ausfallen.

Sonstiges

Bei Fragen zur Implementierung (also nicht zur Umsetzung, sondern nur zu den Randbedingungen), steht die freiesMagazin-Redaktion unter natürlich gerne zur Verfügung.