Information Technology Reference
In-Depth Information
oder sind erweiterte Felder oder Bitmaps zweckmäßiger? Wie sind die unterschiedli-
chen Figurentypen zu kodieren, wie weitere Besonderheiten (Rochaderechte etc.)? Wie
sollen Zugfolgen abgespeichert werden?
•
Zuggenerator
: Die Aufgabe des Zuggenerators ist es, zu einer vorgegebenen Schach-
stellung alle legalen Züge für die am Zug befindliche Seite zu generieren. Eigentlich
eine leichte Aufgabe, aber die Prüfung auf Legalität stellt dabei einen gewissen Auf-
wand dar, weil dabei bereits mögliche Gegenzüge zu untersuchen sind. Daher werden
gelegentlich Zuggeneratoren benutzt, die die pseudolegalen Züge in der generierten
Liste stehen lassen. Das verlängert die Zugliste zwar etwas (Wie viele legale Züge kann
es in einer legalen Stellung maximal geben?), aber die überflüssigen Einträge werden
durch die späteren Zugauswahlroutinen wieder ausgemustert, so dass insgesamt etwas
Berechnungsaufwand eingespart zu werden scheint.
•
Zugausführung
: Alle vom Zuggenerator gefundenen Züge müssen nacheinander auf
dem (internen) Brett zur Probe ausgeführt werden. Der „beste“ Zug ist dann als Ant-
wort auszuwählen. Der Idealfall wäre es, wenn in der generierten Zugliste ein Mattzug
enthalten wäre. Doch leider ist das nur selten der Fall und es ist nicht trivial, den besten
Zug sofort zu erkennen, weswegen weitere Berechnungen angestellt werden. In der
Regel wird man sich genötigt sehen, in den möglichen Nachfolgestellungen wiederum
alle legalen Fortsetzungen ermitteln zu lassen (Zuggenerator!) und dieses Verfahren bis
zu einer gewissen (selbst gewählten oder durch die verfügbaren Speicher- bzw. Zeit-
Ressourcen beschränkten) Tiefe fortzusetzen. Die entstehende logische Struktur hat
eine Baumstruktur, die schnell gigantische Ausmaße annimmt. Beispielsweise würden
aus der Anfangsstellung heraus nach nur 6 Halbzügen (3 Züge von jeder Seite) bereits
ca. 120 Mio. Knoten generiert werden. In Mittelspielstellungen kann dieser Wert noch
um Größenordnungen höher liegen, weil man dort von Verzweigungsfaktoren von ca.
40 (statt den 20 beim Partiebeginn) ausgehen muss.
•
Bewertungsfunktion
: Um innerhalb des Spielbaums die stärkste Fortsetzung zu fin-
den, müsste man theoretisch alle möglichen Pfade bis zu einer finalen Situation (Matt,
Patt, zwangsläufiges Remis) verfolgen, was jedoch praktisch aus Komplexitätsgründen
beim Schach nicht sinnvoll erscheint und im Gegensatz zu einfacheren Spielen (z. B.
Mühle oder Dame) auch in absehbarer Zeit nicht gelingen wird. Daher ist man darauf
angewiesen, einen Vergleich der nicht-finalen Stellungen auf der Basis heuristischer
Kriterien durchzuführen. Dazu dient die Bewertungsfunktion. Sie wird im Allgemei-
nen so konstruiert, dass sie in ausgeglichenen Stellungen etwa den Wert 0 hat, positi-
ve Werte annimmt, falls ein Vorteil für Weiß erkannt wird, und negative Werte, wenn
Schwarz besser steht. Je größer der Absolutbetrag des Wertes ist, umso größer ist der
Vorteil einzuschätzen. Welche Kriterien mit welchem Gewicht genau zur Berechnung
der Bewertungen herangezogen werden, ist völlig der Intuition der jeweiligen Entwick-
ler überlassen. Es gibt jedoch eine Reihe von Faktoren, die sich mehr oder weniger
bisher „bewährt“ haben. Alle diese Faktoren sind jedoch reine Ermessenssache. Eine
wissenschaftliche Garantie gibt es nicht, dass die errechneten Bewertungen tatsäch-
lich genau die Stärkeverhältnisse auf dem Brett widerspiegeln. Man kann auch davon
