Information Technology Reference
In-Depth Information
ausgehen, dass abhängig vom Stellungstyp (offen, geschlossen, Eröffnungsphase, Mit-
telspiel, Endspiel) ein Programm unterschiedliche Bewertungsfunktionen verwendet.
Die Bewertungsfunktionen bleiben oft das „Betriebsgeheimnis“ der Entwickler. Ohne
eine Bewertungsfunktion kann ein Schachprogramm in den Spezialfällen auskommen,
wenn eine vollständige Analyse des Spielbaums bis in seine finalen Endknoten gelingt.
Das könnte beispielsweise bei Endspielstellungen und Schachkompositionen (z. B.
Aufgaben des Typs Matt in 3 Zügen etc.) der Fall sein.
Folgende „bewährte“ Faktoren können als Basis für weitere Überlegungen in der Konzep-
tionalisierung herangezogen werden:
•
Material
: Das ist das klassische primäre Kriterium. Den Figuren werden die aus der
Praxis bekannten ungefähren Tauschwerte als Materialwert zugeordnet: Bauer = 1,
Springer = 3, Läufer = 3, Turm = 5, Dame = 9, König = 200.
•
Bonuspunkte
: + 0,5 für Läuferpaar und Freibauern, und/oder Abzugspunkte; − 0,5 für
isolierte, rückständige oder Doppelbauern, fehlende Königssicherheit, u. a.
•
Beweglichkeit
: Erreichbarkeit der Felder bezüglich einzelner Figuren (jeweils + 0,1)
•
Suchalgorithmus
: Der Suchalgorithmus ist derjenige Teil des Programms, der aus dem
erzeugten Spielbaum mit Hilfe der Bewertungsfunktion(en) den besten Zug heraus-
filtern soll. Dazu ist ein valides Evaluationskriterium zur Bewertung von Knoten im
Suchbaum, eine sogenannte
Tree Pruning Strategie
, unabdingbare Voraussetzung. Falls
die Endknoten im generierten Spielbaum ein sicheres Ergebnis repräsentieren (defini-
tive Schlußsstellungen wie Matt, Patt, Remis wegen unzureichendem Material usw.),
wird dieses verwendet, ansonsten ist man auf die heuristische Einschätzung durch die
Bewertungsfunktion angewiesen. Sind für einen Knoten zu allen Nachfolgern die Be-
wertungen ermittelt, so lässt sich auch für ihn eine Aussage machen: Da man von bei-
derseits bestem Spiel ausgeht, bedeutet das, dass Weiß am Zug stets eine solche Fort-
setzung wählt, bei der er in einen Nachfolgeknoten mit maximaler Bewertung gelangt.
Schwarz dagegen wird stets die Pfade wählen, in der die Stellungsbewertungen ihr
Minimum annehmen. Diesem Charakteristikum verdankt die Tree Pruning Strategie
als Algorithmus auch seinen Namen: Minimax-Algorithmus. Dabei werden eine Maxi-
mierung des eigenen Problemlöseprofits und gleichzeitig eine Minimierung des durch
die Lösung eingehandelten Schadens angestrebt. Da die praktische Ausführung des Mi-
nimax-Verfahrens ohnehin als ein sequentieller Durchlauf durch die Knoten des Spiel-
baums realisiert wird, kann man die Informationen, die man in einem Zweig gewinnt,
in die höheren Knoten weitergeben, wodurch diese den Aufwand bei der Durchmuste-
rung in den nächsten Teilbäumen möglicherweise senken können. Das ist eine trick-
reiche Verbesserung, die es erlaubt, meist mit deutlich weniger Aufwand zum gleichen
Resultat zu gelangen wie bei einer vollständigen Prüfung aller Knoten des Spielbaums.
Dieses effektivere Verfahren heißt
Alpha-Beta-Algorithmus
(benannt nach zwei Varia-
blennamen für den jeweils aktuell besten Wert jedes der beiden Spieler). Alpha steht
dabei für den Wert des besten bisher gefundenen eigenen Zuges, Beta für den Wert des
