Programmier­wettbewerb 2015

In diesem Semester geht es um das Puzzlespiel SameGame. Hierbei geht es darum so geschickt Steine zu entfernen, dass so wenige wie möglich übrig bleiben.

Die Herausforderung in diesem Wettbewerb ist es ein Programm zu entwickeln, welche in der Lage ist, das Spiel zu spielen.

Es gelten die allgemeinen Richtlinien für Programmierwettbewerbe.

Allgemeine Spielregeln

Das Spielfeld ist immer rechteckig. An jeder Position kann ein Stein mit einer Farbe liegen.

In jedem Zug wird ein Stein ausgewählt, der entfernt werden soll. Damit ein Stein entfernt werden kann muss mindestens einer seiner Nachbarn die gleiche Farbe besitzen wie er selbst. Nachbarschaft gilt nicht in der diagonalen.

Wenn ein Stein entfernt wird, werden mit ihm alle Nachbarn und deren Nachbarn usw. gleicher Farbe mit entfernt. Entstehen dadurch Lücken im Feld, “fallen” die Steine nach unten. Ist eine Spalte komplett entfernt, rücken die rechts davon liegenden Spalten nach links auf. Entsprechend der Anzahl der pro Zug entfernten Steine erhält der Spieler Punkte. Die Punkte werden nach der Formel \((n-1)^2\) berechnet, wobei n die Anzahl der entfernten Steine ist.

Ein-/Ausgabe Format

Euer Programm wird über die Standard Ein- und Ausgabe mit dem Spiel kommunizieren.

Vor jeder Runde erhält euer Programm das aktuelle Spielfeld als Liste von Listen.

[[1, 3, 2, 3], [4, 1, 4, 4], [2, 3, 4, 2], [3, 1, 1, 2]]

Jede innere Liste entspricht einer Zeile des Spielfeldes, jedes Element einer Liste einem einzelnem Spielstein. Ein Feld mit dem Steinwert 0 ist eine leeres Feld. Jede andere Steinwert steht dabei für eine Farbe. Das Spielfeld wird grundsätzlich in einer einzigen Zeile übertragen.

Ein Stein wird über seine Koordinaten \((x,y)\) ausgewählt. Die Zählung beginnt bei 0. Der erste Wert (\(x\)) steht dabei für die Spalte, der zweite Wert (\(y\)) steht für die Zeile.

Die Zeile 0 ist die unterste Zeile des Spielfeldes, alle Steine “fallen” in diese Richtung.

Das obige Spielfeld:

  <---- Spaltenvorschub

3 |  3  1  1  2  |
2 |  2  3  4  2  | Fallrichtung
1 |  4  1  4  4  |
0 |  1  3  2  3  v
--+-------------
  |  0  1  2  3

In jedem Zug wird ein Stein ausgewählt der entfernt werden soll. Eine Lösung für eine Runde besteht aus einer Liste von Zügen. Dabei wird jede Lösung in einer eigenen Zeile ausgegeben. Erst mit dem Schreiben des Zeilenumbruchs gilt die Lösung als vollständig.

[(2, 1), (2, 1), (1, 0), (0, 0), (2, 2)]

Woraufhin das Brett dann so aussieht:

3 |  3  1  1  2     3 |  3  1  0  0     3 |  3  0  0  0     3 |  3  0  0  0     3 |  0  0  0  0     3 |  0  0  0  0
2 |  2  3 [4] 2     2 |  2  3  0  2     2 |  2  1  0  2     2 |  2  0  0  2     2 |  3  0 (2) 0     2 |  3  0  0  0
1 |  4  1 (4)[4] -> 1 |  4 [1](1) 2  -> 1 |  4 [3] 0  2  -> 1 |  4  0  0  2  -> 1 |  2  0 [2] 0  -> 1 |  2  0  0  0
0 |  1  3  2  3     0 |  1  3  2  3     0 |  1 (3) 2  3     0 | (1)[1] 2  3     0 |  4  2  3  0     0 |  4  2  3  0
--+-------------    --+-------------    --+-------------    --+-------------    --+-------------    --+-------------
  |  0  1  2  3       |  0  1  2  3       |  0  1  2  3       |  0  1  2  3       |  0  1  2  3       |  0  1  2  3

Punkte: (3-1)^2   +         (2-1)^2   +         (2-1)^2   +         (2-1)^2   +         (2-1)^2
            2^2   +             1^2   +             1^2   +             1^2   +             1^2
              4   +               1   +               1   +               1   +               1       = 8 - 0 - 1 - 1 = 6

Es dürfen innerhalb einer bestimmten Zeit beliebig viele Lösungen abgegeben werden. Gewertet wird am Ende die letzte vollständige Lösung. Achte darauf nach jeden Schreibvorgang den Schreibpuffer zu leeren, damit nicht eine Lösung eventuell im Puffer hängen bleibt und nicht gewertet wird.

Es ist zu beachten, dass während der Durchführung des Wettbewerbs die Standardeingabe von uns nicht geschlossen wird. Es sollte beim Einlesen der Daten also nicht auf ein EOF gewartet werden

Fehler

Shoot-out

Jeder Teilnehmer erhält für den Shoot-Out einen Rechner im Rechenzentrum. Auf dem Rechner wird der Spiel-Client gestartet, welcher mit den Kontroll-Server kommuniziert. Der Spiel-Client startet dann für jede Runde das Programm.

Es werden mehrere Runden gespielt.

In jeder Runde werden die Parameter, wie Auftrittswahrscheinlichkeiten der Farben oder die Spielfeldgröße angepasst. Es wird auch nicht zufällig generierte Spielfelder geben. Alle Spielfelder auf denen gespielt wird, enthalten keine ungültigen Positionen, wie schwebende Steine oder leere Spalten mitten im Brett.

Alle Programme bekommen das gleiche Spielbrett, um Vergleichbarkeit zu gewährleisten.

Nach Programmstart werden die benötigten Daten über die Standardeingabe übergeben. Mit dieser Übertragung beginnt die Rundenzeit und es können Lösungen eingereicht werden.

Zwischen dem Start der Programme und der Übergabe der Nachrichten lassen wir aus Gründen der Chancengleichheit genug Zeit, um z.B. eine VM oder einen Interpreter vollständig zu starten.

Die Zeit bis zur Terminierung des Programms ist begrenzt, beträgt jedoch minimal eine Sekunde, so dass jedes Programm die Möglichkeit hat wenigstens eine Lösung auszugeben. Die Teilnehmerprogramme werden nach abgelaufener Zeit falls nötig gewaltsam beendet.

Die Bewertung läuft in jeder Runde gleich: Wenn in einem Zug n Steine zerstört werden, dann bekommt der Spieler \((n-1)^2\) Punkte für die Runde gutgeschrieben. Am Ende der Runde gibt es für jede verbleibende Farbe auf dem Feld einen Punkteabzug. Wenn n Blöcke einer Farbe auf dem Spielfeld verbleiben werden \((n-1)^2\) Punkte abgezogen.

Die Gesamtpunktzahl wird aus der Summe der Punkte der einzelnen Runden gebildet. Da unterschiedlich große Spielfelder verschiedene Größenordnungen von Punkten ermöglichen, werden die Punkte pro Runde über die Größe des Feldes normalisiert.

Aktualisierung 18.05.: Die Normalisierung wird nicht nur über die Größe des Feldes stattfinden. Wie normalisiert wird steht noch nicht endgültig fest. Die maximale Feldgröße ist 256x256 mit 255 Farben (‘0’ ist das leere Feld).

Aktualisierung 02.06.: Sowohl beim Ein- als auch beim Ausgabeformat dürfen beliebig viele Leerzeichen zwischen den Tokens ('[', ']', '(', ')', ',', Zahl) auftauchen.


by AStA Wedel