Programmieren »en passant«: Tartan-Schachprogramm

Schach gilt allgemein als ein »königliches«, da schwieriges, Intelligenz erforderndes Spiel. Es ist erstaunlich, daß Computerprogramme gut Schach spielen können, obwohl Computer nur Rechenmaschinen ohne Leben sind. Wie diese »denken« lernen, erfahren Sie in diesem Artikel.

Schach und Computer waren seit der Erfindung von Rechnern eng verbunden. Die ersten Gedanken über das Aussehen einer Programmiersprache machte sich 1943 Konrad Zuse - der Vater des Computers. Er nannte das noch »Plankalkül« und als erste Anwendung schrieb er damit ein Schachprogramm. Leider sind diese Überlegungen durch die stürmische Entwicklung der Computertechnik in den USA untergegangen. Dort hat in den 50er Jahren Claude Shannon, der Begründer der Informationstheorie, die ersten entscheidenden Beiträge zur Schachprogrammierung geleistet. Er zeigte, wie das Schachproblem mit Hilfe des sogenannten Minimax-Algorithmus für den Computer berechenbar ist. Alles sah danach aus, daß man mit schnelleren Computern und mehr Speicher nicht nur Schach, sondern auch viele andere Probleme aus dem Bereich der KI, der »künstlichen Intelligenz«, lösen könne.

Da Geschwindigkeit die wichtigste Anforderung an ein Schachprogamm ist, kommt als Programmiersprache zunächst Assembler in Frage. Trotzdem eignet sich zum Experimentieren eine Hochsprache besser, da die Programme darin einfacher zu ändern und weniger fehleranfällig sind. »Tartan« ist vollständig in C geschrieben. Auch die Programmbruchstücke, die im folgenden auftauchen, sind C-Code. Sie sollten aber auch jedem Pascal- oder Basic-Programmierer verständlich sein.

Das Grundprinzip, nach dem fast alle Schachprogramme arbeiten, geht auf Claude Shannon zurück. Danach besteht das Programm neben der Ein-/Ausgabe aus den drei wesentlichen Bestandteilen: Zuggenerator, Minimax-Algorithmus und Bewertungsfunktion. Natürlich gilt dasselbe Prinzip auch für andere strategische Brettspiele. Sie unterscheiden sich nur durch den Zuggenerator und die Bewertungsfunktion.

Der Zuggenerator stellt eine Liste aller möglichen legalen Züge in einer bestimmten Situation auf. Dazu codieren wir Züge, Figuren und Stellungen auf dem Schachbrett in computergerechte Form. Wir ordnen z. B. jeder Schachfigur eine bestimmte Zahl zu:

#define BAUER	1
#define SPRINGER	3
#define LAEUFER	4
#define TURM	5
#define DAME	7
#define KOENIG	8

Die Lücken in der Numerierung sind absichtlich gelassen, so daß rochadefähige Türme oder en-passant schlagbare Bauern noch mit einer eigenen Zahl ausgezeichnet sind. Die schwarzen Figuren bekommen zur Unterscheidung ein negatives Vorzeichen.

Um das Schachfeld mit der aktuellen Stellung zu speichern, bietet sich ein zweidimensionales Feld an. Dann müßte aber bei jedem Feldzugriff das Programm den Index für den im Computer linear angeordneten Speicher umrechnen. Um die Zugriffe zu beschleunigen, nehmen wir also besser ein eindimensionales Feld. In die einzelnen Plätze dieses Feldes schreiben wir die Zahlen für die Figuren. Leere Felder erhalten den Wert Null. Damit die Figuren nicht vom Brett laufen, erweitern wir das Schachfeld an den Rändern, und stellen dort imaginäre Figuren auf, die »unschlagbar« sind:

#define LEER	0
#define RAND	16

Unsere Feldliste hat demnach 120 Einträge: char brett[120];

Zu Spielbeginn ist die Feldliste wie in Bild 1 belegt. Der Computer stellt fest, mit welcher Figur ein bestimmtes Feld besetzt ist. Um die umgekehrte Frage, auf welchem Feld eine bestimmte Figur steht, zu beantworten, müßte der Computer aber jedesmal die gesamte Feldliste durchsuchen. Um dies zu vermeiden, führen wir parallel noch eine Figurenliste, in der alle momentan auf dem Brett stehenden Figuren mit ihren Feldern vermerkt sind. Aus Feldliste und Figurenliste bildet der Zuggenerator nun eine dritte Liste, die Zugliste:

struct
{
 char von, nach;

}
 zug[MAXZUEGE];

Der weiße König auf Feld 61 z. B. darf nur die angrenzenden Felder betreten, das sind die Felder 62, 72, 71, 70, 60, 50, 51, und 52. Die Differenzen zwischen Ziel- und Ausgangsfeld sind 1,11,10, 9, -1, -11, -10, und -9. Diese Differenzen addiert das Programm zum Ausgangsfeld hinzu. Der Zug darf natürlich nicht ausgeführt werden, wenn das Zielfeld mit dem Wert »RAND« oder einer Zahl mit gleichem Vorzeichen besetzt ist. In unserem Fall scheiden also alle acht zunächst möglichen Zielfelder aus. Genauso verfährt man mit den anderen Schachfiguren (Bild 2). Wie man sieht, können auch die Springer nicht vom Brett hüpfen, sie treffen vorher immer auf Felder, die mit dem Wert RAND belegt sind. Etwas unangenehm ist es, die Ausnahmeregeln, wie Doppelschritte, Umwandlungen, Rochade und en-passant-Schlagen zu berücksichtigen. Falls der König geschlagen wurde, bleibt die Zugliste leer, als Zeichen, daß die Partie zu Ende ist.

Zum Zuggenerator gehören noch zwei Routinen, die Züge auf dem Brett ausführen, bzw. wieder rückgängig machen:

void fuehre_zug_aus(int i)
{
	merke_stein(brett[zug[i].nach]);
	brett[zug[i].nach] = brett[zug[i].von]; 
	brett[zug[i].von]=LEER;
}
void nimm_zug_zurueck( int i)
{
	brett[zug[i].von]=brett[zug[i].nach]; 
	brett[zug[i].nach]=gemerkter_stein();
}

Das Kernstück des Schachprogramms bildet eine Funktion, die zu jeder Situation den besten Zug und ihren Wert liefert. Der Wert einer Stellung auf dem Schachbrett ist durch eine Zahl ausgedrückt, die umso größer ist, je besser die Stellung für Weiß ist. Wenn Schwarz günstiger steht, bekommt der Wert ein negatives Vorzeichen. Eine für sicher gewonnene Stellung erhält einen maximalen Wert (positiv oder negativ):

#define WMAX 16384

Der beste Zug ist einfach der Zug der Zugliste, nach dessen Ausführung die Stellung den besten Wert hat. Die Funktion sieht für Weiß etwa so aus:

int bester_zug_weiss (int *von, int *nach)
{
	int wert,w, v,n, i ;
	zuggenerator_weiss(); 
	wert = -WMAX; 
	*von = 0; 
	for (i = 0; zug[i].von; ++i)
	{
		fuehre_zug_aus(i);
		w = bester_zug_schwarz(&v,&n); 
		nimm_zug_zurueck(i); 
		if (w>wert)
		{
			wert = w; *von = v; *nach =n;
		}
	}
	return wert;
}

Die Funktion für Schwarz sieht genauso aus, nur ist dort »weiss« durch »schwarz« zu ersetzen (und umgekehrt). Außerdem muß es dort w < wert statt wi> wert heißen, denn aus schwarzer Sicht ist der beste Wert ja der kleinste. Aus dieser Beziehung (minimaler und maximaler Wert) entstand der Name »Minimax-Algorithmus«.

Bild 1. Das Schachbrett mit Randfeldern zu Beginn jedes Spiels

Unsere Funktion ist rekursiv: »bester_zug_weiss()« und »bester_zug_schwarz()« rufen sich gegenseitig auf. Falls die Partie vorbei ist (kein Eintrag in der Zugliste), weil Weiß mattgesetzt ist, liefert die Funktion den korrekten Wert -WMAX. Es fehlt noch ein Test, ob eine Pattsituation vorliegt, ln diesem Fall ist der korrekte Rückgabewert Null. Auch ein Remis durch die 3- oder 50-Züge-Regel ist zu berücksichtigen, um keine unendlich langen Partien entstehen zu lassen. Auf die Grundstellung angewendet, wüßte man, ob zum Beispiel Weiß immer gewinnen kann, egal wie gut sich Schwarz verteidigt, und bekäme auch noch den optimalen Eröffnungszug geliefert. Die Rechenzeit für eine vollständige Analyse ist ebenso astronomisch wie die Anzahl aller möglichen Schachpartien. Auf diese »brutale« Weise löst daher kein Supercomputer dieses Problem. Wir müssen also irgendwie dafür sorgen, daß die Funktion vorher abbricht, und nicht erst bei einem Matt oder Remis. Dazu kann man eine globale Variable für die Rechentiefe benutzen, die zu Anfang null enthält und sich bei jedem rekursiven Aufruf erhöht. Ist eine maximal vorgegebene Rechentiefe erreicht, verzweigt das Programm in den dritten Bestandteil des Schachprogramms, die Bewertungsfunktion. Diese Funktion liefert den geschätzten Wert einer Stellung auf dem Schachbrett. Sie ist sehr wesentlich für das Schachprogramm, denn ohne eine gute Bewertungsfunktion liefert der Minimax-Algorithmus keine brauchbaren Ergebnisse.

Ist die Stellung nicht offensichtlich Matt oder Remis, berechnet die Bewertungsfunktion einen Zwischenwert zwischen 0 und WMAX, bzw. 0 und -WMAX. Das erste Kriterium dafür ist natürlich die Materialbilanz. Jede Figur hat einen bestimmten Materialwert.

#define WBAUER	128
#define WSPRINGER	S84
#define WLAEUFER	384
#define WTURM	640
#define WDAME	1152

Schwarze Figuren bekommen wieder die entsprechenden negativen Materialwerte. Die Summe der Werte aller Figuren auf dem Schachbrett ist die Materialbilanz. Die Zahlen sind deswegen so groß gewählt, weil sie die bestimmende Komponente in der Bewertung bilden. Große Probleme bekommt die Bewertungsfunktion, wenn sie mitten in einem Schlagabtausch in Aktion tritt, da sich dann die Materialbilanz und damit die Bewertung mit jedem Zug drastisch ändert. Deswegen ist es nötig, alle bei einem Schlagwechsel beteiligten Figuren gegeneinander aufzurechnen. Eine solche statische Materialbewertung führt aber leicht zu Fehlern. Erst wenn Schlagzüge tatsächlich ausgeführt sind, sind gute Ergebnisse zu erwarten natürlich auf Konten der Rechenzeit.

Bei einer ruhigen Stellung entscheiden weitere Faktoren über die Bewertung. Einer davon ist die Beweglichkeit der Figuren. Sie drückt sich durch die Größe der Zugliste aus. Sehr wichtig ist auch die Bauernstellung. Doppelbauern und isolierte Bauern schlagen in der Bewertung negativ zu Buche. Die Kontrolle des Brettzentrums sowie die Sicherheit des eigenen Königs zählen ebenfalls zu den wichtigen Kriterien. Deren Bewertung und die Berücksichtigung weiterer Faktoren bzw. deren Gewichtung, ist die eigentliche Kunst der Schachprogrammierung; hier muß man viel experimentieren.

Die Arbeitsweise des Minimax-Algorithmus läßt sich an einem sogenannten Baumdiagramm veranschaulichen (Bild 3). Die Äste des Baums repräsentieren die dabei erlaubten Züge. Es gibt zwei Arten von Verzweigungsstellen: An den eckig umrandeten ist Weiß am Zug. Diese Stellen heißen auch Maximierungsknoten, da hier das Programm den Zug mit der maximalen Bewertung sucht. Analog dienen die Minimierungsknoten der Suche nach einem Zug mit einer minimalen Bewertung für die schwarzen Figuren. Der Übersichtlichkeit halber betrachten wir nur zwei Züge. Die Verzweigungsstellen sind in der Reihenfolge numeriert, in der sie das Programm bearbeitet.

Bild 2. Jede Figur unterliegt einer bestimmten Regel bezüglich ihrer Zugmöglichkeit. Die für die Figuren erreichbaren Felder werden zum Startfeld addiert bzw. subtrahiert und in einer Tabelle abgelegt.

An Punkt 4 wird zum Beispiel gerade die Funktion »bester_zug_schwarz« aufgerufen. Der Zuggenerator liefert die Züge b8-c6 und g8-f6. Da die maximale Rechentiefe (in diesem Beispiel 4) erreicht ist, ruft das Programm die Bewertungsfunktion auf. Diese liefert nach Ausführen der beiden Züge die Werte 0 und 36. Da Schwarz am Zug ist, wird minimiert, also der Zug b8-c6 mit dem Wert 0 gewählt. Am Punkt 3 folgt die Funktion »bester_zug__weiss«. Die Zugliste besteht hier aus den Zügen b1-c3 und g1-f3. Ist die maximale Rechentiefe noch nicht erreicht, ruft das Programm bei jedem Zug die Funktion »bester_zug_schwarz« auf. Für den Zug b1-c3 liefert diese, wie wir uns gerade überlegt haben, den Wert 0 zurück. Zug g1-f3 liefert den Wert -36. Da Weiß am Zug ist, folgt eine Maximierung, also wird der Zug b1-c3 mit dem Wert 0 gewählt. So geht es weiter, bis schließlich der Zug e2-e4 als bester Zug mit dem Wert 0 erkannt ist.

Wir haben zum Schluß insgesamt 2 hoch 4 gleich 16 Stellungen bewertet. Gehen wir aber von einem realistischen Wert von 40 möglichen Zügen an jeder Verzweigung aus, dann hätte der Baum schon zweieinhalb Millionen Endknoten, an denen jeweils die Bewertungsfunktion aufgerufen würde. Zum Glück gibt es Techniken, den Baum zu »beschneiden«. Betrachten wir dazu den Beispiel-Baum.

Am Punkt 7 lieferte der erste Zug d7-d6 die Bewertung -8. Egal, welche Werte die weiteren Züge liefern, ist der Wert an Punkt 7 niemals größer als -8, da bereits an diesem Punkt die Minimierung einsetzt. Da aber am Punkt 3 maximiert wird, und schon ein Zug mit dem besseren Wert 0 gefunden ist, ist es unnötig, die restlichen Züge am Punkt 7 zu untersuchen. Der Zug d7-d6 ist also ein Widerlegungszug für g1-f3. Mit der gleichen Idee beschneiden wir weitere Äste (wie im Diagramm angedeutet). Dazu übergeben wir den bisher maximalen Wert an den folgenden Minimierungsknoten.

Dieser Wert, für den sich der Name Alpha eingebürgert hat, stellt eine untere Schranke für die folgenden Bewertungen dar. Nur wenn diese größer als Alpha sind, ist die weitere Berechnung von Zügen am Minimierungsknoten sinnvoll. Dieses sogenannte Alpha-Abschneiden erfolgt in unserem Beispiel an den rechten Ästen der Knoten 7, 17, 19 und 22. Entsprechend übergeben wir den bisher minimalen Wert (Beta), an den folgenden Maximierungsknoten. Beta-Abschneiden findet am rechten Ast des Knoten 10 statt.

Zufällig ist der Baum in unserem Beispieldiagramm für das Alpha-Beta-Verfahren gerade optimal sortiert. Statt 16mal wird die Bewertungsfunktion nur noch siebenmal aufgerufen. Bei einem solchermaßen günstigen Baum mit realistischen 40 möglichen Zügen an jeder Verzweigung bräuchten wir statt 2,5 Millionen mal die Bewertungsfunktion nur 3199mal aufzurufen - ein erheblicher Zeitgewinn. Bei optimal sortierten Bäumen bearbeitet dieses Verfahren in der gleichen Rechenzeit Bäume bis zur doppelten Tiefe.

Trotz dieser und weiterer Verfahren zur Beschneidung sind die Bäume immer noch so groß, daß der Computer in annehmbarer Rechenzeit nur eine relativ geringe Rechentiefe erreicht, da der Computer komplette Zuglisten betrachtet und jeden Zug - sei er noch so unsinnig - abarbeitet. Ein menschlicher Schachspieler geht völlig anders vor. Er sieht meist die wenigen sinnvollen Züge, und verfolgt oft auch nur einen einzigen Zug weiter, um zu prüfen, ob ihn seine Intuition nicht täuscht.

Schon Shannon hat dies bemerkt und schlug deshalb neben unserer »A-Strategie« eine »B-Strategie« vor, die sich nur auf die erfolgversprechenden Züge konzentriert. Die Züge entsprechend vorzuselektieren ist aber natürlich leichter gesagt als getan, und führt schnell zu Fehlern. Das Hauptproblem des Minimax-Ansatzes, seine »Kurzsichtigkeit«, erfährt durch diese Strategie kaum Milderung. Der Computer ist einfach nicht in der Lage, Pläne zu schmieden, die zur Ausführung vielleicht zwanzig bis dreißig Züge benötigen.

Bild 3. Die Funktionsweise des »Minimax«-Algorithmus anhand eines Baumdiagramms. Die Kästchen bzw. Ellipsen stellen die Maximierungs- bzw. Minimierungsknoten dar. Die schrägen Doppelstriche markieren das Beschneiden des Baumes.

Um die genannten Probleme zu vermeiden, bedarf es wahrscheinlich völlig neuer Ansätze. Am weitesten in diese Richtung ist bisher der Schachweltmeister der 50er Jahre, Michail Botwinnik, gegangen. Er versucht, Computerprogramme zu entwickeln, die mehr der menschlichen Denkweise nachempfunden sind. Vielleicht erlauben es aber erst völlig neue Computerkonzepte, wie die der neuronalen Netze, solche Ideen zu verwirklichen. (ah)

Christoph Zwerschke

---

---