Python Nim Strategie |
Dr.Java
Foren As
Dabei seit: 21.03.2016
Beiträge: 99
|
|
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.
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
|
def subtraction_game(s):
'''Game loop.'''
while True:
s -= user_action(s)
if (s == 0):
print('Congratulations! You won!')
break
s -= computer_action(s)
if (s == 0):
print('You lost! Better luck next time!')
break
def user_action(s):
'''User's action selection (by console input).'''
print('%d matches are on the table. How many do you want to take?' % s)
amount = 0
while int(amount) not in CHOICES or int(amount) > s:
amount = input('> ')
return int(amount)
def computer_action(s):
'''Computer's action selection.'''
amount = nim_strategy(s)
if not amount:
from random import choice
amount = choice(tuple(filter(lambda x: x <= s, CHOICES)))
print('Computer takes %d matches.' % amount)
return amount
if __name__ == '__main__':
subtraction_game(INITSTATE)
|
|
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
__________________
Zitat: |
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson |
|
|
25.06.2016 18:37 |
|
|
|
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.
__________________ Syntax Highlighting fürs Board (Link)
|
|
25.06.2016 19:18 |
|
|
|
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.
__________________ Syntax Highlighting fürs Board (Link)
|
|
26.06.2016 20:33 |
|
|
Dr.Java
Foren As
Dabei seit: 21.03.2016
Beiträge: 99
|
|
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.
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
|
def nim_strategy(s):
choices=
if s ==choices:
return False
elif s<=4:
return False
|
|
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
__________________
Zitat: |
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson |
|
|
28.06.2016 12:11 |
|
|
|
Aber s ist die Zahl der übrigen Hölzer.
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
|
CHOICES = (1,2,5,9) #(1,2,3) ist langweilig
INITSTATE = 24
def subtraction_game(s):
'''Game loop.'''
while True:
s -= user_action(s)
if (s == 0):
print('Congratulations! You won!')
break
s -= computer_action(s)
if (s == 0):
print('You lost! Better luck next time!')
break
def nim_strategy(s):
if s in CHOICES: return s
for i in CHOICES:
if s > i and not nim_strategy(s-i): return i
return False
def user_action(s):
'''User's action selection (by console input).'''
print('%d matches are on the table. How many do you want to take?' % s)
amount = 0
while int(amount) not in CHOICES or int(amount) > s:
amount = input('> ')
return int(amount)
def computer_action(s):
'''Computer's action selection.'''
amount = nim_strategy(s)
if not amount:
from random import choice
amount = choice(tuple(filter(lambda x: x <= s, CHOICES)))
print('Computer takes %d matches.' % amount)
return amount
if __name__ == '__main__':
for i in range(1,30): print str(i) + ': ' + str(nim_strategy(i))
subtraction_game(INITSTATE) |
|
__________________ Syntax Highlighting fürs Board (Link)
|
|
28.06.2016 15:00 |
|
|
Dr.Java
Foren As
Dabei seit: 21.03.2016
Beiträge: 99
|
|
Zitat: |
Aber s ist die Zahl der übrigen Hölzer. |
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.
code: |
1:
2:
3:
|
for i in CHOICES:
if s > i and not nim_strategy(s-i): return i
return False |
|
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
__________________
Zitat: |
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson |
|
|
30.06.2016 11:08 |
|
|
|
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.
__________________ Syntax Highlighting fürs Board (Link)
|
|
30.06.2016 20:12 |
|
|
Dr.Java
Foren As
Dabei seit: 21.03.2016
Beiträge: 99
|
|
Zitat: |
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. |
Ah ,klar das ergibt Sinn.
Zitat: |
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. |
Das rechnet also ob der Gegner von den übrigen Hölzern so viele nehmen kann ,so dass er nur gewinnt?
Zitat: |
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. |
False kommt also nur wenn der Computer und man selber keine optimale Strategie mehr finden kann?
lg
__________________
Zitat: |
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson |
|
|
02.07.2016 09:13 |
|
|
|
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.
Zitat: |
False kommt also nur wenn der Computer und man selber keine optimale Strategie mehr finden kann? |
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.
__________________ Syntax Highlighting fürs Board (Link)
|
|
02.07.2016 09:22 |
|
|
Dr.Java
Foren As
Dabei seit: 21.03.2016
Beiträge: 99
|
|
Zitat: |
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.
|
Klingt einleuchtend.
Zitat: |
Also: wenn wir am Zug sind und keinen Zug finden, bei dem wir sicher gewinnen, geben wir False zurück. |
Und das ist dann das False im Programm,nehme ich an.
So oder so, danke nochmals, für deine Ausdauer und Unterstützung.
lg
__________________
Zitat: |
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson |
|
|
02.07.2016 09:54 |
|
|
|
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.
__________________ Syntax Highlighting fürs Board (Link)
|
|
02.07.2016 10:04 |
|
|
Dr.Java
Foren As
Dabei seit: 21.03.2016
Beiträge: 99
|
|
Zitat: |
Das False ist das in Zeile 20 in meinem Code vom 28.06.2016 15:00. |
Ja,genau das meinte ich.
lg
__________________
Zitat: |
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson |
|
|
02.07.2016 20:12 |
|
|
|