Jeder Schachspieler weiß, daß manche Partien einfach im Sande verlaufen: Anscheinend kann keiner der beiden Kontrahenten gewinnen, man vermag nichts Konstruktives zu tun, und es gibt keine offensichtliche Möglichkeit, zu einem Ergebnis zu kommen – wenn sich die Spieler nicht auf ein Unentschieden einigen.

Die für die Schachregeln zuständigen internationalen Gremien haben zahlreiche Verfahrensweisen vorgeschlagen, um solche Situationen geordnet zu beenden. Die wichtigste lautet: Ein Spiel endet unentschieden, wenn einer der Spieler geltend macht, daß in den letzten 50 Zügen beider Parteien weder eine Figur geschlagen noch ein Bauer gezogen wurde.

Vor wenigen Jahren haben jedoch Analysen mit Hilfe des Computers gezeigt, daß diese Regel zu voreilig ist. Es gibt Endspiele, in denen eine Seite den Sieg erzwingen kann, aber dafür mehr als 50 Züge braucht, bei denen weder ein Bauer gezogen noch eine Figur geschlagen wird (Spektrum der Wissenschaft, April 1992, Seite 22). Die Schachregeln müssen nun also gewisse Ausnahmen zulassen, vielleicht unter gewissen Zusatzbedingungen 300 statt 50 umkehrbare Züge in Folge erlauben. Indes könnte jede – auch bedingte – Begrenzung der Anzahl von Zügen sich aus demselben Grund als unzulässig erweisen wie die ursprüngliche Regel. Läßt sich das Problem vielleicht völlig anders lösen?

Vor einiger Zeit wurde vorgeschlagen, daß ein Spiel als unentschieden beendet gelten sollte, wenn dieselbe Folge von Zügen – mit allen Figuren in genau denselben Positionen – dreimal hintereinander vorkommt. Das ist nicht zu verwechseln mit der Standardregel, wonach der Spieler, der am Zug ist, Remis verlangen kann (aber nicht muß), wenn sich dieselbe Stellung zum dritten Mal und mit demselben Spieler am Zuge ergeben hat.

Für die neue Regel gibt es zweifellos gute Gründe. Aber ist sie vielleicht zu schwach? Gibt es sinnlose Spiele, bei denen sie nicht anwendbar ist? Ist es also theoretisch möglich, daß ein Schachspiel ewig weitergeht, ohne daß irgendeine - beliebig lange – Folge von Zügen dreimal in unmittelbarer Folge vorkommt?

Beschränken wir uns der Einfachheit halber auf ein ziemlich sinnloses, aber regelgetreues Spiel: Jeder Spieler wählt, wenn er am Zuge ist, einen aus nur zwei Zügen aus, die mit 0 und 1 bezeichnet seien. Dabei steht 0 für den Zug "Bewege den Königsspringer" und 1 für "Bewege den Damenspringer". Je nachdem, wo der Springer gerade steht, zieht er aus seiner Ausgangsstellung ins Feld oder wieder in die Ausgangsstellung zurück (Bild). Es wird mithin kein Bauer bewegt und keine Figur geschlagen – noch nicht einmal eine angegriffen.

Ein derartiges Spiel wäre vollständig als Folge von Nullen und Einsen zu beschreiben. Kann es eine unendliche Folge dieser Art geben, die kein Tripel enthält, das heißt keine dreifache Wiederholung eines Teilstücks beliebiger Länge?

Es gibt sogar sehr viele. Der Mathematiker Marston Morse (1892 bis 1977), der lange am Institute for Advanced Study in Princeton (New Jersey) tätig war, und sein Kollege Gustav A. Hedlund stießen bei der Untersuchung eines Problems aus der Dynamik auf eine tripellose Folge, die viel Beachtung fand und heute Morse-Hedlund-Folge heißt. Dabei hatte der norwegische Mathematiker Axel Thue (1863 bis 1922) schon von 1906 an mehrere Arbeiten zu diesem Thema verfaßt; und noch ein halbes Jahrhundert zuvor hatte ein Franzose namens E. Prouhet die Folge zumindest implizit verwendet. Zudem hat der Niederländer Max Euwe (1901 bis 1981), Schachweltmeister von 1935 bis 1937, unabhängig von seinen Vorgängern dieselbe Folge gefunden.

Beginnen Sie mit einer Null. Hängen Sie dann an das jeweils schon vorhandene Teilstück die komplementäre Folge an; das ist diejenige, bei der 0 und 1 vertauscht sind. Im ersten Schritt besteht die komplementäre Folge einfach aus der Eins. Wir erhalten also 01, hängen die komplementäre Folge 10 an, und so weiter:

0

01

0110

01101001

...

Diese Folge ist tripellos, aber das ist nicht einfach zu beweisen. Betrachten wir statt dessen ein zugänglicheres Beispiel.

Dafür müssen wir zunächst einige Begriffe einführen. Wir erinnern uns, daß jede gerade Zahl ein Vielfaches von 2 ist, also von der Form 2m für irgendein m; eine ungerade Zahl ist um eins größer als ein Vielfaches von 2, läßt sich also als 2m+1 schreiben. Wir brauchen eine ähnliche Beschreibung für die Vielfachen von 3. Wir nennen eine Zahl einen Alt, wenn sie ein Vielfaches von 3 ist, also von der Form 3m, einen Sopran, wenn sie um eins größer ist als ein Vielfaches von 3, das heißt von der Form 3m+1, und einen Baß, wenn sie um 1 kleiner ist als ein Vielfaches von 3, wenn man sie also als 3m-1 ausdrücken kann. Jede ganze Zahl gehört zu einer der drei Singstimmen. Wenn eine Zahl von der Form 3m+1, also ein Sopran, ist, nennen wir die Zahl m ihren Agenten. Beispielsweise ist 16=(3×5)+1 ein Sopran, und ihr Agent ist 5, ein Baß, denn 5=3×2-1.

Es folgt das Bildungsgesetz für eine tripellose Folge:

Regel 1: Das erste Glied ist 0.

Regel 2: Das n-te Glied ist 0, wenn n ein Alt ist.

Regel 3: Das n-te Glied ist 1, wenn n ein Baß ist.

Regel 4: Wenn n ein Sopran ist und m ihr Agent, dann ist das n-te Glied gleich dem m-ten.

Die ersten drei Regeln sagen uns, daß die Folge die Gestalt 010*10*10*10*10... hat, wobei sich das Muster *10 unendlich oft wiederholt; was an den Plätzen mit den Sternen steht, wird erst durch die vierte Regel festgelegt. Beispielsweise ist das vierte Glied gleich dem ersten, also 0, denn der Agent von 4 ist 1. Das siebte Glied ist gleich dem zweiten, also 1, und so weiter. Jeder Agent ist kleiner als sein Sopran; deswegen ist sein Wert stets schon festgelegt, wenn der Wert eines Soprans zu bestimmen ist, und die Regeln definieren tatsächlich vollständig die Folge: 010 010 110 010 010 110 010 110 110 010 010 110.

Ich nenne sie die Chorfolge. Man stelle sich einen - nicht gerade eintönigen, aber doch nur zweitönigen – Wechselgesang vor, in dem Sopran, Baß und Alt reihum einen von zwei Tönen (namens 0 oder 1) singen. Ich habe die Glieder in Dreiergruppen zusammengefaßt und die Sopranzahlen hervorgehoben, um die Struktur deutlich zu machen. Kurioserweise singt der Sopran allein dasselbe Stück wie alle drei Stimmen zusammen. Dagegen sind Alt- und Baßstimme viel langweiliger: nur Nullen beziehungsweise Einsen. Es gibt in der Folge viele Wiederholungen; beispielsweise werden die ersten neun Töne gleich noch einmal gesungen. Aber kein Block tritt dreimal hintereinander auf (siehe Kasten).

Was hat das nun mit einer endlosen Schachpartie zu tun? Man verwendet die Symbole 0 und 1 als Bezeichnungen für die erwähnten Springerzüge. Es ergibt sich ein nicht sehr erregendes, aber erlaubtes Spiel. Und wegen der Eigenschaften der Chorfolge dauert es garantiert ewig, ohne daß eine Folge von Zügen dreimal hintereinander vorkäme. Mehr noch: Selbst wenn man nicht Züge, sondern nur gezogene Figuren registrieren würde, ergäbe sich keine Dreifachwiederholung. Eine Schachregel, die zuverlässig sinnlose Spiele beendet – selbst solche, in denen die Spieler konspirieren, um Unfug zu treiben –, muß also deutlich besser sein als das alte Verbot der Dreifachwiederholung.

Ein Mathematiker käme alsbald auf die Idee, die Fragestellung zu erweitern. Wie ist zum Beispiel die Situation, wenn mehr als zwei Symbole erlaubt sind? Es könnte lustig sein, eine solche Frage in ein Schachspiel umzusetzen – auch wenn sich daraus kein Anlaß ergeben wird, die Schachregeln zu ändern oder neue Strategien zu ersinnen.

Erstaunlicherweise finden selbst solch praxisferne Spielereien Anwendungen. Auf die englische Version dieses Artikels im Scientific American hin schrieb mir Irvin J. Good vom Virginia Polytechnic Institute in Blacksburg, daß die Veröffentlichung des Schachweltmeisters Max Euwe ihn in den Jahren 1943/44 dazu inspirierte, einen fehlerkorrigierenden Code für Fernschreibzeichen zu erfinden. Es handelt sich um denselben Code, den unabhängig von Good der Ingenieur Frank Gray bei den AT&T-Bell-Laboratorien in Murray Hill (New Jersey) entwickelt hat und der heute seinen Namen trägt (Spektrum der Wissenschaft, Januar 1985, Seite 8).

Literaturhinweise

- A Mathematician Gives an Hour to Chess. Von Donald McMurray in: Chess Review, Band 6, Heft 10, Seite 238, Oktober 1938.

– Mémoire sur quelques relations entre les puissances des nombres. Von E. Prouhet in: Comptes Rendus des Séances de l'Académie des Sciences, Band 33, Heft 8, Seite 225, 1851.

– Set Theory Observations and Chess. Von Max Euwe in: Proceedings of the Academy of Sciences Amsterdam, Band 32, Seiten 633 bis 642, 1929.

– Enigma and Fish. Von Irving J. Good in: Codebreakers. Herausgegeben von F. H. Hinsley und Alan Stripp. Oxford University Press, 1993.


Aus: Spektrum der Wissenschaft 7 / 1996, Seite 10
© Spektrum der Wissenschaft Verlagsgesellschaft mbH