Hausarbeit Informatik 1, 1.Semester Statistik, Algorithmus entwerfen

[Easyrain]

Hallo zusammen,

wir studieren im 1. Semester Statistik an der Fachhochschule in Magdeburg und haben im Fach Informatik 1 zum Semesterende eine Hausarbeit (Gruppenarbeit von zwei Personen) zu schreiben. Wir haben uns schon viele Gedanken darüber gemacht und sind verschiedene Lösungsansätze durchgegangen und wollten zu unserem derzeitigen "Grundgerüst" mal ein Feedback von Leuten erhalten die sich mit der Materie (einen Algorithmus zu schreiben) evtl. etwas besser auskennen als wir es tun .

-------------------------------------------------------------------------------------

Die Aufgabe ist folgende:

Spielfiguren sollen auf ein quadratisches Spielbrett vom Format N x N

gesetzt werden. Dabei stehen die folgenden Figuren zur Verfügung

Typ_____|___bedroht alle Felder (bezogen auf das Ausgangsfeld)

-----------------------------------------------------------------------------------------

C(l1,l2)__|___alle Felder mit einem Abstand l mit l1 ≤ l ≤ l2

B_______|___unmittelbar benachbart [Abstand 1, also C(1,1)]

S_______|___die einen Abstand von √5 haben [C(√5,√5), Springer]

Abstände zweier Spielfelder sind hier jeweils die geometrischen Entfernungen der Quadratmitten.

Als Längeneinheit gilt die Kantenlänge eines Feldes.

Ein Spieler möchte eine Folge von Spielguren so auf das Feld setzen, dass

sich keine zwei Figuren gegenseitig bedrohen. Das Spiel bricht ab, wenn kein

Zug mehr möglich ist. Ziel ist es, möglichst viele Figuren unterzubringen.

Entwickeln Sie ein Programm, dass jeweils den nächsten Zug des Spielers

entgegennimmt, ihn überprüft, gegebenenfalls mögliche Felder für diesen

Zug angibt und feststellt, ob das Spiel beendet ist.

Der Spieler setzt dabei abwechselnd die Figuren S und B.

Hinweise:

- Formalisieren Sie die Aufgabe, d.h. geben Sie eine Codierung an, die die Aufgabenstellung

adäquat beschreibt.

- Entwerfen Sie einen Algorithmus der die Aufgabe löst und dokumentieren Sie Ihn. Der

Algorithmus kann, muss aber nicht, in einer gängigen Programmiersprachen realisiert

werden. Computercodes allein ersetzen aber nicht die Beschreibung des Algorithmus.

- Es können nur solche Unterprogramme oder Systemfunktionen als Block verwendet

werden, die allgemein in den Standardbibliotheken vorhanden sind.

- Weisen Sie die geforderte Funktionalität nach. D.h., zeigen Sie, dass der Algorithmus

endlich ist, wenn die Eingaben und Daten korrekt sind und dass er eine Fehlermeldung

generiert, wenn die Eingaben fehlerhaft sind und auch in diesem Fall regulär abbricht.

- Analysieren Sie den Aufwand des Algorithmus' und diskutieren Sie ggf. Varianten.

- Verwendete Hilfsmittel, Literatur und weitere Quellen sind nach wissenschaftliche

Kriterien zu dokumentieren. Die Selbstständigkeit der Arbeit ist durch Unterschrift

zu erklären.

-------------------------------------------------------------------------------------

Es ist klar das dies nicht alles ist, wird sind eben noch am Anfang.

-----------------------------------------------------------------------------------

Nun zu unserem "Grundgerüst":

Programmstart

- Eingabe der Spielfeldgröße N x N , N ≥ 1

- das Programm generiert das Spielfeld

→ Unterprogramm Sn-Start

- die Bedrohungsradien r müssen sich nicht vollständig auf dem Spielfeld befinden

- n ≥ 0 , n ⋲ Nat. Zahlen , N ≥ 1 , N ⋲ Nat. Zahlen

- da möglichst viele Figuren untergebracht werden sollen, werden dem Spieler nur

Möglichkeiten der Positionierung angeboten, welche an die zuletzt gesetzte Figur angrenzen

Sn-Start

- der Spieler wird aufgefordert die erste Figur S1 auf ein beliebiges Feld Cn zu setzen

- S1 nimmt dann das ausgewählte Feld ein und erzeugt den Bedrohungsradius r

→ Unterprogramm Bn-Prüfung

Bn-Prüfung

- das Programm überprüft das Spielfeld auf die Möglichkeit der Positionierung für die Figur B1+n ohne Überschneidung von r

- besteht keine Möglichkeit die Figur B1+n ohne Überschneidungen von r zu setzten

→ Unterprogramm Programmende

- besteht die Möglichkeit die Figur B1+n ohne Überschneidungen von r zu setzten,

prüft das Programm auf alle möglichen und gleichzeitig an r von S1+n angrenzenden

Positionen für B1+n und gibt diese dann wiederum als Auswahlmöglichkeiten an den Spieler aus

- der Spieler muss sich nun für eine der Möglichkeiten entscheiden

→ Unterprogramm Bn-Zug

Bn-Zug

- der Spieler setzt die Figur B1+n auf eine der Auswahlmöglichkeiten

- B1+n nimmt dann das ausgewählte Feld ein und erzeugt r

→ Unterprogramm Sn-Prüfung

Sn-Prüfung

- das Programm überprüft das Spielfeld auf die Möglichkeit der Positionierung für die Figur S1+n+1

ohne Überschneidung von r

- besteht keine Möglichkeit die Figur S1+n+1 ohne Überschneidungen von r zu setzten

→ Unterprogramm Programmende

- besteht die Möglichkeit die Figur S1+n+1 ohne Überschneidungen von r zu setzten,

prüft das Programm auf alle möglichen und gleichzeitig an r von B1+n angrenzenden

Positionen für S1+n+1 und gibt diese dann wiederum als Auswahlmöglichkeiten an den Spieler aus

- der Spieler muss sich nun für eine der Möglichkeiten entscheiden

→ Unterprogramm Sn-Zug

Sn-Zug

- der Spieler setzt die Figur S1+n+1 auf eine der Auswahlmöglichkeiten

- S1+n+1 nimmt dann das ausgewählte Feld ein und erzeugt r

→ Unterprogramm Bn-Prüfung

Programmende

- Textausgabe: Anzahl der gesetzten Figuren Bn & Sn, der Felder die mit r belegt sind und der freien Felder

- grafische Ausgabe des Spielfeldes

- Abfrage, ob ein neues Spiel gestartet werden soll

-----------------------------------------------------------------------------------

Ich hoffe das Ganze ist ohne mündlicher Erklärung (wie wir es Meinen) halbwegs verständlich .

Ist dieser Ansatz okay?

Oder sind noch gravierende Denkfehler und Logiklücken enthalten?

Wie freuen uns über Euer Feedback.

Bearbeitet 2. April 2011 von Easyrain

[flashpixx]

Ein sehr naiver Ansatz, der bei großem N sehr ineffizient wird. Ich empfehle zum Basisverständnis Nash-Gleichgewicht Selbst für einen naiven Ansatz würde man wohl zu Backtracking übergehen.

Kann man sicherlich so umsetzen, aber man kann es eleganter lösen: Anhand des Nash-Gleichgewichtes kann man dem Spieler die beste Möglichkeit für den Zug geben. Weiterhin sollte man sich eben für große N Gedanken machen, ob der Algorithmus dann noch effizient ist. Bei entsprechend großen N ist die Berechnung der gültigen Positionen aufwändig und auch von der Verteilung der aktuellen Spielfiguren abhängig. Wobei man hier eben die Berechnung mit Hilfe des Nash-Gleichgewichtes optimieren kann.

Bearbeitet 2. April 2011 von flashpixx

[Easyrain]

Danke für die Infos, ich werde mir die Links gleich mal zu Gemüte führen.

[Easyrain]

Ich finde leider irgendwie keinen richtigen Zusammenhang zwischen unserer Aufgabe und dem Nash-Gleichgewicht. Bei dem Nash-Gleichgewicht geht es doch um mehr als einen Spieler, in unserer Aufgabe gibt es doch aber nur einen. Können Sie mir da evtl. noch den einen oder anderen Tipp geben?

[flashpixx]

Über das Nash Gleichgewicht lassen sich die Ergebnisse zur Ausgabe sortieren, so dass der aktuelle Spieler nur die Felder angezeigt bekommt, die höchstmögliche Gewinnchance bieten