Spielsituationen auf dem Schachbrett (Stellungen) müssen für verschiedene DokChess-Module bereitgestellt und zwischen ihnen ausgetauscht werden. Gestalten wir die zugehörige Datenstruktur veränderlich oder unveränderlich (immutable)?
Eine Stellung verändert sich im Verlauf einer Partie durch das Ausführen von Zügen. Darüber hinaus führt die Engine im Rahmen ihrer Analyse mögliche Züge aus, zieht Antworten des Gegners, bewertet das Resultat und verwirft Züge wieder. Dabei entsteht ein Baum, der je nach Tiefe viele tausend verschiedene Stellungen beinhaltet.
Je nachdem, ob die Stellung als Datenstruktur unveränderlich ist oder nicht, sind Algorithmen einfacher oder schwieriger zu implementieren, und ihre Ausführung ist unterschiedlich effizient.
Von der Schnittstelle der Stellung hängen sämtliche Module ab; eine nachträgliche Änderung beträfe ganz DokChess.
Ausgangspunkt sind fachlich motivierte Klassen für Feld, Figur und Zug (→ 8.2 „Schach-Domänenmodell“). Die Klassen sind unveränderlich als Wertobjekte realisiert (Feld e4 bleibt nach Erzeugung stets e4).
Für die Stellung betrachten wir zwei Alternativen:
// Pseudocode Stellung s = new Stellung(); // Anfangsstellung, weiss am Zug s.fuehreZugAus(e2e4); // Koenigsbauer zwei Felder vor, danach schwarz am Zug s.nimmLetztenZugZurueck(); // anschliessend wieder auf Anfang ...
Stellung s = new Stellung(); Stellung neueStellung = s.fuehreZugAus(e2e4) // s bleibt unveraendert ...
Die folgende Tabelle fasst Stärken und Schwächen der beiden Optionen zusammen, sie werden im Folgenden weiter ausgeführt.
Tabelle: Stärken und Schwächen der beiden Optionen
| (1) veränderlich | (2) unveränderlich | |
|---|---|---|
| Implementierungsaufwand | (-) höher | (+) geringer |
| Effizienz (Speicherverbrauch) | (+) sparsamer | (-) Bedarf höher |
| Effizienz (Zeitverhalten) | (o) neutral | (-) schlechter |
| Eignung für nebenläufige Algorithmen | (-) schlecht | (+) gut |
(+) Positiv
Wir müssen die Stellung mit ihrem umfangreichen Zustand nicht bei jedem Zug kopieren. Das spart Speicher und Rechenzeit, und es schont den Garbage Collector. Für Analysealgorithmen ist allerdings Funktionalität zu implementieren, die ausgeführte Züge zurücknimmt („undo“). Dieses Zurücknehmen kostet ebenfalls Zeit, daher die neutrale Bewertung (o) beim Zeitverhalten.
(-) Negativ
Die Implementierung des Zurücknehmens ist aufwändig. Sie muss nicht nur geschlagene Figuren wieder hinstellen. Die Rochade-Regel und En passant erfordern zusätzlich eine gesonderte Behandlung. Das Command-Pattern [Gamma+94] bietet sich als Option an. Auch die Verwendung durch Algorithmen ist aufwändiger, da diese das Zurücknehmen von Zügen explizit aufrufen müssen.
Veränderbarer Zustand hat Nachteile bezüglich Nebenläufigkeit.
(+) Positiv
Beim Ausführen eines Zuges wird die Stellung kopiert, das Original nicht verändert. Damit entfällt die Implementierung des Zurücknehmens von Zügen. Verwender können sich die alte Stellung als Wert merken. Das spart verglichen mit Option (1) Aufwand in der Umsetzung. Unveränderliche Objekte bieten signifikante Vorteile bei nebenläufigen Algorithmen.
(-) Negativ
Das Kopieren des Zustandes für jede neue Stellung kostet Zeit. Da es in Analysesituationen um sehr viele Stellungen geht, in Summe potentiell viel Zeit.
Das Kopieren des Zustandes für jede neue Stellung kostet darüber hinaus Speicher. Die Implementierung von Suchalgorithmen mit Backtracking vermeidet zwar, dass komplette Spielbäume auf dem Heap landen. Nichts desto trotz ist der Speicherbedarf höher, und der Garbage Collector hat viel mehr zu tun.
Beide Punkte wirken sich negativ auf die Effizienz aus.
Die Entscheidung fiel Anfang 2011 auf die unveränderliche Stellung (Option 2) aufgrund der Vorteile bezüglich einfacher Implementierung und Aussicht auf die leichtere Ausnutzung von Nebenläufigkeit. Die Nachteile der Option 2 beziehen sich ausschließlich auf Effizienz.
Aufgrund des Risikos, die Ziele bezüglich der Spielstärke in akzeptabler Rechenzeit (Attraktivität, Effizienz) nicht zu erreichen, wurden Prototypen beider Varianten implementiert und im Rahmen einer Mattsuche (Matt in 3 Zügen) mit Minimax-Algorithmus verglichen. Mit Option 2 dauerte die Suche 30% länger, vorausgesetzt, man implementiert das Kopieren effizient. Sie lag aber noch deutlich innerhalb des Geforderten.
Es gab weitere Optimierungsoptionen, die den Effizienznachteil gegenüber Option (1) bei Bedarf weiter verkürzt hätten. Sie wurden nicht umgesetzt, um die Implementierung einfach zu halten.
Zu diesen Optionen zählte die Ausnutzung mehrerer Prozessoren/Kerne durch Nebenläufigkeit, mittlerweile (mit DokChess 2.0) mit einem parallelen Minimax exemplarisch umgesetzt.