Differences between revisions 113 and 114

Projektspezifikation

Contents

Projektspezifikation

Es gibt drei Projekte zur Auswahl:

Projekt 1: 2048 (Das Spiel)

Projekt 2: 2048 (Automatischer Löser)

Projekt 3: Ein Projekt eigener Wahl (nur für Fortgeschrittene)

Im Folgenden werden wir zunächst das Spielprinzip von 2048 erklären und danach die drei Projekte detaillierter beschreiben.

Spielprinzip von 2048

Online spielen
Das Spiel wird auf einem Spielbrett mit 4x4 Feldern gespielt.
Auf jedem Feld kann sich eine Kachel befinden, die mit einer Zweierpotenz (2, 4, 16, 32, ...) beschriftet ist.
Zu Beginn des Spiels befinden sich zwei Kacheln auf zwei zufällig gewählten Feldern des Spielbretts. Diese Kacheln sind jeweils mit 90% Wahrscheinlichkeit mit dem Wert 2 und mit 10% Wahrscheinlichkeit mit dem Wert 4 beschriftet.
Mit den Pfeiltasten (rechts, links, oben, unten) können die Kacheln in die jeweilige Richtung bewegt werden. Jede Kachel bewegt sich dabei so weit, bis sie entweder auf eine Kachel mit einem anderen Wert oder auf den Spielbrettrand stoßen. Dabei gelten folgende Regeln:
1. Die Kacheln, die durch Verschmelzen entstanden sind, werden im selben Zug nicht noch einmal mit anderen Kacheln verschmolzen. Beispiel: Die Kacheln der Reihe
```
[2 2 2 2]
```
  werden bei einer Bewegung nach rechts zu
```
[0 0 4 4]
```
  und nicht
```
[0 0 0 8]
```
  verschmolzen.
2. Falls es mehrere Möglichkeiten beim Verschmelzen der Kacheln in einer Reihe/Spalte des Spielbretts gibt, werden immer die zwei Kacheln zuerst verschmolzen, die näher an dem Spielbrettrand liegen, in dessen Richtung man schiebt. Beispiel: Die Kacheln der Reihe
```
[0 2 2 2]
```
  werden bei einer Bewegung nach rechts zu
```
[0 0 2 4]
```
  und nicht
```
[0 0 4 2]
```
  verschmolzen.
Stoßen bei einem Zug zwei Kacheln mit demselben Wert aufeinander, werden sie zu einer Kachel verschmolzen. Der Wert dieser Kachel ist die Summe der beiden Kacheln.
Ein Zug ist nicht gültig, wenn sich keine Kacheln bewegen oder verschmelzen. Im Falle eines ungültigen Zuges passiert nichts.
Mit jedem gültigen Zug wird eine neue Kachel an einer zufälligen, leeren Position des Spielbretts hinzugefügt. Der Wert dieser Kachel ist entweder 2 (mit 90% Wahrscheinlichkeit) oder 4 (mit 10% Wahrscheinlichkeit).
Die Punktzahl des Spiels ist zu Beginn 0 und erhöht sich bei jedem Verschmelzen zweier Kacheln um den Wert der resultierenden Kachel.
Das Spiel ist gewonnen, sobald eine Kachel mit dem Wert 2048 beschriftet ist.
Das Spiel ist verloren, wenn kein Zug mehr möglich ist.

Projekt 1: 2048 (das Spiel)

Implementieren Sie das Spiel 2048 mit Konsolengrafik (verwenden Sie hierfür ncurses).

Anforderungen (Minimum)

Folgende Anforderungen müssen Sie mindestens erfüllen, um volle Punktzahl zu erreichen.

Korrekte Implementierung der oben beschriebenen Spiellogik.
Bedienung des Spiels mit folgenden Tasten:
- Pfeil links/rechts/oben/unten: Zug in die entsprechende Richtung durchführen
- ESC: Spiel beenden
- n: Spiel neu starten
Anzeige der aktuellen Punktzahl.
Anzeige der Anzahl bisher durchgeführter Züge.
Anzeige einer Nachricht, wenn das Spiel gewonnen wurde (das Spiel soll aber weiter spielbar bleiben).
Anzeige einer Nachricht, wenn das Spiel verloren wurde.
Undo Funktion, mit der man x Züge rückgängig machen kann, wobei x als Kommandozeilenargument übergeben wird (standardmäßig ist x = 0).
Farbliche Markierung der Kacheln (Kacheln mit unterschiedlichen Werten sollen unterschiedlich farblich hervorgehoben werden).
Größe der Kacheln: Alle Kacheln sollen im gesamten Spielverlauf die gleiche, quadratische Größe haben. Wählen Sie die Größe der Kacheln so, dass (1) alle möglichen Beschriftungen einer Kachel genug Platz haben und vollständig lesbar sind und (2) das gesamte Spielbrett auf den Bildschirm passt. Das Erscheinungsbild des Spiels darf im Verlauf des Spiels unter keinen Umständen beeinträchtigt werden (z.B. durch zu lange Beschriftungen einer Kachel, o.ä.). Zusätzlich sollen die Kacheln mit einem geeigneten Abstand zueinander dargestellt werden (die Kacheln sollen nicht aneinander "kleben").
Trennung von Spiellogik und Grafik. Alle Funktionalitäten, die mit Ein- bzw. Ausgabe zu tun haben, sollen von der Spiellogik getrennt in eigenen Methoden und/oder Klassen stehen.
Achten Sie selbstverständlich auf alles, was Sie in der Vorlesung gelernt haben: gutes und sinnvolles Klassendesign, Trennung in .h und .cpp Dateien, Einteilung in public/private/protected, Tests für jede nicht-triviale Methode (außer für die Grafik-Methoden), const correctness, valgrind, und allgemein die 10 Gebote.

Anforderungen (Optional)

Wenn Sie möchten, können Sie ihr Spiel um beliebige Funktionalitäten erweitern (müssen es aber nicht, um volle Punktzahl zu bekommen). Hier sind einige Ideen:

Variable Spielfeldgröße, die als Kommandozeilenargument übergeben werden kann.
Animierte Bewegungen der Kacheln.
Shuffle Mode: Alle vorhandenen Kacheln zufällig auf dem Spielbrett verteilen.
Evil Mode: Zusätzliche "Evil-Kacheln", die keinen Wert haben (oder einen Wert, der keine Zweierpotenz ist) aber trotzdem ein Feld auf dem Spielbrett belegen (und somit mit keiner normalen Kachel verschmolzen werden können). Wenn zwei Evil-Kacheln aufeinander stoßen, lösen sich beide wieder auf.
Optimalen Zug vorschlagen lassen.

Projekt 2: 2048 (Automatischer Löser)

Implementieren Sie ein Programm, das versucht 2048 automatisch zu lösen. Als Hilfe stellen wir Ihnen die Bibliothek libgame2048.a zur Verfügung. Diese enthält eine Klasse Game2048State mit den folgenden Methoden.

copy Konstruktor: Diesen können Sie zum Simulieren von Zügen nutzen.
void move(int key): Führt den entsprechenden Zug aus (KEY_LEFT, KEY_RIGHT, KEY_UP, KEY_DOWN).
bool movePossible(int key): Gibt zurück, ob sich bei Ausführen des Zuges key etwas bewegen würde (andernfalls ist der Zug nicht gültig).
uint8_t getTile(int x, int y): Gibt den logarithmischen Wert der entsprechenden Kachel zurück.
void set Tile(int x, int y, uint8_t tile): Fügt eine Kachel mit logarithmischem Wert tile an der Stelle (x, y) ein, falls der Wert dort vorher 0 war und tile entweder 1 oder 2 ist. Dies soll zum Simulieren der zufälligen Kachel dienen.
uint16_t getRow(int x): Gibt die x-te Zeile als uint16_t zurück (wie in Vorlesung 11 erklärt).
uint16_t getColumn(int y): Gibt die y-te Spalte als uint16_t zurück (wie in Vorlesung 11 erklärt).

Anforderungen

Folgende Anforderungen müssen Sie mindestens erfüllen, um volle Punktzahl zu erreichen.

Implementierung einer Klasse Strategy mit der Methode selectMove, die für eine Game2048State-Instanz (siehe oben) einen gültigen Zug zurückgibt.
Der Löser sollte regelmäßig das Spiel gewinnen (d.h. eine Kachel mit dem Wert 2048 erreichen). Genauer wird Ihr Löser mit 100 Spiel-Instanzen getestet. Sie bekommen dann für jede Instanz größte Kachel / 2048 Punkte, d.h. gewinnt Ihr Löser jedes Spiel, bekommen Sie volle Punktzahl. Ist die größte Kachel kleiner, bekommen Sie entsprechend Abzug, was Sie dadurch ausgleichen können, dass Ihr Löser mehr als 2048 schafft. Sie können jedoch nicht mehr als 100 Punkte bekommen. Verwenden Sie hierzu die von uns bereitgestellte Bibliothek libgame2048Benchmark.a, die eine main Funktion enthält, um das Benchmark mit unseren 100 Instanzen laufen zu lassen.
Tipp: Überlegen Sie sich eine nicht-triviale heuristische Funktion, die bewertet, wie gut ein Zustand ist. Schreiben Sie eine Methode, die einige Züge simuliert und einen Zug in die Richtung des bestmöglichen Zustandes macht. Behandeln Sie dabei die zufällige Kachel als den Gegner (siehe Vorlesung 11) und simulieren Sie auch verschiedene (bzw. alle) Züge des Gegners, um den Erwartungswert zu approximieren (bzw. zu berechnen) (siehe Expectimax).

Projekt 3: Ein Projekt Ihrer Wahl

Alternativ zu den beiden oben beschriebenen Projekten können Sie auch ein Projekt Ihrer Wahl, das in Umfang und Komplexität vergleichbar zu den beiden Projekten ist, wählen.