Im November spielten in New York Magnus Carlsen und Sergej Karjakin um den Weltmeistertitel im Schach. Schach gilt als sehr komplexes Spiel. Seit Jahrhunderten suchen Schachspieler nach der optimalen Strategie, um das Spiel zu gewinnen – bisher ohne Erfolg. Auf der Suche nach solch einem perfekten Spiel ist es zunächst nötig, die Komplexität von Schach zu verstehen und zu beschreiben. Dass ein Spiel wie Tic-Tac-Toe viel einfacher ist, ist recht offensichtlich. Doch wie berechnet man die Komplexität eines Spiels?
Üblicherweise gibt man die Komplexität mittels zweier Größen an: der Größe des Zustandsraums und der des Spielbaums. Der Zustandsraum besteht aus allen denkbaren Anordnungen der Steine auf dem Spielbrett. Der Spielbaum besteht aus allen möglichen Spielabläufen, das heißt aus allen Abfolgen von erlaubten Zügen. Beim Schachspiel gibt es etwa 1042 Zustände (eine Eins mit 42 Nullen) und etwa 10120 Spielabläufe. Das hat der US-amerikanische Mathematiker Claude Shannon in den 1950-er Jahren berechnet.
Diese Zahlen gelten noch immer als Richtwerte, nach denen die Komplexität des Schachspiels abgeschätzt wird. Manch geübtem Schachspieler kommen sie intuitiv zu hoch vor. Der Schachgroßmeister Emmanuel Lasker soll einmal auf die Frage, wie viele Züge er vorausdenke, scherzhaft geantwortet haben: „Einen, aber einen guten!“
Im Rahmen unserer Forschung in der Physics and Materials Science Research Unit der Universität Luxemburg haben wir den Zustandsraum des Schachspiels genauer untersucht. Wir stellten fest, dass das Spiel tatsächlich längst nicht so komplex ist wie bisher angenommen. Der Student Arshia Ataspendar erzeugte mehrere Millionen Schachspiele auf dem Computer und wertete die besuchten Teile des Zustandsraums und des Spielbaums mit der Graphentheorie, einer Disziplin der Mathematik, aus.
Das Ergebnis seiner Masterarbeit lautet: Der Zustandsraum zerfällt in Teilbereiche, so genannte Taschen. Die Taschen resultieren daher, dass man Züge der Bauern (im Unterschied zu allen anderen Figuren) nicht wieder rückgängig machen kann. Jeder Zug eines Bauern macht also eine ganze Reihe denkbarer Konstellationen im weiteren Spielverlauf unmöglich. Sobald einige Spielzüge ausgeführt worden sind, kann man einen großen Teil der denkbaren Stellungen nicht mehr erreichen. Für das praktische Spiel sind sie also nicht mehr relevant.
Um abzuschätzen, ob eine Stellung von einer anderen Stellung aus noch zu erreichen ist oder nicht, haben wir eine Computersimulationmethode aus der Materialforschung verwendet. Diese Methode dient eigentlich dazu, die Faltungsmechanismen von Proteinen zu untersuchen und chemische Reaktionspfade zu finden – also ebenfalls Verbindungen zwischen Anordnungen komplexer Systeme herzustellen. Die wesentliche Idee der Masterarbeit war es, diese Methoden auf ein anderes komplexes System zu übertragen, das Schachspiel.
Wenn man einen Teil der denkbaren Stellungen auf dem Schachbrett nach den ersten Spielzügen ausschließen kann, wird die Berechnung der Komplexität einfacher: Die Taschen enthalten „nur noch“ 1022 Zustände, sind also deutlich kleiner als der gesamte Zustandsraum, aber immer noch groß genug, um ein spannendes Spiel mit unvorhergesehenen Wendungen zu erlauben. In welcher Tasche das Spiel gespielt wird, legt man am Anfang durch die Wahl der Bauernstruktur fest. Danach verzweigt sich der Spielbaum kaum noch – eben so, wie in Laskers Zitat behauptet.
Die Ergebnisse der Forschung erschienen in der Fachzeitschrift Europhysics Letters. Die rein physikalische Herangehensweise ist bewusst „blind“ gegenüber empirischen Stellungsbewertungen, wie Schachprogramme sie verwenden. Dennoch finden sich zahlreiche Faustregeln der von den Großmeistern entwickelten Schachtheorie bestätigt. Vor allem aber zeigt sich, dass nicht die Größe des Stellungsraums der Faktor ist, der das Schachspiel spannend macht, sondern dessen zerklüftete Struktur.