Projekt "Vier gewinnt" Ziel: Sie, als Gruppe, aber mit erkennbaren Einzelbeiträgen entwickeln ein Fortran-90 Programm, gegen das man "four in line" ("Vier gewinnt") spielen kann. Wir haben bereits gemeinsam besprochen, dass man die Implementation des Spiels in mehrere Prozeduren unterteilen kann. Eine Routine hatten wir noch vergessen, einfuegen(), welche einen Spielstein in eine bestimmte Spalte einfügt. Die Prozeduren wären also: SUBROUTINE ausgabe() - gibt das aktuelle Spielfeld aus SUBROUTINE einfuegen() - wirft einen Spielstein in eine bestimmte Spalte ein SUBROUTINE zug() - berechnet den nächsten Zug des Computers FUNCTION gewonnen() - prüft, ob einer der beiden Spieler gewonnen hat PROGRAM viergewinnt - Das Hauptprogramm, initialisiert, gibt Züge aus und liest die Züge des Gegners ein, prüft, ob die Züge möglich sind, ruft zug() auf, stellt fest, wenn einer der Spieler gewonnen hat und endet dann Überlegen Sie sich nun, welche Datenstrukturen benötigt werden. Wie soll das Spielfeld abgespeichert werden? Wie haben noch keine Argumente für die Prozeduren festgelegt, überlegen Sie sich, welche Argumente notwendig sind und definieren Sie den zugehörigen INTENT. Einigen Sie sich untereinander auf Typ, INTENT und Reihenfolge der Argumente. Sie können dann mit der Programmierung der Prozeduren beginnen. SUBROUTINE zug() wird bei weitem die anspruchvollste Prozedur sein. Die Scoring-Technik habe ich ja bereits kurz erläutert: Züge, unter deren vielen möglichen Nachfolgezügen viele Gewinnzüge sind, sind gut. Jeder Gewinnzug in Nachfolgezügen erhöht den Score. Züge, bei denen der Gegner viele Gewinnmöglichkeiten in Nachfolgezügen hat sind schlecht, also erniedrigen gegerische Gewinnzüge in Nachfolgezügen den Score. Je tiefer in den Nachfolgezügen die Gewinnzüge sind, umso einen geringer fällt das Score-Inkrement oder -Dekrement aus. Der beste Zug ist dann derjenige mit dem besten Score. Damit zug() arbeiten kann, muss es nach und nach erst die gegnerischen Züge entwickeln, dann die eigenen Antworten auf diese Züge, dann wieder die Antworten auf diese Züge usw. bis zu einer maximalen Tiefe, über die die Routine nicht hinausgeht. Diese Tiefe wird durch die zur Verfügung stehende Rechenzeit und den zur Verfügung stehenden Speicher begrenzt. Überlegen Sie sich, wie groß die maximale Tiefe etwa sein kann. Eine elegante Möglichkeit (aber nicht die Beste) ist es, SUBROUTINE zug() so zu schreiben, dass sie sich selbst aufruft. Man spricht dann von Rekursion. Rekursive Aufrufe in Fortran sind erlaubt, man muss dann die Routinen aber als RECURSIVE vereinbaren, also z. B. RECURSIVE SUBROUTINE zug(feld, spieler, tiefe, score) Rekursive Aufrufe führen dazu, dass alle Aufrufparameter und automatischen Variablen jeder Instanz der Subroutine auf dem Prozess- (oder Thread-)Stack gespeichert werden müssen. Dies führt dazu, dass der Stack extrem groß werden kann. Oft begrenzen Betriebssysteme die Stackgröße, so dass der möglichen Rekursionstiefe Grenzen gesetzt sind. Aus diesem Grund ist es meistens günstiger oder erforderlich, Rekursion durch Iteration zu ersetzen, Dies ist immer möglich. SUBROUTINE zug könnte dann 7 Nachfolgefelder allozieren, die sieben möglichen Züge machen, prüfen, ob Gewinnzüge dabei sind und dementsprechend den score verändern und dann sich selbst mit den 7 möglichen Nachfolgefeldern aufrufen, bis die maximale Tiefe erreicht ist. Wichtig ist, dass die Rekursion irgendwann endet (sonst bricht das Programm wegen des zu großen Ressourcenverbrauchs ab). Unabhängig davon, ob SUBROUTINE zug() rekursiv oder iterativ implementiert wird, ist es sinnvoll, dass Sie sich mit der Datenstruktur eines Baums (engl. "tree") vertraut machen. Die Züge und Gegenzüge des Spiels können auf natürliche Weise als Baum organisiert werden, wobei man mit dem leeren Spielfeld (als Nulltem Zug) beginnt. Dieses hat 7 mögliche Nachfolgezüge eine Ebene darunter und diese haben wieder jeweils 7 mögliche Nachfolgezüge usw. Diese Baumstruktur muss erstellt und abgearbeitet werden. Sehen Sie sich zur Theorie am Besten die Seite https://en.wikipedia.org/wiki/Tree_traversal an. Überlegen Sie sich, in welcher Reihenfolge Sie den Baum am Besten anlegen/abarbeiten (Pre-Order, In-Order, Post-Order). Im Abschnitt "Implementations" sind Pseudo-Codes sowohl zur rekursiven als auch zur iterativen Implementation angegeben. Bedenken Sie, dass die Beispiele nur für binäre Bäume (binary trees, also solche, in der jedes Baumobjekt maximal zwei Kind-Objekte hat). Bei dem Baum für Vier gewinnt hätte jedes Baumobjekt 7 Kind-Objekte. Die Algorithmen müssten darauf angepasst werden, was aber nicht sehr schwierig ist. Falls Sie Zug iterativ implementieren wollen (was ich empfehle), dann müssten Sie auch noch einen einfachen Stack für Fortran schreiben mit den Methoden push(), pop() und is_empty() (und evtl. clear()) um das Tree traversal zu serialisieren. Wenn Sie den ganzen Baum speichern, dann können Sie zwei Optimierungen des Programms vornehmen: - Nach dem gegerischen Zug befindet sich ja noch ein Großteil der möglichen Nachfolgezüge im Baum. Diese müssen Sie nicht neu berechnen sondern können sie aus dem alten Baum übernehmen. Dieser kann als Grundlage für die nächsten Berechnungen dienen und muss nur in die Tiefe erweitert werden. - Neben der Scoring-Technik kann eine gezielte Suche nach Gewinnzügen einbauen. Dies funktioniert dann, wenn es Züge gibt, mit denen man innerhalb einer bestimmten Zugtiefe sicher gewinnt, also frühestens erst nach ein paar Spielzügen. Überlegen Sie sich, wie Sie sichere Gewinnzüge in einem bestehenden Baum finden können. Sie können dies in einer separaten SUBROUTINE gewinnzug() implementieren, die nach zug() aufgerufen wird. Zum weiteren Ablauf des Projekts: Diskutieren und einigen Sie sich auf Datenstrukturen und evtl. auf globale Variablen. Teilen Sie die Programmierarbeit unter sich auf. Es können mehrere Personen an einer Routine programmieren, aber bitte stellen Sie dann sicher, dass die individuellen Beiträge gut dokumentiert sind (z. B. durch geeignete Kommentare im Code). Die Abgabe ist für den 17. Januar 2017 vorgesehen. Wir werden die Mittwochstermine bis dahin für kurze Projektbesprechungen nutzen. Die Zahl der Extrapunkte, die für Beiträge kreditiert werden, richten sich nach Qualität und Aufwand.