Das Minimax-Verfahren zur Variantenberechnung von Suchbäumen im Schach

Abstract

Im 1.Kapitel werden die Regeln und Grundlagen des Schachs vorgestellt. Die ersten Modellbeispiele einer vereinfachten Suche zur Entscheidungsfindung werden vorgestellt und analysiert. Bereits an diesen Beispielen wird die Problematik der Zeitkomplexität sehr deutlich. Wegen des Verzweigungsfaktors von 20 bis 50 pro zusätzlichem Halbzug Rechentiefe in durchschnittlichen zu analysierenden Problemstellungen, können auch nur vereinfachte Beispielbäume mit Verzweigungsfaktoren ? 3 zu Demonstrationzwecken der Verfahren visualisiert werden. Obwohl das Minimax-Verfahren zur Variantenberechnung das Herzstück einer jeden Schachengine ist, müssen zuvor im 2.Kapitel die grundlegenden Fragen der datentechnischen Realisation des Schachbrettes geklärt werden. Die Darstellung des Schachbrettes mit seinen 64 Feldern verleitet sehr schnell zu der Überlegung, die 64-Bit Fähigkeiten moderner Prozessoren zu nutzen. Tatsächlich ist genau dieser Ansatz nicht nur recheneffizient und zukunftsorientiert, sondern es eröffnen sich auch bislang unzugängliche Möglichkeiten der Datenauswertung. Es lassen sich beliebig komplexe Informationen über das Zusammenspiel der Figuren und die Zusammenhänge auf dem Spielbrett gewinnen, einzig durch geschickte Datenmanipulation. Ein weiterer Vorteil dieser sogenannten Bitboard-Technologie ist die hervorragende Erweiterbarkeit und Modifikationsmöglichkeit der Verfahren zur Datenauswertung während des Entwicklungsprozesses. Zudem sind die Rechenbausteine, unabhängig von ihrer Komplexität, stets übersichtlich und gut verständlich. Es ist weiterhin möglich die Bausteine einer Schachengine trotz ihres engen Zusammenspiels in generische Module zu verlagern. Die aktuellen Mikroprozessoren sind sogenannte 64-Bit-Prozessoren. Der grundlegende Datentyp solcher Prozessoren besteht aus 64 Bit. Die meisten 64-Bit-Rechenoperationen werden daher in einem einzigen Taktzyklus erledigt. Da Bitboards 64-Bit-Zahlen sind, werden bei der Programmierung auf modernen 64-Bit-Prozessoren echte 64-Bit-Zahlen verwendet, und nicht wie auf 32-Bit-Systemen nur eine Simulation solcher Zahlen durch Zusammenfassung zweier aufeinanderfolgender 32-Bit-Zahlen. Da das Schachbrett aus 64 Feldern besteht, kann genau dieser Datentyp sehr effizient zur Darstellung des Schachbrettes verwendet werden. Jedes Bit dieser 64-Bit-Zahl steht für ein Feld des Schachbrettes. Da aber ein Bit lediglich die Information über Vorhandensein (Wert = 1) oder Nichtvorhandensein (Wert = 0) einer Figur liefert, lässt sich auf diese Weise nicht Feststellen welche Figur auf einem Feld des Schachbrettes sitzt. Zur Lösung dieses Problems werden mehrere Bitboards parallel und inkrementell verarbeitet, für jeden Figurentyp genau eines. Um mit den Gleiteigenschaften der Gleitfiguren Turm, Läufer und Dame genauso effizient rechnen zu können, wie mit den übrigen Figuren, wird ein weiteres 64-Bit-Verfahren hergeleitet. Dieses Verfahren der Bitboard-Rotationen ermöglicht es durch Zusammensetzung der jeweiligen Gleitrichtungen, beispielsweise die horizontalen und die vertikalen Gleitrichtungen des Turmes, die vollständige Bewegung einer Gleitfigur zu berechnen. Dies kann wiederum durch sehr geschickte Bitmanipulation und Nachschlagen in initialisierten, mehrdimensionalen Tabellen erreicht werden. Die Verwaltung grosser Datenmengen und das schnelle Wiederfinden von Informationen ist zentrales Thema im 3.Kapitel. Daher stellt sich die Frage, ob es nicht Verfahren gibt, bei denen der Suchaufwand völlig unabhängig von der Grösse des Datenvolumens ist, und die gibt es tatsächlich, es sind dies die Hashverfahren. Im Verlauf der Suche wird ein Schachprogramm mehrere Millionen Stellungen untersuchen, wobei in jeder Suche viele Stellungen mehrfach untersucht werden müssen. Das Hashverfahren für Schachprogramme soll die zuletzt untersuchten Stellungen in einem Hashspeicher ablegen, und bei Bedarf auf diese Daten zurückgreifen, um den Suchvorgang zu beschleunigen. Neben der inkrementellen Berechnung von 64-Bit-Hashschlüsseln wird aus mehreren Speichermodellen eines, das in der Praxis besonders zuverlässig arbeitet ausgewählt. Anschliessend werden die Hashschlüssel nochmals für die Berechnung von Speicheradressen genauer untersucht. Abgeschlossen wird dieses Kapitel mit einem Speicherorganisationsmodell, welches um ein zusätzliches Gütekriterium bereichert, eine enorme Effizienzsteigerung verspricht. Das 4.Kapitel meiner Arbeit beschäftigt sich mit der Variantensuche. Schachprogramme durchsuchen in unglaublicher Geschwindigkeit möglichst viele Varianten auf dem Schachbrett, um sich für die vielversprechendste zu entscheiden. Besonders in taktischen Stellungen sind moderne Schachprogramme darauf angewiesen, ihr mangelndes Schachverständnis durch stupides Ausprobieren möglichst vieler Varianten auszugleichen. Die Variantensuche und deren zeitkomplexes Verhalten ist somit der Kern eines Schachprogrammes.