Vier Gewinnt Anforderungsbeschreibung - Datenstrukturdokument Hausarbeit fur die Veranstaltung Di referat

Das Programm dient dem Vergnügen. Es wendet sich an Anfänger, die dieses Spiel noch nicht kennen, aber auch an Fortgeschrittene, die ihre Spielkenntnisse vertiefen wollen. Desweiteren können verschiedene Computer--Strategien (defensiv bis aggressiv) gegen das eigene Spielkonzept getestet werden.

Soft- und Hardwareanforderungen

Benötigt wird ein AMIGA-Rechner mit der Benutzeroberfläche WORKBENCH 2.X/3.X und KICKSTART 2.0.

Qualitätskriterien

Vorgaben

Lauffähigkeit auf allen AMIGA-Rechnern, die die obengenannten Betriebssystemvoraussetzungen erfüllen. Verwendung des Maxon-C++ Compilers (MaxonC++). Das Programm soll nach den Methoden der objektorientierten Programmierung implementiert werden. Das Programm soll auf Farb- und Monochromdisplays lauffähig sein.

Geschwindigkeit

Nach ca. 3 Sekunden, jedoch spätestens nach 40 Sekunden soll beim Spiel gegen die Computer--Strategie ein Antwort-Zug generiert werden.

Der Wechsel zwischen den verschiedenen Eingabemasken soll im schlechtesten Fall 6 Sekunden dauern.

Die Hilfefunktion wird spätestens nach 40 Sekunden, im Idealfall nach 30 Sekunden erreicht.

Funktionalität

Start des Programms

Beim Start des Programms befindet sich dieses direkt im Spielmodus. Das bedeutet, daß sofort durch Eingabe eines Zuges losgespielt werden kann. Das Spiel ist dazu mit Defaultwerten initialisiert. Neben der Eingabe eines Zuges gibt es noch die folgenden Optionen:

Starten der Hilfefunktion. Die Hilfefunktion wird asynchron gestartet, so das das Spiel unbehindert fortgesetzt werden kann.

Beenden des Programms. Es erfolgt eine Sicherheitsabfrage. Wird diese positiv beantwortet, wird das Spiel abgebrochen. Ansonsten kann einfach weitergespielt werden.

Neues Spiel

Wird der Menüpunkt Neues Spiel angewählt, geschieht das Folgende. Es erscheint eine Sicherheitsabfrage, die erfragt, ob das Spiel wirklich neu begonnen werden soll. Wird dies positiv beantwortet, so wird eine Initialisierungsroutine aufgerufen, welche die internen Spielwerte neu initialisiert und die graphische Ausgabe aktualisiert. Danach kann erneut gespielt werden. Wird die Sicherheitsabfrage negativ beantwortet, so kann einfach weitergespielt werden.

Falls ein neues Spiel beginnt, wird per Zufallsgenerator bestimmt, wer den ersten Zug machen darf. Dem neu gestarteten Spiel liegt die gewählte (bzw. voreingestellte) Computerstrategie zugrunde (defensiv / normal / aggressiv).
Die Funktion Neues Spiel ist jederzeit aufrufbar.

Spielbeginn

Wird ein neues Spiel begonnen, so gilt:

Fängt der Gegner an, erfolgt sofort ein Gegenzug. Falls dies nicht der Fall ist, kann der Gegner einen Zug machen.

Nach jedem Zug erfolgt ein Gegenzug und umgekehrt, sofern das Spiel noch nicht gewonnen ist. Nach jedem Zug wird geprüft, ob das Spiel von einer Partei gewonnen ist bzw. ob ein Remis vorliegt.

Die Funktionen Hilfe, Programmende und Neues Spiel sind jederzeit verfügbar.

Spielende

Wechselt der Spielstatus in den Zustand gewonnen oder remis, so wird eine Meldung ausgegeben, welche den Benutzer über den Spielstatus informiert. Danach sind nur noch die Funktionen Hilfe, Programmende und Neues Spiel erlaubt.

Spielregeln / Spielstrategien

Spielstrategien

Es existieren 3 Spielstrategien mit verschiedenem taktischen Konzept. Die erste Strategie spielt ein defensives System (d.h. sie versucht in erster Linie einen Sieg des Gegners zu verhindern). Die zweite Strategie gewichtet defensives und agressives Spiel gleich. Die dritte Strategie bevorzugt das agressive Spiel (d.h. sie versucht möglichst schnell eine eigene 4er Reihe aufzubauen).

Spielregeln

Das Spiel beginnt mit einem leeren Spielfeld, welches 7 Felder breit und 6 Felder hoch ist. Abwechselnd wird jeweils von einem Spieler eine Kugel seiner Farbe gesetzt. Dabei wird die Kugel oben am Feld angesetzt und fällt dann unter Berücksichtigung der Schwerkraft von oben nach unten bis sie entweder ganz unten angekommen ist oder auf eine bereits liegende Kugel trifft. Demjenigen, dem es als erstes gelingt, eine gerade Reihe von 4 eigenen Kugeln zu bilden, hat gewonnen. Eine gültige 4er Reihe ist horizontal, vertikal und diagonal möglich. Reihen, welche links oder rechts (oben / unten) an den Spielfeldrand stoßen, enden dort (d.h. es sind keine 4er Reihen erlaubt, die auf der entgegengesetzten Seite des Spielfeldes fortgesetzt sind). Wenn alle Felder belegt sind, ohne daß eine 4er Reihe von einem Spieler gebildet wurde, so endet das Spiel unentschieden.

Beispiel für Sieg-Reihen

Bedienungsoberfläche

Einleitung

Die Bedienungsoberfläche ist unter WORKBENCH 2.X/3.X und INTUITION auf einem AMIGA-Betriebssystem implementiert. Die Benutzerführung erfolgt in Deutsch. Die Bedienung erfolgt mittels Maussteuerung.
Der Aufbau sämtlicher Bildschirmdialoge, d.h. Menüs, Dialogboxen und das Hauptfenster Skizze) ist konform mit den AMIGA-User-Interface Style Guides. Dies ergibt sich u.a. durch den Einsatz eines Interface-Builders (GADTOOLSBOX).
Das Programm arbeitet vollständig in einem eigenen Fenster, das nicht als Icon verkleinert werden kann.

Grafik des Programmfensters

Elemente der Programmoberfläche

Spielbrett

Das Spielfeld wird durch ein 67 Felder großes Raster dargestellt.

Status Anzeige

Hier werden entsprechend dem aktuellen Status folgende Informationen Dargestellt:

Gewählte Strategie.

Farbe der Spielsteine des Spielers.

Wer ist am Zug.

Spielstand, d.h. Spieler1/2 hat gewonnen oder Remis.

Sonstige Hinweise (z.B. auf fehlerhafte Eingaben)

Button-Bedienelemente

Die Züges des menschlichen Spielers werden mittels der Maus realisiert. Betätigen der Maus über einem Button mit einem Pfeil nach unten führt dazu, daß in der entsprechenden Spalte ein Zug (sofern zulässig) durchgeführt wird. Ist kein weiterer Zug möglich, erfolgt keine Reaktion.

Menüleiste

Eine Menüleiste am oberen Fensterrand enthält die folgenden Menüpunkte:

Menüpunkt Steuerung

Strategie 1 (defensiv):

Für den Computer-Gegner wird die defensive Strategie eingestellt.

Strategie 2 (normal):

Für den Computer-Gegner wird eine Strategie eingestellt, welche aggressive und defensive Züge gleich bewertet.

Strategie 3 (aggressiv):

Der Computer-Gegner spielt mit einer aggressiven, hauptsächlich auf den eigenen Sieg ausgerichteten Strategie.

Die Strategie kann jederzeit neu eingestellt werden.

Neues Spiel:

Bei einem laufenden Spiel wird nach einer Sicherheitsabfrage der Art ,,Ein neues Spiel beginnens` ein neues Spiel initialisiert und gestartet. Bei einer negativen Antwort läuft das Spiel ohne Veränderung weiter.

Spiel beenden:

Nach einer Sicherheitsabfrage der Art ,,Programm wirklich beendens` wird das Programm beendet. Bei einer negativen Antwort läuft das Spiel ohne Veränderung weiter.

Menüpunkt Hilfe

Bedienung:

Die Bedienung des Programms wird erklärt.

Spielregeln:

Die Spielregeln von ,,Vier Gewinnt`` werden erläutert.

Info:

Es werden Informationen über den Autor und das Spiel angezeigt (z.B. Version etc.)

Für alle Punkte des Hilfemenüs gilt: Die Hilfstexte werden mittels eines externen Textanzeigers mit Hypertext-Fähigkeiten angezeigt (z.B. MOSAIC od. AMIGAGUIDE). Die Texte erscheinen in einem separaten Fenster.

Datenstrukturen

Einleitung

,,Vier-Gewinnt`` soll nach den Regeln der objektorientierten Programmierung implementiert werden. Grundlegendes Konzept dabei ist die Verbindung von Daten und den auf ihnen anzuwendenden Aktionen. Deshalb wurde für die vorliegende Implementation eine Klasse Brett gewählt, welche einerseits die Daten des Spielbretts enthält und andererseits Methoden zu deren Manipulation (z.B. Setzen und Löschen von Steinen, Bewertungsfunktion, Strategie etc.). Da die Strategie letztlich auch nur Steine innerhalb des Spielbretts verändert, ist sie ebenfalls in der Klasse Brett angesiedelt.

Datenstruktur für einen Zug

Um einen Zug zu speichern oder zu übergeben, wird die folgende Datenstruktur benutzt:

struct Zug

Dabei kommt den Komponenten im einzelnen folgende Bedeutung zu:

Die x-Koordinate der gesetzten oder zu setzenden Kugel im 67 Raster.

Die y-Koordinate der gesetzten oder zu setzenden Kugel im 67 Raster.

spieler

Enthält einen Wert aus dem enum-Typ Farbe, der wie folgt definiert ist: enum Farbe ; Dieser Wert bezeichnet welche Kugel an der angegebenen Position zu setzen ist.

status

Enthält einen Wert aus dem enum-Typ Status, der wie folgt definiert ist: enum Status ; Dieser Wert bezeichnet ob ein Zug an die angegebene Position zugelassen ist oder nicht.

Die Klasse Brett

Die Klasse Brett enthält als Daten das Brett und einige weitere interne (private) Variablen. Desweiteren enthält sie die Funktionen zur Manipulation des Bretts und die Strategie, die anhand der Daten des Bretts einen Gegenzug berechnet.
Die Klasse Brett hat den folgenden Aufbau:

class Brett

void take_back()

Zug put(int x, Farbe f)

int detect( Zug zg )

Ergebnis check_result()

void strat(Farbe f)

Den einzelnen Daten und Funktionen kommt dabei die folgende Bedeutung zu:

Zug last; (private)

Diese Hilfsvariable vom Typ Zug speichert den letzten Zug, der im Brett gesetzt wurde. Mit ihrer Hilfe kann nach einen vorausschauenden Zug der ursprüngliche Zustand des Bretts wieder hergestellt werden.

int counter; (private)

In dieser Hilfsvariablen wird gespeichert wieviele Kugeln sich aktuell im Spielbrett befinden.

Ergebnis Zustand; (private)

Diese Hilfsvariable vom enum-Typ Ergebnis speichert den aktuellen Zustand (gewonnen / remis / verloren) welcher sich aus der aktuellen Belegung des Bretts ergibt. Der enum-Typ Ergebnis ist dabei wie folgt definiert: enum Ergebnis ; Dabei steht Sieg1 für einen Sieg des menschlichen Spielers und Sieg2 für den Sieg der Computer-Strategie.

Strategie str; (private)

Diese Hilfsvariable vom enum-Typ Strategie speichert, welche Strategie aktuell eingestellt ist. Der enum-Typ Strategie ist dabei wie folgt definiert: enum Strategie ; Die zugeordneten Zahlenwerte werden bei der Bewertung von Computerzügen addiert.

int brett[6][7]; (public)

Im Array brett wird das Spielbrett gespeichert.

Brett( Strategie strategie ) (public)

Konstruktor für die Klasse Brett. Dem Konstruktor wird die Default-Strategie übergeben. Er initialisiert das Brett und andere interne Daten.

void take_back() (public)

Diese Funktion nimmt den letzten Zug zurück. War noch kein Zug getätigt, so passiert nichts.

Zug put(int x, Farbe f) (public)

Diese Funktion versucht in der Spalte x, eine Kugel der Farbe f zu setzen. War dies erfolgreich, so wird im Rückgabezug neben der Spalte auch die y-Position, bei welcher die Kugel endete gespeichert. Desweiteren wird vermerkt, daß es sich um einen legalen Zug handelte und der Zähler für abgelegte Kugeln wird erhöht. Konnte die Kugel nicht mehr gesetzt, werden wird im zurückgegebenen Zug als x,y-Koordinate und illegal als Status vermerkt.

int detect( Zug zg ) (public)

Diese Funktion testet von der im Zug übergebenen x,y Position aus in alle Richtungen, wieviele Steine der im Zug übergebenen Farbe bereits vorhanden sind. In Abhängigkeit von der Länge der gefundenen Reihen einer Farbe wird ein Zahlenwert ermittelt, welcher der Rückgabewert der Funktion ist. Besondere Konstellationen (3er, 4er) werden mit Bonuspunkten bewertet. Konnte aus irgendwelchen Gründen keine Bewertung vorgenommen werden, wird ein negativer Zahlenwert zurückgegeben.

Ergebnis check_result() (public)

Diese Funktion ermittelt den innerhalb der Strategie gespeicherten Zustand (gewonnen / verloren / remis) und liefert diesen als Rückgabewert.

void strat(Farbe f) (public)

Diese Funktion ermittelt für die Farbe f (ausgehend von der aktuellen Brettposition und der eingestellten Strategie) einen möglichst optimalen Gegenzug und setzt diesen im Brett. Andert sich dadurch der aktuelle Zustand, so wird dies in der privaten Variablen Zustand gespeichert.

Zur verwendeten Strategie

Der Strategiekern der vorliegende ,,Vier-Gewinnt`` Implementation basiert auf einer Kombination von strategischem vorausberechnen von Zügen und Zugwahl mittels einer Greedy-Heuristik.
Kern der Strategie ist die Bewertungsfunktion, welche eine beliebige Stellung für den jeweiligen Spieler bewertet. Die Bewertungsfunktion achtet dabei darauf, daß

möglichst lange Folgen oder Pulks einer bestimmten Farbe entstehen und

mögliche 3er und 4er erkannt werden.

Um Züge vorauszuberechnen, wird nach dem Zug des menschlichen Spielers für jede Zugmöglichkeit eine weitere menschliche Kugel gesetzt und das Ergebnis bewertet. Die gemachten Züge werden danach zurückgenommen. Dann wird für die Farbe des Computers dasselbe Verfahren angewendet. Das Ergebnis dieser Prozedur ist nun eine Bewertung für die bestmögliche Stellung des Gegners (sprich: höchster Zahlenwert der Bewertungsfunktion) und eine Bewertung für den besten Zug des Computers. Bei dieser Bewertung werden darüberhinaus die nächstbesten Züge in Hilfsvariablen gespeichert.
Die Strategie entscheidet sich nun (je nach Gewichtung eher aggressiv oder defensiv) dafür, ob sie eine eigene Stellung weiterentwickelt, oder ob sie eine gute Stellung des menschlichen Gegenspielers zu verhindern versucht. Für den gewählten Zug werden nun alle Zugmöglichkeiten des menschlichen Spielers und eigene Antwortmöglichkeiten (Vorausberechnung des 2. Zuges) ausprobiert und bewertet. Ergibt diese Bewertung, daß der vermeintlich optimale Zug innherhalb von 2 Zügen zu einem Sieg des menschlichen Spielers führt (z.B. Aufbau einer Falle), so wird der errechnete Zug verworfen und der zweitbeste Zug unter der jeweiligen Prämisse (aggressiv/ defensiv) zum auszuführenden Zug gemacht. Für diesen Zug werden nun erneut alle möglichen Antwortzüge des menschlichen Spielers getestet. Ergibt sich dabei eine signifikante Abweichung, so wird der drittbeste Zug gewählt. Danach zieht die Strategie auf jeden Fall, einerseits um Rechenzeit zu sparen und andererseits um nicht unschlagbar zu sein. Die Einschätzung von Stellungen beruht also auf Vorausberechnung, wohingegen die Auswahl von Alternativzügen auf einer Greedy-Heuristik beruht (Es wird einfach der nächstbeste Zug genommen)

Mankos der Strategie

Die oben beschriebene Arbeitsweise der Strategie bedingt allerdings auch einige Probleme:

Die Strategie ist gehalten, Züge, die von der Bewertungsfunktion ähnlich gut bewertet werden (Intervall:) als gleichwertig zu behandeln. Unter gleichwertigen Zügen wird eine zufällige Auswahl getroffen. Im praktischen Einsatz hat sich aber gezeigt, daß dieses Intervall nicht ausreicht um genügend Überraschungen ins Spiel einzustreuen (vor allem in kritischen Situationen). Wählt man das Intervall jedoch größer, besteht die Gefahr das ein tatsächlich schlechterer Zug ausgewählt wird.

Auch die Greedy-Heuristik birgt einige Tücken. Die Hilfsfelder mit den nächstbesten Zügen werden bei der Bewertung der Simulation des ersten Gegenzuges gefüllt. Benutzt werden diese Alternativzüge allerdings erst, wenn sich beim 2. oder 3. vorausberechneten Zug die Notwendigkeit einer Anderung ergibt. Die Prämisse unter der ein Zug zum zweit- oder drittbesten erkoren wurde muß dann aber nicht unbedingt weitergelten. Die Alternative wäre, die Alternativzüge bei jedem simulierten Zug neu zu berechnen. Dies würde die Rechenzeit allerdings deutlich erhöhen. Der praktische Einsatz hat gezeigt, daß eventuelle Fehlentscheidungen beim zweit- oder drittbesten Zug kaum auftreten (bzw. kaum Auswirkungen haben).

Trotz dieser Mankos hat sich die Strategie im praktischen Einsatz als ausreichend Spielstark gezeigt, ohne jedoch unschlagbar zu sein. Dies ist angemessen, da das Programm ja schließlich dem Vergnügen dienen soll.