WikiDer > Sprossen

Ein Spiel von Sprouts mit zwei Ausgangspunkten. Die neuen Punkte sind rot. Nach dem vierten Zug ist das Spiel zu Ende, da zwischen den beiden verbleibenden freien (grünen) Punkten keine Linie gezogen werden kann, ohne eine andere Linie zu überschreiten.

Sprossen ist ein Mathe-Spiel die von zwei Spielern mit Stift und Papier gespielt wird. Es wurde konzipiert von John Conway und Michael S. Patterson bei der Universität von Cambridge Anfang der 1960er Jahre des zwanzigsten Jahrhunderts. Conway und andere haben dieses Spiel gründlich analysiert.

Regeln

Das Spiel beginnt mit einer Anzahl von Punkten auf einem Blatt Papier. Die Spieler wechseln sich ab. In jeder Runde zeichnet der Spieler eine Linie zwischen zwei Punkten oder eine Schleife von einem Punkt zum gleichen Punkt und zeichnet einen neuen Punkt auf diese Zeile. Der Spieler muss die folgenden Regeln beachten:

• die neue Linie darf keine andere Linie kreuzen oder berühren;
• der neue Punkt darf nicht mit einem Endpunkt der Linie zusammenfallen;
• in einem Punkt dürfen sich nicht mehr als drei Linienenden treffen.

Gebogene Linien sind erlaubt. Der Spieler, der keine gültige Linie mehr ziehen kann, verliert; Dies ist die "normale" Version von Sprouts. Ein Unentschieden ist unmöglich.

Anzahl der Züge

Am Ende einer Partie Sprouts hat jeder überlebende (grüne) Punkt zwei tote Nachbarn.

Während jeder Zug einen Punkt hinzufügt, ist die Anzahl der Züge in einer Partie Sprouts begrenzt. Wenn da nein Punkte sind am Start, die Anzahl der Züge beträgt mindestens 2nein und maximal 3nein-1.

Dies kann man sehen, wenn man die Anzahl der "Leben" oder Freiheitsgrade eines Punktes betrachtet; Dies ist die Anzahl der Zeilen, die noch hinzugefügt werden können. Ein Punkt, an dem sich drei Linien treffen, hat null Leben; es ist eine Sackgasse.

Beim Starten eines Spiels mit nein Punkte gibt es 3nein Leben. In jeder Runde gehen zwei Leben verloren, während mit nur 1 Leben ein Punkt gewonnen wird. Somit verringert sich die Gesamtzahl der Leben pro Runde um 1. Das Spiel endet spätestens, wenn nur noch 1 Punkt am Leben ist; die Gesamtzahl der Umdrehungen beträgt also höchstens 3nein-1.

Gewinnstrategie

Da eine Partie Sprouts eine endliche Anzahl von Zügen und kein Unentschieden hat, gibt es je nach Punktzahl zu Beginn eine Gewinnstrategie für den ersten oder zweiten Spieler. Diese können für wenige Startpunkte manuell ermittelt werden, jedoch wird diese Analyse schnell kompliziert. 1990 berechneten David Applegate, Guy Jacobson und Daniel Sleator das Ergebnis für Sprouts bis zu elf Punkte mit einem Computer.^[1] 2011 haben Julien Lemoine und Simon Viennot einen effizienten Algorithmus entwickelt und ermittelt, wer bei normalen Sprouts für Spiele bis 44 Startpunkte gewinnt.^[2]

Die Ergebnisse für den ersten Spieler sind:

Applegate, Jacobson und Sleator haben beobachtet, dass der erste Spieler gewinnt, wenn die Anzahl der Startpunkte neinmodular sechs gleich drei, vier oder fünf. Der erste Spieler verliert, wenn nein modulo 6 ist gleich 0, 1 oder 2. Die Ergebnisse von Lemoine und Simon bestätigten diese Vermutung.