</div>

Sprouts ( engl. Sprosse (n)) ist der Name eines 1967 von den Mathematikern John Conway und Michael S. Paterson erfundenen Spiels für zwei Spieler. Beide Spieler verbinden auf einem Blatt Papier Punkte mit Linien. Es gewinnt, wer die letzte Linie setzt. Neben dem Zeitvertreib ist das Spiel eine gute Einführung in die Topologie .

Der Zusammenhang mit der Topologie besteht darin, dass alle Sprouts-Partien unter Homöomorphismen invariant sind: eine Sprouts-Partie kann man auf ein Gummituch aufmalen und dann das Gummituch beliebig verzerren. Durch diese Verformung bleiben dennoch alle wesentlichen Merkmale der Partie erhalten (insbesondere, wer die Partie gewinnt!).

Geschichte

Sprouts wurde 1967 von den Mathematikstudenten John Conway und Michael Paterson auf der Universität Princeton als Zeitvertreib erfunden. Laut Conway verteilt sich der Anteil der beiden Erfinder im Verhältnis 2/5 (Conway) zur 3/5 (Paterson), denn Paterson habe die Idee gehabt, auf die neu eingezeichneten Linien einen neuen Punkt zu malen. Den Namen erhielt es durch seine baldige, rege Verbreitung auf dem Campus, die an die essbaren Sprossen erinnerte - es "spross" sprichwörtlich überall und innert kurzer Zeit entstanden eine ganze Zahl von Varianten und Lösungsvorschlägen.

In der Originalversion, Princeton sprouts, wird mit einer beliebigen Anzahl von Punkten auf dem Papier begonnen - je mehr, desto komplexer und länger wird das Spiel. Abwechselnd verbindet jeder Spieler zwei Punkte mit einer Linie. Die Linie darf keine vorhandenen Linien oder Punkte berühren oder kreuzen. Auf die Verbindungslinie zeichnet er einen neuen Punkt ein. In jedem Punkt dürfen max. 3 Linien enden.

Analyse

Obwohl sich das Spiel recht einfach anhört, entwickelt jeder Spieler nach den ersten Partien bereits ein Gespür für seine Komplexität. Die Länge eines Spiels ist jedoch stets begrenzt, wie sich leicht zeigen läßt:

Wir betrachten ein Spiel mit n Startpunkten, welches m Züge dauert. Am Anfang hat jeder Punkt 3 Leben, denn es können maximal drei Linien von ihm ausgehen. Das Spiel beginnt also mit 3n Leben. Jeder Zug verbraucht 2 Leben (am Anfang- und Endpunkt der Linie) und bringt ein neues (der neue eingezeichnete Punkt hat genau ein freies Leben), reduziert die Anzahl der Leben daher um eins. Da beim letzten Zug immer noch ein freies Leben entsteht (beim letzten eingezeichneten Zug), gilt: 3n − m ≥ 1, oder andersherum : m ≤ 3n − 1.

Das Spiel ist daher spätestens nach 3n − 1 Zügen zu Ende.

Auch die Zahl der Punkte, die kein freies Leben mehr haben (tote Punkte), ist begrenzt. Solche Punkte heißen Pharisäer ( hebräisch für die Abgeschiedenen), wenn alle ihre Nachbarn ebenfalls tote Punkte sind. Ein toter Punkt, der an einen Überlebenden angrenzt, heißt Nachbar. Kein toter Punkt kann mit zwei Überlebenden verbunden sein, sonst könnte man immer diese beiden Überlebenden verbinden.

Es gilt also:

n + m = 3n − m + 2(3n − m) + p

denn n + m ist die Gesamtzahl der Punkte am Ende (anfängliche Punkte + Anzahl der Züge, bei jedem Zug kommt ein Punkt hinzu), diese wiederum ergibt sich aus Anzahl der Ãœberlebenden (3n − m) plus Anzahl der Nachbarn 2(3n − m) plus Anzahl der Pharisäer (p). Durch Umstellen und Zusammenfassen erhält man:

m = 2n + p/4

Also dauert ein Spiel mindestens 2n Züge, und die Zahl der Pharisäer ist immer durch 4 teilbar.

Notation

Die offizielle Notation der WGOSA , die sog. Conway-Notation, entstand etwa 1999 in einem Diskussionsforum auf http://www.mathforum.com . Diese Version wurde längere Zeit akzeptiert, bis Dan Hoey herausfand, dass sie nicht alle Partien eindeutig beschreiben kann. Hoey entwickelte daraufhin eine eigene Notation, während die Standardnotation ergänzt wurde.

Die Standardnotation beginnt mit der Anzahl der Startpunkte, und es folgt ein "+" für eine Normalpartie oder ein "−" für eine Misère-Partie , siehe unten. Anschließend werden die Namen der Spieler in Klammern aufgeführt, zuerst der Spieler, der den ersten Zug hat, dann der zweite Spieler. Der einladende Spieler wird mit einem Stern "*" markiert.

Beispiel: 3+ (Müller, Schmitz*) ist eine normale 3-Punkt-Partie zwischen Müller und Schmitz, Schmitz hat eingeladen, Müller am Zug.

In der Standardnotation werden zunächst die Startpunkte in der Reihenfolge ihrer Verwendung durchnummeriert, neue Punkte erhalten fortlaufende Nummern, so wie sie entstehen. Jeder Zug besteht mindestens aus einem Zahlentripel der Form f(g)h, wobei f und h die Endpunkte der Linie markieren und g den neu eingezeichneten Punkt. Wenn bei einem Zug eine neue Region entsteht, werden die Punkte, die durch diesen Zug von allen übrigen getrennt werden, in eckigen Klammern aufgeführt.

Beispiel: 1(10)3 [2, 5, 7−9] ist ein Zug von 1 nach 3, Punkt 10 neu erzeugt, die Punkte 2, 5 und 7 bis 9 werden von den übrigen abgetrennt.

Wie man auf dem nebenstehenden Bild sieht, gibt es in bestimmten Situation mindestens zwei (topologisch verschiedene) Möglichkeiten, zwei Punkte zu verbinden.

Beispiel: Die Illustration zeigt ein 5-Punkte-Spiel, bisher wurde gezogen 1(6)2 3(7)4. Für den folgenden Zug 6(8)7 gibt es vier topologisch verschiedene Zugmöglichkeiten.

Zur Unterscheidung der vier Zugmöglichkeiten verwendet man das sog. Hoey-Exclam, ein Ausrufezeichen, das zur Unterscheidung eingesetzt wird. Um die Funktionsweise des Hoey-Exclams zu verstehen, denke man sich eine Ameise, die von Punkt 8 ausgehend in Richtung der Punkte 6 oder 7 krabbelt. Am Punkt 6 oder 7 angekommen, sieht sie die Nachbarn dieser Punkte. Entweder ist der Punkt mit der höheren Nummer rechts oder links. Wenn der Punkt mit der höheren Nummer links ist, wird das Hoey-Exclam eingesetzt.

Beispiel:: Die Varianten A bis D werden folgendermaßen notiert:

• A: 1(6)2 3(7)4 6(8)7
• B: 1(6)2 3(7)4 6!(8)!7
• C: 1(6)2 3(7)4 6(8)!7
• D: 1(6)2 3(7)4 6!(8)7

Wer gewinnt?

Durch vollständige Analyse aller möglichen Spielverläufe kann man zeigen, dass der erste Spieler ein Spiel mit 3, 4 oder 5 Punkten gewinnen kann. Der zweite Spieler kann jedes Spiel mit einem, zwei oder sechs Punkten gewinnen.

David Applegate, Guy Jacobson, and Daniel Sleator von den Bell Labs lösten 1990 alle Spiele mit maximal 11 Punkten. Sie fanden, dass der erste Spieler eine Gewinnstrategie hat, wenn die Zahl der Punkte beim Teilen durch 6 einen Rest von 3, 4 oder 5 ergibt. Es wird angenommen, dass diese Regel auch gilt, wenn die Zahl der Punkte höher ist.

Varianten

Jede Variante von Sprouts kann durch eine Variation der Startpunkte verändert werden. Zudem besteht die Möglichkeit, misère zu spielen - es verliert der Spieler, der die letzte Linie zieht. Wenig Sinn hat eine Erhöhung der erlaubten Linien pro Punkt.

Beim Black-and-white sprouts hat der ziehende Spieler die Wahl, ob er auf seine gerade gezogene Linie einen Punkt setzt oder nicht. Diese Version ist gelöst [1] , es gewinnt bei perfektem Spiel der beginnende Spieler.

Beim Brussels sprouts (scherzhaft nach Rosenkohl , englisch en:Brussel sprouts benannt) spielt man nicht mit Punkten, sondern mit Kreuzen, deren vier Arme zu verbinden sind. Jeder Punkt hat also vier "Leben", doch sind die Linien vorgegeben. Diese Version ist wesentlich einfacher als die Originalversion, gelöst und nur als Spaß gedacht. Jedes Spiel dauert 5n-2 Züge.

Beim Antwerp sprouts [2] wird das Spiel zusätzlich mit Farben gespielt.

Weblinks

• World Game of Sprouts Association
• Links zu Analysen und Foren
• Snort und Col sind mit Sprouts verwandt.

Literatur

Martin Gardner: Mathematical Carnival. Penguin, 1976

Kategorien : Freies Spiel | Strategiespiel