\(\begingroup\) In diesem Artikel möchte ich mich mit dem Nim-Spiel beschäftigen. Es ist ein Spiel, das fast jeder kennt und vorallem in Kneipen sehr beliebt ist. Es heißt, es sei ein Spiel, bei dem man nur mit Glück gewinnen kann, ähnlich wie bei Tic Tac Toe, doch ist dies wirklich der Fall? Diese und ähnliche Fragen stellt man sich in der Spieltheorie. Dies wird ein Artikel über die Regeln des Spiel, dessen Variante und über dessen mathematischen Hintergrund.
Ich möchte mich zu beginn mit der einfachsten Variante beschäftigen. Das Nim-Spiel mit 5 Reihen abfallend bis zu 1 Münze. Dies sieht dann in etwa so aus:
Dies ist unsere Startfigur vor beginn des Spiels, wenn ich also im Verlauf des Artikels, von der Startfigur spreche, dann meine ich obige Abbildung. Und wenn ich von Reihen spreche, dann mein ich eine Münzfolge von links nach rechts bzw. horizontal laufend.
Nun möchte ich kurz die Spielregeln erläutern.
Spieler A beginnt, die Partie, indem er aus einer Reihe, eine beliebige Anzahl an Münzen wegnimmt. So entsteht dann folgende Situation für Spieler B.
Dieser macht dann auch einen Zug, nach dem selbigen Prinzip. Wichtig ist, dass nur das Entnehmen von mehreren Münzen aus derselben Reihe möglich ist.
Das Spiel endet, wenn alle Münzen entfernt worden sind. Sieger ist, wer die letzte(n)
Münze(n) aufnimmt.
Nun stellt sich die Frage, sind die Gewinnchancen gleich verteilt, oder hat man einen Vorteil wenn man anfängt oder nicht?
Gibt es sogar ein richtiges Gewinnprinzip?
Diese Frage möchte ich im Folgenden klären.
Um auf die Erste der obigen Fragen, eine Antwort zu finden, beginnen wir doch erstmal damit, zu zeigen, dass es ein Gewinnrezept gibt.
1.Situation
Wir beginnen beim vorletzten Zug. Vorausgesetzt beide Spieler haben bis dahin bestmöglich gespielt.
Wenn Spieler A, Spieler B in obige Situation bringt, dann hat Spieler A gewonnen.
Dies ist sofort zu sehen, denn egal welchen Zug Spieler B macht, es wird 1 Münze übrig bleiben, die dann Spieler A, glücklich über den Sieg, aufnimmt. Spieler B kann nicht beide Münzen gleichzeitig aufnehmen da sie sich in unterschiedlichen Reihen befinden.
Spieler A hat auch gewonnen, wenn statt jeweils 1 Münze, 2 oder mehr Münzen in den beiden Reihen liegen. Sobald Spieler B von einer Reihe eine bestimmte anzahl wegnimmt, dann nimmt Spieler A einfach von der andern Reihe die gleiche Anzahl weg, irgendwann wird er bei der obigen Situation landen.
2.Situation
Jetzt schauen wir uns als Beispiel folgende Situation an, vor die Spieler B steht.
Eigentlich hat sich von oben nicht viel verändert nur statt 2 Reihen, haben wir jetzt 4 Reihen, wobei 2 sich in ihrer Anzahl entsprechen. Wer diese Situation vor sich liegen hat, hat schon verloren. Egal was Spieler B nun wegnimmt, Spieler A nimmt die gleiche Anzahl, an der zuvor entsprechend großen Reihe weg. So wird Spieler B, wenn er es herauszögert und immer nur 1 wegnimmt, spätestens nach 5 Zügen vor Situation 1. stehen. Wie wir oben schon gezeigt haben, kann Spieler dann nur verlieren, also ist bei dieser Position die Niederlage auch schon besiegelt.
3.Situation
Jetzt haben wir bisher für gleichgroße Reihenblöcke gezeigt, dass Spieler B verliert, jetzt schauen wir uns mal eine andere Stellung an.
Diese Liegen in einer 1;2;3 Stellung da. Nun denkt man da kann man bestimmt als Spieler B noch was machen?! Nein kann man nicht. Denn wenn man jetzt die möglichen Züge von Spieler B durchgeht, stellt man fest, dass Spieler A ihn in seinem folgenden Zug immer auf Situation 1 bringen kann. Wenn Spieler B also vor dieser Position steht, ist es ihm auch nicht mehr möglich das Spiel zu seinen Gunsten zu wenden, d,h er verliert.
4.Situation
Jetzt betrachten wir eine ähnliche Position nur mit mehr Münzen.
Diesmal liegen sie in 1;4;5 Stellung. Gibt es diesmal wieder keinen Ausweg für Spieler B? Das schauen wir uns jetzt mal genauer an und überprüfen 2.Möglichkeiten.
1. Möglichkeit
Spieler B entfern die Weiße Münze. Man sieht sofort wie Spieler A reagieren muss, er nimmt den 5. Stein in der 5er Reihe weg. Es entsteht Situation 1. Gleicherweise könnte Spieler B in der letzten Reihe 1 Münze entnehmen, dann nimmt Spieler B die einzelne Weiß markiert. Oder aber Spieler B nimmt aus einer der größeren Reihen, alle , oder alle bis auf einen, auch diesmal kann Spieler A leicht Situation 1. herstellen. Bei diesen Zügen Hat spieler B also verloren.
2.Möglichkeit
Spieler B macht einen der Züge, die oben nicht mitinbegriffen sind. Und zwar entfernt er beispielsweise die zwei weißen Münzen. Spieler A musss nun aber nichts weiter tun, als aus der 5er Reihe 2 Münzen zu entfernen und es entsteht die 1;2;3 Position. Also hat Spieler B verloren. Was auch immer Spieler B aber an den verbleibend möglichen Zügen macht, Spieler A wird ihn immer auf die 3.Situation bringen.
Das heißt also, auch die 4.Situation ist eine Gewinnposition für Spieler A.
5.Situation
Nun eine noch frühere Stellung.
Mit dieser brauch ich mich wohl nicht länger beschäftigen, da man nach Stellung 4 auch hier wieder in zwei Richtungen gehen kann, egal was Spieler B macht, Spieler A wird ihn entweder auf Situation 2, oder 4 bringen.
Das heißt also auch dieses hier ist eine Gewinnposition.
Dies wiederrum ist sehr erstaunlich, denn das bedeutet, Spieler A, wenn er die Partie beginnt, gewinnt. Er kann in seinem ersten Zug Spieler B schon auf die letzte Gewinnpositon bringen. Spieler B hat von Anfang an verloren.
Damit haben wir auch die Frage geklärt ob die Gewinnchancem gleichverteilt sind.
Um dieses Spiel zu gewinnen merken Sie sich bloß obige Gewinnpositionen und versuchen sie stehts die Partie zu beginnen. Viel Erfolg auf dem nächsten Geburtstag oder der nächsten Hochzeit. Wenn ihnen das genügt an Information, dann können Sie es hierbei belassen. Wenn Sie sich jedoch, für ein Spielvariante interessieren, oder sie den mathematischen Grund wissen wollen, was diese Gewinnpositionen alle gemeinsam haben, dann lesen Sie doch weiter.
Nun möchte ich einmal eine Variante des Nim-Spiels vorstellen, bei der man ohne mathematische Kenntniss des Spiels nicht so einfach immer gewinnt. Da das Spielfeld ständig variiert. Gespielt wird auf einem Blatt Papier. Das Spielfeld wird drauf gemalt.
Die Kreuze stellen die Münzen da. Jeder Spieler darf Kreuze wegstreichen in seiner Farbe, aber nur die, die er erreichen kann, ohne die Wände (das Schwarze um die Kreuze) durchzustreichen. Diese Kreuze, die man so mit einem Strich, durchstreichen kann, bilden sozusagen unsere Reihen.
Nun schauen wir uns ein ganzes Spiel in dieser Variante an.
Spieler A macht den ersten Zug
Spieler B macht seinen ersten Zug.
Nun kann man erkennen, wenn man sich die "Reihen" nebeneinander denkt, dass Spieler A, den Spieler B in die 2. Gewinnposition gebracht hat. Spieler B wird also verlieren.Schauen wir uns den weiteren Spielverlauf an.
Spieler B hat es nurn auch gemerkt und macht einfach einen Zug, hoffend, auf einen Fehler von Spieler A
Dieser Lässt sich nicht beirren und liegt weiter auf Siegeskurs.
Spieler A gewinnt die Partie.
In der nächsten Parite, malt Spieler B ein Spielfeld hin und darf beginnen. Es entsteht somit jedes mal eine neue Anfangssituation.
Spieler A hatte dieses mal entweder einfach nur Glück, oder er ist sich des mathematischen Systems bewusst.
Es muss doch einen Zusammenhang geben zwischen den Gewinnpositionen, und den Anfangsvorteilen.
Falls Sie dass nächste Kapitel verstanden haben, werden sie auch diese scheinbar fairerer Variante immer gewinnen.
Um uns die Position überhaupt mathematisch denken zu können,
vereinfachen wir diese und schreiben die Reihen mit der Anzahl der in ihnen
vorhandenen Münzen auf. Und Rechnen diese dann zusammen, um mit der
Gesamtzahl dann auch etwas zu machen.
Schauen wir uns doch zunächst die 1. Anfangsposition an, sie gibt uns Folgendes vor:
1
+2
+3
+4
+5
---
15
Jetzt schauen wir uns mal die Summen der Gewinnpositionen 3 und 5 an:
5.Position:
2
+3
+4
+5
---
14
4.Position:
1
+2
+3
---
6
Nun merkt man irgendwie, dass die Gewinnposition gerade sind, aber das kann es nicht sein. Wir vereinfachen das Ganze und rechnen wie der Computer.
Starposition:
1
10
11
100
101
---------
1111
Und zum Vergleich die einer Gewinnposition:
10
11
100
101
---------
1110
Doch auch das bringt uns nicht recht weiter. Wir vereinfachen noch mehr und schauen uns alle die Gewinnposition mit der "Nim-Addition" Binärsystem ohne Übertrag an.
Startposition:
1
10
11
100
101
---------
1
1.Gewinnposition:
10
10
---------
0
2.Gewinnposition:
10
10
100
100
---------
0
3.Gewinnposition:
1
10
11
---------
0
4.Gewinnposition:
1
100
101
---------
0
5.Gewinnposition:
10
11
100
101
---------
0
Nun stellen wir endlich durch mehrfaches Vereinfachen eine Gemeinsamkeit fest. Alle Gewinnpositionen haben die Nim-Summe 0.
Nun stellt sich die Frage, ist Spieler B wirklich nicht in der Lage aus einer Gewinnposition ebenfalls eine Gewinnposition zu machen?
Nein, schauen wir uns die 3. Gewinnposition dazu mal an:
1
10
11
---------
0
Denn egal was Spieler B wegnimmt, eine 1 in der Addition wird sich verschieben oder verschwinden, und somit fehlt irgendwo ne 1 um auf 0 zu kommen, oder es ist eine zu viel. Damit habe ich hoffensichtlich einleuchtend gezeigt, dass man durch Nachrechnen mit der "Nim-Addition" herausfinden kann, ob man eine Gewinnposition spielen kann oder nicht. Diese Technik ist sehr von Vorteil bei der oben erwähnten Variante des Spiels, da sich dort die Anfangsposition immer ändern und man umöglich alle auswendig können kann.
Jetzt können wir auch verallgemeinern, wann Spieler A oder Spieler B einen Vorteil hat. Wenn die Nim-Summe der Startposition ungleich 0 ist, so gewinnt Spieler A, wenn nicht dann Spieler B. Voraussetzung, Spieler A ist immer derjenige, der die Partie beginnt.
Und noch allgemeiner, um zu gewinnen:
Man muss den Gegner durch geschicktes wegnehmen(durchstreichen) der Münzen, auf die Nim-Summe 0 bekommen.
Hiermit möchte ich dann meinen Artikel abschließen. Vielleicht wird der ein oder andere von Ihnen demnächst das Spiel mit seinen Freunden spielen. Oder Sie wetten, dass sie kein Spiel verlieren. Auf jeden Fall werden sich Ihre Freunde ärgern.
Viel Spaß damit.
In diesem Artikel möchte ich mich mit dem Nim-Spiel beschäftigen. Es ist ein Spiel, das fast jeder kennt und vorallem in Kneipen sehr beliebt ist. Es heißt, es sei ein Spiel, bei dem man nur mit Glück gewinnen kann, ähnlich wie bei Tic Tac Toe, doch ist dies wirklich der Fall? Diese und ähnlich
\(\begingroup\)Hallo,
das schöne Spiel ist bei mir fast schon wieder in Vergessenheit geraten.
Edit:
Schon gut; sollte erstmal zuende lesen.
Schöner Artikel!
Jockel\(\endgroup\)
\(\begingroup\)Hallo,
leider ist das nicht als allgemeines Kriterium verwendbar. Es ist gewissermaßen nur Zufall, dass es mit der Binäraddition bei den wenigen Stellungen hinhaut. Es gibt einfache Gegenbeispiele:
3-4-4 ist eine Gewinnposition für den Anziehenden, OBWOHL die letzte Ziffer der Binärsumme 1 ist, sprich die Summe ungerade ist. (Der Anziehende streiche die erste zeile komplett und gewinnt)
Umgekehrt kann der Anziehende natürlich im Allgemeinen aus einer Summe=0 Stellung (vermeintlich eine Versluststellung für den Anziehenden) wieder eine Summe=0 Stellung machen (in dem er einfach eine gerade Anzahl von Steinen wegnimmt).
Gibt es ein allgemeines Prinzip um schlagartig sagen zu können, ob eine Stellung (immer aus der Sicht des Anziehenden) eine Gewinn- oder Verluststellung ist, für ein verallgemeinertes Spiel mit einer beliebigen Anzahl von Zeilen mit jeweils beliebig vielen Steinen?
Grüße
Anonymous\(\endgroup\)
von: ramonpeter am: So. 31. Dezember 2006 15:41:34
\(\begingroup\)3-4-4 ist keine gewinnposition in meinem Sinne bei mir ist ne Gewinnposition eine stellung bei dem der Ziehende nicht mehr gewinnen kann!!!
Und nein man kann bei dieser Art Addition aus einer Summe=0 nicht durch ziehen von geraden Anzahlen wieder auf ne Summe=0 kommen, die Addition wird wie gesagt ohne Übertrag gemacht!!
Denk nochmal drüber nach!!
Gruß ramon_peter\(\endgroup\)
\(\begingroup\)An alle, die Spaß an diesem Artikel haben:
John H. Conway, Über Zahlen und Spiele.
Manchmal ganz schön kosmisch, aber auch unterhaltsam. Sollte in jerder Uni-Bib auszuleihen sein.
Wally\(\endgroup\)
\(\begingroup\)@ramon: Ich muss mich entschuldigen, du hast Recht. Ich habe nicht aufmerksam genug gelesen, ich dachte dein Spiel würde die sehr komplexe Variante durchnehmen, die nur einen Regelunterschied zu deiner sehr einfachen Variante hat: Der, der den letzten Stein nehmen muss, hat verloren. Man könnte denken, dass man nur die Gewinnstrategie umdrehen muss, das ist aber nicht der Fall. Meines Wissens existiert zu dieser sehr komplexen Variante keine einfache allgemeingültige Gewinnstrategie (sollte ich mich irren, bitte Hinweis!). Entschuldige nochmals, ich dachte du hast diese Variante untersucht. Die Standard-Gewinnstrategie kann man überall nachlesen (sogar in Wikipedia).
@Wally: Danke für den Hinweis.
Gruß
Anonymous\(\endgroup\)
von: ramonpeter am: So. 31. Dezember 2006 19:14:39
\(\begingroup\)die andere Variante wird Misere-Spiel genannt. Sieht ähnlich aus aber funktioniert ganz anders. Dafür gibt es kein so leichtes Gewinnprinzip\(\endgroup\)
\(\begingroup\)Für diejenigen, die es interessiert.
Es handelt sich hierbei um ein spezielles Problem der Kombinatorischen Spieltheorie.
Die von ramonpeter angegebenen Gewinnpositionen kann man allgemein mit Hilfe der sogenannten Sprague-Grundy-Werte bzw. -Funktion berechnen.
Wer allgemein Spaß an solchen Spielen hat, der kann sich ja mal auf der Seite www.cut-the-knot.org/index.shtml umschauen.
Unter der Rubrik Combinatorial Games wird er dann fündig, aber auch die anderen Rubriken halten interessante Dinge für einen bereit.
Die jahrzehntelang gesuchte Lösung der allgemeinen Miseré-Variante ist erst vor ganz kurzer Zeit von Thane Plambeck gegeben worden.
Man findet sie hier:
www.integers-ejcnt.org/vol5.html
Taming the Wild in Impartial Combinatorial Games
Wir sind also ganz dicht am Puls der Zeit.
mire2\(\endgroup\)
\(\begingroup\)Hallo.
Ich habe in Delphi mal ein kleines Nimm-Spiel programmiert. Man kann es in meinem Notizbuch herunterladen oder über diesen Link:
dl.php?id=139\(\endgroup\)
\(\begingroup\)jetzt versteh ich endlich mal wie man auf komplexe mathematische ereignisse kommt
ich hoffe es macht dir nichts aus wenn ich dich in meiner facharbeit über das nim-spiel zitiere :)
\(\endgroup\)
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Mathematik: Das NIM-Spiel
Printer-friendly version
In diesem Artikel möchte ich mich mit dem Nim-Spiel beschäftigen. Es ist ein Spiel, das fast jeder kennt und vorallem in Kneipen sehr beliebt ist. Es heißt, es sei ein Spiel, bei dem man nur mit Glück gewinnen kann, ähnlich wie bei Tic Tac Toe, doch ist dies wirklich der Fall? Diese und ähnliche Fragen stellt man sich in der Spieltheorie. Dies wird ein Artikel über die Regeln des Spiel, dessen Variante und über dessen mathematischen Hintergrund.
Dieser macht dann auch einen Zug, nach dem selbigen Prinzip. Wichtig ist, dass nur das Entnehmen von mehreren Münzen aus derselben Reihe möglich ist.
Das Spiel endet, wenn alle Münzen entfernt worden sind. Sieger ist, wer die letzte(n)
Münze(n) aufnimmt.
Nun stellt sich die Frage, sind die Gewinnchancen gleich verteilt, oder hat man einen Vorteil wenn man anfängt oder nicht?
Gibt es sogar ein richtiges Gewinnprinzip?
Diese Frage möchte ich im Folgenden klären.
Wenn Spieler A, Spieler B in obige Situation bringt, dann hat Spieler A gewonnen.
Dies ist sofort zu sehen, denn egal welchen Zug Spieler B macht, es wird 1 Münze übrig bleiben, die dann Spieler A, glücklich über den Sieg, aufnimmt. Spieler B kann nicht beide Münzen gleichzeitig aufnehmen da sie sich in unterschiedlichen Reihen befinden.
Spieler A hat auch gewonnen, wenn statt jeweils 1 Münze, 2 oder mehr Münzen in den beiden Reihen liegen. Sobald Spieler B von einer Reihe eine bestimmte anzahl wegnimmt, dann nimmt Spieler A einfach von der andern Reihe die gleiche Anzahl weg, irgendwann wird er bei der obigen Situation landen.
Eigentlich hat sich von oben nicht viel verändert nur statt 2 Reihen, haben wir jetzt 4 Reihen, wobei 2 sich in ihrer Anzahl entsprechen. Wer diese Situation vor sich liegen hat, hat schon verloren. Egal was Spieler B nun wegnimmt, Spieler A nimmt die gleiche Anzahl, an der zuvor entsprechend großen Reihe weg. So wird Spieler B, wenn er es herauszögert und immer nur 1 wegnimmt, spätestens nach 5 Zügen vor Situation 1. stehen. Wie wir oben schon gezeigt haben, kann Spieler dann nur verlieren, also ist bei dieser Position die Niederlage auch schon besiegelt.
Diese Liegen in einer 1;2;3 Stellung da. Nun denkt man da kann man bestimmt als Spieler B noch was machen?! Nein kann man nicht. Denn wenn man jetzt die möglichen Züge von Spieler B durchgeht, stellt man fest, dass Spieler A ihn in seinem folgenden Zug immer auf Situation 1 bringen kann. Wenn Spieler B also vor dieser Position steht, ist es ihm auch nicht mehr möglich das Spiel zu seinen Gunsten zu wenden, d,h er verliert.
Diesmal liegen sie in 1;4;5 Stellung. Gibt es diesmal wieder keinen Ausweg für Spieler B? Das schauen wir uns jetzt mal genauer an und überprüfen 2.Möglichkeiten.
1. Möglichkeit
Spieler B entfern die Weiße Münze. Man sieht sofort wie Spieler A reagieren muss, er nimmt den 5. Stein in der 5er Reihe weg. Es entsteht Situation 1. Gleicherweise könnte Spieler B in der letzten Reihe 1 Münze entnehmen, dann nimmt Spieler B die einzelne Weiß markiert. Oder aber Spieler B nimmt aus einer der größeren Reihen, alle , oder alle bis auf einen, auch diesmal kann Spieler A leicht Situation 1. herstellen. Bei diesen Zügen Hat spieler B also verloren.
2.Möglichkeit
Spieler B macht einen der Züge, die oben nicht mitinbegriffen sind. Und zwar entfernt er beispielsweise die zwei weißen Münzen. Spieler A musss nun aber nichts weiter tun, als aus der 5er Reihe 2 Münzen zu entfernen und es entsteht die 1;2;3 Position. Also hat Spieler B verloren. Was auch immer Spieler B aber an den verbleibend möglichen Zügen macht, Spieler A wird ihn immer auf die 3.Situation bringen.
Das heißt also, auch die 4.Situation ist eine Gewinnposition für Spieler A.
Mit dieser brauch ich mich wohl nicht länger beschäftigen, da man nach Stellung 4 auch hier wieder in zwei Richtungen gehen kann, egal was Spieler B macht, Spieler A wird ihn entweder auf Situation 2, oder 4 bringen.
Das heißt also auch dieses hier ist eine Gewinnposition.
Dies wiederrum ist sehr erstaunlich, denn das bedeutet, Spieler A, wenn er die Partie beginnt, gewinnt. Er kann in seinem ersten Zug Spieler B schon auf die letzte Gewinnpositon bringen. Spieler B hat von Anfang an verloren.
Damit haben wir auch die Frage geklärt ob die Gewinnchancem gleichverteilt sind.
Um dieses Spiel zu gewinnen merken Sie sich bloß obige Gewinnpositionen und versuchen sie stehts die Partie zu beginnen. Viel Erfolg auf dem nächsten Geburtstag oder der nächsten Hochzeit. Wenn ihnen das genügt an Information, dann können Sie es hierbei belassen. Wenn Sie sich jedoch, für ein Spielvariante interessieren, oder sie den mathematischen Grund wissen wollen, was diese Gewinnpositionen alle gemeinsam haben, dann lesen Sie doch weiter.
Die Kreuze stellen die Münzen da. Jeder Spieler darf Kreuze wegstreichen in seiner Farbe, aber nur die, die er erreichen kann, ohne die Wände (das Schwarze um die Kreuze) durchzustreichen. Diese Kreuze, die man so mit einem Strich, durchstreichen kann, bilden sozusagen unsere Reihen.
Nun schauen wir uns ein ganzes Spiel in dieser Variante an.
Spieler A macht den ersten Zug
Spieler B macht seinen ersten Zug.
Nun kann man erkennen, wenn man sich die "Reihen" nebeneinander denkt, dass Spieler A, den Spieler B in die 2. Gewinnposition gebracht hat. Spieler B wird also verlieren.Schauen wir uns den weiteren Spielverlauf an.
Spieler B hat es nurn auch gemerkt und macht einfach einen Zug, hoffend, auf einen Fehler von Spieler A
Dieser Lässt sich nicht beirren und liegt weiter auf Siegeskurs.
Spieler A gewinnt die Partie.
In der nächsten Parite, malt Spieler B ein Spielfeld hin und darf beginnen. Es entsteht somit jedes mal eine neue Anfangssituation.
Spieler A hatte dieses mal entweder einfach nur Glück, oder er ist sich des mathematischen Systems bewusst.
Es muss doch einen Zusammenhang geben zwischen den Gewinnpositionen, und den Anfangsvorteilen.
Falls Sie dass nächste Kapitel verstanden haben, werden sie auch diese scheinbar fairerer Variante immer gewinnen.
Get link to this article
Comments
Für diesen Artikel gibt es keine pdf-Datei
Dieser Artikel ist im Verzeichnis der 
