Python Nim Strategie |
25.06.2016, 18:37 | Auf diesen Beitrag antworten » | |||||||
Dr.Java | Python Nim Strategie Moin. Hab wieder eine kompliziertere Aufgabenstellung zu lösen. Und zwar geht es um das Nimspiel . Nehmen wir jetzt an das wir zum Beispiel 24 Streichhölzer auf dem Tisch hätten und zwei Spieler dürfen nur 1,2 oder 3 Hölzer nehmen. Nun soll ein Programm entwickelt werden das je nachdem wie viele Hölzer noch auf dem Tisch liegen eine optimale Zahl an Hölzern nimmt,sodass das Programm am Ende gewinnt. Sollte das Spiel nicht mehr gewonnen werden können so sollte das Programm False herausgeben. Als Hinweis ist dann noch gegeben das man eher auf Rekursion als auf die gewöhnlichen Lösungswege zugreifen soll. Außerdem war folgende funktionstüchtige Pythondatei anbei. Diese dient aber nur dazu das Spiel zu spielen.
Bei Rekursion bin ich dann auf eine Nimstrategie basierend auf Fibonaccizahlen gestoßen und dachte dann das man dann womöglich eine Strategie basierend auf der Fibonacci Funktion entwickeln könnte. Aber da bin ich bisher auch noch nicht sehr weit gekommen . Meine Frage wäre dann kann man das mit der Fibonacci Funktion machen ,gibt es bessere andere Möglichkeiten? Ist leider etwas länger geworden ,wäre trotzdem dankbar für jegliche Hilfe lg |
|||||||
|
||||||||
25.06.2016, 19:18 | Auf diesen Beitrag antworten » | |||||||
eulerscheZahl | Eigentlich ist das mathematisch sehr einfach zu lösen. Aber da du es mit Rechenleistung machen sollst: Wenn noch du am Zug bist und noch 1,2 oder 3 Hölzchen übrig sind, ist das offensichtlich eine Gewinnposition für dich. 4 ist deshalb eine Verlustposition: egal was du machst, es ergibt sich eine Gewinnposition für den Gegner. Bei 5 Hölzchen kannst du 1 nehmen, was für den Gegner eine Verlustposition - für dich also eine Gewinnposition bedeutet. Und das dann eben allgemein mit CHOICES, statt 1,2,3. Habe es mal eingetippt, bei mir hat die Funktion def nim_strategy(s) mit Kopf und Zeilenumbruch nach jedem Doppelpunkt 7 Zeilen. Also nicht zu kompliziert denken. |
|||||||
26.06.2016, 20:26 | Auf diesen Beitrag antworten » | |||||||
Dr.Java | Danke erstmal für die schnelle Antwort. Was du sagst klingt auf jeden Fall einleuchtend,ich weiß aber nicht ob ich das alles direkt ins Programm übertragen kann.
So in etwa? Ich überlege auch noch was als allgemeine Formel/Funktion geeignet wäre. lg |
|||||||
26.06.2016, 20:33 | Auf diesen Beitrag antworten » | |||||||
eulerscheZahl | Nein, viel zu statisch. Wenn s Hölzchen gezogen werden dürfen, gewinnt man, wenn man alle nimmt. Ansonsten gehen wir alle Möglichkeiten durch: liefert die Funktion für ein i in CHOICES False, ist das gut: das heißt ja, dass der Gegner verliert, wenn wir i Hölzchen nehmen. Ansonsten bleibt uns nur, selbst Falst zu liefern. |
|||||||
Anzeige | ||||||||
|
||||||||
28.06.2016, 12:11 | Auf diesen Beitrag antworten » | |||||||
Dr.Java | Ich dachte s steht für die Zahl der übrigen Hölzer.Und ich glaube langsam zu verstehen was du meinst,kann es aber noch nicht ganz konkret in Worte fassen.
Das wäre dann mein nächster Versuch.Das Problem ist das ich nicht drauf komme was für einen Wert man choice zuordnen sollte,ich meine choices=i reicht ja nicht. lg |
|||||||
28.06.2016, 15:00 | Auf diesen Beitrag antworten » | |||||||
eulerscheZahl | Aber s ist die Zahl der übrigen Hölzer.
|
|||||||
30.06.2016, 11:08 | Auf diesen Beitrag antworten » | |||||||
Dr.Java |
Oh. Ah das ist das Programm,danke, aber schade das ich wieder nicht selbst drauf kommen konnte. Ich befürchte aber dein Programm noch nicht ganz verstanden zu haben.
Wie kommst du darauf,das ist Rekursion oder, und wie funktioniert die hier genau?Wenn i also Teil von Choices ist und das s dann größer i ist und nicht nim_strategy(s-i) gilt soll er i herausgeben und in allen anderen Fällen False ? Danke nochmal. lg |
|||||||
30.06.2016, 20:12 | Auf diesen Beitrag antworten » | |||||||
eulerscheZahl | s > i prüft einfach, dass nach dem aktuellen Zug noch Hölzer übrig sein müssen. Sonst ist die Abbruchbedingung im Hauptprogramm erfüllt. Wenn nim_strategy(s) False zurückgibt, dann ist es bei s verbleibenden Hölzern nicht möglich, einen Sieg zu erzwingen. nim_strategy(s-i) prüft, ob man eine solche Situation erreichen kann: wenn der Gegner keinen Sieg erzwingen kann, ist das ja gut für uns. return False heißt, dass wir keinen Zug finden, der den Gegner in Bedrängnis bringt. Also wissen wir selbst nicht, was wir tun sollen. |
|||||||
02.07.2016, 09:13 | Auf diesen Beitrag antworten » | |||||||
Dr.Java |
Ah ,klar das ergibt Sinn.
Das rechnet also ob der Gegner von den übrigen Hölzern so viele nehmen kann ,so dass er nur gewinnt?
False kommt also nur wenn der Computer und man selber keine optimale Strategie mehr finden kann? lg |
|||||||
02.07.2016, 09:22 | Auf diesen Beitrag antworten » | |||||||
eulerscheZahl | not nim_strategy(s-i): Wenn wir am Zug sind und i Hölzer nehmen: wenn der Gegner dann nicht mehr gewinnen kann (das wird rekursiv berechnet), dann machen wir das natürlich auch.
Für einen der beteiligten gibt es immer eine optimale Strategie. Ich habe das so erklärt, dass du am Zug bist, wenn noch s Hölzer übrig sind. Beim rekursiven Aufruf ist dann logischerweise der Gegner am Zug. Also: wenn wir am Zug sind und keinen Zug finden, bei dem wir sicher gewinnen, geben wir False zurück. |
|||||||
02.07.2016, 09:54 | Auf diesen Beitrag antworten » | |||||||
Dr.Java |
Klingt einleuchtend.
Und das ist dann das False im Programm,nehme ich an. So oder so, danke nochmals, für deine Ausdauer und Unterstützung. lg |
|||||||
02.07.2016, 10:04 | Auf diesen Beitrag antworten » | |||||||
eulerscheZahl | Das False ist das in Zeile 20 in meinem Code vom 28.06.2016 15:00. Ob das Ergebnis False (bzw. 0) ist, wird auch in Zeile 34 überprüft. |
|||||||
02.07.2016, 20:12 | Auf diesen Beitrag antworten » | |||||||
Dr.Java |
Ja,genau das meinte ich. lg |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|