Hallo, ich würde gerne ein NIM Spiel mit einerm Mikrocontroller und Bascom realisieren. Weis aber noch net wie anfangen zu programmieren. Hier ne Seite wo das Spiel bischen erklärt wird. http://de.wikipedia.org/wiki/Nim-Spiel
@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.
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....
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
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!!
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
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
Hallo Leute Hat jemand eine Ahnung, wie man das Nim-Spiel in Python oder JAVA programmieren kann? ich nehem an, de eine oder andere hat es schon mal programmiert! ich würde mich auf Vorschläge sehr freuen. viele grüsse Leo
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 ;-)
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.