NIM-Spiel

Was ist ein NIM Spiel? Muss man das kennen?

Gruß

Ok jetzt funktioniert das mit dem Link auch bei mir!

@Wegstaben Verbuchsler

Soll ich da vielleicht noch ne Antwort darauf geben.

Sorry, konnte mir aber bis vorhin nicht vorstellen was ein NIM-Spiel
ist, der Link funktionierte bei den ersten Versuchen irgendwie nicht.
Erst als ich ihn abtippte funktionierte er.

Aber halten wir diesen Thread wenigstens sauber, dass auch Leute
schreiben können, welche auf die Fragestellungen von Manuel auch
irgendeine sinnvolle Antwort geben können.

Nicht das noch ein paar Einfallspinsel auf die Idee kommen solche
sinnlosen Fragen zu stellen, wie du :-)

@Manuel:

Wie du anfangen solltest, kommt ganz drauf an, was der uC denn am
Schluss machen soll. Sollte er als Gegenspieler agieren, oder einfach
nur anzeigen, was die beiden Spieler machen?
Ersteres ist ja nicht wirklich sinnvoll, wenn man der Wikipedia glaubt,
da der uC in jedem Fall die richtige Spielvariante wählen wird, und
somit auf jeden Fall gewinnt, wenn der Spieler anfängt.

Hallo
man soll auswählen können zwischen Mensch gegen Mensch und Mensch gegen
µC.

Aber Anfangen will ich mal mit Mensch gegen Mensch

Dann fang doch damit an, wie das Userinteface aussehen soll. Z.B. würde
man ja eine Anzeige brauchen, die die verbleibenden Streichhölzer oder
Münzen oder was auch immer anzeigt ==> also ein paar 7-Segment-Displays
mit entpsrechenden Treibern dafür, je nach µC
Dann noch Taster zum Einstellen der Anzahl, zum Reset, zur Auswahl
Mensch/Maschine undundund. All dies wird die Wahl des Controllers
vermutlich beeinflussen oder bei wenn du dir schon einen ausgesucht
hast, die wahl der Zusatzhardware.
Dann fang doch erstmal damit an, die Anzeige und Tastenabfrage
(entprellen nicht vergessen) zu schreiben, dann die Mensch-zu-Mensch
Spielweise, wenn das läuft, die KI (bei diesem Spiel nicht so schwer,
im Prinzip nur eine Modulo-Operation zur Auswahl der zu nehmenden
Münzen).
Ach ja, toll wäre auch noch n Lautsprecher, aus dem dann "Du hast
gewonnen" oder "Der Computer hat gewonnen" und ähnliches ertönt.
Aber das hat noch Zeit ;-)

Hallo,
das ganze habe ich schon. Ich benütze einen Atmel 8515 oder Mega 16 die
haben wir hier rumliegen wie Sand am Meer. Anzeigen will ich die
Streichhölzer mit LED's die hab ich auch schon. Die Taster um
auszufwählen wieviel weg sollen hab ich auch schon mit einer Matrix
Tastatur gelöst. Also fehlt jetzt noch die realisierung der Software
:-D

>>Atmel 8515 oder Mega 16 die
haben wir hier rumliegen wie Sand am Meer.

...kann man an dem Strand auch Urlaub machen?! Träum....

Um eine Vorstellung zu bekommen um was es geht ...

http://www.volkard.de/vcppkold/nimmspiel.html

... und so gefällt es mir noch viel besser!

http://www.schwalfenberg.com/Spiele/Nimm/

... noch eine sehr gute Anregung.

http://www.nero.uni-bonn.de/course/nimmspiel/nimmspiel.html

Hallo,
ich habe meinen Schaltplan so konstruiert das ich die Auswahl der
led'S die weg sollen wie bei diesem Spiel auf der Seite hier gemacht
habe. (Auswahl mit Taster)

http://www.alraft.de/altenhein/nim.htm

Hab als Anhang mal meinen Schaltplan.

Schreibt einfach mal was ihr dazu so denkt.

Das Problem das ich habe ist, dass ich noch überhaupt nicht weis wie ich
das ganze mit der Software anfangen soll. Die Seite von Tester hilft mir
nicht da ich das Spiel anders gestallte. Weil ich es auf 4 Zeilen mach
und nicht alles in eine.

@Manuel

An Deiner Stelle würde ich mir vor dem Programmieren sehr genau
überlegen wie du vorgehst und was du willst. Bei solchen Speilen kannst
Du Dich nämlich sehr schnell überschätzen. Wir hatten das Problem bei
dem Kartenspiel MAU MAU in Prolog.

Hier ein paar Links zum Thema NIM Spiel in der KI.
http://www.o-bizz.de/qbtuts/ai-tuts/ki-inqb/ki-inqb.htm
http://www.freiequelle.de/ki/html/node11.html
http://ki.cs.tu-berlin.de/lehre/gkiws03/skript/spiele.pdf

Gruß
Christian

Hallo Manuel!

Jetzt wird es Zeit dass du dein Projekt genauer zu spezifizieren
beginnst. Du hast also 16 LEDS und ein 4 Zeiliges LCD. Welche Version
des Spiels willst du nun realisieren? Schreib die Regeln genau
zusammen. Was willst du wo Anzeigen? Eingabeaufforderungen und
Einstellungen am LCD, Streichhölzer als LEDs usw.
Wenn du diesen Ablauf genau beschreiben kannst können wir uns ans
Programmieren machen ...

Greets Gerhard

PS.: Irgendwie gefällt mir die Idee mit dem NIMM Spiel. Ich habe gerade
ein altes FORTH 80C167 Board ausgegraben, werd mal ein LCD und eine
Tastatur anschließen und mich an meine eigene Version des Spiels
ranmachen.
Die Links von Christian sind auch nicht schlecht, jedoch für eine
schnelle erste Version des Spiels werde ich keine künstliche
Intelligenz einbauen...

Hallo,
ich habe mir gedacht ich fange erstmal etwas kleiner an. Ohne Display.
Hab mir jetzt was geeaglet auf der nur die LED's Der Controller und
die Taster mehr nicht.

Das Spiel will ich genau so gestallten wie es auf der Seite gespielt
wird die ich gepostet hab.

http://www.alraft.de/altenhein/nim.htm

Also eine Art Pyramide. Gewonnen hat der der das letzte nimmt. Die
LED'S nimmt wann weg mit den Taster. WIe auf der seite eben

So hab mir mal mein erstes Konzept gemacht wie ich mir das so gedacht
hab.

Nach dem Prinzip der Eklärung auf Wikipedia (Ungerade/Gerade)

Beispiel:
Folgende Situation in der zweiten Reihe hat Spieler 1 zwei Hölzer
weggenommen.

   O
   O
 OOOOO
0OOOOOO

Im Binären würde es so aussehn:

0001   für 1 Holz
0001   für 1 Holz
0101   für 5 Hölzer
0111   für 7 Hölzer

Wenn ich nun für jede Spalte eine Variable erstelle, in die der
Binärwert eingetragen wird.

Anhand vom Beispiel:

-In der 4. Spalte sind alles einser. Das wär dann die Zahl 4. Das
 heißt eine gerade Zahl also entspringt es einer 0. Wenn man die vier
 einser Binär in Hex wandelt wäre es die 15.

-In der 3. Spalte sind es drei Nullen und eine 1, zusammengerechnet
 also eine 1 das heißt eine ungerade Zahl. Binär 1 und Hex auch 1.

usw.

Sooooo

Somit könnte ich einmal die vier Variablen anlegen für die Spalten und
einem 15 Variablen für die 15 möglichkeiten die es gibt.

Wenn ich die dann vergleiche und jeweils dann die ungerade oder gerade
Zahl rausbekomme wäre es ja gut.

Nur wie soll ich dann weiter machen?????

Das er die ungerade dann wegbekommt damit der gegner wieder eine gerade
bekommt.

Ich hoff ihr versteht ungefähr was ich meine.

Jetzt bin ich verwirrt ;-)

Also das mit G und U ist doch die Gewinnstrategie oder habe ich das
falsch verstanden? Oder soll

Ich würde an Deiner Stelle direkt mit Binärwerten arbeiten. Das Bit ist
gesetzt wenn das Streichholz vorhanden ist. Es ist nur die Frage was
macht mehr Sinn die Werte Zeilenweise oder Spaltenweise anzuordnen.

Wie machst du das mit den Reihen hats du für jede Reihe eine Taste mit
der du vorgibst in Welcher Reihe du ein/zwei/drei weg nimmst, oder hast
du 10 Tasten die du entsprechend angeordnet hast? Ich werde aus deinem
Schaltplan irgendwie nicht schlau.

Gerade und ungerade bekommst du in Binär ganz einfach raus ;-) wenn das
2^0 => 1 Bit (LSB) gesetzt ist dann ist die Zahl ungerade z.B 3 oder 5
usw.

Gruß
Christian

---
http://chris.cybertux.org

Das mit dem G und U hast du richtig verstanden, dass ist die
Gewinnstrategie.

Ich habe für jede Reihe auser der ersten, 3 Tasten zum auswählen für
3,2,1 hölzer.



Spaltenweise macht es sind. Da ich ja schauen muss ob die Spalte
ungerade oder gerade ist. Aber Achtung nicht der Binärwert muss gerade
sein. Man muss die einsen in der Spalten zählen, habe ich nun 3 einsen
in einer spalte ist sie ungerade aber habe ich 2 einsen ist es gerade.

Hallo Manuel!

Im Anhang findest du ein EXCEL File.
Darin findest du den Aufbau des Spiels (Eingabe im blauen Binärfeld um
alle G und U Kombinationen zu finden) sowie im Zweiten Blatt alle 50
möglichen G Kombinationen.
Daraus eine C Funktion zu schreiben ist nicht mehr so schwer...

Gruß Gerhard

Und wie bekomme ich dann aus einer U Situation die richtige G Situation.
Ich kann ja nicht irgendein Holz wegnehmen ich muss ja genau dieses
wegnehmen das aus der U Situation wieder eine G Situation wird.

Im Anhang habe ich mal kurz angefangen die Auswertung zu programmieren,
der Rest folgt (wenn du es noch benötigst) demnächst ...

Ohhhh. im Excel File ist mir ein kleiner Fehler unterlaufen: Es sind
nicht 50 G Möglichkeiten sondern nur 44, die letzte Reihe kannst du
löschen, ist doppelt mit Reihe 2 -> hat sich doch keiner genauer
angeschaut ;-)
Ach ja, kleiner Tipp: Du kannst entweder den nächsten G Spielzug immer
nach gleichem Schema fix berechnen lassen (fade Lösung weil dein
Programm dann auf einen Spielzug immer gleich reagiert)oder eben um es
für den menschlichen Gegenspieler schwieriger zu machen die G Situation
durch unterschiedliche Spielzüge erreichen.

Danke an Christian Ege für die 2^0 = 1 ergibt ungerade Zahl; das muß man
natürlich gleich anwenden!!!

Hallo,
vielen Danke für den Code doch leider kenn ich mich in C noch nicht aus
ich habe meine letzte Projekte alle mit Bascom gemacht.

Aber ich schau mir den Code mal in Ruhe an und versuch ihn zu
verstehen.

Info: Du brauchst dir nur die Funktion check_GU() ansehen und den Aufruf
dazu im main(). Das ist der Teil mit der G und U -Situations
Überprüfung. Das kannst du sicher mit BASCOM nachbilden.

Also ich würde es so machen, daß du Deine Variable mit
1  (00001)
2  (00010)
4  (00100)
8  (01000)
16 (10000)
verundest und dann überprüfst ob 1 2 4 8 16 rauskommt falls ja erhöst
du eine zählvariable die du am Schluß auf gerade/ungerade überprüfst.
Oder Du schiebst deine Bits durch die Gegend ich denke da hat jeder
seine Vorlieben. ;-)

cu
chege

Hallo,
melde mich mal wieder :-)

Hab nun mal angefangen mein Prog zu schrieben. Und hab dann gleich
wieder ein Problem.
Ich habe es schon hinbekommen das der µC aus einer U eine G Situation
macht. Das Problem das ich gerade habe ist wie mach ich aus einer G
Situation eine U möglichst zufällig. Ich bekomm das ums verecken net
hin.

Ich hab das mal mit einer Randomzahl von 1-4 also für die Reihe dann
anzulegen versucht. Aber wie sag ich ihm dann wieviel er jeweils
wegnehmen soll möglichst auch wieder zufällig. Und das er beachtet  das
er nicht mehr wegnimmt wie da sind

Stell mal in den Anhang rein was du schon schönes gemacht hast !

Also ich hab bis jetzt nur die Unterprogramme. Die Taster habe ich noch
nicht Prog Die Auswertung habe ich so gemacht programmiert. ich es auf
der Homepage gesehen hab mit der NIM Summation.

http://www.fh-karlsruhe.de/servlet/PB/show/1015913/goem-mathe04-krzensk.pdf

Also erst davor auf die Seite gehn und sich das anschauen mit der
Summation und so.



Im Anhang ist der Code.

Ich bin für Tips Verbesserungsvorschläge dankbar. Da ich noch nicht so
der Profi programmierer bin

Ganz cool wäre es auch wenn einer Zeit hätte mal Abends mit mir an dem
Prog zu arbeiten. Über VoIP z.b. oder icq

Hallo Manuel!

leider bin ich in den letzten 2 Wochen nicht zum Programmieren
gekommen. Ich habe aber eine interessante Entdeckung gemacht. Die
Berechnung der G/U Situation scheint bei der Einschränkung, dass du nur
max 3 Hölzchen wegnehmen lässt, nicht immer zu funktionieren...!
Überprüfe mal den Fall das du im ersten Zug in der dritten Reihe 2 oder
3 Hölzchen wegnimmst (schau dir dazu mal das neue EXCEL File im Anhang
an).

Greetz

Nun ja, das problem liegt hier begraben:

nehmen wir mal folgende z.B. Endsituation an:
R1=0 R2=0 R3=1 R4=4
laut Berechnung  (XOR) muss ich auf folgende Situation ziehen:
R1=0 R2=0 R3=1 R4=1
Ich würde aber auch gewinnen wenn:
R1=0 R2=0 R3=0 R4=4
... da ja der Computer nur noch auf R4 1 oder 2 oder 3 Hölzchen ziehen
kann.
So wie es aussieht brauchen wir eine bessere Auswertungsfunktion!!

Dann muss er eben wenn er zwei möglichkeiten hat eine zufällig auswählen

Ja schon, aber die verwendete Auswertungsfunktion funktioniert dafür
nicht! Etwas mehr Überlegung dazu ist gefragt!!!

Bsp.:
Start:    1 3 5 7
8051:     1 3 3 7  -> CPU nimmt in Reihe 3 2 Hölzchen
Spieler:  um auf G zu kommen muß er in Reihe 4 6 Hölzchen nehmen,
-> 1 3 3 1; geht nicht weil er ja nur max. 3 nehmen darf. Die XOR
Auswertung funktioniert somit nicht !!

Ich habe dem Verfasser deiner Auswertung mit XOR Logik folgendes eMail
geschrieben:

Sehr geehrte Herr Prof. Dr. Krzensk!

Über ein Internet Forum (www.mikrocontroller.net) zur Programmierung
von Mikrocontrollern bin ich zu ihrer Anleitung zur
programmiertechnischen Anleitung des "Nim" Spiels gekommen.

Ich habe ihr System in Excel (siehe Anhang) und 8051-C Code soweit
umgesetzt.

Leider funktioniert diese Auswertung nur wenn man beliebig viele
Hölzchen aus jeder Reihe entfernen darf.

Meine Anfrage bezieht sich auf eine Auswertungsfunktion wenn folgende
Abgrenzungen gelten:

Startsituation:
Reihe 1: 1 Hölzchen
Reihe 2:  3 Hölzchen
Reihe 3: 5 Hölzchen
Reihe 4: 7 Hölzchen

Die Software macht den ersten Zug.
Die Spieler dürfen abwechselnd pro Zug aus 1ner beliebigen Reihe
(Anzahl Hölzchen in gewählter Reihe > 0) mindestens 1 und maximal 3
Hölzchen entfernen.

Sieger ist wer das letzte Hölzchen entfernt.

Für diese Voraussetzung (maximal 3 Hölzchen entfernen) funktioniert die
angegebene XOR Summations Methode leider nicht immer.

Z.B.
Start: 1 3 5 7
8051 zieht: -2 Hölzchen aus Reihe 3 -> 1 3 3 7
Die nächste mögliche Gewinn Ausgangssituation laut XOR Berrechnung wäre
nun: 1 3 3 1 (d.h. ich müßte aus Reihe 4 sechs Hölzchen entfernen, nicht
möglich da max.=3).

Da ich im Internet keine weiterführenden Informationen zu diesem Thema
finden konnte würde es mich sehr freuen wenn Sie mir mit ein paar Tips
zur Lösungsfindung geben könnten!

Mit freundlichen Grüßen

Und hier die Antwort:

Sehr geehrter Herr xxxx,

nach der Originalfassung des NIM Spiels müssen die Spieler von einem
Haufen mindestens ein Hölzchen entfernen. Die Anzahl der zu
entfernenden Hölzchen ist jedoch nicht nach oben beschränkt. In diesem
Fall kann gezeigt werden, dass folgendes gilt:

"Für jede Position mit einer positiven Nim-Summe existiert mindestens
ein Zug, bei dem eine Position mit der Nim-Summe 0 erreicht wird"

Die funktioniert jedoch nur, wenn die Anzahl der zu entfernenden
Hölzchen nicht nach oben beschränkt ist!

Wenn Sie jetzt eine zusätzliche Regel einführen, wonach die Anzahl der
zu entfernenden Hölzchen nach oben beschränkt ist (hier durch 3), gilt
obige Aussage nicht mehr. Hierfür haben Sie ja auch ein Beispiel
gefunden.

Ob es zu diesem Problem eine ähnliche Lösung gibt und wie diese
aussehen könnte, weiß ich nicht. Leider kann ich Ihnen ohne länger
nachzudenken hierzu auch keine Tips geben. Eines ist sicher: Da es sich
hierbei um ein Spiel mit vollständiger Information handelt, gibt es für
beide Spiele optimale Strategieen. Wie diese jedoch Aussehen, weiß ich
nicht. Es wird vermutlich komplizierter. Falls Sie wissen möchten, wie
man solche Strategieen finden kann, empfehle ich Ihnen das Buch
"Spieltheorie" von Rauhut, Schmitz und Zachow erschienen im Teubner
Verlag.

Mit freundlichen Grüßen,

Nun ja, um endlich eine erste Version des Spiels fertig stellen zu
können werden die Regeln eben aufgeweicht! d.h. zuerst die Reihe
eingeben, dann die zu entfernenden Hölzchen ohne max=3 Beschränkung.

Hallo,
Danke das du dir soviel Mühe machst und du auch so interesiert bist an
diesem Spiel.
Ohne dich hätt ich das garnicht rausbekommen mit dem XOR. Das mit der
Beschränkung ist eine gute Idee. Ich werde mal versuchen das Umzusetzen

Wie siehts aus, geht hier irgendetwas weiter?? 7 Tage vergangen ohne
neue Outputs?

Hi,
bin gerade fertig geworden mit meiner Platine jetzt werf ich das Prog
mal drauf und werd mal schaun ob sich was tut. Leider habe ich es noch
nicht versucht das Problem mit der Summation zu lösen. Ich denk mal das
das noch ein bischen zu hoch für mich ist und ich da länger für brauch

Eine rudimentäre Implementation in Python (getestet mit 2.6.1) ist im
Anhang. Eine Überprüfung der Benutzereingaben fehlt, ebenso Mausunter-
stützung, 3-D-Grafik, Sound und Netzwerkfähigkeit ;-)