Rätsel und Spiele: Streichholzspiel
Released by matroid on So. 20. Juli 2003 13:44:17 [Statistics]
Written by Friedel - 6958 x read [Outline] Printable version Printer-friendly version -  Choose language   
Spiele+Rätsel

\(\begingroup\)
Zum Streichholzspiel anklicken
[Zum Spiel]

        

Streichhölzer nehmen

        

Es gibt viele Spiele für 2 Spieler, bei denen die Spieler abwechselnd nach bestimmten Regeln Streichhölzer von einer vorgegebenen Menge Hölzer wegnehmen. Wer das letzte Holz bekommt hat verloren. Es gibt viele verschiedenen Varianten dieses Spiels. Sie haben meist leicht erkennbare Gewinnstratgien. Spiele dieser Art werden als NIM-Varianten bezeichnet.

Ich weiß nicht, wie genau definiert ist, ob es sich bei einem Spiel um eine NIM-Varianten handelt. Aber auf jeden Fall ist die Gewinnstrategie nicht leicht zu erkennen. Ich kenne sie jedenfalls nicht, obwohl ich schon seit vielen Jahren immer wieder mal darüber nachdenke. Seit mehr als einem Jahrzehnt liegen immer wenn ich krank bin, lange mit dem Zug oder Flugzeug unterwegs bin u.ä., viele Zettel mit Strichen, Tabellen und Notizen um mich herum. Natürlich muss es eine Gewinnstrategie geben, ich komme aber nicht darauf.




        

Bei diesem Spiel liegen eine bekannte Anzahl Streichhölzer in einer Reihe hintereinander (siehe oben).         Der Spieler, der gerade dran ist, muss 1 Streichholz nehmen. Er darf jedes beliebige Holz nehmen. Wenn unmittelbar neben dem Holz         weitere Hölzer liegen, darf er eines davon nehmen. Bei einer lückenlosen Reihe von Hölzern z.B 5 Hölzern, die man von links         nach rechts nummeriert, darf man also z.B. das Holz Nummer 3 nehmen. Man darf auch Holz 3 und Holz 4 nehmen. Oder Holz 2 und Holz         3. Aber man darf z.B. nicht Holz 1 und Holz 3 nehmen. Auch nicht Holz 2, 3 und 4. Wenn Holz 4 bereits genommen ist, darf er nicht         Holz 3 und 5 nehmen. Wenn man 2 Hölzer nehmen will, müssen diese also direkt nebeneinander liegen. Danach kommt der andere Spieler         dran. Wer das letzte Holz bekommt hat verloren. Alles klar?

Falls du gerade keine Streichhölzer zur Hand hast, kannst du auch auf dieser Seite spielen. Am Anfang hast bei         diesem Beipiel 15 Hölzer. Wenn du ein Holz anklickst, wird es markiert. Wenn du das Holz wegnehmen willst, musst du es noch mal         anklicken. Wenn du das markierte Holz und ein Nachbarholz nehmen willst, klickst du das Nachbarholz an. Wenn du die Markierung         aufheben willst, klickst du ein Holz an, das nicht benachbart ist. Das Spiel funktioniert auf dieser Seite nur bei aktiviertem         JavaScript in jedem halbwegs aktuellen Browser (im Internet Explorer ab Version 5.0, Netscape Navigator ab Version 6.0,         Opera ab Version 5.02, Mozilla ab Version 1).

Zum Streichholzspiel anklicken
[Zum Spiel]

\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Spiele+Rätsel :: Spieltheorie :: Spiel und Spaß :
Streichholzspiel [von Friedel]  
Es gibt viele Spiele für 2 Spieler, bei denen die Spieler abwechselnd nach bestimmten Regeln Streichhölzer von einer vorgegebenen Menge Hölzer wegnehmen. Wer das letzte Holz bekommt hat verloren. Es gibt viele verschiedenen Varianten dieses Spiels. Hier wird eine Gewinnstrategie gesucht.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 6958
 
Aufrufstatistik des Artikels
Insgesamt 153 externe Seitenaufrufe zwischen 2012.01 und 2021.07 [Anzeigen]
DomainAnzahlProz
https://duckduckgo.com10.7%0.7 %
https://matheplanet.com21.3%1.3 %
http://google.de6341.2%41.2 %
https://google.de5234%34 %
https://google.com63.9%3.9 %
http://google.dk53.3%3.3 %
http://google.ch21.3%1.3 %
https://www.bing.com32%2 %
http://www.bing.com74.6%4.6 %
http://google.co.za10.7%0.7 %
http://de.search.yahoo.com21.3%1.3 %
http://192.168.0.1:191010.7%0.7 %
http://google.com21.3%1.3 %
http://int.search.myway.com10.7%0.7 %
https://www.ecosia.org10.7%0.7 %
http://www.friedels-home.de10.7%0.7 %
http://globososo.inspsearch.com10.7%0.7 %
http://r.duckduckgo.com10.7%0.7 %
https://google.co.in10.7%0.7 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 1 Aufruf in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2021.07.28 17:44https://duckduckgo.com/

Häufige Aufrufer in früheren Monaten
Insgesamt 120 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2012-2017 (43x)http://google.de/url?sa=t&rct=j&q=
2020-2021 (38x)https://google.de/
2020-2021 (10x)https://google.de
2020-2021 (6x)https://google.com/
201201-01 (6x)http://google.de/url?sa=t&rct=j&q=auf dem tisch liegen z streichhölzer. zw...
201301-01 (5x)http://google.de/url?sa=t&rct=j&q=auf dem tisch liegen z streichhölzer. zw...
2012-2020 (4x)http://google.de/search?q=streichholzspiel
202009-09 (4x)https://google.de/url?sa=t
201612-12 (4x)http://google.dk/url?sa=t&rct=j&q=

[Top of page]

"Rätsel und Spiele: Streichholzspiel" | 46 Comments
The authors of the comments are responsible for the content.

Re: Streichholzspiel
von: Site am: So. 20. Juli 2003 14:59:59
\(\begingroup\)
Ich denke, dass wir hier einfach das Problem haben, dass es gar keine Gewinnstrategie gibt.

Man nehme den Fall mit 4 Streichhölzern:

- - - -

Spieler 1 hat nun folgende Möglichkeiten (Punkt bedeutet weggenommenes Streichholz):

1)
S1: . - - -
S2: . . . -
S1: . . . .
Spieler 1 verliert.

2)
S1: - . - -
S2: - . . .
S1: . . . .
Spieler 1 verliert.

3)
S1: . . - -
S2: . . . -
S1: . . . .
Spieler 1 verliert.

4)
S1: - . . -
S2: . . . -
S1: . . . .
Spieler 1 verliert.

Das dürften alle Möglichkeiten gewesen sein. Und wie man sieht, verliert Spieler 1 immer, es gibt also keine Gewinnstrategie für ihn, die ihn hier immer zum Erfolg bringt.\(\endgroup\)
 

Re: Streichholzspiel
von: Plex_Inphinity am: So. 20. Juli 2003 15:28:44
\(\begingroup\)
Hallo Site und Friedel,

Im Falle n=4 verliert Spieler 1 immer, aber das heißt doch, dass es eine Gewinnstrategie für Spieler 2 gibt !
Ich vermute, dass für alle
n = 3m und
n = 3m-1   Spieler 1 eine Gewinnstrategie hat
und für alle
n = 3m-2   Spieler 2 eine Gewinnstrategie hat

das konnte ich bisher bis n=9 verifizieren, aber noch nicht für alle n beweisen. Vielleicht klappt es irgendwie mit Induktion.\(\endgroup\)
 

Re: Streichholzspiel
von: Plex_Inphinity am: So. 20. Juli 2003 15:55:39
\(\begingroup\)
Nene da war ich zu voreilig, bitte vergessen .\(\endgroup\)
 

Re: Streichholzspiel
von: Friedel am: So. 20. Juli 2003 16:29:14
\(\begingroup\)
Es ist nicht schwer nach zu weisen, dass es für alle derartigen Spiele eine Gewinnstrategie gibt. Wenn keiner der Spieler einen Fehler macht, ist von Anfang an klar wer gewinnt.

@Plex_Inphinity: Bei deiner Überlegung wird nicht berücksichtigt, dass die Hölzer während dem Spiel nicht immer in einer Reihe liegen. Es ist ja ein Unterschied ob da 2 Hölzer nebeneinander liegen, oder ein Holz, Lücke, noch ein Holz.\(\endgroup\)
 

Re: Streichholzspiel
von: Friedel am: So. 20. Juli 2003 17:06:44
\(\begingroup\)

@Plex_Inphinity: Jetzt war ich voreilig. n ist bei dir nicht die Anzahl der Hölzer, sondern die Anzahl der Plätze.


Ich bin etwas anders vor gegangen. Einige Überlegungen sind: (Ich betrachte immer den Zustand, den man seinem Gegner hinterlässt.)

  • Ein einzelnes Holz lässt keine Wahl. Der Gegner hat verloren. Bei 2 einzelnen Hölzern hat er auch keine Wahl. Es spielt ja keine Rolle welches Holz er nimmt. Er gewinnt immer. Bei ungerader Zahl einzelner Hölzer gewinnt man, bei gerader Zahl verliert man.

  • Bei einer Gruppe von 2 Hölzern hat der Gegner die Wahl, ob er beide nimmt oder nur 1. Er gewinnt also. Bei 2 solchen Gruppen hat er die selbe Wahl. Danach habe ich diese Wahl. Ich kann auf seine Entscheidung also entsprechend reagieren und gewinne deshalb. Bei einer geraden Zahl solcher Gruppen gewinne ich, bei ungerader Zahl von 2-er-Gruppen verliere ich. Wenn 2-er-Gruppen und einzelne Hölzer auf dem Tisch liegen, spielen die einzelnen Hölzer keine Rolle. Bei einer beliebigen Anzahl einzelner Hölzer + einer 2-er-Gruppe, kann der Gegner bestimmen ob er eine gerade oder eine ungerade Anzahl von einzelnen Hölzern hinterlässt, indem er von der 2-er-Gruppe ein Holz oder beide weg nimmt. Entsprechend gewinnt man, wenn man eine gerade Zahl von 2-er-Gruppen + beliebig viele einzelne Hölzer hinterlässt.

  • Bei einer 3-er-Gruppe kann der Gegner bestimmen ob die 3-er-Gruppe in 2 oder in 3 Zügen entfernt wird. Es ist egal, wie viele Züge man für eine Gruppe baucht. Es kommt nur darauf an, ob die Zahl gerade oder ungerade ist. Eine 2-er-Gruppe verhält sich also genau so, wie eine 3-er-Gruppe.

\(\endgroup\)
 

Re: Streichholzspiel
von: Ende am: So. 20. Juli 2003 19:01:53
\(\begingroup\)
Habe ich das Spiel richtig verstanden?

Es gibt n nebeneinander liegende Streichhoelzer, und die Spieler duerfen 1 Hoelzchen oder 2 direkt nebeneinanderliegende Hoelzchen nehmen. Und wer das letzte Hoelzchen nimmt, der verliert.

Richtig so?

Gruss, E. 😉\(\endgroup\)
 

Re: Streichholzspiel
von: Friedel am: So. 20. Juli 2003 19:57:03
\(\begingroup\)
@Ende: Richtig. Kannst ja mal testen indem du auf das grüne Feld oben klickst.

Funzt das Spiel eigentlich bei allen? Die IE-Versionen für Mac konnte ich nämlich nicht testen. Auch Linux-Browser wie Conquerer u.ä. konnte ich nicht testen.\(\endgroup\)
 

Re: Streichholzspiel
von: Friedel am: So. 20. Juli 2003 21:23:14
\(\begingroup\)

Als nächstes die 4-er-Gruppe: Wenn man dem Gegner eine 4-er-Gruppe hinterlässt, kann der Gegner nicht wählen ob die Gruppe mit einer geraden oder einer ungeraden Zahl von Zügen entfernt wird. Er kann die beiden mittleren Hölzer nehmen und 2 einzelne Hölzer hinterlassen. Dann sind es 3 Züge. Oder er kann eine 3-er-Gruppe, eine 2-er-Gruppe, oder eine 2-er-Gruppe + 1 Einzelholz hinterlassen. In diesen Fällen überlässt er mir die Wahl.

Fazit:


Bei einer 4-er-Gruppe + gerade Zahl (incl. 0) von Einzelhölzer kann der Gegner mir

  • eine gerade Zahl von Hölzern hinterlassen. ⇒ Ich gewinne.
  • mir eine gerade Zahl von Hölzern + eine 2-er- oder 3-er-Gruppe hinterlassen. ⇒ Ich gewinne.
  • mir eine ungerade Zahl von Hölzern + eine 2-er-Gruppe hinterlassen. ⇒ Ich gewinne.

Er verliert also auf jeden Fall.


Bei einer 4-er-Gruppe + ungerade Zahl von Einzelhölzer kann der Gegner mir

  • eine ungerade Zahl von Hölzern hinterlassen. ⇒ Ich verliere.
  • mir eine ungerade Zahl von Hölzern + eine 2-er- oder 3-er-Gruppe hinterlassen. ⇒ Ich gewinne.
  • mir eine gerade Zahl von Hölzern + eine 2-er-Gruppe hinterlassen. ⇒ Ich gewinne.

Er kann also den Sieg erzwingen.


Bei einer 4-er-Gruppe + ungerade Zahl von 2-er-/3-er-Gruppen + ungerade Zahl von Einzelhölzer kann der Gegner mir

  • eine gerade Zahl von 2-er-/3-er-Gruppen + eine ungerade Zahl von Hölzern hinterlassen. ⇒ Ich verliere.

Die anderen Möglichkeiten sind irrelevant, weil der Gergner mit dieser seinen Sieg erzwingen kann.


Bei einer 4-er-Gruppe + gerade Zahl von 2-er-/3-er-Gruppen + ungerade Zahl von Einzelhölzer kann der Gegner mir

  • eine gerade Zahl von 2-er-/3-er-Gruppen + eine ungerade Zahl von Hölzern hinterlassen. ⇒ Ich verliere.

Die anderen Möglichkeiten sind irrelevant, weil der Gergner mit dieser seinen Sieg erzwingen kann.


Bei einer 4-er-Gruppe + ungerade Zahl von 2-er-/3-er-Gruppen + gerade Zahl von Einzelhölzer kann der Gegner mir

  • eine gerade Zahl von 2-er-/3-er-Gruppen + eine ungerade Zahl von Hölzern hinterlassen. ⇒ Ich verliere.

Die anderen Möglichkeiten sind irrelevant, weil der Gergner mit dieser seinen Sieg erzwingen kann.


Bei einer 4-er-Gruppe + gerade Zahl von 2-er-/3-er-Gruppen + gerade Zahl von Einzelhölzer kann der Gegner mir

  • eine gerade Zahl von 2-er-/3-er-Gruppen + eine gerade Zahl von Hölzern hinterlassen. ⇒ Ich verliere.

Die anderen Möglichkeiten sind irrelevant, weil der Gergner mit dieser seinen Sieg erzwingen kann.


\(\endgroup\)
 

Re: Streichholzspiel
von: SchuBi am: So. 20. Juli 2003 23:01:30
\(\begingroup\)
Also bei mir auf dem Mac ( OS X 10.2.6) läuft es mit
icab
safari
internet explorer 5.2\(\endgroup\)
 

Re: Streichholzspiel
von: scorp am: Mo. 21. Juli 2003 00:14:22
\(\begingroup\)
Hallo Friedel, hallo die anderen.
Eine ununterbrochene Reihe von n Hoelzchen nenne ich fortan "n-er-Gruppe". Zuerst stelle ich fuer die elementarsten Gruppen eine Tabelle auf, wie das Spiel fuer den am Zuge befindlichen Spieler bei perfektem Spiel ausgeht. So erhaelt man fuer eine verbleibende Einser-Gruppe trivialerweise den Verlust. Bei zwei Hoelzchen den Sieg.
Wir erhalten:
E(1) = -
E(2) = +
E(3) = +
E(4) = -
E(5) = +
E(6) = +

Nun stelle man eine Tabelle auf, wie das Spiel endet, wenn zwei Gruppen verbleiben. Gelingt es, einen verlorenen Folgezustand zu erreichen, ist das Spiel gewonnen. Es ist
E(1,1) = + , da E(1) = -
E(2,1) = + , da E(1) = -
E(2,2) = -
E(3,1) = + , da E(1,1,1) = -
E(3,2) = + , da E(2,2) = -
E(3,3) = -
E(4,1) = + , da E(4) = -
E(4,2) = + , da E(2,2) = -
E(4,3) = + , da E(3,3) = -
E(4,4) = - , da alle moeglichen Folgezustaende fuer den am Zug Befindlichen gewonnen sind.
E(5,1) = -
E(5,2) = + , da E(5,1) = -
E(5,3) = + , da E(5,1) = - und E(3,3) = -
E(5,4) = + , da E(4,4) = -

Wie sieht es bei E(5,5) aus? Wir analysieren die moeglichen Folgezustaende:
E(5,4) ist gewonnen fuer den Nachziehenden.
E(5,3) ist gewonnen fuer den Nachziehenden.

Damit ist E(5,5) verloren:
E(5,5) = 0

Mithilfe dieser Tabelle kann man nun schnell E(7) berechnen.
Die Menge aller moeglichen Folgezustaende belaeuft sich auf M_F = {E(6), E(5), E(5,1), E(4,2), E(3,3), E(4,1), E(3,2)}.
Ist nur ein Zustand der Menge verloren, so ist E(7) als gewonnen zu betrachten. Es ist E(3,3) = - und demnach E(7) = +.

Schnell erhaelt man auch E(6,1) = +  und E(7,1) = + , da E(5,1) = -.

Das ganze wird man anschliessend noch fuer drei, vier, fuenf, ... Gruppen aufstellen muessen und hoffen, eine Regelmaessigkeit zu entdecken.
Ich werde weiter ueberlegen...

Viele Gruesse,
/Alex


PS: Durch Induktion kann gezeigt werden, dass fuer alle n>1 E(n,n) = - und daraus, dass alle E(n,n-1) und E(n,n-2) = - fuer alle n>3.

Wie Weiter?\(\endgroup\)
 

Re: Streichholzspiel
von: scorp am: Mo. 21. Juli 2003 00:18:42
\(\begingroup\)
Es muss natuerlich E(n,n-1)=+ und E(n,n-2)=+ heissen...\(\endgroup\)
 

Re: Streichholzspiel
von: scorp am: Mo. 21. Juli 2003 00:34:24
\(\begingroup\)
Da ist wohl noch irgenwo der Wurm drin, sonst nimmt der Beginnende bei n Hoelzern aus der Mitte eins, bei ungeradem n, und zwei, bei geradem n, und hinterlaesst dem Gegner mit E(floor((n-1)/2), floor((n-1)/2)) eine Verluststellung.

Gruesse.\(\endgroup\)
 

Re: Streichholzspiel
von: Site am: Mo. 21. Juli 2003 12:31:01
\(\begingroup\)
Die Aufgabe entpuppt sich ja als ganz schön kompliziert. Ich dachte zunächst, dass sich die Gewinnstrategie immer auf Spieler 1 bezöge und dann gäbe es keine.

Sollte einem kein Geniestreich einfallen, wird man wohl sehen müssen, ob scorps Ansatz zum Erfolg führt, oder sogar - noch banaler - ein Programm schreiben, das jeweils alle Möglichkeiten durchprobiert und ausgibt, für welchen Spieler jeweils eine Gewinnstrategie besteht.

Was mir noch aufgefallen ist - und ich weiß nicht, ob es uns mal von Nutzen sein wird - dass anscheinend zu Beginn für Spieler 1 immer genauso viele Handlungsmöglichkeiten wie Streichhölzer vorhanden sind.\(\endgroup\)
 

Re: Streichholzspiel
von: scorp am: Mo. 21. Juli 2003 12:45:22
\(\begingroup\)
Hi,
ich muss leider eingestehen, dass mir gestern zu spaeter Stunde ein heftiger Denkfehler unterlaufen ist.
Bei dem Induktionsbeweis fuer E(n,n) wird naemlich nicht beruecksichtigt, dass man die Hoelzer auch aus der Mitte entfernen kann und sich somit drei Gruppen bilden...\(\endgroup\)
 

Re: Streichholzspiel
von: Friedel am: Mo. 21. Juli 2003 22:52:05
\(\begingroup\)

Schön, dass sich einige gefunden haben, die sich auch an diesem Problem festbeissen.


Die Auflistung von scorp vom Mo. 21. Juli 2003 00:14:22 passt bis einschließlich E(5,4), wobei E(4,4) wohl ein Glückstreffer war. Auf jeden Fall sollten wir uns jetzt auf eine Nomenklatur einigen. Scorp hat ja eine recht brauchbare benutzt. Aber es ist wichtig fest zu halten, dass er immer der Zustand betrachtet, den man vorfindet. Ich habe immer den Zustand betrachtet, den man seinem Gegner hinterlässt. Um Verwechsungen zu vermeiden wechke ich zu Scorps System. - Aber nicht heute. Um 4:20 Uhr ist die Nacht rum.


Schön, dass das Script in den verbreiteten Mac-Browsern funktioniert. Kann noch jemand mit Linux (z.B. Conquerer) testen?

\(\endgroup\)
 

neuer Ansatz
von: scorp am: Di. 22. Juli 2003 15:04:31
\(\begingroup\)
Hallo an alle.

Eine ganz andere Idee:
Sei gegeben ein Zustand (eine Stellung), bestehend aus zwei Gruppen, A und B.
Nun stelle man folgende Frage: Kann der Anziehende A forciert gewinnen? Kann der Anziehende B forciert gewinnen? Kann der Anziehende A forciert _verlieren_? Kann der Anziehende B forciert _verlieren_?
Forciertes verlieren bedeutet, dass es moeglich ist, eine Gruppe aufzuloesen (es bleibt kein Stein/Holz uebrig), wobei man selbst den letzten Stein nimmt; egal was der Gegner auch erwidert.
Empirisch habe ich gezeigt, dass alle Gruppen von 1-6 erzwungen zu verlieren sind, aber nur 2,3,5,6 erzwungen gewonnen sind.

Zurueck zu den Fragen.
A ist forciert zu gewinnen und forciert zu verlieren
B laesst das Erzwingen eines Sieges nicht zu, wohl aber eines Verlustes.

Man gewinnt die Partie nun, in dem man A derart aufloest, dass man den letzten Stein (das letzte Hoelzchen) nimmt (Verlust von A erzwingen) und somit der Gegner bei verbleibendem B am Zug ist. Die Reihenfolge der Zuege spielt keine Rolle.

Beispiel I:
A = (2)
B = (1)

Nach Plan: Gegner zwingen, mich A verlieren zu lassen. Das ist hier nicht schwer, der Spieler am Zug nimmt einfach beide Hoelzchen (Steine) weg.

Beispiel II:
A = (3)
B = (1)

Man erzwingt den Verlust von A indem man das mittlere Hoelzchen entfernt.


Versuch einer Verallgemeinerung:

Seien wieder zwei Gruppen A und B gegeben. Ich schreibe ev fuer erzwungen verlierbar und eg fuer forciert zu gewinnen.

Die Beispiele oben zeigen, dass A[eg,ev] und B[ev] gewonnen ist.
Im Fall A[ev] B[ev] ist das Spiel ebenso zu gewinnen. Man verliert eine Gruppe und der Gegner verbleibt mit einer verloreren Gruppe.

A[eg], B[eg].
Ich kann den Verlust bei beiden nicht erzwingen, demnach wird der Gegner A verlieren und mich mit B zuruecklassen. Dieser Punkt wuerde an den Gegner gehen.

Naeheres folgt...

@Friedel: Stimmt das soweit mit deiner Erfahrung ueberein?

Gruss,
/Alex\(\endgroup\)
 

Re: Streichholzspiel
von: scorp am: Di. 22. Juli 2003 16:41:48
\(\begingroup\)
Noch ein Fehler, der mir erst aufgrund des neuen Ansatzes auffiel: (4,4) ist doch gewonnen!

Als Spieler eins nimmt man von einem Vierer die beiden Mittelhoelzer heraus. Es verbleiben ein Vierer und zwei Einser.

XXXX X X

Aufgrund der strategischen Eigenschaften des Spiels ist ein Zustand gleichbedeutend zu all denjenigen, die eine gerade Anzahl Einser-Gruppen mehr aufweisen. Wir vereinfachen die Situation gemaess dieser Regel:

XXXX

Und (4) ist, wie oben erlaeutert, verloren. Da zu diesem Zeitpunkt aber der Gegner am Zug ist... :)

Gruss,
/Alex\(\endgroup\)
 

Re: Streichholzspiel
von: Friedel am: Di. 22. Juli 2003 21:20:23
\(\begingroup\)
@scorp: Warum bist du nicht bei deiner Schreibweise geblieben? Bei deiner Antwort von Di. 22. Juli 2003 15:04:31 verstehe ich nicht um was es geht. Mal schreibst du von einer Gruppe A (was ist das?), mal von einer Gruppe B (und das?). Dann wieder von Anzeihenden A und vom Anziehenden B. Was bedeutet "forciert _verlieren_"? Was meinst du mit "Gruppe auflösen"? Außérdem schreibst du "dass alle Gruppen von 1-6 erzwungen zu verlieren sind, aber nur 2,3,5,6 erzwungen gewonnen sind". Was soll das jetzt? Ist 2,3,5 und 6 gewonnen oder verloren? Was bedeutet
A = (2)
B = (1)?
Kurz gesagt, ich habe kein Wort verstanden.
\(\endgroup\)
 

Re: Streichholzspiel
von: scorp am: Di. 22. Juli 2003 23:40:24
\(\begingroup\)
@Friedel:

> ?Warum bist du nicht bei deiner Schreibweise geblieben?

Weil diese mir kaum mehr ausgereicht haette um meine neuen Gedanken zu fassen.

> Mal schreibst du von einer Gruppe A (was ist das?)

Eine Gruppe, die ich "A" nenne.

> Dann wieder von Anzeihenden A und vom Anziehenden B.

Nein, der Anziehende und seine Taetigkeit bezueglich A; die Gruppe.

> Was bedeutet "forciert _verlieren_"?

Das Gegenteil von forciert gewinnen. Ich drehe die Regeln um und schaue ob es moeglich ist, wenn beide Gegner versuchen, ihrerseits den letzten Stein zu nehmen, ob ich derjenige bin, dem der verbleibende Stein gehoeren wird.

> Was meinst du mit "Gruppe auflösen"?

Die Gruppe wird eliminiert indem beide Spieler so lange die Hoelzer von ihr abgrasen bis nichts mehr da ist.

> "dass alle Gruppen von 1-6 erzwungen zu verlieren sind, aber nur 2,3,5,6 erzwungen gewonnen sind". Was soll das jetzt? Ist 2,3,5 und 6 gewonnen oder verloren?

Ich kann 1-6 verlieren, wenn ich es will (siehe oben, umgekehrte Regeln), aber nur 2,3,5,6 gewinnen, wenn ich (und natuerlich wie immer der Gegner) es wollen.

> Was bedeutet
> A = (2)
> B = (1)?

A ist eine Gruppe. Und zwar bestehend aus zwei Hoelzchen. Was B ist, ist dann klar?

> Kurz gesagt, ich habe kein Wort verstanden.

Mach dir nicht die Muehe es zu tun, die Idee geht nicht auf weil sie letztlich in mindestens einem Paradoxon muendet.\(\endgroup\)
 

Re: Streichholzspiel
von: Morris am: Mi. 23. Juli 2003 11:18:32
\(\begingroup\)
Hallo Leute!
Ich habe Eure Kommentare nur ueberflogen, aber ich glaube, zu Friedels Frage zu Browsern unter Linux hat noch niemand etwas gesagt. Ich habe hier gerade nur den Konqueror 3.0.4 zur Verfuegung, damit kann man spielen. Zu Hause kann ich auch noch einen neueren Konqueror, Mozilla und Opera ausprobieren.

Gruss Morris

P.S.: Ob ich in die Suche nach einer Gewinnstrategie einsteige, weiss ich noch nicht.\(\endgroup\)
 

Re: Streichholzspiel
von: Site am: Mi. 23. Juli 2003 12:11:40
\(\begingroup\)
Da nun wieder Ideenlosigkeit herrscht, schreibe ich mal etwas Grundsätzliches für diejenigen, die mit der Suche beginnen wollen.

Wir betrachten Gewinnsituationen und Verlustsituationen. Eine Gewinnsituation ist eine Spielsituation, der mindestens eine Verlustsituation folgen kann. Eine Verlustsituation ist eine Spielsituation, der nur Gewinnsituationen folgen können.

Allgemeine Schreibweise nach scorp:

E(GS) = +
E(VS) = -

Ist man also einmal am Zuge bei einer Gewinnsiutation, so kann man den Gegner auf eine Verlustsituation zwingen, wodurch er einen wieder auf eine Gewinnsituation bringt, etc.

Ein möglicher Weg zur Auflösung des Rätsels wäre es also, eine Regelmäßigkeit in den Verlustsituationen zu entdecken, wodurch man diese voll erfasst. Dann braucht man nur noch zu prüfen, ob bei einer beliebigen Spielsituation eine mögliche Folge eine Verlustsituation ist und schon hat man heraus, wer gewinnt.

Dazu schreibe ich mal einige Verlustsituationen nach der scorpschen Schreibweise auf (diese Angaben sind wie immer ohne Gewähr):

E(1)
E(1,1,1)
E(1,1,1,1,1)
...

E(2,2)
E(2,2,2,2)
E(2,2,2,2,2,2)
...

E(2,1,1)
E(3,1)
E(3,1,1)
E(3,2,2)
E(4)
E(4,3)
E(5,1)

Gelobt sei derjenige, der eine Regelmäßigkeit aufdeckt.

Aber nun zu einer anderen Idee: An sich interessieren uns immer nur die Anfangszustände, also E(n), denn wir dort ablesen können, ob es sich um eine Gewinn- oder Verlustsituation handelt, wissen wir schon ganz zu Beginn, wer gewinnt.

Für E(n) gibt es n Folgezustände, wenn man z.B. spiegelverkehrte Zustände als einen einzigen betrachtet, die Reihenfolge der Gruppen also keine Rolle spielt. Von diesen n Folgezuständen sind g Gewinnsituationen und v Verlustsituationen (g+v=n). Ist g=n, so ist E(n) eine Verlustsituation.

Sollte nun g anders wachsen als n, so kann es sein, dass z.B. ab einem bestimmten n nie wieder ein g so groß wie n wird, Spieler 1 also immer gewinnt.
Tabellarisch:

n=1 => g=1 => Verlust
n=2 => g=1
n=3 => g=2
n=4 => g=4 => Verlust
n=5 => g=3
n=6 => g=4
n=7 => g=6

Wenn jemand möchte, kann er diese Tabelle gerne fortführen, es ist gut möglich, dass Spieler 1 für jedes n>4 gewinnt. Ganz einfach, weil er so viele Möglichkeiten hat, einen Folgezustand zu wählen, dass er darunter immer eine Verlustsituation finden wird.

Von Beweisen ist das aber noch weit entfernt^^\(\endgroup\)
 

Re: Streichholzspiel
von: scorp am: Mi. 23. Juli 2003 12:35:30
\(\begingroup\)
Hallo Site,
schoen, dass du meine Notation uebernimmst. Deine letzte Idee hatte ich auch schon; sie dann aber aus irgend einem Grund, der mir gerade nicht einfaellt wieder verworfen. Es ging glaub ungefaehr so: Wenn du beweisen kannst, dass fuer n>4 alle Zustaende gewonnen sind, musst du zu jedem einen Folgezustand finden, der verloren ist. Jeder Folgezustand hat nur unwesentlich weniger Auswahlmoeglichkeiten (insb. fuer n->oo) als der urspruengliche. So kaemen wir wohl zu einem Kurzschluss, imho.

VERLUSTSITUATIONEN:
E(ungerade Anzahl an Einsen)

E(2,2)
E(2,2,2,2)
E(2,2,2,2,2,2)

Hast du das bewiesen? Bei E(sechs Zweien) bin ich mir nicht sicher, und beweisen laesst es sich auch nicht sonderlich einfach.

Wenn du schon saemtliche Situationen sammelst, sollten wir uns auf eine Vereinfachung einigen.
Es ist
E(Z) = E(Z + zwei Einsen).

Desweiteren kann jede 3er-Gruppe durch eine Zweier- und eine Einsergruppe ersetzt werden, da (3) und (2,1) die gleichen Folgezustaende haben.
So geht der Beweis zu E(3,3)=- bspw. sehr schnell:

E(3,3) =~ E(2,2,1,1) =~ E(2,2) = -

Leider gibt es wohl nicht mehr von diesen Vereinfachungen...


Hab noch ein paar Verbesserungsvorschlaege:

E(2,1,1)   // ist gewonnen, da E(2) gewonnen
E(3,1)     // ist gewonnen, da E(2,1,1) =~ E(2) gewonnen
E(3,1,1)   // ist gewonnen, da E(3) gewonnen
E(3,2,2)   // Ist gewonnen, da Folgezustand E(3,2,1) verloren
E(4,3)     // ist gewonnen, da E(3,3) verloren

Viele Gruesse,
/Alex\(\endgroup\)
 

Re: Streichholzspiel
von: Site am: Mi. 23. Juli 2003 12:51:35
\(\begingroup\)
E("Gerade Anzahl von Zweiergruppen") = -
habe ich noch nicht bewiesen, darum steht dort auch "ohne Gewähr". Allerdings kann man es beweisen, denke ich:

Haben wir eine Gruppe, welche, stünde sie alleine, eine Verlustsituation wäre und dazu eine Einsergruppe, dann ist es eine Gewinnsituation, da die Einsergruppe einfach zu eliminieren ist.

Gibt es nur Zweiergruppen, so kann ich entweder von einer Gruppe ein Hölzchen entfernen oder eine ganze Gruppe.

Aus E(2,2,2) kann also folgen:
E(2,2) = -
oder
E(2,2,1) = + (wie oben gezeigt)
Damit ist E(2,2,2) = +

E(2,2,2,2) kann ich zurückführen auf
E(2,2,2) = +
und E(2,2,2,1) = +, da E(2,2,1,1)=E(2,2)=+
=> E(2,2,2,2) = -

E(2,2,2,2,2) wird zurückgeführt auf
E(2,2,2,2) = -
und E(2,2,2,2,1) = +
=> E(2,2,2,2,2) = +

E(2,2,2,2,2,2) auf
E(2,2,2,2,2) = +
und E(2,2,2,2,1) = +
=> E(2,2,2,2,2,2) = -

Wenn ich jetzt keinen gewaltigen Denkfehler habe, dann lässt sich das immer fortführen, sich jede weitere Situation dieser Art also auf vorherige zurückführen, wodurch (gelobt sei die vollständige Induktion) sich zeigen ließe, dass eine gerade Anzahl von Zweiergruppen zum Verlust führt.\(\endgroup\)
 

Re: Streichholzspiel
von: scorp am: Mi. 23. Juli 2003 13:44:02
\(\begingroup\)
Hey Site,
ich fuehre wieder eine neue Schreibweise ein, weil die alte sehr unuebersichtlich ist. Koennen wir uns auf [n*(a)] einigen, fuer das n-fache Auftreten einer a-er-Gruppe? Ich schreibe als fortan Zustaende in eckigen Klammern.

Wir wissen, dass E[2]=+, E[2*(2)]=-, E[3*(2)]=+, E[4*(2)]=-.

Daraus leiten wir zwei Behauptungen ab:
E[2n*(2)] = -
E[2n*(2),(2)] = +

Die Gewinne sind leicht zu zeigen, wenn man die Verluste bewiesen hat. Fragt sich, wie es mit den Verlusten funktioniert:

Wenn E[2n*(2)] verloren, so sind E[2{n-1}*(2)]  und E[2{n-1}*(2),(1)] gewonnen (jetzt wirds langsam sehr unuebersichtlich).

Ich beschraenke mich darauf zu zeigen, dass E[2{n-1}*(2),(1)] gewonnen ist, also mindestens einen verlorenen Folgezustand hat.

E[2{n-1}*(2),(1)]
Man nehme einen Stein eines verbleibenden Zweiers weg
E[2{n-2}*(2),(1),(2)] =~ E[2{n-2}*(2)]
Und das ist der Induktionsschritt.

Sollte als Beweis genuegen. Ich baue keine logischen Luftschloesser, weil ein Zustand niemals von sich selbst abhaengig ist, aber stets auf einen bekannten zurueck gefuehrt wird.
Dein Ansatz hat mich auf die richtige Idee gebracht.

Wenn wir irgendwann noch eine _uebersichtliche_ Schreibweise ausmachen koennten, dann erleichtert dies in Zukunft die Arbeit :-)

=> E[n*(3)] = E[n*(2), n*(1)] = E[{{n mod 2} + 1}*(2,1)] =
 + fuer n ungerade
 - fuer n ungerade


Viele Gruesse,
/Alex\(\endgroup\)
 

Re: Streichholzspiel
von: Site am: Mi. 23. Juli 2003 14:11:27
\(\begingroup\)
Danke für den formalen Beweis, Alex.

Mir ist gerade aufgefallen, dass meine Auflistung der Verlustsituationen völlig falsch war, meine paar Aufzeichnungen müssen wohl zu ungeordnet gewesen sein^^

Also hier das (magere) Update:

Verlustsituationen:

E[n*(1)] für n ungerade
E[n*(2)] für n gerade
E[(4)]
E[(5),(1)]

Bei der Schreibweise müssen wir uns wirklich was einfallen lassen, sollten wir hier noch lange diskutieren (mein Ehrgeiz schwindet allerdings schon^^).\(\endgroup\)
 

Re: Streichholzspiel
von: scorp am: Mi. 23. Juli 2003 17:43:43
\(\begingroup\)
Tja, is zwar ganz nett, dass gerade Anzahl Zweier und ungerade Anzahl Einser verloren sind und dass sich [3] zu [2,1] umschreiben laesst, aber viel mehr haben wir dem Spiel auch nicht entlocken koennen.
Wie gesagt, glaube ich nicht, dass sich [n] fuer n>3 vereinfachen lassen wird (formaler Beweis steht noch aus). Wir brauchen ne neue Idee :-/


Ein letzter verzweifelter Versuch:
Wir betrachten einige Gruppen und halten fest, in wievielen Zuegen sie sich schnellstens aufloesen (elimieren) lassen und wievielen hoechstens. Ich bezeichne das mit min[Z] und max[Z]. Trivialerweise ist max(n-er-Gruppe)=n.

Es ist
min[n] = floor((n+1)/2)
max[n] = n

Beispiel: min[4]=2, max[4]=4 ; min[5]=3, max[5]=5.

Die Idee besteht darin, das ganze auf Zustaende mehrerer Gruppen anzuwenden.
Bsp.: [3,2,1]
min[3,2,1] = min[3]+min[2]+min[1] = 4
max[3,2,1] = 3+2+1 = 6

Wir wissen, dass E[3,2,1] = -

Jetzt bastle ich Zustaende, die ebenfalls Min=4 und Max=6 erfuellen.
Es erfuellt [4,1,1] die beiden Voraussetzungen, wie auch [5,1] und [2,2,1,1] und damit auch [3,3]. Und siehe da: Diese vier sind alle verloren!

Meinst du das ist zu gebrauchen?

Viele Gruesse,
/Alex\(\endgroup\)
 

Re: Streichholzspiel
von: scorp am: Mi. 23. Juli 2003 18:00:19
\(\begingroup\)
Koennen wir auf diese Weise zusammen fassen? :

Ich schreibe fuer eine Stellung Z die min-/max-Werte in in Klammern: <min,max>. Es ist bspw. [3] = <2,3>

Diese Werte lassen sich wie folgt addieren:

min([a,b]) = min([a]) + min([b])
max([a,b]) = a + b

Zum Berechnen von Min und Max-Wert einer Stellung [a,b] berechne man also das paar <min1,max1> fuer a und <min2,max2> fuer b und addiere diese:
[a,b] = <min1+min2, max1+max2>

Behauptung: Es ist verloren jede Stellung genau dann, wenn gilt (sei Z ein beliebiger Zustand beliebig vieler Gruppen)

[Z] = i * <1,1> + j * <1,2> = < i+j, i+2j >
mit i,j aus der Menge der natuerlichen Zahlen.

Kleines Brainstorming. Ausarbeitung folgt. :)\(\endgroup\)
 

Re: Streichholzspiel
von: scorp am: Mi. 23. Juli 2003 18:02:32
\(\begingroup\)
SORRY, IM LETZTEN HAT'S EIN PAAR SACHEN ZERLEGT.

Koennen wir auf diese Weise zusammen fassen? :

Ich schreibe fuer eine Stellung Z die min-/max-Werte in in Klammern: <min,max>. Es ist bspw. [3] = <2,3>

Diese Werte lassen sich wie folgt addieren:

min([a,b]) = min([a]) + min([b])
max([a,b]) = a + b

Zum Berechnen von Min und Max-Wert einer Stellung [a,b] berechne man also das paar < min1,max1 > fuer a und < min2,max2 > fuer b und addiere diese:
[a,b] = < min1+min2, max1+max2 >
[a,b] = < min(a)+min(b), a+b >


Behauptung: Es ist verloren jede Stellung genau dann, wenn gilt (sei Z ein beliebiger Zustand beliebig vieler Gruppen)

[Z] = i * <1,1> + j * <1,2> = < i+j, i+2j >
mit i,j aus der Menge der natuerlichen Zahlen.

Kleines Brainstorming. Ausarbeitung folgt. :)\(\endgroup\)
 

Re: Streichholzspiel
von: scorp am: Mi. 23. Juli 2003 18:13:38
\(\begingroup\)
Argh, warum kann man hier seine Beitrage nicht aendern...

Da hat sich wieder ein Fehler eingeschlichen. Es ist verloren, wenn

< min(Z),max(Z) > = (2i+1) * <1,1> + 2j * <1,2> = < 2(i+j)+1 , 2(i+2j)+1 >

Hoffentlich stimmt's nun endlich.

Gruss an alle,
/Alex\(\endgroup\)
 

Re: Streichholzspiel
von: scorp am: Mi. 23. Juli 2003 18:26:27
\(\begingroup\)
grmbl... ;-)



<min(Z),max(Z)> = 2i * <1,1> + 2j * <1,2> =  <2i+2j , 2i+4j)>\(\endgroup\)
 

Re: Streichholzspiel
von: scorp am: Do. 24. Juli 2003 17:42:57
\(\begingroup\)
Habe mir ein Programm geschrieben, welches zwar elendig lahm ist, aber es scheint doch zu funktionieren. Werde es demnaechst mit bekannten Verluststellungen fuettern, um die Rechenzeit herabzusetzen.

Das Programm findet ausserdem:

E[3*(3)] = -
E[4*(3)] = -
E[5*(3)] = -

Das ist doch ein beachtliches Ergebnis (sofern es denn stimmt... 😄 )\(\endgroup\)
 

Re: Streichholzspiel
von: scorp am: Do. 24. Juli 2003 18:34:16
\(\begingroup\)
E[ 1] = -
E[ 2] = +
E[ 3] = +
E[ 4] = -
E[ 5] = +
E[ 6] = +
E[ 7] = +
E[ 8] = +
E[ 9] = -
E[10] = +
E[11] = +
E[12] = +
E[13] = +
E[14] = +
E[15] = +
E[16] = +
E[17] = -
E[18] = +
E[19] = +


E[1,1] = +
E[2,2] = -
E[3,3] = -
E[4,4] = +
E[5,5] = +
E[6,6] = -
E[7,7] = -
E[8,8] = +
E[9,9] = +
E[10,10] = -
...das laesst doch etwas ahnen. :-)


E[1,1,1] = -
E[2,2,2] = +
E[3,3,3] = +
E[4,4,4] = -
E[5,5,5] = -
E[6,6,6] = -
E[7,7,7] = -


E[1,1,1,1] = +
E[2,2,2,2] = -
E[3,3,3,3] = -
E[4,4,4,4] = +
E[5,5,5,5] = -
E[6,6,6,6] = -


E[1,1,1,1,1] = -
E[2,2,2,2,2] = +
E[3,3,3,3,3] = +
E[4,4,4,4,4] = -
E[5,5,5,5,5] = -


E[1,1,1,1,1,1] = +
E[2,2,2,2,2,2] = -
E[3,3,3,3,3,3] = -
E[4,4,4,4,4,4] = +


Hoehere Kombinationen hat die bisherige Version nicht in ausreichend kurzer Zeit bewaeltigen wollen.
@Site: Wieder motivierter? 😉\(\endgroup\)
 

Re: Streichholzspiel
von: Plex_Inphinity am: Fr. 25. Juli 2003 19:56:30
\(\begingroup\)
Hallo,

wie Site ja schon gezeigt hat ist
E(2n*(2)) = -
E(2n+1 * (2)) = +  , für alle n, daraus folgt aber , dass auch
E(2n*(3)) = -
, denn wie Scorp gezeigt hat, ist E(z,1,1) = E(z) für jeden Zustand z und die Zustände (3) und (2,1) sind äquivalent.
Also gilt:
E(2n*(2)) = E(2n*(2),2*(1)) = E(2n*(3)) = -

Weiterhin gilt:
Falls E(z) = -  , dann ist E(z,1,2) = E(z,3) = E(z,4) = +.
Denn der 1. Spieler kann in beiden Situationen den Zustand E(z,1,1) = E(z) = - hinterlassen und gewinnt somit.

Also haben wir
E(2n*(3)) = - und E(2n+1*(3)) = E(2n*(3),1,2) = +

für alle n.

Noch eine Beobachtung:
Die Folgezustände von (5) sind (4),(3),(1,2) und (1,3) ~ (1,1,2) ~ (2)
Wenn also E(z) = - für irgendeinen Zustand z.
Dann ist E(z,5) = - .Denn Spieler 1 steht bei E(z,5) immer unter Zugzwang :vom (5)-er Haufen, darf er nichts nehmen, da sonst E(z,5') = + und Spieler 2 somit gewinnt. Also muß er immer von Position (z) zu Position (z') mit E(z') = + ziehen. Worauf Spieler 2 immer mit E(z'') = - kontern kann usw. bis kein Streichholz mehr da ist und wir bei Position E(5)= + sind.

Also müßte, da nach deinem Programm E(5,5,5) = - ist E( n+3 * (5)) = - sein für alle n.

Vielleicht kannst du das ja noch in deinem Programm verwenden. Ich habe auch schon versucht ein Programm zu schreiben, meins gibt allerdings schon bei E(15) wegen Speichermangels auf :).\(\endgroup\)
 

Re: Streichholzspiel
von: Plex_Inphinity am: Fr. 25. Juli 2003 19:57:53
\(\begingroup\)
Ich hab bei:
"Also gilt:
E(2n*(2)) = E(2n*(2),2n*(1)) = E(2n*(3)) = -
"

ein n vergessen..\(\endgroup\)
 

Re: Streichholzspiel
von: Plex_Inphinity am: Fr. 25. Juli 2003 20:56:14
\(\begingroup\)
Nochwas:

Wie oben gezeigt folgt aus E(z) = -  => E(z,5) = -

Also gilt auch E(z,5) = + => E(z) = +

Nun kann man folgern
Wenn E(n) = - => E(n,5) = - => E(n,5,5) = - =>
E(n+6,5) = + und E(n+7,5) = + =>
E(n+6) = + und
E(n+7) = +

Zum Beispiel ist E(4) = - also E(10) = E(11) = +
und
wegen E(9) = - ist E(15) = E(16) = +
und
wegen E(17) = - ist E(23) = E(24) = +
\(\endgroup\)
 

Re: Streichholzspiel
von: scorp am: Fr. 25. Juli 2003 21:02:20
\(\begingroup\)
Hi plex und alle anderen,
mein Programm ist fertig und packt bis (30) und das in akzeptabler Zeit. Wer es will soll mir PMen dann schick ich euch den Link.

> Die Folgezustände von (5) sind (4),(3),(1,2) und (1,3) ~ (1,1,2) ~ (2)

Du hast (2,2) vergessen, macht aber keinen Unterschied, glaube ich.

> Wenn also E(z) = - für irgendeinen Zustand z.
Dann ist E(z,5) = - .

Wow. Bin beeindruckt. :)
Mal sehen ob ich das verwenden kann um noch mehr Tempo raus zu holen. Leider wird der Umkehrschluss nicht gelten...

> Also müßte, da nach deinem Programm E(5,5,5) = - ist E( n+3 * (5)) = - sein für alle n.

Fast; das alte war buggy. Es ist E(n*(5)) = +

Ausserdem sind verloren
(1) , (4) , (9) , (12) , (20)
Bis 31 (inkl.) sind alle anderen gewonnen. Ich hatte oben mehrfach Gegenteiliges behauptet.

@plex: Kannst du das soweit (15) bestaetigen?

Desweiteren draengt sich mir auf, dass Site recht hatte als er schwammig meinte, "je mehr Steine desto mehr Siegsituationen".
Ich habe mir die ersten n Stellungen (Umrechnung nebensaechlich) rechnen lassen und dazu den prozentualen Anteil an siegen. Ich schreibe S(n) fuer den prozentualen Anteil an Siegstellungen in den ersten n moeglichen Zustaenden.

S(1000) = 75
S(10000) = 76
S(100000) = 77
S(1000000) = 78
..riecht, bzw stinkt schon fast logarithmisch.


Viele Gruesse,
/Alex\(\endgroup\)
 

Re: Streichholzspiel
von: Plex_Inphinity am: Fr. 25. Juli 2003 21:06:50
\(\begingroup\)
argl, ich fürchte (2,2) macht doch einen Unterschied weil so der Zugzwang wegfällt. hmpf, also kann man das vergessen :(.\(\endgroup\)
 

Re: Streichholzspiel
von: scorp am: Fr. 25. Juli 2003 21:18:13
\(\begingroup\)
Hi,

wen's interessiert: Site und ich haben heute Mittag noch etwas rausgefunden. Bestehe ein Zustand Z aus beliebig vielen Gruppen. Die Stellung ist gewonnen, wenn es moeglich ist, die Gruppen so auf zwei Mengen zu verteilen, dass beide Mengen fuer sich verloren sind:

E[A] = -
E[B] = -
=>
E[(A,B)] = +


@plex: Schlechte Nachricht, du hast recht:
E[3,2,1] = -
und
E[3,2,1,2,2] = -

:-/

Gruesse,
/Alex\(\endgroup\)
 

Re: Streichholzspiel
von: scorp am: Fr. 25. Juli 2003 21:20:48
\(\begingroup\)
Oh, der Gegenbeweis zu dir passt ja auch auf die obere Behauptung. Das' aber gar nicht gut..!?
Bleibt die Frage, ob's am Programm liegt.\(\endgroup\)
 

Re: Streichholzspiel
von: Plex_Inphinity am: Fr. 25. Juli 2003 21:21:26
\(\begingroup\)
Ah moment, vielleicht kann da noch was retten, wenn man statt (5) (4,1) nimmt.
Denn (4,1) hat die Folgezustände (3,1) , (2,1) , (1,1,1) , (4)

und es gilt E(n) = -   =>  E(n,3,1) = E(n,2,1) = E(n,1,1,1) = E(n,4) = + , da Spieler 1 immer auf den Zustand E(n,1,1) = - kommen kann.

Also müßte es richtig heissen
E(n) = - => E(n,4,1) = -

Man denke sich also überall oben, wo (5) steht (4,1) :). Ich hoffe ich habe mich nicht schon wieder vertan.\(\endgroup\)
 

Re: Streichholzspiel
von: scorp am: Fr. 25. Juli 2003 21:31:11
\(\begingroup\)
> Denn (4,1) hat die Folgezustände (3,1) , (2,1) , (1,1,1) , (4)

Auch nicht ganz. Zur Kontrolle: Es hat bei ungleichem a und b E[a,b] immer a+b Folgezustaende. Du hast (2) vergessen.

=P,
Gruss,
/Alex\(\endgroup\)
 

Re: Streichholzspiel
von: Plex_Inphinity am: Fr. 25. Juli 2003 21:35:24
\(\begingroup\)
Wegen der Umkehrrichtung:

Es gilt E(n) = - => E(n,4,1) = -
also auch
E(n,4,1) = + => E(n) = +
denn wäre E(n) = - dann wäre ja E(n,4,1) = - => Widerspruch.

Ich habe die ersten 14 Ergebnisse in der korrigierten Fassung mit meinem Programm auch ausgerechnet. Die Wahrscheinlichkeit, dass dein Programm richtig arbeitet ist also gestiegen :). In welcher Sprache hast du es geschrieben? Ich hab meins in C unter Linux geschrieben, was ein Fehler war, da die Speicherverwaltung mit free() und malloc() einfach grauslich ist.\(\endgroup\)
 

Re: Streichholzspiel
von: Plex_Inphinity am: Fr. 25. Juli 2003 21:39:59
\(\begingroup\)
(2) würde keinen Unterschied machen, aber (2) ist kein Folgezustand von (4,1) . Entweder ich nehme das eine Streichholz, dann hab ich (4) oder ich nehme welche aus dem (4)-er stapel, dann bleibt aber immer ein (1)-er Stapel übrig.\(\endgroup\)
 

Re: Streichholzspiel
von: scorp am: Fr. 25. Juli 2003 21:47:27
\(\begingroup\)
> Ich hab meins in C unter Linux geschrieben, was ein Fehler war, da die Speicherverwaltung mit free() und malloc() einfach grauslich ist.

Zumindest bist du der moralische Sieger, ich habe windoof und Delphi verwendet. Hat erstaunlich wenig Probleme gemacht.

> (2) ist kein Folgezustand von (4,1) .

Doch, indirekt: (4) -> (2,1) <=> (4,1) -> (2,1,1) =~ (2). Stimmt doch hoffentlich?

Gruesse.


Vorschlag: Wir ziehen ins Forum.
- da lesen es mehr
- es ist uebersichtlicher
- mach kann nachtraeglich aendern
- es komt immer wieder nach oben, hier verschwindet es bald in der Versenkung.\(\endgroup\)
 

Re: Streichholzspiel
von: Plex_Inphinity am: Fr. 25. Juli 2003 22:08:16
\(\begingroup\)
Guter Vorschlag, ich habe im Rätselforum gleich mal ein Topic eröffnet.
Also alle zukünftigen Beiträge bitte hier reinschreiben.
Wegen der (2) hast du natürlich recht, aber es macht wie gesagt glücklicherweise keinen Unterschied.

\(\endgroup\)
 

Re: Streichholzspiel
von: Ex_Mitglied_40174 am: Sa. 20. Mai 2006 21:59:21
\(\begingroup\)
Hey kann mir jemand ganz kurz und päzise sagen wie die spielstrategie aus sieht
\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]