|
Karls Spielkiste: Nim-Spiele
Zurück
Was sind “Nim-Spiele”?
Nim-Spiele sind Spiele für zwei Personen, wobei es darum geht, von einer vorgegebenen
Anzahl von Elementen bei jedem Zug gemäß den Spielregeln eine bestimmte Anzahl von
Elementen zu entfernen. Die Spieler ziehen immer abwechselnd. Wer kein Element mehr
entfernen kann hat verloren.
Gewinnstrategien für diese Art von Spielen bestehen darin, dem Gegner nach jedem Spielzug
jeweils solche Spielstellungen zu hinterlassen, welche als “Verliererstellungen” gelten. Dabei
sind alle Stellungen, von denen nur Stellungen erreicht werden können, welche keine Verlierer-
stellungen sind, selbst Verliererstellungen.
Begrenztes Nim mit einem Haufen:
Das einfachste Nimm-Spiel geht so: Von einem Haufen aus N Elementen dürfen die beiden
Spieler abwechselnd je eine beliebige Anzahl von 1 - n Elementen entfernen.
Gewinnstrategie:
Man sorge dafür, daß der Gegner stets ein Vielfaches von (n+1) Elementen vorfindet!
z.B. für N=50 und n=5: Verliererstellungen sind: 48, 42, 36, 30, 24, 18, 12 und 6 Elemente
Begrenztes Nim mit mehreren Haufen:
Es gibt jetzt mehrere Haufen mit N1, N2, ... Elementen. Die beiden Spieler dürfen
abwechselnd je eine beliebige Anzahl von 1 - n Elementen von einem beliebeigen Haufen
entfernen.
Gewinnstrategie:
Man sorge dafür, daß der Gegner auf allen Haufen ein Vielfaches von (n+1) Elementen
vorfindet!
Nim mit mehreren Haufen:
Beim normalen Nim mit mehreren Haufen dürfen abwechselnd von beiden Spielern jeweils von
einem beliebigen Haufen eine beliebige Anzahl (jedoch mindestens ein Element) von Elementen
entnommen werden.
Gewinnstrategie:
Man bilde zunächst die Binärdarstellungen der Anzahlen der vorhandenen Haufen. Diese
werden untereinander geschrieben. Nun muß eine Anzahl so verringert werden, das die An-
zahl der “1” in jeder Spalte gerade ist. Ist dies bereits der Fall, so ist die vorliegende Stellung
bereits eine Verliererstellung!
z.B.: vier Haufen mit 13, 5, 6 und 1 Element:
Binärdarstellungen:
13: 1101
5: 0101
6: 0110
1: 0001
Nun muß der Haufen mit 13 Elementen so verringert werden, daß die Anzahl der “1” in jeder
Spalte gerade ist, also binär auf 0010 (entspricht der Anzahl 2). Der optimale Zug ist also:
Man entferne vom Haufen mit 13 Elementen 11 Elemente, so daß 2 Elemente übrig bleiben!
Nim mit zwei Haufen:
Eine Variante des Nim-Spiels ist das Spiel mit nur zwei Haufen, wobei entweder eine beliebige
Anzahl von einem beliebigen Haufen oder aber von beiden Haufen die gleiche Anzahl von
Elementen entfernt werden darf.
Gewinnstrategie:
Man sorge dafür, daß der Gegner eine der folgenden Stellungen vorfindet (Haufen1, Haufen2):
(1,2) (2,1) (3,5) (4,7) (5,3) (6,10) (7,4) (8,13) (9,15) (10,6) (11,18) (12,20) (13,8) (14,23) (15,9)
(16,26) (17,28) (18,11) (19,31) (20,12) (21,34) (22,36) (23,14) (24,39) (25,41) (26,16) (27,44)
(28,17) (29,47) ...
Das Kegelspiel:
Beim Kegelspiel stehen die Elemente eines Haufen jeweils nebeneinander in einer Reihe; die
Anzahl der Haufen und die Anzahl der Elemente in den Haufen sind beliebig. Ein Zug besteht
nun darin, entweder ein einzelnes Element oder zwei in der Reihe nebeneinander stehende
Elemente (sofern diese auch benachbart sind) aus einem Haufen zu entfernen. Wird aus der
Mitte eines Haufens ein oder zwei Elemente entfernt, so wird dabei der Haufen in zwei
kleinere Haufen aufgeteilt. Wer kein Element mehr entfernen kann, har verloren.
Gewinnstrategie:
Zuerst muß die Anzahl der Elemente jedes Haufens nach folgender Tabelle in einen “Rang”
umgewandelt werden:
Anzahl: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Rang: 1 2 3 1 4 3 2 1 4 2 6 4 1 2 7 1 4 3 2 1 4 6 7 4 1 2 8 5 4 7
Als Haufen gelten dabei jeweils in einer Reihe nebeneinander stehende Elemente. Die Rang-
Nummern müssen nun wie beim Nim mit mehreren Haufen so abgeändert werden, daß die
Anzahl der “1” in jeder Spalte wieder gerade ist. Entsprechend der neuen Rang-Nummer muß
jetzt auch die entsprechende Anzahl nach obiger Tabelle realisiert werden.
z.B.: 3 Haufen: (4, 5 und 2 Elemente)
Anzahl: oooo ooooo oo
Rang: 1 4 2
Binärdarstellung der Ränge:
1: 001
4: 100
2: 010
-> Der Rang 4 muß auf Rang 3 verändert werden!
-> Die Anzahl 5 muß auf 3 verändert werden
-> 2 Elemente am Rand des mitlleren Haufens müssen entfernt werden:
Verliererstellung: oooo ooo oo
Wenn neben einem und zwei Elementen auch drei Elemente nebeneinander entfernt werden
dürfen, gilt folgende Tabelle:
Anzahl: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Rang: 1 2 3 4 1 6 3 2 1 6 7 4 5 8 1 10 5 4 7 6 1 2 3 6 1 4 3 2 1 8
Das Teilerspiel:
Beim Teilerspiel gibt es wie beim Nim mit mehreren Haufen eine beliebige Anzahl von Haufen
mit jeweils einer beliebigen Anzahl von Elementen. Ein Spielzug besteht nun darin, einen
beliebigen Haufen in zwei ungleich große Teilhaufen aufzuteilen. Wer keinen Haufen mehr
aufteilen kann (alle Haufen haben entweder 1 oder 2 Elemente), hat verloren.
Gewinnstrategie:
Wie beim Kegelspiel müssen die Rang-Nummern der einzelnen Haufen nach folgender
Tabelle bestimmt werden:
Anzahl: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Rang: 0 0 1 0 2 1 0 2 1 0 2 1 3 2 1 3 2 4 3 0 4 3 0 4 3 0 4 1 2 3
Ansonsten gilt das gleich wie beim Kegelspiel.
z.B.: 3 Haufen: (4, 5 und 3 Elemente)
Anzahl: oooo ooooo ooo
Rang: 0 2 1
Binärdarstellung der Ränge:
0: 000
2: 010
1: 001
-> Der Rang 2 muß auf Rang 1 verändert werden!
-> Der Haufen mit 5 Elementen wird aufgeteilt in zwei Teilhauafen mit 3 und 2 Elementen
Verliererstellung: oooo ooo oo ooo
Das Wanderspiel:
Gegeben ist eine (beliebig lange) Reihe von Feldern. Auf diesen Feldern sind n Spielsteine
beliebig verteilt. Ein Spielzug besteht darin, einen beliebigen Spielstein um eine beliebige
Anzahl von Feldern nach rechts zu ziehen, wobei Sprünge über andere Spielsteine
a) nicht erlaubt;
b) erlaubt sind.
Gewinnstrategie:
Der Rang einer Spielstellung errechnet sich aus der Anzahl von freien Feldern zwischen den
Spielsteinen. Dabei werden die Anzahlen der freien Felder zwischen je zwei Spielsteinen im
Binärformat untereinander geschrieben. Ist die Anzahl der Spielsteine ungerade, so ist die
erste Zahl die Anzahl der freien Feldern zwischen dem am weitesten rechts liegenden Spiel-
stein und dem rechten Ende der Felderreihe. Verliererstellungen sind:
bei a): alle Stellungen, bei denen in allen Spalten eine gerade Anzahl von “1” sind (Rang=0);
bei b): alle Stellungen, die den Rang nach folgender Tabelle haben:
n 1 2 3 4 5 6 7 8 9 10 11 12 ...
Rang 1 3 0 4 1 7 0 8 1 11 0 12 ...
Der Rang einer Spielstellung ist die Binärzahl, die man hinzufügen muß, damit in jeder Spalte
die Anzahl der “1” gerade wird.
z.B.: n ist ungerade, keine Sprünge erlaubt:
. . . o . . . o . o . . . . o . . . . . . . o . . . . .
---3--- ----4---- -----5---
Binärdarstellungen:
3: 011
4: 100
5: 101
-> optimaler Zug: 3 muß auf 2 gesetzt werden
-> der Spielstein links außen wird um 1 Feld nach rechts verschoben!
z.B.: n ist gerade, Sprünge sind erlaubt:
. . . o . . . o . o . . . . o . . . . . . . o . . . . . o . . . .
---3--- ----4---- -----5----
Binärdarstellungen:
3: 011
4: 100
5: 101
Rang der Verliererstellungen = 7 = 111
-> optimaler Zug: 4 muß auf 1 gesetzt werden
-> der dritte Spielstein von links wird um 3 Felder nach rechts verschoben!
|
