Matroids Matheplanet Forum Index
Moderiert von viertel
Matroids Matheplanet Forum Index » Rätsel und Knobeleien (Knobelecke) » Fortsetzung des Threads zum Artikel "Streichholzspiel"
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Fortsetzung des Threads zum Artikel "Streichholzspiel"
Plex_Inphinity
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.05.2002
Mitteilungen: 3601
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2003-07-25


hier kann weiterdiskutiert werden

bezieht sich auf den Artikel
Streichholzspiel



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Dies ist eine Knobelaufgabe!
Bitte poste Lösungen zu dieser Aufgabe nur dann im Forum, wenn der Themensteller das verbal in seinem Aufgabentext erwähnt hat. Sonst antworte ihm in einer privaten Nachricht. (Hinweis: Diese Knobelaufgabe wurde gestellt, bevor es die explizite Einstellung 'Antworten nur mit privater Nachricht' gab.)
scorp
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.10.2002
Mitteilungen: 4341
Wohnort: Karlsruhe
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2003-07-25


Hi!

Ein paar Worte zu Beginn fuer die, die keine Lust haben alle Kommentare zu lesen:

Einfuehrung

Nachdem der Artikel unweigerlich in der Versenkung verschwindet und das Forum hier viel mehr Komfort bietet als die Kommentarumgebung zu den Artikeln werden wir die Diskussion zu Friedel's NIM-Spiel hier fortsetzen.

Die Regeln

Man lege  n  Hoelzchen in eine ununterbrochene Reihe. Zwei Spieler nehmen abwechselnd mindestens eines, aber hoechstens zwei Hoelzchen. Letztere muessen benachbart sein; es darf keine Luecke zwischen ihnen liegen. Wer das letzte nimmt, verliert das Spiel.

Kurzer Ueberblick

Im Folgenden bewerten wir den momentanen Zustand immer so, als seien wir am Zug. Liegt nur noch ein Hoelzchen auf dem Tisch verlieren wir trivialerweise das Spiel.
Liegen noch drei nehmen wir zwei davon weg und gewinnen. Leider geht es nicht immer so einfach. Verbleiben z.B. vier Hoelzchen verlieren wir das Spiel (selbst ausprobieren).

Terminologie

Eine ununterbrochene Reihe von Hoelzern nennen wir "Gruppe". Ein Zustand wird dargestellt, indem man angibt wieviele Hoelzer die einzelnen Gruppen umfassen, z.B.  [5,1].
Um Gewinn- und Verluststellungen zu beschreiben benutzen wir folgende Schreibweise: Sei Z ein bel. Zustand:  E(Z) = +/-.
Sind zwei Stellungen A und B nicht gleich, haben aber gleiche Folgezustaende oder unterscheiden sich lediglich durch eine gerade Anzahl an Einsergruppen so heissen diese "aequivalent" und wir schreiben  [A] =~ [B]

Was bisher geschah

Einige Planetarier beissen sich seit Veroeffentlichung des Spiels die Zaehne daran aus, eine allgemeine Vorschrift ausfindig zu machen, um heraus zu finden, welche Spielstellungen gewonnen sind und welche nicht.
Hier kurz zusammengefasst die wichtigsten Ergebnisse:

[3] =~ [2,1]
[Z] =~ [Z,1,1]
[Z,3] =~ [Z,2,1]

E(1) = -
E(4) = -
E(9) = -
E(12) = -
E(20) = -

...alle anderen bis 31 sind gewonnen.

Ausfuehrliches ist unter dem obigen Link nachzulesen.

Viele Gruesse,
/Alex

[ Nachricht wurde editiert von scorp am 2003-07-25 22:22 ]

[ Nachricht wurde editiert von scorp am 2003-07-25 22:23 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
scorp
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.10.2002
Mitteilungen: 4341
Wohnort: Karlsruhe
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2003-07-25


Und hier nochmal Plex' Ansatz:

fed-Code einblenden

Weiter vereinfachen geht wohl nicht.

Gruss.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
scorp
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.10.2002
Mitteilungen: 4341
Wohnort: Karlsruhe
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2003-07-26


Hallo Knobelfreunde!

Tabelle aller Zustaende [a,b]; a,bÎIN0 Ù a+b£28

Bild

Ich verneige mich vor dem, der alle auftretenden Regelmaessigkeiten in eine Formel zu packen vermag...  

Gruss,
/Alex

[ Nachricht wurde editiert von scorp am 2003-07-26 11:40 ]

[ Nachricht wurde editiert von scorp am 2003-07-26 11:43 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Plex_Inphinity
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.05.2002
Mitteilungen: 3601
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2003-07-26


Ich habe im Netz etwas über dieses Spiel gefunden.
Es ist eher bekannt unter dem Namen Kayles, wobei beim normalen Kayles jedoch derjenige gewinnt, der als letzter ziehen kann.
Die andere Variante wird Misère Kayles genannt und wurde 1973 schon gelöst.
Die Lösung kann man anscheinend in dem Artikel
"Sibert WL, Conway JH (1992) Mathematical Kayles Int. J. Game Theory 20:237 - 246"
nachlesen. Ist aber leider nicht im Netz verfügbar, zumindest habe ich ihn nicht gefunden.
Nur diesen Artikel, der sich auf obigen bezieht. Scheint aber nicht so einfach zu sein...

[ Nachricht wurde editiert von Plex_Inphinity am 2003-07-26 17:51 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Friedel
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.05.2002
Mitteilungen: 332
Wohnort: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2003-07-27


Nachdem ich mal wieder ein paar Tage beruflich unterwegs war, muss ich feststellen, dass sich viel getan hat. Aber eine einfache Formel, mit der man bestimmen kann ob man es ion einer bestimmten Stellung mit einer Gewinstellung zu tun hat, hat auch vo euch bisher keiner gefunden. Ich habe noch nichtv alles gelesen und nachvollzogen, werde das aber in nächster Zeit nachholen. Der Link von Plex_Inphinity zu Kayles sollte wohl die Lösung bringen. Ich kannte Misère Kayles bisher nicht.

An den entstandenen Programmen hätte ich schon Interesse. Nicht wegen dem Programm, spndern wegen dem Algorhythmus. Leider kann ich weder C noch Delphi. Schade. Ich nehme an, die Programme untersuchen nicht die vorhandene Stellung auf Lösbarkeit, sondern sie erzeugen ein Datenbank mit Gewinnstellungen. Natürlich ist die andere Variante die schönere, was bei Nim-Spielen ja auch problemlos möglich ist. In diesem Fall muss ich mich aber wohl mit der Datenbank begnügen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
scorp
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.10.2002
Mitteilungen: 4341
Wohnort: Karlsruhe
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2003-07-27


Hallo Friedel,

Nicht wegen dem Programm, spndern wegen dem Algorhythmus.

Der is (bei mir) simpel: Rekursion. Berechnung aller moeglichen Folgezustaende, anschliessend doppelte und aequivalente kuerzen und die Prozedur fuer jeden Folgezustand erneut aufrufen, bis eine verlorene Folgestellung ausgemacht ist.
Uebrigens: Der Algorithmus hat nur sehr entfernt musikalische Zuege  

Ich nehme an, die Programme untersuchen nicht die vorhandene Stellung auf Lösbarkeit, sondern sie erzeugen ein Datenbank mit Gewinnstellungen.

Wenn ich dich richtig verstanden habe, macht das keinen Sinn. Denn das wuerde bedeuten, dass wir haetten jede Stellung von Hand eingeben muessen wie das Ergebnis lautet um anschliessend auf diese Datenbank zurueck zu greifen. Das waere nicht machbar.

Bei mir gibt es die Option, ob er mitlernen soll, das gelernte Wissen verwenden darf, oder stur alles bis zum letzten Stein durchrechnen soll. Bei letzterem gibt's aber ab zehn und mehr Steinen erhebliche Probleme.

Gruss,
/Alex

Nachwort: Ich finde es uebrigens ziemlich gewagt von dir unsere Programme runter zu reden ("mit der Datenbank begnuegen"), _bevor_ du sie ueberhaupt gesehen bzw getestet hast.

[ Nachricht wurde editiert von scorp am 2003-07-27 15:59 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Pagan
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 23.07.2003
Mitteilungen: 23
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2003-07-28


Sehr interesannt, ich glaube hiermit kann ich auch meine Nachmittage verbringen ....

Sag mal scorp, wie hast du das gezeigt :
E[A] = - und E[B] = - =>  E[(A,B)] = +  ??
Was ist mit allen anderen kombinationen,
E[A] = - und E[B] = - =>  E[(A,B)] = ?  
E[A] = + und E[B] = - =>  E[(A,B)] = ?
E[A] = + und E[B] = + =>  E[(A,B)] = ?

Seh ich das richtig wenn man für jeden beliebigen n aus N , E(n) angeben kann, das man dann E von jedem beliebigen Zustand angeben kann?



Wieos kann ich den Springer Artikel nicht sehen? Muss ich da irgendwie abonennt sien ??


Grüße, Pagan


[ Nachricht wurde editiert von Pagan am 2003-07-28 14:24 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
scorp
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.10.2002
Mitteilungen: 4341
Wohnort: Karlsruhe
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2003-07-28


Hallo Pagan.

Das hier:  E[A] = - und E[B] = - =>  E[(A,B)] = +  habe ich nicht gezeigt, nur behauptet. Der angebliche Beweis stammte von jemand anderem, aber wie gesagt: Es stimmt nicht. Es ist E[2,2]=- aber E[2,2,2,2]=-. Nix war's.

Ich glaube nicht, dass man so einfach argumentieren kann (x:=E[A], y:=E[B], => E[A,B]=f(x,y)).

Seh ich das richtig wenn man für jeden beliebigen n aus N , E(n) angeben kann, das man dann E von jedem beliebigen Zustand angeben kann?

Nein. So einfach ist es (glaube ich) nicht.

Gruss,
/Alex



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Anonymous
Unregistrierter Benutzer
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2003-08-27


Hallo,
bin kein Mathematiker und habe nicht alle posts gelesen. Geht es darum zu beweisen, daß es für jeden Anfangszustand (Zahl der Hölzer) eine und nur eine determinierte Lösung gibt (solange niemand einen fehler macht), oder soll auch gezeigt werrden, wie diese Lösung jeweils für n Hölzer genau aussieht (wer also gewinnt)?
Das erste ist recht einfach zu beweisen, das zweite wohl eher etwas schwierig.
mfg



Eine Notiz zu diese Forumbeitrag schreiben Notiz  Quote  Link auf diesen Beitrag Link
scorp
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.10.2002
Mitteilungen: 4341
Wohnort: Karlsruhe
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2003-08-27


Hallo anonymous,
natuerlich das zweite.  

Wir suchen noch immer eine Formel die ausdrueckt wer gewinnt, wenn n Hoelzchen auf dem Tisch liegen und beide Spieler ideal spielen.

Gruss.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Jockel
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 30.01.2003
Mitteilungen: 1006
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2003-08-28


In dem Zusammenhang:

Ich hab mal ein anderes Streichholzspiel als Java-Applet geschrieben.
Regeln:
Hölzer werden wie folgt aufgebaut:
   |
  |||
 |||||
|||||||

Jeder der 2 Spieler darf num Abwechselnd beliebig viele Hölzer
entfernen, aber immer nur aus einer Reihe.
Wer das letzte Stäbchen ziehen muss, der hat verloren.

Sieht billig aus, hat mich aber ein Wochenende zur Lösung gekostet.
Leiderhabe ich keine Seite, auf der ich das Spiel verfügbar machen
kann. Bei Interesse würde ich es aber gerne zu mailen.

Jockel



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Friedel
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.05.2002
Mitteilungen: 332
Wohnort: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2003-08-30


Hallo Jockel
Dein Spiel ist unter dem Namen 1-3-5-7 bekannt und für dieses Spiel ist der Lösungalgorhythmus vergleichsweise einfach. Es handelt sich um eine Nim-Variante. Aber dein Postind bringt mich auf eine Idee für einen neuen Artikel. ber das muss warten, bis die Sommeraufträge erledigt sind.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Anonymous
Unregistrierter Benutzer
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2003-09-02


Da war ich gerade auf der Suche nach dem oben erwaehnten Artikel "Mathematical Kayles" von Silbert und Conway, und bin dabei zufaellig auf Eure Diskussion gestossen.
War recht interessant Euren Ausfuehrungen zu folgen - hab' aber nicht alles genau angeguckt!
Was Ihr Euch mal mit Sicherheit genauer angucken koenntet, sind die Buecher "Winning Ways for Your Mathematical Plays" von Berlekamp, Conway und Guy.
Da sind sowohl die Gewinnstrategie fuer normales Kayles (Vol. 1, Kapitel 4) als auch fuer die Misere Variante (Vol. 2, pp 446-451) beschrieben - neben vielem, vielem anderem!
Ihr braucht also eigentlich nicht mehr weiter zu suchen, es sei denn, Ihr wollt noch andere Gewinnstrategien finden.:-)
Von einer "geschlossenen Formel" kann man aber natuerlich nicht direkt reden!;-)

Uebrigens wenn Ihr mal das normale Kayles spielen wollt, koennt Ihr das auch zum Beispiel auf meiner Webseite:
ihome.ust.hk/~trippen/MSRI/triang.html

Und zu Friedels Ehrenrettung:
Wir brauchen zwar Algorithmen, um diese Probleme zu loesen, aber diese Nim-Spiele haben durchaus manchmal Rhythmen, siehe z. Bsp. Seite 97 in Vol. 1 der oben erwaehnten Buecher: "The .6 Waltz".

Gruesse aus Hong Kong,
Gerhard

P.S.: Ich habe den Artikel letztendlich auch nicht online finden koennen und ihn mir daher jetzt ueber die Bibliothek bestellt.
(Bei Springer muss man uebrigens registriert sein, um Zugriff auf die Artikel zu haben!)



Eine Notiz zu diese Forumbeitrag schreiben Notiz  Quote  Link auf diesen Beitrag Link
Anonymous
Unregistrierter Benutzer
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2003-09-26


The Sibert-Conway solution to misere Kayles is described on the web
in this document,

"Pretending in Misere Combinatorial Games"

www.qxmail.com/mathematics/games/misere/genus/miseregames.pdf

in section 5.2

Alles gute!

Thane Plambeck



Eine Notiz zu diese Forumbeitrag schreiben Notiz  Quote  Link auf diesen Beitrag Link
Friedel
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.05.2002
Mitteilungen: 332
Wohnort: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2007-05-17


Inzwischen ist viel Zeit vergangen. Ich bin zufällig durch Google auf meine alte Frage gestoßen. Wir alle haben uns damals viel zu sehr den Kopf zerbrochen. Die Gewinnstrategie ist ganz einfach.

Zunächst beschreibe ich mal eine Strategie nach der man immer gewinnt, wenn es darum geht, dass derjenige Gewinnt, der das letzte Holz nimmt. Also umgekehrt wie die normale Spielregel.

Es gibt 2 mögliche Fälle.
- Wenn es am Angang nur ein Hölzchen gibt, gewinnt zwangsläufig derjenige, der anfängt.
- Im anderen Fall gibt es mehr Hölzer. Wenn die Zahl der Hölzer gerade ist, nimmt man die mittleren beiden Hölzer. Ansonsten nimmt man das mittlere Holz. Wenn es am Anfang nur 2 Hölzer waren, hat man jetzt schon gewonnen. Ansonsten gibt es jetzt zwisch gleiche Gruppen. Was auch immer der Gegner jetzt in einer Gruppe macht, man macht das selbe in der anderen Gruppe. So bekommt man zwangsläufig das letzte Holz.

Wenn derjenige verliert, der das letzte Holz bekommt, spielt man nach der selben Strategie. Mit dieser Strategie hat man nämlich die Wahl wer das letzte Holz bekommen soll. Man muss nur in dem Moment, in dem nur noch 1 Reihe mit mehreren Hölzern vorhanden ist so nehmen, dass danach eine ungerade Anzahl von Einzelhölzern liegen bleibt. Man ist zu diesem Zeitpunkt zwangsläufig an der Reihe, denn wenn der Gegner dran ist, treten die Reihen ja immer paarweise auf.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Plex_Inphinity
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.05.2002
Mitteilungen: 3601
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, vom Themenstarter, eingetragen 2007-05-17


Hi Friedel,

ja inzwischen ist ziemlich viel Zeit vergangen smile .
Also deine Strategie für den Fall, dass derjenige gewinnt, der das letzte Streichholz nimmt, sehe ich ein. Die ist auch recht clever.
Aber für den anderen Fall klappt die Strategie doch nicht.
Wenn zum Beispiel am Anfang 4 Streichhölzer in einer Reihe liegen, nimmt Spieler 1 nach deiner Strategie erst die mittleren beiden. Dann nimmt Spieler 2 irgendeines der verbleibenden zwei und Spieler 1 muß das letzte nehmen, hat also verloren.
Scorps Tabelle zeigt doch auch schon, dass nicht immer derjenige gewinnt, der anfängt, sondern es davon abhängt, mit wievielen Hölzchen man beginnt.

@Gerhard und Thane Plambeck:
Auch schon ein Weilchen her, aber trotzdem ein verspätetes Dankeschön für die Hinweise.

Das Paper von Thane Plambeck liegt jetzt hier:
www.plambeck.org/archives/miseregames.pdf

Gruß
Plex

[ Nachricht wurde editiert von Plex_Inphinity am 18.05.2007 00:02:42 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Friedel
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.05.2002
Mitteilungen: 332
Wohnort: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2007-05-18


Stimmt. Die Strategie funktioniert nur bei mindestens 5 Hölzern, wenn derjenige verliert, der das letzte Holz bekommt. Bei 1 Holz verliert der Anfangende zwangläufig. Bei 2 Hölzern muss er 1 Holz nehmen um zu gewinnen. Bei 3 Hölzern nimmt er 2 Hölzer. Bei 4 Hölzern verliert er, wenn der Gegner richtig nimmt. Der Anfangende gewinnt also immer, wenn am Anfang nicht 1 oder 4 Hölzer auf dem Tisch liegen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Plex_Inphinity
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.05.2002
Mitteilungen: 3601
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, vom Themenstarter, eingetragen 2007-05-18


Die Strategie funktioniert auch nicht bei 9,12,20,... Hölzern. Siehe Scorps Tabelle.
Bei 9 nimmt der zweite Spieler die mittleren beiden Hölzer aus einer Gruppe. Spieler 1 kopiert das in der zweiten Gruppe => Es bleiben 4 einzelne Hölzer liegen.
Spieler 2 nimmt eins
Spieler 1 nimmt eins
Spieler 2 nimmt eins
Spieler 1 nimmt eins und hat verloren.





Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Friedel
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 09.05.2002
Mitteilungen: 332
Wohnort: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2007-05-19


Mist. Wenn der Gegner die mittleren beiden Hölzer aus der einen Gruppe nimmt, liegt nur noch eine Gruppe mit mehr als 1 Holz da. Ich müsste nach meiner Strategie also so nehmen, dass eine ungerade Anzahl von Einzelhölzern liegen bleibt. Das ist aber gar nicht möglich bei 4+2n Hölzern. Wäre wohl auch zu scön gewesen, wenn es so einfach lösbar wäre.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten
algol
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 19.03.2008
Mitteilungen: 19
Wohnort: Schweiz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, eingetragen 2021-06-19


SGV: Sprague-Grundy values

      0010100111001011101111000
1X
2X
3X
4X
5X
6X
7X
8X
9X
10X
11X
12X
13X
14X
15X
16X
17X
18X
19X
20X
21X
22X
23X
24X
25X
26X
27X
28X
29X
30X
Data source: oeis.org/A002186

Ich beziehe mich hier nur auf Kayles, nicht auf Nim oder ähnliche Streich­holz­spiele.

Eine Position bestehe aus Gruppen von Kegeln (oder Steinen), getrennt durch Lücken. Die Ge­winn­po­si­tio­nen findet man fol­gen­der­mas­sen heraus: OEIS A002186 («The On-Line Encyclopedia of Integer Sequences», oeis.org), liefert zu jeder Grup­pen­grös­se einen Sprague-Grundy value (SGV). Wenn die binäre Summe dieser SGV mod 2 (oder exklusives Oder, EXOR, ⊕) = 000 ist, hat man eine Gewinnposition.

Beispiele:

1—4       → 001 ⊕ 001 = 000
3—4—10    → 011 ⊕ 001 ⊕ 010 = 000
1—2—3—4—8 → 001 ⊕ 010 ⊕ 011 ⊕ 001 ⊕ 001 = 000
und natürlich alle x—x, weil 001 ⊕ 001 = 000 usw.
Somit alle Kombinationspaare aus einer SGV-Kolonne.

Spielablauf-Beispiel:

Spieler A erstelle 1—3—5—7—9 → 001 ⊕ 011 ⊕ 100 ⊕ 010 ⊕ 100 = 000
Spieler B teilt Gruppe 9 auf in 4—4
Spieler A analysiert 1—3—5—7—4—4: 4—4 ist Gewinn-(teil-)Position,
bleibt noch, aus 1—3—5—7 eine weitere Gewinn-(teil-)Position zu machen:
SGV 1—3—5—7 → 001 ⊕ 011 ⊕ 100 ⊕ 010 = 100,
somit ist SGV 100 (also Gruppe 5) zu eliminieren.
Aus 5 mache 2—2, somit erstellt Spieler A 1—3—2—2—7—4—4
mit den Gewinnpositionen 1—3—7, 2—2 und 4—4
Wenn nun Spieler B 2—2 oder 4—4 verändert, kann A parallel nachziehen, oder
falls B aus 1—3—7 z.B. 3—7 macht, erstellt A 3—6, usw.

Der von Gerhard aus Hongkong angegebene Link für sein pro­gram­mier­tes Kayles exis­tiert nicht mehr (404 Not Found). Ich habe un­ab­hän­gig davon ein Kayles-Spiel pro­gram­miert und ins In­ter­net gestellt: sfs-witikon.ch/gehirntraining/kayles. Man kann entweder vom Computer eine zu­fäl­li­ge Start­po­si­tion er­zeu­gen las­sen und darf be­gin­nen. Oder man er­stellt sel­ber eine An­fangs­po­si­tion, dann beginnt der Com­pu­ter mit dem ersten Zug.

Viel Vergnügen!

Jörg




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Dies ist eine Knobelaufgabe!
Bitte poste Lösungen zu dieser Aufgabe nur dann im Forum, wenn der Themensteller das verbal in seinem Aufgabentext erwähnt hat. Sonst antworte ihm in einer privaten Nachricht. (Hinweis: Diese Knobelaufgabe wurde gestellt, bevor es die explizite Einstellung 'Antworten nur mit privater Nachricht' gab.)
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
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]