Information Technology Reference
In-Depth Information
gegnerischen Zuges. Endet irgendeine Zugfolge mit einem Beta, das größer ist als Al-
pha, wird die Suche am gerade analysierten weißen Zug abgebrochen. Der Alpha-Beta-
Algorithmus ist eine Form des Rückwärts-Abschneidens, indem rückwirkend ein Zug
einer Partei als schlecht erklärt und die Berechnung weiterer Zugfolgen abgebrochen
wird.
•
Suchbaumbegrenzungen
und
-erweiterungen
: Im vorangehenden Punkt wurde von ei-
ner festen Baumtiefe ausgegangen. In der Praxis ist das jedoch mit dem Risiko ver-
bunden, dass in taktischen Stellungen starke Schwankungen der Bewertungsfunktion
auftreten. Insbesondere wenn Figuren ausgetauscht werden, hätte die Seite, die zuerst
schlägt, einen Halbzug lang einen materiellen Vorteil, der jedoch nicht dauerhaft ist.
Man hat daher erkannt, dass es zweckmäßig ist, bei Endknoten, in denen noch Schlag-
züge möglich sind, diese Schlagzüge weiter zu untersuchen, bis eine „Beruhigung“
der Stellung eintritt. Dies nennt man die
Ruhesuche
. Der bereits erwähnte Aspekt der
Vorsortierung der generierten Zugliste implizierte die Idee, den Spielbaum dadurch
zu begrenzen, dass man die (vermutlich) schlechten Züge dieser Liste von vornherein
nicht weiter verfolgt. Dieses flexibel scheinende Konzept hat jedoch den Nachteil, dass
viele mit einem Opfer beginnenden Kombinationen nicht mehr gefunden werden, weil
deren Einleitungszüge wegen des Verlusts von Material als „schlecht“ eingestuft und
somit nicht weiter verfolgt würden. Eine sinnvolle Ergänzung für die Suchalgorith-
men sind die
Hash-Tables
, in denen das Programm Informationen zu ausgewerteten
Stellungen ablegt. Das bringt dann großen Nutzen, wenn der tatsächliche Spielverlauf
der erwarteten besten Fortsetzung folgt, weil dann ein Teil des Spielbaums bereits in
ausgewerteter Form vorhanden ist und die Suche nach der besten Fortsetzung bereits in
höherer Tiefe begonnen werden kann.
•
Einsatz externer Hilfsmittel
: In der Eröffnungsphase einer Partie und im Endspiel grei-
fen Programme häufig auf zusätzliche (externe) Datenbanken zurück:
−
Eröffnungsbücher
(Books): Enthalten die meisten bekannten Fortsetzungen (aus
Großmeisterpartien) zu fast allen Eröffnungen. Solange das Programm die aktuelle
Stellung noch im Eröffnungsbuch findet, braucht es nichts zu berechnen und ant-
wortet „sofort“. Die Varianten in den Books sind teilweise bis zu einer Länge von
mehr als 20 Zügen abgespeichert.
−
Endspiel-Tabellen
(Tablebases): Für Endspiele mit nur noch wenigen Steinen (zur
Zeit bis max. 6 Steine) sind sogenannte „Tablebases“ erstellt worden, die zu allen
möglichen Positionen Einträge enthalten, was das theoretische Resultat (Gewinn,
Verlust, Remis) dieser Position ist, und wie viele Züge (für Gewinn oder Verlust bei
beiderseits bestem Spiel) es bis zum Eintritt des Resultats noch sind. Die Tableba-
ses für 3-, 4-Steine passen noch auf eine Diskette, mit den 5-Steiner benötigt man
zusammen ca. 8,5 GB Speicherplatz. Der Platzbedarf für die 6-Steine-Tablebases
geht bereits in den TeraByte-Bereich. Hiezu findet man im Internet Server, die die
Abfrage dieser Tablebases erlauben.
•
Zeitmanagment
: Die Engine darf nicht beliebig lange rechnen müssen, bevor sie zu
einem Resultat kommt. Im Schachsport gibt es feste Bedenkzeitvorgaben, deren Über-
