Margarete, das Schwanenmädchen, und Hans-Martin, der Schafhirt, ruhten auf einer Wiese in der Frühlingssonne, während Taps, der Schäferhund, unter einem Wacholderbaum schlief. Die Blümlein blühten, die Fliegen flogen, die Grashüpfer hüpften, und die Vögel – zwitscherten. Es war idyllisch.

"Dieses Herumsitzen ist langweilig", maulte Margarete. "Laß uns irgend etwas spielen."

Hans-Martin schüttelte den Kopf. "Nicht mit dir. Dann gewinnst du immer. Du bist mir zu logisch."

"Dann einigen wir uns doch auf ein Spiel, bei dem man den Sieg nicht durch Logik erzwingen kann – oder von dem ich jedenfalls nicht weiß, wie es geht."

"Na gut", stimmte Hans-Martin zu, der von der ersten Mai-Hitze schon leicht benommen war. Sonst wäre ihm klar gewesen, daß Margarete auch dann überlegene Züge finden würde, wenn sie keine absolut sichere Gewinnstrategie im Kopf hatte. "An welches Spiel denkst du denn?"

"Go-Moku", sagte Margarete entschieden. "Manche nennen es auch Go-Bang. Das Spiel mit den fünf Steinen in einer Reihe. Man spielt es mit zweierlei Steinen auf einem Brett."

"Haben wir aber nicht."

Margarete blickte sich suchend um. Der Bauer wollte den unteren, sauren Teil der Wiese entwässern und hatte dazu schon Dränagerohre gitterförmig ausgelegt. "Sieh doch", rief das Mädchen. "Du setzt deine schwarzen Schafe und ich meine weißen Schwäne."

"Die Schafe gehen doch nie dahin, wo ich will."

"Laß das den alten Taps machen. Ich rufe die Schwäne mit meiner lieblichen Stimme, und sie werden mir folgen."

Margarete fuhr fort: "Wir stellen immer abwechselnd eines unserer Tiere auf einen freien Platz. Gewonnen hat, wer zuerst fünf Tiere nebeneinander in einer Reihe hat" (Bild 1).

"Längs oder quer?"

"Oder diagonal – sonst würde das Spiel mit perfekter Strategie immer unentschieden ausgehen."

"Wieso das denn?"

"Oh, verzeih. Ich vergaß, daß du kein Logiker bist. Ich erkläre es dir später."

Margarete gewann die ersten 20 Spiele. Aber Hans blieb unverzagt, denn er sah ab und zu Möglichkeiten, sich zu verbessern. Während der ersten Spiele war ihm noch nicht aufgefallen, wenn er im nächsten Zug zu verlieren drohte. Margarete ging dazu über, "Gleich bist du tot!" zu rufen, so daß er ihren Siegeszug noch mit einem Schaf verhindern konnte (Bild 2). Hans-Martin warnte sie auf die gleiche Weise – er hatte allerdings nicht so häufig Gelegenheit dazu.

Wenn sie sich aber zwei solche Möglichkeiten auf einmal verschaffte, war sein Schicksal besiegelt. Sie begann, ihn auch darauf hinzuweisen, indem sie "zweimal tot" rief, aber dann war es schon zu spät. Sie warnte ihn nun bereits einen Zug vorher mit "fast zweimal tot". Mit zunehmender Erfahrung kamen die Warnungen immer früher, und Zungenbrecher wie "Fast halb tot fast fast zweimal tot" endeten in großem Gekicher. Auch der arme Taps hatte sich bei dem Versuch, mitunter zwei Dutzend Schafe am Platz zu halten, völlig verausgabt und legte sich hechelnd in den Schatten.


Strategien für Unentschieden

"Warum ist das Spiel so schwer?" fragte Hans-Martin.

"Überleg dir mal dasselbe Spiel mit n statt fünf Steinen", erklärte Margarete. "Wenn n klein ist, dann ist es für den, der anfängt, leicht zu gewinnen, weil die Aufgabe so schnell erledigt ist, daß der Gegner nicht viel dagegen tun kann. Wenn n dagegen groß ist, kann der zweite Spieler immer ein Unentschieden erzwingen, denn der erste muß seine Absichten so früh preisgeben, daß der zweite genügend Zeit hat, eine sich bildende Reihe zu unterbrechen. Die schwierigen Spiele liegen dazwischen, und die kompliziertesten scheinen die zu sein, bei denen fünf oder sechs Steine in einer Reihe gefordert werden."

"Ach so. Bei Eins-in-einer-Reihe gewinnt immer der erste Spieler, denn er erreicht sein Ziel schon im ersten Zug."

"Kluges Kerlchen, Hänsel."

"Lästere nicht, Gretel. Ich überlege mir doch nur zuerst die trivialen Fälle. Bei Zwei-in-einer-Reihe gewinnt auch immer der erste Spieler: Einerlei, wo der zweite seinen Stein hinlegt – es gibt immer ein freies Feld neben dem ersten."

"Richtig."

"Bei drei Steinen ist der Eröffnungszug eine Fast-tot-Stellung. Egal, was der zweite Spieler tut, der erste kann zwei Steine in einer Reihe mit zwei offenen Enden erreichen. Es gibt zwar mehrere verschiedene Fälle, aber es ist immer noch ziemlich offensichtlich."

Margarete nickte.

"Aber mit Vier-in-einer-Reihe komme ich nicht zurecht", gab Hans-Martin zu. "Was für eine Art Drohung ist der Eröffnungszug?"

"Das ist auch ein schwieriges Problem. Carlyle Lustenberger von der Staatsuniversität von Pennsylvania in Philadelphia hat unter Verwendung eines Computers bewiesen, daß der erste Spieler immer gewinnen kann – vorausgesetzt, das Brett hat wenigstens 4×30 Felder. Andererseits gibt es einen sehr schönen Beweis dafür, daß der zweite Spieler bei Neun-in-einer-Reihe immer ein Unentschieden erreichen kann. Die Idee besteht darin, die Felder geschickt zu Paaren zusammenzufassen: Immer wenn der erste Spieler ein Feld besetzt, geht der zweite sofort auf das andere. Die Paare sind so gewählt, daß jede Reihe mit neun Steinen beide Felder mindestens eines Paares enthalten muß. Also entsteht keine Reihe aus neun gleichfarbigen Steinen, und das Spiel geht unentschieden aus" (Bild 3).

"Was du nicht alles weißt!"

"Ich weiß sogar noch mehr. Diese Art Strategie nennt man eine Hales-Jewett-Paarung. A. W. Hales und R. I. Jewett haben auf diese Weise bewiesen, daß Fünf-in-einer-Reihe auf einem 5×5-Brett stets unentschieden ausgehen kann. Eine Gruppe holländischer Mathematiker hat unter dem Pseudonym T. G. L. Zetters bewiesen, daß dasselbe für Acht-in-einer-Reihe gilt. Dagegen haben Victor Allis und seine Kollegen von der Universität von Limburg in Maastricht gezeigt, daß der erste Spieler bei Fünf-in-einer-Reihe stets gewinnen kann, wenn das Brett mindestens 15 × 15 Felder groß ist" (Spektrum der Wissenschaft, April 1993, Seite 25). "Ob es eine Gewinnstrategie für Reihen der Länge sechs oder sieben gibt, ist noch unbekannt. Wahrscheinlich bringt einen die Idee von Hales und Jewett da nicht weiter."

Hans-Martin lehnte sich ins Gras zurück. "Am schwierigsten fand ich die Einflüsse über große Entfernungen. Du stellst einen Schwan weit weg vom Gedränge, und 20 Züge später stellt sich heraus, daß es gerade auf ihn ankommt."

"Siehst du wohl."


Polyomino-Spiele

"Taps hat sich wieder erholt. Laß uns noch ein Spiel probieren, das ich mir gerade ausgedacht habe. Die gleichen Regeln wie eben, nur daß man zum Gewinnen vier Felder in Form eines 2×2-Quadrates belegen muß."

Margarete dachte einen Augenblick nach. "Ich sollte dich warnen..."

"Ach was. Ich fange an."

Nach 57 Spielen, die sämtlich unentschieden ausgingen, kroch Taps erschöpft in den Baumschatten, und Hans-Martin legte sich frustriert ins Gras. "War doch nicht so eine gute Idee."

"Na ja; nicht so ganz durchdacht... Eine einfache Hales-Jewett-Paarung zeigt, daß das Spiel bei der richtigen Strategie immer unentschieden ausgeht. Stell dir vor, das Brett sei mit Dominosteinen der Größe 2×1 gepflastert, so daß jede Zeile gegenüber der benachbarten um ein Feld versetzt ist, wie Ziegel in einer Mauer. Jeder Dominostein faßt zwei Felder zu einem Paar zusammen. Du kannst nachprüfen, daß jedes 2×2-Quadrat einen Dominostein enthalten muß, und das war's."

"Ach so. Aber was ist mit anderen Formen?"

"Du hast ein Spiel wiedererfunden, das Frank Harary von der Staatsuniversität von New Mexico in Las Cruces einmal vorgeschlagen hat. Wähle irgendeine Form aus aneinanderhängenden Quadraten – ein Polyomino, um den Markennamen von Solomon W. Golomb zu verwenden. Die Spieler besetzen im Wechsel einzelne Felder mit dem Ziel, ein solches Polyomino ihrer Farbe zu erzeugen. Ob noch weitere Steine herumstehen, spielt dabei keine Rolle.

Nennen wir das vereinbarte Polyomino einen Gewinner, wenn der erste Spieler eine Gewinnstrategie hat, also bei beliebigem Gegenspiel als erster die geforderte Form bilden kann. Und nennen wir eine Figur einen Langweiler, wenn der zweite Spieler immer ein Unentschieden erreichen kann. Dann muß jedes größere Polyomino, das einen Langweiler enthält, selbst ein Langweiler sein."

"Warum?"

"Nun, wenn du eine Gewinnstrategie für ein großes Polyomino hättest, würdest du mit derselben Strategie zugleich jedes kleinere erzwingen, das in dem großen enthalten ist. Das ist aber ausgeschlossen, weil unter diesen kleineren – wie wir vorausgesetzt haben – zumindest ein Langweiler ist. Es gibt zwölf minimale Langweiler, und für jeden kann man diese Eigenschaft durch eine geeignete Hales-Jewett-Paarung beweisen" (Bild 4). "Jedes Polyomino, das einen dieser zwölf enthält, ist also auch ein Langweiler. Andererseits ist in einem minimalen Langweiler nicht noch einer enthalten – deswegen heißen sie ja minimal. Da bleiben nur zwölf Formen übrig, und elf von ihnen sind als Gewinner bekannt. Der einzige ungelöste Fall ist die Schlange" (Bild 5; wahrscheinlich ist auch diese Figur ein Gewinner – wenn Sie dafür einen Beweis oder eine Widerlegung finden, bin ich dankbar für eine Zuschrift an die Redaktion).

"Das Polyomino, das aus fünf nebeneinanderliegenden Quadraten besteht, ist übrigens ein Langweiler", nahm Margarete den Faden wieder auf. "Das beantwortet deine Frage von vorhin: Wenn diagonale Reihen nicht erlaubt sind, ist Fünf-in-einer-Reihe wirklich ein ziemlich langweiliges Spiel."

"Ach so. Taugen diese Paarungen denn auch für andere Probleme?"

"Oh, Dutzende. Zum Beispiel hat Golomb eine Hales-Jewett-Paarung für Acht-in-einer-Reihe in einem 8×8×8-Würfel gefunden. Hales und Jewett selbst haben über n-in-einer-Reihe auf einem k-dimensionalen n×n×...×n-Hyperwürfelbrett nachgedacht und bewiesen, daß das Spiel unentschieden ausgeht, wenn n sehr viel größer als k ist. Wenn dagegen k groß gegen n ist, kann der erste Spieler stets gewinnen. Für den Fall, daß n und k annähernd gleich groß sind, weiß man bisher nichts."

"Das ist mir zu esoterisch, Margarete. Aber es erinnert mich an den Witz von dem Mathematiker, der sich in perfekten Kreisen drehte -"

Hans-Martin kam nicht mehr bis zur Pointe, denn in diesem Moment erwachte Taps und begann aufgeregt zu bellen. Alle Schafe waren davongelaufen.

Literaturhinweise

- Regularity and Positional Games. Von A. W. Hales und R. I. Jewett in: Transactions of the American Mathematical Society, Band 106, Heft 2, Seiten 222 bis 229, Februar 1963.

– Gewinnen. Band 2: Bäumchen-wechsle-dich. Von Elwyn R. Berlekamp, John H. Conway und Richard K. Guy. Vieweg, Braunschweig 1986.


Aus: Spektrum der Wissenschaft 5 / 1994, Seite 12
© Spektrum der Wissenschaft Verlagsgesellschaft mbH