Das Rechenschachbrett
Der Computer arbeitet nur mit Zahlen. Daher ist seine Sicht des Schachbretts eine Reihe von addressen in seinerm Speicher. Jede Adresse repräsentiert ein Feld. Der Wert, der an der addresse gespeichert wird, gibt dem Computer Auskunft über die Figur, die auf dem Feld steht. Die Adressen sind hintereinander angeordnet und können über einen Index angesprochen werden. (Für die Programmierer: es ist ein Array).
Diese Beschreibung war sehr abstrakt. Ich will versuchen, die Situation mit einem Beispiel zu verdeutlichen.
Stellen Sie sich vor, Sie würden vor einer Kommode mit 64 Schubladen sitzen. Diese Schubladen sind durchgehend von 1 bis 64 nummeriert. Sie haben auch ein Schachbrett durchnummeriert, so dass jede Schublade einem Feld auf dem Brett entspricht. Wenn auf einem Feld des Schachbretts eine Figur steht, ist die selbe Figur auch in der Schublade mit der selben Nummer. Natürlich können Sie das Schachbrett nicht sehen (das kann der Computer ja auch nicht), aber wenn Sie wissen möchten, was für eine Figur beispielsweise auf Feld 12 ist, schauen Sie einfach in der entsprechenden Schublade nach.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 Die Schachregeln
Die wichtigste Regel des Schachs ist die Gangart der Figuren. Alle anderen Regeln bauen auf diese Regel auf. Da der Computer nur mit Zahlen arbeitet, mit denen er einfache arithmetische Operationen ausführt, müssen wir die Gangart der Figuren mathematisch ausdrücken.
Gehen wir nochmals auf das Beispiel der Kommode vom vorhergehenden Abschnitt ein. Während Sie normalerweise auf einem richtigen Schachbrett eine Figur einfach verschieben würden, um Sie zu ziehen, können Sie das mit ihrer Kommode nicht. Sie müssen eine Figur aus einer Schublade nehmen und sie in eine andere legen. Doch natürlich können Sie die Figuren nicht einfach in eine beliebige Schublade legen, denn dann könnten Sie ja ungültige Züge machen, genauso wie Sie die Figuren auf dem Brett nicht wahllos verschieben. Für das Schachbrett gibt es einfache Regeln wie "ein Feld in jede Richtung (König)" oder "immer ein L (Springer)". Mit unserer Kommode ist es aber schwierig, solche geographischen Angaben zu befolgen, da wir nur Schubladen mit Zahlen darauf vor uns haben.
Betrachten wir einmal, wohin ein Springer von Feld 29 aus ziehen kann:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
- nach Feld 19 (19 - 29 = -10)
- nach Feld 12 (12 - 29 = -17)
- nach Feld 14 (14 - 29 = -15)
- nach Feld 23 (23 - 29 = -6)
- nach Feld 39 (39 - 29 = +10)
- nach Feld 46 (46 - 29 = +17)
- nach Feld 44 (44 - 29 = +15)
- nach Feld 35 (35 - 29 = + 6)
Und von Feld 37 aus?
- nach Feld 27 (27 - 37 = -10)
- nach Feld 20 (20 - 37 = -17)
- nach Feld 22 (22 - 37 = -15)
- nach Feld 31 (31 - 37 = - 6)
- nach Feld 47 (47 - 37 = +10)
- nach Feld 54 (54 - 37 = +17)
- nach Feld 52 (52 - 37 = +15)
- nach Feld 43 (43 -37 = + 6)
Fällt ihnen etwas auf? Wir können jeden möglichen Zug des Springers mit einer einfachen Addition oder Subtraktion definieren. Wenn wir den Springer aus einer Schublade nehmen und in eine andere 10 Schubladen weiter legen, haben wir einen gültigen Zug gemach. Die Gangart aller anderen Figuren lassen sich auch mit einfachen Operationen bestimmen. Probieren Sie es aus!
Natürlich muss der Computer, bevor er einen Zug ausführt, überprüfen, ob er nicht zufällig über den Schachbrettrand zieht. Auf diese Kontrollstrukturen gehen wir hier nicht weiter ein, da Sie im praktischen Teil behandelt werden.
Die Stellungsbewertung
Das kennen der Regeln macht noch keinen Schachspieler aus. Unser Computer kann ja nicht einfach einen beliebigen gültigen Zug ausführen und auf das beste hoffen. Um die Konsequenzen eines Zuges abzuschätzen, wird er die entstehende Stellung bewerten. So kann er den für ihn besten Zug finden. Bei der Bewerung zählt der Computer den Wert der eigenen Figuren zusammen und zieht den Wert der gegnerischen Figuren ab. Normalerweise gehen auch positionelle Aspekte wie die Beweglichkeit der Figuren, die Kontrolle des Zentrums und die Bauernstruktur in die Bewertung ein.
Die Zugsuche
Für die Suche nach dem besten Zug erzeugt der Computer einen sogenannten Zugbaum. Dabei generiert er für jeden gültigen Zug einen Ast. Natürlich ist das Vorausrechnen auf nur einen Halbzug sehr schwach und führt nicht zu brauchbaren Ergebnissen. Daher geht der Computer nun zu jedem Ast, führt den Zug auf seinem Rechenschachbrett aus und erzeugt wieder alle gültigen Züge - diesmal natürlich für die Gegenseite. Der Vorgang wird noch einige Male wiederholt. Die genaue Anzahl wiederholungen hängt von der eingestellten Suchtiefe ab.
Ist einmal ein Endknoten erreicht, d.h. das für diesen Knoten keine weiteren Unterknoten mehr generiert werden, wird dieser Knoten bewertet.
Jetzt wählt der Computer den besten Zug aus. Dafür gibt es den sogenannten “Minimax” Algorithumus. Dieser besagt, das jeder Spieler so zieht, das sein eigener Vorteil maximiert und der des Gegners minimiert wird. Konkret bedeutet das: Wenn der Computer den Wert eines Knoten berechnet, der kein Endknoten ist, schaut er zuerst nach, ob aus dem Knoten eigene Züge oder Züge des Gegners ausgehen. Sind es eigene Züge, nimmt der Knoten den Wert des am höchsten bewerteten Unterknoten an. Sind es Züge des Gegners, nimmt der Knoten den Wert des am tiefsten bewerteten Unterknoten an.
Nach einer gewissen Rechenzeit haben alle Äste, die von der Wurzel ausgehen, eine Bewertung erhalten. Der Computer wählt dann den besten aus und führt ihn als seinen Zug aus.
Die Theorie