- = Projektspezifikation =
Contents
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
- 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:
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.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.
Nach einem Zug, bei dem sich mindestens eine Kachel bewegt hat, 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). Wenn sich bei einem Zug keine Kachel bewegt hat, wird keine solche Kachel dem Spielbrett hinzugefügt.
- 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.
Der höchste erreichbare Wert einer Kachel ist 2^17 = 131.072, die maximal erreichbare Punktzahl ist 3.932.100.
Projekt 1: 2048 (das Spiel)
Implementieren Sie das Spiel 2048 mit Konsolengrafik (verwenden Sie hierfür ncurses).
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 (überlegen Sie sich, dass die Anzahl der möglichen Beschriftungen begrenzt ist) 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.
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)
Die Formulierung in diesen Absatz werden noch überarbeitet, vom Prinzip her sind aber alle Informationen schon enthalten.
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 oder verschmelzen 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 können Sie zum Simulieren der zufälligen Kachel verwenden.
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).
Folgende Anforderungen müssen Sie erfüllen, um volle Punktzahl zu erreichen.
Implementierung einer Unterklasse der gegebenen abstrakten 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.
Ü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.
Ein Projekt eigener Wahl ist nur für diejenigen Kursteilnehmer:innen gedacht, denen die bisherigen Übungsblätter relativ leicht gefallen sind und die dort eine hohe Punktzahl erreicht haben.
- Das Projekt muss in Umfang und Komplexität vergleichbar zu den beiden oben beschriebenen Projekten sein.
- Sie müssen in der Lage sein, das Projekt selbstständig durchzuführen und bei eventuellen Problemen eigenständig Lösungsstrategien zu erarbeiten. Sie können bei Problemen natürlich gerne im Forum nachfragen; Sie müssen aber damit rechnen, dass wir Ihnen nicht bei jedem einzelnen Problem weiterhelfen können.
- Sind diese Voraussetzungen erfüllt, schreiben Sie bitte bis spätestens Donnerstag, den 23. Juli 2020, eine kurze Mail an Ihren Tutor (mit Cc an Claudius Korzen und Hannah Bast) mit einer kurzen Beschreibung Ihres Projektes (ein Absatz) und einer kurzen Begründung, warum es in Umfang und Komplexität mit Projekt 1 oder 2 vergleichbar ist (ebenfalls ein Absatz). Wir werden die bis Donnerstag eingegangenen Mails dann am Freitag, den 24. Juli 2020 besprechen und Ihnen dann anschließend Bescheid geben, ob wir einverstanden sind.
- Sollten wir einverstanden sein, sind Sie nicht verpflichtet, dieses Projekt auch tatsächlich zu bearbeiten. Sie können jederzeit wieder zu Projekt 1 oder Projekt 2 wechseln (z.B. wenn Sie merken, dass Sie doch kein Interesse mehr haben).