Projektspezifikation

Abgabefrist für das Projekt ist Dienstag, der 11. August um 12:00 Uhr. Die Abgabefrist kann auf begründeten Antrag verlängert werden. Schreiben Sie dazu bitte eine Mail an Claudius Korzen, mit Cc an Ihren Tutor und Prof. Bast. Wir empfehlen aber sehr, das Projekt sobald wie möglich fertig zu stellen. Die Erfahrung vergangener Jahre zeigt, dass man im Programmieren schnell aus der Übung kommt und es sehr viel mehr Arbeit ist, nach einer längeren Pause wieder anzufangen.

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.
• Stoßen bei so einer Bewegung zwei Kacheln mit demselben Wert aufeinander, werden sie zu einer Kachel verschmolzen. Der Wert dieser Kachel ist die Summe der beiden Kacheln. Weiterhin 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.

• 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 vorbei, 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 vorbei ist.

• 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 Größe haben und dem Bildschirm quadratisch aussehen. 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)

Implementieren Sie ein Programm, das 2048 automatisch so spielt, dass ein möglichst großer Wert für die größte Kachel (und damit auch eine möglichst hohe Punktzahl) erreicht wird. Als Hilfe stellen wir Ihnen zwei statische Bibliotheken libgame2048.a und libgame2048_main.a und die Header-Dateien Game2048Strategy.h, Game2048State.h und Game2048Drawer.h zur Verfügung. Sie finden die Dateien auf dem SVN unter public/code/projekt. Hier eine kurze Erklärung dazu:

1. Die Datei Game2048Strategy.h enthält die Deklaration einer einfachen abstrakten Klasse Game2048Strategy. Ihr Solver muss eine Unterklasse dieser Klasse sein und eine Methode selectMove bereitstellen, die für ein gegebenes Objekt der Klasse Game2048State (siehe nächster Punkt) den nächsten Zug berechnet.

2. Die Datei Game2048State.h enhält die Deklaration einer Klasse Game2048State. Ein Objekt dieser Klasse repräsentiert einen Zustand des Spiels. Die Klasse stellt diverse Methoden für Ihren Solver zur Verfügung. Einige davon brauchen Sie auf jeden Fall (die Methoden dieser Klasse sind Ihre einzige Möglichkeit, den Zustand des Spieles zu verändern), andere sind optional (zum Beispiel getColumn und getRow, die eine Zeile bzw. Spalte als uint16_t zurückliefern, was für eine besonders effiziente Implementierung mittels table lookup interessant sein kann).

3. Die Datei Game2048Drawer.h enthält die Deklaration einer Klasse Game2048Drawer mit einer Methode drawGameState, die einen gegebenen Zustand schön darstellt. Sie müssen diese Methode nicht benutzen, sie könnte aber beim Debuggen oder beim Testen Ihrer Strategie hilfreich sein.

4. Die Bibliothek libgame2048.a liefert die Implementierung für die Methoden aus den Klassen Game2048State und Game2048Drawer. Sie können Sie wie eine .o Datei einfach dazulinken oder mit -L. -lgame2048 (siehe Vorlesung 2).

5. Die Bibliothek libgame2048_main.a liefert die Implementierung einer main Funktion, mit der Sie Ihre Strategie auf 100 von uns vorgegebenen Benchmarks laufen lassen können. Sie müssen dazu in einer Ihrer .o Dateien die globale Funktion Game2048Strategy* getStrategy() implementieren. Achtung: diese Bibliothek muss bei Linken *vor* der libgame2048.a kommen.

Die main Funktion aus Punkt 5 visualiert den Zustand des Spiels (Sie werden es sehen, wenn Sie das Ü11 bearbeiten). Mit der Leertaste lässt sich die Visualisierung anhalten und wieder fortsetzen. Mit der Taste s (für step) können Sie sich langsam einen Zug nach dem anderen anschauen. Mit dem ersten Argument der Kommandozeile können Sie die Anzahl Benchmarks kontrollieren (Sie können auch mehr als 100 laufen lassen, für die Wertung zählen aber nur die ersten 100).

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

• Implementierung einer Unterklasse der gegebenen abstrakten Klasse Game2048Strategy mit der Methode selectMove, die für ein Objekt der Klasse Game2048State (siehe Punkt 2 oben) einen gültigen Zug zurückgibt. Bereitstellung einer Funktion Game2048Strategy* getStrategy(), so dass der vorgegebene Benchmark (siehe Punkt 5 oben) durchläuft.

• Sie bekommen für jede der 100 Instanzen des Benchmarks einen Score von größte Kachel / 2048. Falls die größte Kachel 2048 ist, ist das ein Score von 1.0. Falls die größte Kachel 1024 ist, ist das ein Score von 0.5. Falls die größte Kachel 4096 ist, ist das ein Score von 2.0. Um die volle Punktzahl für das Projekt zu erreichen, muss die Summe dieser Scores für die ersten 100 Benchmark-Instanzen mindestens 80 sein.

• Ihr Solver muss die 100 Instanzen hinreichend schnell lösen. Im Schnitt darf Ihr Solver pro 10.000 erreichter Punkte nicht mehr als 10-15 Sekunden brauchen.

Es gibt viele Möglichkeiten und Strategien für dieses Spiel. Hier ist eine relativ naheliegende: Ü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).