Wir spielen das folgende Spiel. Wir beginnen bei 0 und sind abwechseln am Zug. In einem Zug addiert man 1 bis 10 zur aktuellen Zahl. Wer durch einen Zug auf 100 oder mehr kommt, hat gewonnen. Was ist eine gute Strategie für dieses Spiel? Ist anfangen ein Vorteil oder doch eher ein Nachteil?
In diesem Artikel werden wir Spiele dieser Art analysieren und uns einige Konzepte anschauen, die dabei nützlich sind. Wir betrachten dabei nur 2-Personen-Spiele. Meist sollen sie symmetrisch sein in dem Sinne, dass jeder am Zug die gleichen Züge ausführen kann. Schach ist ein Beispiel, dass diese Bedingung nicht erfüllt ist, weil jeder seine eigenen Steine besitzt. Außerdem sollen die Spiele endlich sein und genau einen Gewinner haben.
Gewinn- und Verluststellungen
Die erste Methode schaut sich alle möglichen Stellungen des Spiels an und bewertet sie mit einer Gewinn- bzw. Verluststellung. Eine Gewinnstellung ist eine Position aus der man am Zug den Sieg erzwingen kann. Bei einer Verluststellung kann man den Sieg nicht erzwingen. Da es einen Gewinner geben muss, das Spiel endlich ist und jeder die gleichen Züge ausführen kann, kann folglich der andere Spieler den Sieg erzwingen.
Um die obige Aufgabe zu lösen, wollen wir also wissen, ob die Startposition eine Gewinn- oder eine Verluststellung ist und wie man auftretende Gewinnstellungen ausnutzt. Eine Spielposition ist in dem Beispiel nur die aktuelle Zahl. Es spielt schließlich keine Rolle, wie man auf diese Zahl gekommen ist. Doch wie bestimmt man Gewinn- und Verluststellungen? Eine gute Vorgehensweise ist es hier, beim Spielende zu beginnen.
Die Zahlen 90 bis 99 sind Gewinnstellungen. Schließlich kann man am Zug auf 100 ergänzen. Was ist mit der 89? Egal was welche Zahl man addiert, man kommt auf eine Zahl von 90 bis 99. Diese sind Gewinnstellung, das heißt der andere Spieler kann gewinnen. Also ist 89 eine Verluststellung. Hier sehen wir die erste wichtige Eigenschaft über Gewinn- und Verluststellungen. Aus einer Verluststellung kann man in einem Zug nur Gewinnstellungen erreichen. Schließlich würde man ja gewinnen können, wenn man dem Gegner eine Verluststellung überlässt.
Bei der 88 kann man einfach auf 89 erhöhen. Allgemein geht das für Zahlen von 79 bis 88. Da 89 eine Verluststellung ist, kann man gewinnen, wenn man den Gegner in diese Position bringt. Hier kommt die zweite wichtige Eigenschaft von Gewinn- und Verluststellung ins Spiel. Aus einer Gewinnstellung gibt es zumindest einen Zug, der eine Verluststellung herbeiführt. Man muss dem Gegner eine Stellung überlassen können, aus der diesen den Sieg nicht erzwingen kann, sonst kann man selber nicht den Sieg erzwingen.
Beide Eigenschaften gelten auch in die andere Richtung. Wenn man aus einer Position nur Gewinnstellungen erreichen kann, handelt es sich um eine Verluststellung. Falls man zumindest eine Verluststellung herbeiführen kann, ist es eine Gewinnstellung. Wir können jetzt also eine Stellung bewerten, indem wir uns alle Stellungen anschauen, die man erreichen kann. Wenn es unter diesen eine Verluststellung gibt, ist die betrachtete Stellung eine Gewinnstellung. Andernfalls ist es eine Verluststellung.
In unserem Beispiel kann man vielleicht schon ein Muster erkennen. Die Zahlen 89, 78, 67, usw. also die Zahlen a\equiv 1 \mod 11 sind die Verluststellungen. Alle anderen sind Gewinnstellungen. Insbesondere ist 0 eine Gewinnstellung, der anfangende Spieler kann also einen Sieg erzwingen. Man kann diese Belegung der Gewinn- und Verluststellungen über vollständige Induktion beweisen. Beispielsweise kann man beweisen, dass für alle natürlichen Zahlen die Verluststellungen von 100-n bis 100 genau die Zahlen sind, die Rest 1 bei Division durch 11 lassen. Der Induktionsanfang ist, dass 100 eine Verluststellung ist, weil der Gegner mit dem Zug auf 100 gerade das Spiel gewonnen hat. Im Induktionsschritt benutzt man dann, dass man von einer Zahl mit Rest 1 nur Zahlen mit anderem Rest erreichen kann. Andererseits kann man von jedem anderem Rest auch die 1 erreichen, weil man 1 bis 10 addieren kann.
Die Strategie ist also immer so zu spielen, dass man auf einen Rest von 1 bei Division durch 11 kommt. Im ersten Zug wählt man die 1, im nächsten Zug addiert man auf die 12, usw. Nach einigen Zügen erhöht man auf 89 und gewinnt im folgenden Zug. Natürlich kann man diese Strategie auch ohne Betrachtung von Gewinn- und Verluststellungen anschauen und zeigen, dass sie funktioniert (man kann immer auf genau 11 ergänzen), allerdings ist es dann deutlich schwieriger auf diese Idee zu kommen.
Ausnutzen von Symmetrie
Zwei Spieler legen abwechseln gleich große Münzen auf einen quadratischen Tisch, sodass die Zahlseite der Münze den Tisch vollständig berührt. Insbesondere dürfen die Münzen nicht gestapelt werden. Wer keine Münze mehr legen kann, hat verloren. Wer kann hier den Sieg erzwingen?
Zunächst einmal sollte man sich überlegen, dass dieses Spiel tatsächlich endlich ist. Der Tisch hat aber eine endlich große Fläche, damit passen auch nur eine bestimmte Zahl an Münzen auf diesen Tisch. Egal wie die Münzen platziert werden, endet das Spiel also. Wenn man jetzt also eine Strategie hat, mit der man verhindert, dass man verliert, so ist das eine Gewinnstrategie. Schließlich muss der Gegner dann irgendwann verlieren.
Wir suchen also eine Strategie, mit der man auf jeden Zug des Gegners einen weiteren Zug ausführen kann. Man könnte einfach den Zug des Gegners spiegeln und auf die entsprechende Position eine Münze legen. Dann hat man aber ein Problem, wenn der Gegner auf die Spiegelachse setzt. Der erste Spieler kann allerdings eine Münze in die Tischmitte legen und dann jeden Zug des Gegners an der Tischmitt punktspiegeln. Dann ist die Tischbelegung nach jedem seiner Züge punktsymmetrisch, also ist der gespiegelte Ort immer noch frei. Also hat der erste Spieler eine Gewinnstrategie. Es gibt eine Ausnahme und zwar, wenn die erste Münze nicht gelegt werden kann, weil keine einzige Münze auf den Tisch passt. Dann hat der zweite Spieler eine Gewinnstrategie, weil der erste Spieler den ersten Zug schon nicht ausführen kann.
Stehlen der Strategie
Dieses Konzept ist recht ähnlich zum Symmetrieargument. Es hilft leider nicht, eine Gewinnstrategie zu entwickeln, sondern nur um zu zeigen, wer das Spiel gewinnen kann. Wir schauen uns dafür das folgende Spiel an. Eine Tafel Schokolade ist in rechteckige Stücke unterteilt. Das Stück in der rechten unteren Ecke ist vergiftet. Zwei Spieler spielen abwechselnd. Ein Zug besteht darin, eine Zeile und eine Spalte auszuwählen und alle Stücke zu nehmen, die oberhalb der Zeile und gleichzeitig links von der Spalte liegen. Dabei muss man mindestens ein Stück nehmen. Wer das vergiftete Stück nimmt hat verloren. Wer kann hier den Sieg erzwingen?
Ein möglicher Zug aus der Startstellung ist nur das linke obere Stück zu nehmen. Wenn das gleichzeitig das rechte untere Stück ist, hat natürlich der beginnende Spieler sofert verloren. Dann besteht die Tafel aber auch nur aus einem Stück und das Spiel ist nicht so interessant. Nehmen wir also an, dass das nicht der Fall ist. Eine wichtige Beobachtung ist, dass man alle Züge, die man aus der Stellung mit diesem einem fehlenden Stück, machen kann, auch schon aus der Startstellung herbeiführen kann. Schließlich könnte man die gleiche Zeile und Spalte auswählen.
Nehmen wir also an, dass der zweite Spieler eine Gewinnstrategie für die Stellung mit dem fehlenden Stück hat. Diese Strategie könnte man dann auch in ein Buch aufschreiben, indem man für jede mögliche Spielposition zumindest einen Gewinnzug aufschreibt. Der Plan ist jetzt, dieses Buch zu stehlen und zum eigenen Vorteil zu nutzen. Statt im ersten Zug nur ein Stück zu nehmen, befolgen wir diese Strategie. Wir könnnen ja den gleichen Zug ausführen.
Falls es keine Gewinnstrategie für den zweiten Spieler in der Stellnung gibt, so muss der anfangende Spieler eine Gewinnstrategie haben. Wie diese funktioniert, ergibt sich aus dieser Beweismethode nicht. Wir wissen nur, dass sie existiert.
In beiden Fällen hat der erste Spieler für die Ausgangsposition eine Gewinnstrategie, also kann er den Sieg erzwingen.
Im nächsten Artikel setzen wir uns mit dem Invarianzprinzip auseinander.