Manfred Börgens
Mathematische Probleme  # 58
Liste aller Probleme mit Lösungen
voriges Problem      nächstes Problem
zur Leitseite


Würfel-Nim

und ein Exkurs in die Theorie der endlichen Spiele




Im Problem # 46 wurde bereits ein Nim-Spiel vorgestellt. Diesmal gehört ein Würfel dazu, mit dem aber nicht gewürfelt wird (mit Ausnahme der Spielvorbereitung), sondern der von den beiden Spielern nur gedreht wird. Hier sind die Spielregeln:


Wuerfel wird gedreht
Drehung über eine Kante


Nur die Spielvorbereitung beruht auf Zufallsereignissen. Der eigentliche Spielverlauf liegt vollständig in der Hand der beiden Spieler, die also bemüht sein werden, erfolgreiche Strategien zu entwickeln.

Eine geeignete Notation für Würfel-Nim ist das Zahlenpaar  (m,k) , das der Spieler am Zuge vorfindet, bevor er seinen Zug ausführt.  (m,k)  wird also vom Gegner "hinterlassen" oder "übergeben". Dabei steht  m  für den aktuellen Score und  k  für die Augenzahl, die der Würfel auf seiner Oberseite zeigt. Bei Spielbeginn findet A  (m,k) = (n,j)  vor.  (m,k)  heißt Gewinnposition, wenn es für den Spieler am Zuge eine Strategie gibt, mit der er ausgehend von  (m,k)  sicher gewinnt.  (m,k)  heißt Verlustposition, wenn es für jeden Zug, den der Spieler am Zuge machen kann, eine Strategie seines Gegners gibt, mit der dieser sicher gewinnt.

1. Geben Sie eine Gewinnstrategie für dieses Spiel an.

2. Welches  N  sollten A bzw. B wählen, um ihre Gewinnchancen zu maximieren? Gibt es ein "faires  N"?



Ein Rückgriff auf allgemeine Prinzipien der Spieltheorie ist nicht erforderlich, um dieses Problem zu lösen. Es kann aber nützlich sein, das Spiel "Würfel-Nim" in einen allgemeineren Zusammenhang zu stellen. Würfel-Nim ist ein endliches Zweipersonenspiel. Solche Spiele lassen sich mit speziellen Graphen darstellen, nämlich mit Bäumen, die alle denkbaren Spielverläufe abbilden. Jeder Knoten stellt die Ausgangslage für den jeweiligen Spieler am Zug dar, bevor er seinen Zug ausführt. Jede Kante im Baum stellt einen möglichen Zug dar, der Knoten darunter also die neue Ausgangslage (für den Gegner) nach diesem Zug. Von einem Knoten gehen also immer so viele Kanten (nach unten) aus, wie es Zugmöglichkeiten für den Spieler am Zuge gibt. Die untersten Knoten stellen Spielstände dar, die das Spiel beenden oder für die der Ausgang des Spiels klar ist. Natürlich wird es bei den meisten Spielen mit solchen Baumstrukturen mehrere verschiedene Knoten mit denselben Spielständen geben, da ein bestimmter Spielstand in der Regel mit verschiedenen Zugfolgen erreicht werden kann. (Bei Würfel-Nim steht der oberste Knoten für die Anfangssituation  (n,j)  und jeder andere Knoten für eine Position  (m,k) ; auch hier gilt: ein bestimmtes  (m,k)  kann in mehreren Knoten vorkommen.) Die folgenden Bilder zeigen ein einfaches fiktives Spiel, das kein Unentschieden zulässt. Die linke Darstellung ordnet jede Ebene im Baum einem Spieler zu (schwarze Knoten für A am Zug, weiße Knoten für B am Zug). Die rechte Darstellung zeigt die Gewinn- und Verlustpositionen (grün für Gewinn, rot für Verlust), allerdings nur für die Endknoten.

Graphen (Beispiele)

Für jedes halbwegs interessante Spiel sind diese Bäume zu groß, um sie vollständig durchrechnen zu können. Aber sie vermitteln durch ihre Struktur wesentliche Einsichten. Im rechten Bild sind absichtlich nur die Endknoten gefärbt worden. Denn dadurch sind alle anderen Knoten als Gewinn- oder Verlustpositionen determiniert. Insbesondere folgt aus den Endknoten die Färbung des obersten Knotens, also ob A oder B dieses Spiel gewinnt (fehlerloses Spiel vorausgesetzt). Eine kleine Vor-Übung für das Würfel-Nim-Problem: Welche Färbung haben die anderen Knoten im rechten Bild? Welche einfache Regel kann man dafür angeben? Gewinnt A oder B? Welche Zugfolge muss der Gewinner wählen? Diese Graphen zeigen also auf einfache Weise, dass die zugehörigen Spiele immer eine Optimalstrategie haben, dass also von vornherein festliegt, ob der Anziehende gewinnt oder der Nachziehende (falls beide keine Fehler machen). Eine Zusatzfrage: Was ändert sich an den Färbungsregeln für die Knoten, wenn das Spiel auch unentschieden enden kann?

Für Würfel-Nim lässt sich jeder Knoten durch das Zahlenpaar  (m,k)  beschreiben. Eine vollständige Analyse des Spiels kann man "von Hand" durchführen, allerdings erleichtert man sich durch ein kleines Programm die Arbeit. Welche besondere Gestalt hat der Baum für Würfel-Nim? Natürlich muss der Baum nicht vollständig durchlaufen werden, da sich die möglichen Spielstände jeweils in vielen Knoten finden. Aus der Struktur des Graphen benötigt man lediglich, durch welche Züge Knoten mit ihren Unterknoten zusammenhängen und auf welche Weise sich Gewinn- und Verlustpositionen aus den Unterknoten ergeben. Dann arbeitet man sich ausgehend von den Endknoten systematisch aufwärts durch die möglichen Spielstände.


Lösung



Publiziert 2007-02-13          Stand 2006-06-09


voriges Problem   |   Liste aller Probleme mit Lösungen   |    nächstes Problem


Manfred Börgens   |    zur Leitseite