Rekursion:Strategiespiel, Haufenspiel

[Janus]

Hallo, kapier irgendwie ein Beispiel in unserem Skript nicht:

Strategiespiel:

-Ausprobieren aller möglichen Spielzüge
-Wahl jenes Zuges, der zum Sieg führt
-Annahme:Gegner wählt ebenfalls den jeweils besten Zug

Pseudocode:

int besterZug(stand){
for(z "Element von" mögliche Züge){
neu = ziehen(stand,z)
if(gewonnen){return z}
if(bester Zug(neu) == 0) {return z}
}
return 0
}

Also hier kapier ich gar nichts...Was soll dieser Code bedeuten?

Bsp.:
Haufenspiel:
Spielregeln:
- Zu Beginn: n Zündhölzer
- Erster Zug: m = 1...n-1 entfernen
- Folgezug: m' = 1..2*m entfernen
Wer das letzte Holz entfernt gewinnt.

Lösung:
Idee: mit größter Hölzchenanzahl beginnen; reduzieren, solange der Gegner gewinnen kann:
in Pseudocode:

int G(n,m){
while(m>0 && g(n-m,min(n-m,2*m))>0){
m=m-1
}
return m
}

Aufruf von außen: bester Zug = G(n,n-1)
Aufruf mit m = 0 (weil zuvor vom Gegner abgeräumt) bedeutet Misserfolg

Also ich kapier schonmal nicht die Spielregeln. Wenn ich bsp. 5 Zündölzer habe und mir ist es möglich 4 davon abzuheben wie ist es mir im Folgezug dann möglich das Doppelteabzuheben wenn nur mehr 1 Zündholz da ist?

mfg,
Janus

[Jan Krüger]

Strategie: der Algorithmus probiert alle derzeitig noch möglichen Spielzugkombinationen rekursiv aus (weil er davon ausgehen kann, dass der Gegenspieler jedes Mal den optimalen Gegenzug durchführt, weiß er auch, wie der Gegner reagieren würde). Findet er eine, die zum Sieg führt, gibt er davon den ersten Zug aus (der dann als nächstes gesetzt wird).

Haufenspiele laufen normalerweise so ab: es gibt N Objekte und jeder Spieler darf bei seinem Zug 1 bis K Objekte nehmen. Wer das letzte Objekt nimmt, hat gewonnen. Je nachdem, mit wie vielen Objekten man anfängt, kann einer der beiden Spieler durch eine geschickte Taktik auf jeden Fall gewinnen. Beispiel: es liegen 16 Streichhölzer auf dem Tisch und ein Spieler darf bei seinem Zug bis zu vier davon nehmen. Dann kann Spieler 1 gewinnen, indem er zuerst ein Streichholz nimmt und in jedem weiteren Zug (5 - Anzahl der Streichhölzer, die Spieler 2 gerade genommen hat) Streichhölzer aufnimmt.

[Janus]

Hallo...danke für die Antwort...
Mir ist beim Strategiepiel folgender Teil nicht klar:

int besterZug(stand){
for(z "Element von" mögliche Züge){
neu = ziehen(stand,z)
if(gewonnen){return z}
if(bester Zug(neu) == 0) {return z}
}
return 0
}

Bei der for-Schleife geht der Algo jeden möglichen Zug durch außer den besten denn den hat der Gegner schon gewählt oder?
neu = ziehen(stand,z) .....er probiert den freien Zug aus (Was heißt z?)
Wenn der zum Sieg führt.. return z
Was heißt dann if(bester Zug(neu) == 0) {return z} ? Ich meine wann wird der Ausdruck jemals 0?

mfg,
Janus

[Jan Krüger]

"Jeden möglichen Zug" bedeutet jeden Zug, den der Computer zum aktuellen Zeitpunkt machen kann. Einige davon sind schlecht, andere gut. Wenn man genau weiß, welche Strategie der andere Spieler verfolgt, kann man für einen Zug aus dem aktuellen Spielstand bestimmen, welchen Zug der Gegner machen wird, so dass man den nächsten eigenen Zug entscheiden kann usw. Auf diese Weise kannst du zu jedem Zeitpunkt jeden möglichen Ausgang des Spiels vorhersagen, und den Zug, der die beste Vorhersage hat, setzt du dann.

Der Pseudoalgorithmus geht also sämtliche möglichen Züge durch. Wenn einer der Züge sofort zum Sieg führt, wird er natürlich zurückgeliefert. Ansonsten bestimmt das Spiel den Zustand nach diesem Zug und dem Zug des Gegners und ruft besterZug rekursiv auf.
besterZug gibt 0 zurück, wenn es in einer Situation keine weiteren Züge gibt (passiert, wenn man mit dem letzten Zug verloren hat oder es eine Patt-Situation gibt).

[Xpyder]

"...wann wird der Ausdruck jemals 0?"
Im Allgemeinen basier Rekursion darauf, daß es irgendwann
mal ein Ende gibt (also - wenn z.B. keine Züge mehr
möglich sind, weil es keine Hölzer mehr gibt).
Man nennt dies auch die Abbruchbedingung. Diese
ist - gerade bei der rekursiven Programmierung - sehr
wichtig, weil sich sonst der Prozeß immer weiter in sich
selber rein verschachtelt. Ist natürlich erstmal rein
"technisch" schon schlecht (weil es keinen Rechner gibt,
der das kann - Stichwort Stack/Stapelspeicher)...

Btw: Natürlich wäre ein Spiel mit N Hölzern, in dem jeder
Spieler 1 bis N-1 Hölzer wegnehmen kann, und wer das letzte
wegnimmt, verliert, schonmal prinzipiell schlecht, weil
ich Dich dann in einem Zug besiegen könnte, wenn Du mich
anfangen läßt.
Würde der, der das letzte Holz nimmt, gewinnen
statt verlieren, würde ich lieber Dich anfangen
lassen, weil ich dann in jeden Fall gewinnen würde, wenn
Ich den zweiten Zug machen würde.

Daß Spieler1 1 bis N-1 Hölzer entfernen darf und jeder
folgende Zug das Doppelte entfernen dürfte, würde an
beiden Regeln nichts ändern.

Würde man die Regel so abändern, daß man im 1. Zug nur
soviele Hölzer entfernen daß der nächste die doppelte
Anzahl Hölzer ziehen kann, wäre das eine Schlange, die
sich in den Schwanz beißt - denn der übernächste Zug
würde wieder das doppelte brauchen, etc... Und wenn man
das alles dann berücksichtigen wollte, müßte man
vorher festlegen, wieviel Züge es geben darf - was
natürlich Blödsinn wäre, da man dann auch gleich festlegen
könnte, wer das Spiel gewinnt - denn das wäre ja dann nur
noch davon abhängig, ob die Anzahl Züge gerade oder
ungerade ist. (Abgesehen davon wäre natürlich die maximale
Anzahl Züge in jedem Fall =N.)

Dieses "Hölzer wegnehmen" (aka "Nimm!") ist n ziemlich
bekanntes Gesellschaftsspiel - aber ich glaube auch, es
funktionierte eher so, wie Jan Krüger gesagt hat: Daß
die max. Anzahl Objekte irgendeine Zahl K<N ist, die mit
N erstmal nichts zu tun hat (und nicht N-1 ist, sondern
höchstens sowas wie N/2-1).

Irgendwann hab ich mal ein "Perceptron" KI-Programm (halt
ein kleines Beispielprogramm) gesehen, was die richtigen
Züge "erlernen" konnte. - Aber dafür braucht man eigentlich
keine KI - und noch nichtmal Rekursion.
Wenn K konstant bleibt (also die max. Anzahl Hölzer, die
man nehmen darf) braucht man eigentlich nur eine Tabelle im
Speicher, die für die gerade auf dem Tisch liegende
Anzahl Hölzer die jeweils beste Anzahl zu ziehender Hölzer
enthält.
(Auf die Art könnte man das ganze dann wohl in einem
*.COM-File lösen, das weit weniger als 1KB brauchen würde.
(Na OK, selbst wenn MIT Rekursion bräucht es nicht mehr...)

"Geheimnis" des ganzen ist wohl, darauf hinzuarbeiten, daß
am Ende noch mindestens K+1 bis K*2-1 Hölzer für den Gegner
daliegen, um zu gewinnen (also das letzte Holz zu nehmen).
Will sagen: Eigentlich gibt es nur einen wirklich
"interessanten" Zug am ganzen Spiel:
Nämlich den, wenn K*2+1 bis K*3 Hölzer daliegen (und man
selber am Zug ist) oder - falls nicht - den unmittelbar
davor liegenden.
Und auch, wenn beide Spieler das natürlich wissen, ist es,
glaub ich, immer so, daß der, der den ersten Zug macht,
auch gewinnt - außer es gibt nur K+1 Hölzer.

Kann mich natürlich auch irren.

[Janus]

Hallo...danke für die Antworten: Ich habe noch eine Frage zum Strategiespiel

Code:
int besterZug(stand){
for(z "Element von" mögliche Züge){
neu = ziehen(stand,z)
if(gewonnen){return z}
if(bester Zug(neu) == 0) {return z}
}
return 0
}

Der Algorithmus prüft also solange alle Züge durch bis es entweder unentschieden steht oder er gewonnen hat. Rekursiv aufrufen tut er sich über if(bester Zug(neu) == 0) {return z} ...dass ist die eine Terminierungsbedingung.Die andere ist "if(gewonnen){return z}".
Also hat der Algorithmus somit 2 Terminierungsbedingungen oder?
mfg,
Janus