Gewinnstrategie eines Löschspiels „Rand oder isolierter Scheitelpunkt“

11

Ist dieses perfekte Informationsspiel, das auf Grafiken gespielt wird, bekannt / studiert?

Bei einem Graphen wählen zwei Spieler abwechselnd eine Kante oder einen isolierten Knoten aus. Wenn der Spieler eine Kante die beiden Knoten und zusammen mit ihren einfallenden Kanten gelöscht. Wenn der Spieler einen isolierten Knoten auswählt, wird der Knoten gelöscht. Der erste Spieler, der sich nicht bewegen kann, verliert das Spiel. e = ( u , v ) u vG=(V,E)e=(u,v)uv

Wie komplex ist es, den Gewinner zu finden?

Irgendwelche Verweise auf ähnliche Spiele?

Marzio De Biasi
quelle
1
Ich gehe davon aus, dass der isolierte Knoten entfernt wird, wenn er ausgewählt wird. In diesem Fall gewinnt Spieler 0 auch auf allen nicht leeren Pfaden, indem er den ersten Zug damit verbringt, das Problem in zwei gleiche Komponenten zu unterteilen und dann die gegnerischen Bewegungen von da an auf die entgegengesetzte Komponente zu spiegeln, um den Isomorphismus aufrechtzuerhalten. Dies bedeutet, dass Spieler 1 in einem Zyklus gewinnt, da der erste Zug das Problem auf einen Pfad reduziert.
Yonatan N
2
@YonatanN: Ja, ein isolierter Knoten kann ausgewählt (und entfernt) werden. Die Simmetrie-Strategie funktioniert jedoch auf Pfaden mit gerader Länge (Spieler 0 wählt die 2 zentralen Knoten als ersten Zug aus und spiegelt dann die Züge von Spieler 1 wider), jedoch nicht auf Pfaden mit ungerader Länge: Versuchen Sie, die Strategie auf einen Pfad mit langer Länge anzuwenden 11, und es funktioniert nicht (tatsächlich ist der Gewinner für einen Pfad der Länge 11 Spieler 1).
Marzio De Biasi
5
@Marzio De Biasi: Es tut mir leid, aber wenn ich schöne Spiele spiele, spiele ich normalerweise von Hand. Wenn ich keine Fehler gemacht habe, hat Spieler 0 eine Gewinnstrategie: Beachten Sie Folgendes: a) Für P1, P2, P5 und P8 gewinnt Spieler 0 immer. b) Bei P3 und P7 gewinnt immer Spieler 1. c) Für P4 und P6 kann Spieler 0 entscheiden, ob er gewinnt oder verliert. Jetzt im Fall von P11: - Nummerieren Sie die Knoten von P11 mit v1, v2, ... v11. - Spieler 0 nimmt die Kante v9, v10 und der Rest ist der isolierte Knoten v11 und P8. Wenn Spieler 1 v11 nimmt, gewinnt Spieler 0, weil er einen geraden Weg hat. Andernfalls gewinnt Spieler 0 mit a), b) und c).
user13136
1
Nach meinem Programm sind die Werte von n ≤ 100, so dass der erste Spieler im Spiel auf dem Pfad mit n Eckpunkten verliert, 3, 7, 23, 27, 37, 41, 57, 61, 71, 75, 91 und 95. Leider sehe ich kein anderes Muster als ungerade (was bereits bekannt war), und OEIS zeigt keine Übereinstimmungen an.
Tsuyoshi Ito
1
@TsuyoshiIto: ... nimm die paarweise Differenz: (3 7) (23 27) (37 41) (57 61) (71 75) (91 95) und du bekommst 4 4 4 4 4 4 ... es scheint a Muster :-) .... (3 ... 23) ... (37 ... 57) ... (71 ... 91) und du bekommst 20 20 20 ... noch einen! :-D
Marzio De Biasi

Antworten:

2

Ich poste ein Update nur als Selbstantwort, um es von der noch offenen Frage zu unterscheiden .

Wie in den Kommentaren gezeigt (dank Tsuyoshi Ito), ist das Problem in der Polynomzeit für Pfade lösbar:

Win(Pn)=1 iif(nmod34){3,7,23,27}

Ab 0 ist die (berechnete) Folge der Nim-Werte periodisch:

0,1,1,0,2,1,3,0,1,1,3,2,2,3,4,1,5,3,2,2,3,1,1,0,3,1,2,0,1,1,4,4,2,6,
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6,
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6,
...
the subsequence rseq of length 34:
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6
is repeated

Ich habe nicht an einem strengen mathematischen Beweis gearbeitet, aber die Idee ist:

Angenommen, wir wollen das Element berechnen , dann kann die erste Bewegung (eine Kante auswählen) den Pfad auf verschiedene Arten (n-2,0), (n-3, 1), (n-4,2), ...). Der neue Nim-Wert ist gleich:Win(Pn),n=k34+x(k4,0x<34)n/2

mex{Pn2+P0,Pn3+P1,...,Pn/2+Pnn/2}

Die ersten 34 Elemente der Menge werden durch die erste nicht wiederholte Sequenz (0,1,1,0, ...) (nim) erzeugt, die mit den Elementen der sich wiederholenden Sequenz in umgekehrter Reihenfolge beginnend mit Element .(342x)mod34

Zum Beispiel: für :x=0

     0,1,1,0,2,1,3,0,1,1,3,2,2,3,4,1,5,3,2,2,3,1,1,0,3,1,2,0,1,1,4,4,2,6 +
     3,4,4,1,1,0,2,1,3,0,1,1,3,2,2,7,5,4,4,3,2,2,3,1,1,0,3,1,2,0,1,1,4,6 =
mex{ 3,5,5,1,3,1,1,1,2,1,2,3,1,1,6,6,0,7,6,1,1,3,2,1,2,1,1,1,3,1,5,5,6,0 } = 4

Für x = 0..33 ist die resultierende mex-Sequenz gleich der sich wiederholenden Sequenz:

4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6

Die verbleibenden Elemente der Menge werden nur für die Wiederholungssequenz (en) : (für die Paare also wiederholt Sie ändern das mex-Ergebnis nicht. Die resultierende mex-Sequenz für x = 0..33 lautet:rseq[jmod34]+rseq[(342xj)mod34]j34

4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,4,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,4,

Welches ist gleich der Wiederholungssequenz mit Ausnahme von und ; aber die Werte sind niedriger als das entsprechende mex in der nicht wiederholenden Sequenz, also:x=16x=33

mex{Pn2+P0,Pn3+P1,...,Pn/2+Pnn/2} =mex{Pn2+P0,Pn3+P1,...,Pn233+P33}

und für ist(k4,0x<34)Win(Pk34+x)=Win(P34+x)=Win(Px)

Marzio De Biasi
quelle
Nach meiner Berechnung hat der erste Spieler eine Gewinnstrategie für , die ein Gegenbeispiel zu Ihrer Behauptung gibt. iff . P23Win(Pn)=1(nmod34){3,7,23,27}
user13136
@ user13136: hast du die nim Werte überprüft? Für der nim-Wert 0 (ich habe die gleichen Werte von Tsuyoshi mit einem anderen Programm erhalten, aber vielleicht liegen wir beide falsch). P23
Marzio De Biasi
Ich denke, ein möglicher Fehler in Ihren Programmen könnte das Ignorieren des . In diesem Fall verliert der erste Spieler immer. Wenn Sie möchten, können wir jetzt den Fall . P0P23
user13136
Entschuldigung, ich muss jetzt gehen.
user13136
(n17,n18)(n5,n6)(n11,n12)(n1,n2) (Sie können die vorherigen Kommentare mit den Zügen löschen)
Marzio De Biasi