Das Spiel Nim

Nim, ist ein mathematisches Spiel in dem zwei Spieler rundenweise Elemente aus einzelnen Stapeln entfernen. Bei der hier vorgestellten Software handelt es sich um eine Kommandozeilenversion des Spiels auf .Net Basis.

Das Spiel Nim und seine Varianten sind uralt und die Ursprünge des Spiels liegen wahrscheinlich in China. Seit dem 16 Jahrhundert ist es auch in Europa bekannt und bekam seinen Namen von Charles Leonard Bouton, der 1901 eine komplette Theorie des Spiels mit einer Gewinnstrategie veröffentlichte.

Nim ist eines der ersten Computerspiele und wurde schon 1940 von einer Maschine, Nimatron, in New York gespielt1. 1951 schlug der in England gebaute Rechner Nimrod den damaligen deutschen Wirtschaftsminister Ludwig Erhard.

Ablauf und Gewinnstrategie

Im Nim Spiel nehmen zwei Spieler abwechselnd eine Anzahl von Elementen aus einzelnen Stapeln. Dies können Streichhölzer in mehreren Reihen2 sein oder auch Lakritzstangen in mehreren Töpfen3. Derjenige Spieler, der das letzte Element nimmt, hat gewonnen.

Die Gewinnstrategie nach Bouton4 besteht darin, dass die Anzahl der Elemente je Stapel binär dargestellt wird und die Spaltensummen für jede Ziffer berechnet wird. Ein Spielstand, bei dem die Spaltensummen aller Ziffern gerade ist, ist eine Gewinnstellung. Bei einer oder mehrerer ungerader Summen handelt es sich um eine Verluststellung. Aus der Gewinnstellung eines Spielers wird im nächsten Zug automatisch eine Verluststellung für den Gegenspieler. Daher gewinnt immer der Spieler, der die Gewinnstellung als erster erreicht und bis zum Spielende beibehält. Ob eine Spaltensumme gerade oder ungerade ist, lässt sich am einfachsten über eine XOR-Operation der Elementanzahlen berechnen. Hier ein Beispiel:

Verluststellung:           Spielzug:        Gewinnstellung:
1: 00000010 = 2                             1: 00000001 = 1
2: 00000011 = 3  => Nim 1 von Stapel 1 =>   2: 00000011 = 3
3: 00000101 = 5                             3: 00000101 = 5
4: 00000111 = 7                             4: 00000111 = 7
--------                                    --------
XOR: 00000011 = 3                           XOR: 00000000 = 0

Außerdem können auch 3 Elemente vom Stapel 2 oder 4 genommen werden, um von der Verluststellung zu einer Gewinnstellung zu kommen. Da im nächsten Spielzug nur aus einem Stapel Elemente genommen werden dürfen, ergibt sich nach dem nächsten Spielzug eine Verluststellung.

Nim Software

Im Fall der C# Kommandozeilenversion des Nim Spieles werden die Stapel mit ihren Elementen in der Form von Zahlen als Parameter übergeben. So erstellt [nim.exe 1 3 5 7] ein Nim Spiel mit vier Stapeln. Standardmäßig ist der Benutzer der erste Spieler und beginnt das Spiel mit seinem Zug. Hierfür gibt der Spieler den Stapel und, durch einen Doppelpunkt getrennt, die Anzahl der Elemente an, die er nehmen möchte. Der Stapel wird durch seinen Index beginnend bei Eins identifiziert. So bedeutet die Eingabe „3:2“, dass der Benutzer zwei Elemente aus dem dritten Stapel nimmt. Danach führt der Computer seinen Spielzug aus und der Benutzer ist wieder am Zug. Dieser Prozess wiederholt sich, bis Benutzer oder Computer das letzte Element genommen haben:

C:\>Nim.exe 2 3 5 7
YOUR MOVE? ([Heap]:[Count]) 1:1
MY MOVE    ([Heap]:[Count]) 4:7
YOUR MOVE? ([Heap]:[Count]) 3:3
MY MOVE    ([Heap]:[Count]) 2:3
YOUR MOVE? ([Heap]:[Count]) 3:1
MY MOVE    ([Heap]:[Count]) 1:1
YOUR MOVE? ([Heap]:[Count]) 3:1
YOU WIN AFTER 00:00:06

Da das Spielfeld nicht angezeigt wird, muss der Benutzer Änderungen im Gedächtnis nachhalten. Um zu gewinnen, muss der Benutzer darüber hinaus die Binärzahl aller Elementanzahlen bestimmen und die XOR-Werte oder Spaltensummen der einzelnen Ziffern berechnen. Dadurch ist die Kommandozeilen-Version ein hervorragendes Gedächtnistraining.

Kommandozeilenschalter

Um dem Benutzer zu helfen, können über den Verbose-Schalter „-v“ immer mehr Informationen zum aktuellen Spielstand, den Binärzahlen und den XOR-Ergebnissen ausgegeben werden, je nachdem wie viele „v“s angegeben werden. Mit dem Schalter „-c“ erfolgt die Ausgabe farbig, so dass einfacher zwischen den einzelnen Informationen unterschieden werden kann.

Verschiedene Spielstrategien lassen sich mit den Schaltern „-l“ (benutze größte Elementanzahl),  „-s“ (verwende kleinste Elementanzahl), „-u M“ (nehme maximal „M“ Elemente“ und „-m“ (Misère game bei dem derjenige verliert, der das letzte Element nimmt) auswählen. Mit „-f“ wird angegeben, dass der Computer den ersten Zug ausführen darf.

Downloads

NIM.zipNim8,7 KBNIM 1.0.1 als Kommandozeilenprogramm

Weitere Informationen

1. Nim in Wikipedia (Englisch)

2. Online Nim Spiel

3. Denken wie ein Computer Das NIM-Spiel und der Trick mit den binären Zahlen, Peter Schmitz, Heise c’t 2017, Heft 17, Seite 132-136

4. Nim Spiel in Wikipedia

» Quellcode auf GitHub

» English version of this post