Projektspezifikation

Abgabefrist für das Projekt ist Dienstag, der 9. August um 12:00 Uhr. Die Abgabefrist kann auf begründeten Antrag verlängert werden. Schreiben Sie dazu bitte eine Mail an Ihren Tutor bzw. Ihre Tutorin. 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: Nerdle, das Spiel

Projekt 2: Nerdle, automatischer Löser

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

Im Folgenden werden wir zunächst die Spiellogik von Nerdle erklären und danach die drei Projekte detaillierter beschreiben.

Die folgenden Beschreibungen sind noch nicht perfekt und können bis zur nächsten Woche noch leicht angepasst werden.
Die wesentlichen Elemente stimmen aber.

Das Spiellogik von Nerdle

• Selber spielen, dann versteht man es am besten :-)

• Zu Beginn wird zufällig eine mathematische Gleichung ausgewählt, die aus exakt acht Symbolen besteht, zum Beispiel 23+34=57. Welche Gleichungen genau erlaubt sind, wird im Abschnitt "Details" erklärt.

• Ziel des Spiels ist es, die gewählte Gleichung zu "erraten". Zu Beginn kann man wirklich nur raten, im Laufe des Spiele bekommt man Hinweise, die einem helfen, den Raum der möglichen Lösungen einzugrenzen.
• Das Spiel verläuft in Runden.
• In jeder Runde muss man eine Gleichung bestehend aus exakt 8 Zeichen eingeben. Es werden nur Eingaben akzeptiert, die auch eine mögliche Lösung sein könnten, siehe zweiter Punkt oben und den Abschnitt "Details".
• Nach der Eingabe erhält man Hinweise, indem jedes Zeichen mit einer der folgenden drei Farben unterlegt wird: grün, magenta, schwarz. Grün bedeutet, dass dieses Zeichen in der zu erratenden Gleichung an genau dieser Stelle vorkommt. Magenta bedeutet, dass dieses Zeichen in der zu erratenden Gleichung vorkommt, aber nicht an dieser Stelle. Schwarz bedeutet, dass dieses Zeichen nicht in der zu erratenden Gleichung vorkommt. Zur Einfärbung, wenn ein Zeichen mehrmals eingegeben wurde, siehe Abschnitt "Details".
• Die Eingabe und Hinweise jeder Runde werden in einer Zeile dargestellt. In der ersten Runde füllt man die erste Zeile aus, usw. Es gibt insgesamt sechs Zeilen und damit maximal sechs Runden. Errät man die Gleichung innerhalb von sechs Runden (in der entsprechenden Zeile sind dann alle Zeichen grün unterlegt), hat man gewonnen. Sonst hat man verloren.

Details

• Erlaubte Gleichungen: Erlaubte Operatoren sind die der vier Grundrechenarten, also * + - / . Es gibt genau ein Gleichheitszeichen. Rechts vom Gleichheitszeichen dürfen nur Ziffern stehen. Es gibt keine Klammern und keine unären Operatoren wie in +3 oder -4. Jede Gleichung enthält mindestens einen Operator (1234=1234 is verboten). Es gibt keine führenden Nullen wie in 04. Die Operanden von * und / dürfen nicht 0 sein (durch Null zu teilen ist verboten, und die Ausdrücke der Form 0*xxxx=0 machen in Nerdle nicht so viel Spaß). Alle Gleichungen müssen mathematisch gültig sein (denken Sie an "Punkt vor Strich"!), also 12-3*4=0, aber nicht 9-2*4=28. Divisionen sind nur erlaubt, wenn das Ergebnis exakt eine Ganzzahl ist (4*5/2=10 gilt, da 20 durch 2 teilbar ist, aber 5/2*4=10 nicht, da 5 nicht durch 2 teilbar, Operatoren werden von links nach rechts ausgewertet). Die Anzahl der nach diesem Regeln gültigen Expressions nach Länge ist: 7:7501, 8:18290, 9:320008, 10:1464019 und 11:15678220.

• Farbliche Unterlegung: Wenn ein Zeichen mehrfach eingegeben wurde, wird zuerst geschaut, an welchen Stellen dieses Zeichen auch in der zu erratenden Gleichung vorkommt. Diese Zeichen werden alle grün hinterlegt. Nehmen wir an, das Zeichen wurde noch an k weitere Stellen eingegeben. Wenn das Zeichen in der zu erratenden Gleichung an k' nicht-grünen Stelle vorkommt, dann werden k' dieser k weiteren Stellen magenta eingefärbt (welche ist egal) und die übrigen schwarz.

• Grafik: Jedes Zeichen steht zentriert in einer Box. Alle acht Boxen einer Zeile sind gleich groß und zwischen den Boxen ist etwas Abstand. Auch zwischen den Zeilen ist etwas Abstand. Die Boxen sind und während der Eingabe grau. Nach der Eingabe ändert sich die Farbe entsprechend der Hinweise, wie oben beschrieben. Die Zeichen werden immer in weiß und fett gemalt.

• Tastatureingabe: In der Zeile der aktuellen Eingabe gibt es einen Cursor (die entsprechenden Box ist leicht umrandet, alternativ kann sie auch in einer ansonsten unbenutzten Farbe gemalt werden). Wird eine Ziffer oder einer der vier zulässigen Operatoren oder ein Gleichheitszeichen eingegeben, ändert sich das Zeichen unter dem Cursor entsprechend und der Cursor wird um eins nach rechts bewegt (falls er nicht schon ganz rechts ist). Mit den entsprechenden Pfeiltasten kann man den Cursor nach links oder rechts bewegen. Bei der Eingabe von backspace hängt das Verhalten davon ab, ob unter dem Cursor ein Zeichen steht. Falls ja, wird das Zeichen gelöscht und der Cursor bewegt sich nicht. Falls nein und der Cursor nicht ganz links steht, wird der Cursor um eins nach links bewegt und falls dort ein Zeichen steht, wird es gelöscht. Bei der Eingabe von enter hängt das Verhalten davon ab, ob in der aktuellen Zeile eine (nach Nerdle-Regeln) gültige Gleichung steht. Falls nein ändert sich die Zeile nicht, aber ein entsprechender Hinweis wird angezeigt (der nach weiterem Tippen auch wieder verschwinden sollte). Falls ja, werden die Einfärbungen der Gleichung berechnet und angezeigt. Das Spiel ist dann entweder gewonnen (alles Grün), verloren (zu viele Zeile verbraucht) oder geht weiter (die nächste Zeile wird aktiv). Jeder dieser Fälle sollte sinnvoll abgehandelt werden.

• Auf dem Wiki stellen wir Dateien bereit, die alle Expressions der Länge 7, 10, und 11 enthalten. Die Expressions der Länge 7 können Sie zum Debuggen verwenden, die Expressions der Länge 10 und 11 sind recht aufwendig zu berechnen. Laden Sie diese Dateien auf keinen Fall ins SVN hoch (Ihr Tutor hat diese Dateien ja ebenfalls zur Verfügung). Falls Sie für den Solver solche Dateien auch für die Länge 8 und 9 selbst erzeugen (das geht schnell), sollten Sie diese hochladen.

Projekt 1: Nerdle, das Spiel

Aufgabe: Implementieren Sie das oben beschriebene Spiel Nerdle mit Konsolengrafik.

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

• Korrekte Implementierung der oben beschriebenen Spiellogik, Grafik und Tastenbedienung.
• Zu Beginn muss jede gültige Gleichung die gleiche Wahrscheinlichkeit haben, ausgewählt zu werden (unter der Annahme eines perfekten Zufallszahlengenerators).

• Verwendung einer TerminalManager Klasse (mit Unterklassen) von der Art wie beim 10. Übungsblatt. Sie können die Klassen entsprechend den Anforderungen des Spiels abändern.

• Spiellogik, Ausgabe (Grafik) und Eingabe (Tastendrücke) sollten in getrennten Funktionen stehen.

• Für jede Methode, die zur Spiellogik oder zur Ausgabe gehört, sollte es einen Unit Test geben. Beim Testen des Zeichnens reicht es, wenn Sie das Zeichnen einer Zeile eines Nerdlezustandes (Die Gleichung in farbigen Zellen) mocken + testen. Wir empfehlen dafür noch eine drawSymbol/drawCharacter-Methode für ein einzelnes Zeichen. Das Malen von Spielanleitungen etc. mittels "drawString" müssen Sie explizit nicht testen. Die Methoden, die einen UserInput verarbeiten müssen getestet werden ("bei linker Pfeiltaste funktioniert immer das richtige" etc), aber nicht die Methoden, die die Eingabe von der Tastatur lesen.

• Achten Sie selbstverständlich auf alles andere, was Sie in der Vorlesung gelernt haben: gutes und sinnvolles Klassendesign, Trennung in .h und .cpp Dateien, Einteilung in public/private/protected, const correctness, valgrind correctness, sinnvolle Übergabe von Argumenten (ohne unnötiges und teures Kopieren von Objekten), etc.

• Es gelten natürlich auch weiterhin die 10 Gebote und die § 2386 und 2387 BGB.

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:

• Konfigurierbare Anzahl von Zeichen pro Zeile (9, 10 oder 11 spielen sich auch sehr gut)
• Konfigurierbare Anzahl von Zeilen
• Diverse Verschönerungen der Grafik
• Motivierende Rückmeldung an den Spieler bzw. die Spielerin, wie zum Beispiel "das dauert aber ganz schön lange" oder "schon wieder falsch", wenn man die Lösung in der zweiten Zeile immer noch nicht gefunden hat.

Projekt 2: Nerdle, automatischer Löser (Solver)

Aufgabe: Implementieren Sie ein Programm, das Nerdle so spielt, dass die Gleichung in möglichst wenigen Runden (Zeilen) gefunden wird.

Als Hilfestellung stellen wir Ihnen eine statische Bibliothek libnerdle.a, sowie die Header-Datei NerdleBenchmark.h. Sie finden die Dateien auf dem SVN unter public/code/projekt. Hier eine kurze Erklärung dazu:

1. Die Header-Datei enthält die Deklaration der Klasse NerdleGameState: ein Objekt dieser Klasse stellt den aktuellen Zustand des Spiels dar (bereits erfolgte Eingaben und die farblichen Unterlegungen dazu).

2. Die Header-Datei enthält außerdem die Deklaration der abstrakten Basisklasse NerdleSolver: Für Ihren Solver sollten Sie eine Unterklasse erzeugen, die insbesondere die Methode nextGuess überschreibt ("override"). Die Methode nextGuess ist die zentrale Methode Ihres Solvers: sie nimmt als Argument den aktuellen Zustand des Spiels und berechnet daraus die nächste Eingabe und gibt sie zurück.

4. Die Bibliothek libnerdle.a liefert die Implementierung einer Grafik, die den Anforderungen des Projekts 1 entspricht, und eines Benchmarks, mit dem Sie Ihren Solver auf einer von uns vorgegebenen Menge von zu erratenden Gleichungen laufen lassen können. Das Vorgehen Ihres Solvers wird dabei grafisch dargestellt (Sie können es automatisch durchlaufen lassen, anhalten und Schritt für Schritt durchgehen) und es werden Statistiken zur Qualität angezeigt, mit denen Sie nachvollziehen können, ob Ihr Solver schon den Anforderungen genügt. Sie können diese Bibliothek wie eine .o Datei einfach dazulinken oder mit -L. -lnerdle -lncurses (die Reihenfolge ist hierbei wichtig, siehe Vorlesung 2. Falls Sie Probleme hierbei haben, lesen und ggf. antworten Sie auf diesen oder diesen Forumspost). Sie müssen außerdem eine Datei NerdleBenchmarkMain.cpp schreiben, die ein Main-Funktion enthält, sodass ./NerdleBenchmarkMain <n> <mögliche Weitere Argumente...> ein Objekt ihrer Solver-Klasse erstellt und initialisiert, und dann runNerdleBenchmark(n, &yourSolverObject) (aus der Datei NerdleBenchmark.h) aufruft. Ein Template für diese Datei finden Sie ebenfalls im SVN.

5. Falls ihre NerdleBenchmarkMain neben der Länge der Expressions noch weitere Argmumente benötigt (z.B. eine Datei mit allen möglichen Expressions der Länge) sollte das aus der Usage message und Ihren Erfahrungen hervorgehen, sodass Ihr*e Tutor*in weiß, wie man den Solver aufruft.

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

• Ihr Solver muss für Eingaben der Länge 8, 9, 10 und 11 funktionieren.

• 80% der Funktionalität gemäß Bewertungsschema sind erreicht, wenn Ihr Solver im Durchschnitt nicht mehr als die folgende Anzahl von Runden braucht. Für Eingabelänge 8: 3.5. Für Eingabelänge 9: 4.0. Für Eingabelänge 10: 3.9. Für Eingabelänge 11: 4.1. Diese Werte erreicht man schon mit einem konzeptionell einfachen Solver, der in jeder Runde alle Eingaben bestimmt, die mit allen bisher erhaltenen Hinweisen in Einklang sind, und davon eine zufällige wählt.

• Die restlichen 20% der Funktionalität gemäß Bewertungsschema sind erreicht, wenn Ihr Solver im Durchschnitt nicht mehr als die folgende Anzahl von Runden braucht. Für Eingabelänge 8: 3.4. Für Eingabelänge 9: 3.8. Für Eingabelänge 10: 3.85. Für Eingabelänge 11: 4.05. Diese Werte erreicht man, wenn man vorgeht wie unter dem vorherigen Punkt beschrieben, aber aus der Menge der möglichen Lösungen etwas geschickter wählt als rein zufällig.

• Ihr Solver darf nicht offensichtlich auf den gegebenen Benchmark overfitten. Also nicht "Ich weiß, welche Expressions der Benchmark abfragt, und berücksichtige nur die. Konzeptionell sollte ihr Solver auch bei einem anderen zufälligen Benchmark der gleichen Länge eine ähnliche Performance bringen.

• Ihr Solver sollte hinreichend effizient sein. Pro Benchmark sollte die Laufzeit maximal 1 Minute betragen.

Projekt 3: Ein Projekt Ihrer Wahl

Alternativ zu den beiden oben beschriebenen Projekten können Sie auch ein Projekt Ihrer Wahl bearbeiten.

• Ein Projekt eigener Wahl ist nur für diejenigen Kursteilnehmer:innen gedacht, denen die bisherigen Übungsblätter leicht gefallen sind und die dort eine hohe Punktzahl erreicht haben.

• Das Projekt muss von Umfang und Komplexität her vergleichbar sein zu den beiden oben beschriebenen Projekten.
• 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 21. Juli 2022, eine kurze Mail an Ihren Tutor (mit Cc an Johannes Kalmbach 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 Ihnen dann bis spätestens Freitag, den 22. Juli 2022 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.