#acl adpult:read,write Hannah Bast:read,write Claudius Korzen:read,write All:read = 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 == * [[https://play2048.co/|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). {{{ #!html
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 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 [[https://ad-wiki.informatik.uni-freiburg.de/teaching/ProgrammierenCplusplusSS2020/Regeln|10 Gebote]]. {{{ #!html
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 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 [[https://daphne.informatik.uni-freiburg.de/ss2020/ProgrammierenCplusplus/svn/public/code/projekt/|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''). {{{ #!html
Anforderungen (Minimum)
}}} 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. {{{ #!html
Tipp
}}} 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) ([[https://www.geeksforgeeks.org/expectimax-algorithm-in-game-theory/|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. {{{ #!html
Anforderungen (Minimum)
}}} * 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).