|
Mathematik: Das NIM-Spiel | Freigegeben von matroid am Do. 28. Dezember 2006 12:53:10
Verfasst von ramonpeter - 4928 x gelesen [Gliederung] [Statistik]  Druckerfreundliche 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.
Inhalt
1)Nim-Spiel mit 5 Reihen
2)Spezielles Gewinnprinzip
3)Spielvariante
4)Allgemeines Gewinnprinzip
Das Nim-Spiel mit 5 Reihen
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.
Spezielles Gewinnprinzip
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.
Spielvariante
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 diese, die er erreichen kann ohne die Wände (das Schwarze um die Kreuze) zu durchstreichen. Diese Kreuze die man so, mit einem Strich, durchsreichen 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.
Allgemeines Gewinnprinzip
Um uns die Position überhaupt mathematisch zurechrdenken zu könne,
vereinfachen wir diese und schreiben die Reihen mit der Anzahl in ihnen
vorhandenen Münzen auf. Und Rechnen diese dann Zussamen um mit der
Gesamtzahl dann auch etwas zu machen.
Schauen wir uns doch zunächst die 1. Anfangsposition an sie gibt uns folgendes vor:
\fedon\mixon 1
+2
+3
+4
+5
---
\fedoff15
Jetzt schauen wir uns mal die Summen der Gewinnpositionen 3 und 5 an:
5.Position:
\fedon\mixon 2
+3
+4
+5
---
14
\fedoff
4.Position:
\fedon\mixon 1
+2
+3
---
6
\fedoff
Nun merkt man irgendwie dass die Gewinnposition gerade sind, aber dass kann es nicht sein. Wir vereinfachen das ganze und rechnen wie der Computer.
Starposition:
\fedon\mixon 1
10
11
100
101
---------
1111
\fedoff
Und zum Vergleich die einer Gewinnposition:
\fedon\mixon
10
11
100
101
---------
1110
\fedoff
Doch auch das bringt und nichtreccht weiter wir vereinfachne noch mehr und schauen uns die alle Gewinnposition mit der "Nim-Addition" Binärsystem ohne Übertrag.
Startposition:
\fedon\mixon 1
10
11
100
101
---------
1
\fedoff
1.Gewinnposition:
\fedon\mixon
10
10
---------
0
\fedoff
2.Gewinnposition:
\fedon\mixon
10
10
100
100
---------
0
\fedoff
3.Gewinnposition:
\fedon\mixon
1
10
11
---------
0
\fedoff
4.Gewinnposition:
\fedon\mixon
1
100
101
---------
0
\fedoff
5.Gewinnposition:
\fedon\mixon
10
11
100
101
---------
0
\fedoff
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:
\fedon\mixon
1
10
11
---------
0
\fedoff
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 Technick ist sehr von Vorteil bei der oben erwähnten Variante des Spiel, 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. Vorausetzung Spieler A ist immer der jenige, 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 verliern. Auf jeden Fall werden sich Ihre Freunde ärgern.
Viel Spaß damit.
|
Link auf diesen Artikel Druckerfreundliche Version  Weitersagen  Kommentare
 Für diesen Artikel gibt es keine pdf-Datei |
Kommentar schreiben
 Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
| : Spiele+Rätsel :: Spieltheorie :: Schüler aufwärts :
Das NIM-Spiel [von ramonpeter] | | 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
| |
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten] | | Verwandte Links |
Wie unterstütze ich den Matheplaneten mit Geld?
