Laskers NIM

Spielerklärung

Lasker's NIM ist eine Variante des NIM-Spiels. Der Unterschied dabei ist, dass man nicht nur Steine eines Stapels nehmen kann, sondern den Stapel auch aufteilen kann.

Spielregeln

  • Es wird abwechselnd gespielt.
  • Keine zufälligen Einflüsse.
  • Der Spieler sucht sich einen Stapel aus, von dem er mindestens eines Stein nimmt oder ihn aufteilt.
  • Der Spieler, der den letzten Stein nimmt, hat gewonnen.

Berechnung der Sprague-Grundy Werte

Der Sprague-Grundy Wert ist gleich der kleinsten natürlichen Zahl, die nicht in einer Menge vorkommt. Hier betrachtet man die Werte der Nachfolgepositionen, um den tatsächlichen S-G Wert zu erhalten. Jeder Stapel hat seinen eigenen S-G Wert. Ausgehend von einem Ausgansstapel werden alle Nachfolgepositionen betrachtet. Wenn der Ausgangsstapel aufgeteilt wird, benötigt man die Nim-Summe, um den Wert dieser Position herauszufinden. Aus diesen verschiedenen Zahlen wird nun die kleinste, nicht vorhandene gesucht, die den S-G Wert ist.
Beispiel:
Man hat einen Stapel von zwei Steinen. Man kann in drei versch. Positionen spielen.

  • Beide Steine nehmen, so dass nichts mehr bleibt: S-G Wert = 0
  • Einen Stein nehmen, so dass einer bleibt: S-G Wert = 1
  • Den Stapel aufteilen, in zwei Stapeln mit je einem Stein: [001]2 + [001]2 = [000]2 = 0

Man hat nun die Werte 0 und 1. Die kleinste Zahl, die nicht dabei ist, entspricht der 2. Somit ist der S-G Wert von einem Stapel mit zwei Steinen 2.

x 0 1 2 3 4 5 6 7 8 9 10 11 12…
g(x) 0 1 2 4 3 5 6 8 7 9 10 12 11…

Wichtig bei der Berechnung der S-G Werte ist, dass man die vorhergegangenen Werte beachten muss.

Beispiel für den Miteinbezug der vorhergehenden Werte.

Wie in der obigen Tabelle abgelesen werden kann, ist der S-G Wert bei 3 Steinen 4. Jedoch bei 4 Steinen ist er 3.

Stapel mit 3 Steinen:

  • alle Steine weg; keiner bleibt: 0
  • Zwei Steine weg; einer bleibt: 1
  • Ein Stein weg; zwei bleiben: 2
  • aufteilen (1,2): [001]2 + [010]2 = [011]2=3

Der S-G Wert ist gleich 4

Stapel mit 4 Steinen:

  • alle Steine weg; keiner bleibt: 0
  • drei Steine weg; einer bleibt: 1
  • zwei Steine weg; zwei bleiben: 2
  • ein Stein weg; drei bleiben: !! siehe vorher bei drei Steinen, ist der S-G Wert 4 !!
  • aufteilen (2,2): [010]2 + [010]2 = [000]2 = 0
  • aufteilen (1,3): [001]2 + [011]2 = [010]2 = 2

Somit ist der S-G Wert gleich 3

Gewinnstrategie

Die Gewinnstrategie liegt darin, mit dem Zug eine Position herzustellen, bei der der Sprague- Grundy Wert Null beträgt. Den Sprague- Grundy Wert der Position erhält man, indem man die Werte aller Stapel mit der Nim- Addition zusammenaddiert. Besitzt das Spiel einen Sprague- Grundy Wert von Null, liegt es in einer P- Position. Denn der Spieler, welcher das Spiel in diese Position gebracht hat, besitzt die Gewinnchance.

Die Gewinnstrategie wird nun anhand eines konkreten Beispiels dargestellt:

Das Spiel besteht aus drei Stapeln von 2, 5 und 7 Steinen.

OO
OOOOO
OOOOOOO

Der oben beigefügten Tabelle entnehmen wir, dass für Stapeln mit 2, 5 und 7 Steinen die Sprague- Grundy Werte gelten:

G(2)=2
G(5)=5
G(7)=8

Den Sprague- Grundy Wert des Spiels erhält man mit der Nim- Addition der Werte der jeweiligen Stapeln:

2= [0010]2
5= [0101]2
8= [1000]2

15= [1111]2

Um das Spiel zu gewinnen muss nun eine P-Position hergestellt werden. Dies wird zum Beispiel erreicht, indem man den Stapel mit 7 Steinen in einen Stapel mit 6 Steinen und einen mit 1 Stein teilt:

2= [0010]2
5= [0101]2
6= [0110]2
1= [0001]2

0= [0000]2

Spielt der Spieler, welcher diese Position hergestellt hat, weiter nach dieser Strategie, gewinnt er das Spiel. Ausserdem ist hier anzumerken, dass man sich der Symmetrie im Lasker's NIM genau so gut
bedienen kann, wie in der Standard-Version.

Beispiel

Laskers%20Nim.PNG
Laskers%20Nim2.PNG

Video

Quellenangabe

http://www.example.com http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf
http://www.example.com http://www.mathematik.uni-wuerzburg.de/~steuding/hofmann.pdf

certainty.png
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License