Entwurf eines Schachspiels

[*Q* 1]

Hallo zusammen,

ich arbeite zurzeit zusammen mit Eggy an einem Schachspiel.
Wir haben gerade mit einem Klassenentwurf angefangen, dabei haben wir erstmal mit ein paar Logikklassen begonnen.

Wir haben uns folgendes überlegt:
Es gibt eine abstrakte Klasse ChessFigure, von der dann konkrete Klassen wie Queen, King und wahrscheinlich auch die Klasse "Empty" abgeleitet werden.
Außerdem gibt es eine Klasse ChessField, die das Schachfeld modelliert.

Wir haben zu dem, was wir uns bisher überlegt haben mal ein Klassendiagramm erstellt:
http://imageshack.us/photo/my-images/703/chessx.jpg/

Was haltet ihr von dem bisherigen Entwurf? Würdet ihr das auch so machen? Gibt es Verbesserungsmöglichkeiten?

Außerdem haben wir eben überlegt, wie das ganze weitergeführt wird.
Natürlich wollen wir eine grafische Oberfläche haben. Und dabei wollen wir auch flexibel sein, so dass wir z.B. zwischen einer 2d und einer 3d ansicht wechseln können.
Deswegen wollen wir Model-View-Controller oder etwas ähnliches benutzen.
Dabei sind wir eben auf ein paar (Verständnis-?)Probleme gestoßen:
Zuerst hatten wir gesagt, dass ChessField unser Model ist, schließlich speichert es, an welcher Position welche Figuren sind. Dazu regelt es auch noch die ganze Spiellogik.
Allerdings sind für die graphische Anzeige z.B. auch Sachen wichtig, wie, welche Figur gerade ausgewählt ist und welche Züge man mit dieser Figur machen könnte (dabei sollen dann später Züge, die eine gegnerische Figur schlagen rot markiert werden).
Allerdings gehört z.B. die Information, welche Figur ausgewählt ist meiner Meinung nach nicht mit in die ChessField Klasse.
So würden wir allerdings dann 2 Models habe. Einmal das Model der Logik (ChessField) und einmal noch ein Model für Sachen, die die Anzeige betreffen.
Ich habe letztens von dem Model View ViewModel gelesen, wäre das dann hier das richtige? Oder einfach die Information, welche Figur ausgewählt ist mit in die View packen (was dann aber für Wiederverwertung von anderen Views vermutlich nicht so optimal ist)? Wie würdet ihr das umsetzen?

Viele Dank schonmal für eure Hilfe!

Edit:

Mit List ist keine Linkedlist gemeint, sondern ein vector/eine arraylist.

[Hektor]

ChessField->content[x][y] beinhaltet eine ChessFigure mit ChessFigure.position == (x,y)

Das ist nicht schön, sieht man aber oft.
Lös' erstmal dieses Problem.

[*Q* 1]

Mir ist auch schon aufgefallen, dass das redundant ist und zu inkonsitenzen führen könnte.
Allerdings ist es auch komfortabel, die Positionen bei der Figur zu haben.
Ansonsten muss man bei GetValidTurns die position übergeben.
Ist das die Lösung, auf die du hinaus wilst (falls du überhaupt auf was bestimmtes hinauswillst^^)?

[Hektor]

Desweiteren muss das Spielfeld in der Lage sein, "Probezüge" der KI zu speichern. Die KI (MinMax oder besser Alpha-Beta-Algorithmus http://de.wikipedia.org/wiki/Alpha-Beta-Suche) probiert sehr viele Positionen aus und bewertet sie.

Das kann man z.B. realisieren durch Stacks auf jedem Feld des Brettes. Die werden beim durchtesten auf und abgebaut.

[Hektor]

Q schrieb:

Ist das die Lösung, auf die du hinaus wilst (falls du überhaupt auf was bestimmtes hinauswillst^^)?

Ich will darauf hinaus, dass so etwas Punkte sind, die auf Designfehler hindeuten.

[Hektor]

Get/SetFigureAt sprengt die Kapselung von Figure[][].
GetRemovedFirguresWhite/Black sprengt die Kapselung von List<Figure>.

Wozu dann überhaupt kapseln?

ChessField ist insgesamt zu groß. Zu viel Logik, zu viele Aufgaben an einem Platz. Am Ende packt ihr dort auch noch die Renderlogik rein.

Neee ... mir gefällt der Ansatz bisher nicht.

[Hektor]

Es ist eine überladene Ansamlung von Methoden. Echte Kapselung gibt es nicht, am Ende ist alles public oder über Getter direkt Zugreifbar.

An der Stelle kannst Du Dich fragen, ob Du Objektorientiert programmieren willst (dann kann der bisherige Ansatz verworfen werden) oder ob ein prozeduraler Ansatz nicht auch ausreichend ist.
Ein Schachspiel ist in 1000 Zeilen abgefrühstückt. Also ein einfaches Spiel mit moderater KI, keine Großmeistersoftware. Da kann man auch auf OO verzichten, wenn man es sowieso nicht richtig umsetzen kann.

[*Q* 1]

Hektor schrieb:

Get/SetFigureAt sprengt die Kapselung von Figure[][].

Ein getter ist aber auf jeden fall nötig, wenn man z.B. das feld darstellen will.
Du hast recht, dass set evtl. nicht nötig ist. Wenn kein set, dann müssen aber andere methoden, wie z.B. DoMove dasein, die indirekt ein set erwirken.

Hektor schrieb:

GetRemovedFirguresWhite/Black sprengt die Kapselung von List<Figure>.

Das ist in dem Diagramm etwas unglücklich ausgedrückt. Zurückommen soll da eine immutable collection, wie genau das umgestzt wird sehen wir später.

Hektor schrieb:

Neee ... mir gefällt der Ansatz bisher nicht.

Hast du Alternativvorschläge?

Hektor schrieb:

Am Ende packt ihr dort auch noch die Renderlogik rein.

Das wollten wir ja gerade nicht machen, wir wollen ja austauschbare views haben.

Vielen Dank schonmal für dene Hilfe!

Edit:
Auf OO verzichten wollen wir nicht.

[Eggy]

Hektor schrieb:

Es ist eine überladene Ansamlung von Methoden. Echte Kapselung gibt es nicht, am Ende ist alles public oder über Getter direkt Zugreifbar.

An der Stelle kannst Du Dich fragen, ob Du Objektorientiert programmieren willst (dann kann der bisherige Ansatz verworfen werden) oder ob ein prozeduraler Ansatz nicht auch ausreichend ist.
Ein Schachspiel ist in 1000 Zeilen abgefrühstückt. Also ein einfaches Spiel mit moderater KI, keine Großmeistersoftware. Da kann man auch auf OO verzichten, wenn man es sowieso nicht richtig umsetzen kann.

Ich fürchte, so langsam ist ein Disclaimer angebracht.

Hektor, du hast völlig recht. Das ganze kann in 1000 Zeilen ohne OO und mit mittelmäßiger KI "abgefrühstückt" sein. Da sprechen jedoch einige Aspekte dagegen:

• Wir sind beide Informatikstudenten und haben bis jetzt nur OO-Sprachen gelernt. Natürlich könnten wir uns auch trockenes C nehmen oder in einer OO-Sprache alle OO-Elemente rauslassen... was würde das bringen? Schließlich wollen wir einen Lerneffekt von der ganzen Sache haben
• 1000 Zeilen? Möglich. Dennoch: Wir haben weder Speicherplatzprobleme noch Zeitprobleme. Wir coden, weil wir eine Idee haben und sie umsetzen wollen, und dabei würden wir uns gerne sowenig Restriktionen wie möglich auferlegen. Sonst könnten wir nämlich auch gleich aufgeben und Schach auf einer 0815-Seite spielen und uns ärgern, dass die Seite nicht die Funktionen anbietet, die uns vorgeschwebt haben
• Die KI sollte erstmal außen vor gelassen werden, die ist ja (zumindest für uns) ne Klasse für sich. Uns genügt es, wenn zwei Leute ein selbstgeschriebenes Spiel über Netzwerk spielen können.

Außerdem: Warum so negativ? Warum nur destruktive Kritik? Sätze wie "auf OO verzichten, wenn man es sowieso nicht richtig umsetzen kann" kannst du dir eigentlich sparen, sie bringen nämlich nichts. Ich weiß nicht, wer du bist, und wir sind mit Sicherheit nicht so gut im Programmieren, wie du, aber das ist der Grund, warum wir hier sind: Wir haben ein Konzept, sind damit unzufrieden und hoffen auf Hilfe in der Form "Warum macht ihr nicht das und das, dann läuft jenes besser" und nicht "Lasst es wenn ihr es nicht könnt".

Also dann, auf ein Neues

[Th69]

Hallo Q und Eggy,

laßt euch nicht runtermachen

Sicherlich gibt es noch ein paar Verbesserungen am Design, jedoch erkennt man diese auch meist erst, wenn man schon einige Projekte gemacht hat (d.h. mittels Erfahrung).

Im OO-Sinne solltet ihr tatsächlich nicht direkt Zugriff auf einzelne Member geben, sondern Aktionen (Tätigkeiten) definieren, z.B.

bool IsMovePossible(Field from, Field to) const;
void MoveFigure(Field from, Field to);

wobei Field z.b. eine Struktur/Klasse mit X- und Y-Position wäre (entspricht wohl in etwa eurem "Point").

Und dann solltet ihr noch strikter zwischen Spielfeld und Spielfiguren unterscheiden (daß ein leeres Feld (Empty) eine Figur darstellt, ist nicht gerade intuitiv
Und bei einem Zug würdet ihr ja immer das Feld (Figure bzw. ChessFigure bei euch?) komplett kopieren.

Ihr könntet es intern so machen, daß ihr eine feste Liste (bzw. Array) von Figuren habt (also mit 16 Elementen) und euer Spielfeld dann nur auf diese Figuren referenziert (bzw. ein Feld NULL ist).

Für die KI ist es sogar (aus Performance-Gründen) oftmals erforderlich, daß die Positionen doppelt gespeichert werden, so daß man vom Spielfeld auf die Figur und von der Figur auf dessen Position auf dem Spielfeld schnell zugreifen kann.

[Hektor]

Eggy schrieb:

Außerdem: Warum so negativ? Warum nur destruktive Kritik? Sätze wie "auf OO verzichten, wenn man es sowieso nicht richtig umsetzen kann" kannst du dir eigentlich sparen, sie bringen nämlich nichts.

War absolut nicht negativ oder destruktiv gemeint. Falls das so angekommen ist bitte ich um entschuldigung.

Ich finde es gut, dass ihr einen OO-Ansatz wählen wollt. Im wesentlichen wollte und will ich nur folgendes sagen: Wenn schon OO in einem Lernprojekt, dann konsequent und bedingungslos. Man kann sehr viel bei sowas lernen.
Schaut euch wichtige Prinzipien der OO an (http://en.wikipedia.org/wiki/Solid_%28object-oriented_design%29), wühlt euch durch Design-Pattern (http://de.wikipedia.org/wiki/Entwurfsmuster). Verfeinert den Entwurf bis er durchgehend konsistent, erweiterbar, sauber und schön ist. Das kann durchaus mit Code passieren und muss nicht in Form von UML stattfinden.

Im übrigen ist der Alpha-Beta-Algorithmus nicht sehr schwierig zu implementieren und als kleine aber feine Anforderung, solltet ihr eine darauf basierende KI in Betracht ziehen. Es ist extrem befriedigend, gegen eine eigens entwickelte KI zu verlieren

Und die Frage betreffend ob ich Verbesserungsvorschläge oder sogar ein konkretes Design hätte: Ja. Aber das ist euer Projekt. Man lernt durch eigenes Entdecken am meisten. Wenn hier gemeckert wird, bitte nicht persönlich nehmen.

[Hektor]

Eggy schrieb:

Sätze wie "auf OO verzichten, wenn man es sowieso nicht richtig umsetzen kann" kannst du dir eigentlich sparen, sie bringen nämlich nichts.

Unglücklich formuliert. Sorry.
Ich wollte eher ins Bewusstsein rufen, dass OO nicht immer notwendig ist und manchmal viel anstrengung erfordert. Wie oben gesagt lernt man trotzdem extrem viel dabei, ein kleines Projekt mit OO-Konzepten zu überladen. Also weiter mit eurem Plan

[*Q* 1]

Ok, wenn du uns dein konkretes Design nicht nennen willst, dann kannst du ja unseres kommentieren.

Du meintest ja dir wär da zuviel in einer klasse.
Wärst du dann für eine solche Aufteilung?

ChessField
--
-content: Figure[8][8]
--
+SetAsNormalField(): void
+SetAs960Field(): void
+GetFigureAt(Point): Figure
+DoTurn(Point, Point): void

ChessLogic
--
-field: ChessField
--
+IsValidTurn(Point, Point): bool
+IsCheck(): Figure
+IsCheckMate(): Figure

ChessGame
--
-field: ChessField
-logic: ChessLogic
--
//TODO

[µngbd]

Q schrieb:

Allerdings sind für die graphische Anzeige z.B. auch Sachen wichtig, wie, welche Figur gerade ausgewählt ist und welche Züge man mit dieser Figur machen könnte (dabei sollen dann später Züge, die eine gegnerische Figur schlagen rot markiert werden).

Ich würde Engine und GUI trennen.

Q schrieb:

Wie würdet ihr das umsetzen?

Lest mal ein paar Zeilen zum Computerschach, zum Beispiel hier:
http://www.frayn.net/beowulf/theory.html

Zum Beispiel die ganze Magie mit den 64-Bit-Worten bei der Zuggeneration. Ich würde darauf achten, dass mein Entwurf solche Techniken nicht völlig unmöglich macht.

[*Q* 1]

µngbd schrieb:

Ich würde Engine und GUI trennen.

Genau das haben wir vor.
Die GUI muss die Engine aber fragen können, welche Figur wo ist, um sie anzuzeigen, oder wie soll das sonst gehen?

Und KI ist fürs erste eigentlich gar nicht geplant, aber trotzdem danke für den Artikel.

Es geht uns in erster linie darum, dass man das übers internet spielen kann und das wir später auch eine 3d ansicht haben.
Aber im Moment arbeiten wir am Logikkern.

[rapso]

bei schach bietet es sich an, figuren als bits abzulegen, zuege kann man dann mit simplen shift und bit operationen machen. chess+bitboards sind eure keywords

[*Q* 1]

Vielleicht ist es noch nicht deutlich geworden,
aber uns geht es nicht wirklich um high performance.
Solange man keine KI benutzt, wird man das niemals benötigen. Und eine KI ist eigentlich nicht geplant (wenn dann eine sehr sehr einfache).

Es geht hier eigentlich mehr um die Architektur als um besonders schnelle verarbeitungen durch bitschiebereien.

Trotzdem Danke an alle die sich hier beteiligen!

[µngbd]

Q schrieb:

Es geht hier eigentlich mehr um die Architektur als um besonders schnelle verarbeitungen durch bitschiebereien.

Dann lasst doch am besten die Engine ganz aussen vor und verwendet etablierte. Es gibt zwei verbreitete Kommunikationsprotokolle:

http://en.wikipedia.org/wiki/Chess_Engine_Communication_Protocol
http://en.wikipedia.org/wiki/Universal_Chess_Interface

Wenn ihr eines davon unterstützen könnt, wäre das sicher nicht schlecht. Ihr hättet dann sicher bald echte User.