Permutationsspiel Redux

20

Dies ist eine Wiederholung einer früheren Frage .

Betrachten Sie das folgende unparteiische, perfekte Informationsspiel zwischen zwei Spielern, Alice und Bob. Die Spieler erhalten eine Permutation der ganzen Zahlen 1 bis n. Bei jeder Runde verliert der aktuelle Spieler, wenn die aktuelle Permutation zunimmt, und der andere Spieler gewinnt. Andernfalls entfernt der aktuelle Spieler eine der Zahlen und das Spiel geht zum anderen Spieler über. Alice spielt zuerst. Beispielsweise:

  • (1,2,3,4) - Bob gewinnt per Definition sofort.

  • (4,3,2,1) - Alice gewinnt nach drei Runden, egal wie jemand spielt.

  • (2,4,1,3) - Bob kann in seinem ersten Zug gewinnen, egal wie Alice spielt.

  • (1,3,2,4) - Alice gewinnt sofort, indem sie die 2 oder die 3 entfernt; Andernfalls kann Bob in seinem ersten Zug gewinnen, indem er die 2 oder die 3 entfernt.

  • (1,4,3,2) - Alice gewinnt schließlich, wenn sie in ihrem ersten Zug die 1 gewinnt; Andernfalls kann Bob in seinem ersten Zug gewinnen, indem er die 1 nicht entfernt.

Gibt es einen Polynom-Zeit-Algorithmus, um zu bestimmen, welcher Spieler dieses Spiel ausgehend von einer gegebenen Startpermutation gewinnt, vorausgesetzt, er spielt perfekt ? Da dies ein unparteiisches Standardspiel ist, hat im Allgemeinen jede Permutation einen Sprague-Grundy-Wert . Zum Beispiel hat (1,2,4,3) den Wert * 1 und (1,3,2) den Wert * 2. Wie schwer ist es, diesen Wert zu berechnen?

Die offensichtliche Backtracking - Algorithmus läuft in O (N!) Zeit, obwohl dies reduziert werden kann Zeit über dynamische Programmierung.O(2npoly(n))

Jeffε
quelle
4
Scheint mir, dass der naive Algorithmus in O (2 ^ n⋅poly (n)) läuft.
Tsuyoshi Ito
Aus Ihren Beispielen geht hervor, dass Alice immer gewinnt, wenn die Sequenz absteigend ist, und Bob immer gewinnt, wenn die Sequenz aufsteigend ist. Dieses Problem erinnert mich an die Analyse von Sortieralgorithmen, die ausgiebig untersucht wurden und die es Ihnen ermöglichen, ein breites Arsenal von Tools zu verwenden.
Chazisop
1
@chazisop: "Alice gewinnt immer, wenn die Reihenfolge absteigend ist": Das ist genau dann der Fall, wenn n gerade ist.
Tsuyoshi Ito
@ Jɛ ɛ E Wie gewinnt Bob in Fall 3 in seinem ersten Zug?
Suresh Venkat
2
@Suresh: Im Fall von (2,4,1,3) ist die Graphendarstellung der lineare Graph auf 4 Eckpunkten (2-1-4-3). Wenn Alice einen Endknoten entfernt, verbleibt der lineare Graph auf drei Eckpunkten. Bob gewinnt, indem er den mittleren Eckpunkt entfernt (also wird 3 mit 1 und 2 mit 4 beantwortet). Wenn Alice einen inneren Knoten entfernt, verbleiben zwei verbundene Scheitelpunkte und ein isolierter Knoten. Bob gewinnt, indem er einen der beiden verbundenen Eckpunkte entfernt (also wird 1 mit 3 oder 4 beantwortet und 4 mit 1 oder 2).
mjqxxxx

Antworten:

7

Das "Permutationsspiel" ist isomorph zu dem folgenden Spiel:

Trennen. Spieler abwechselnd Ecken aus einem Diagramm entfernen . Der Spieler, der eine vollständig getrennte Grafik erstellt (dh eine Grafik ohne Kanten), ist der Gewinner.G

Der Graph , der einer bestimmten Anfangspermutation π S n entspricht, enthält nur die Kanten ( i , j ), für die i - j und π ( i ) - π ( j ) entgegengesetzte Vorzeichen haben. Das heißt, jedes Zahlenpaar ist falschGππSn(i,j)ijπ(i)π(j)Ordnung in der Permutation ist mit einer Kante verbunden. Die erlaubten Züge sind eindeutig isomorph zu denen im Permutationsspiel (eine Zahl entfernen = einen Knoten entfernen), und die Gewinnbedingungen sind ebenfalls isomorph (keine Paare in absteigender Reihenfolge = keine Kanten übrig).

Eine komplementäre Ansicht wird erhalten, indem in Betracht gezogen wird, ein "duales" Spiel auf dem Graphenkomplement , das die Kanten ( i , j ) enthält, für die i und j in der Permutation in der richtigen Reihenfolge sind. Das duale Spiel zum Trennen ist:Gπc=GR(π)(i,j)ij

Erneut verbinden. Spieler abwechselnd Ecken aus einem Diagramm entfernen . Der Spieler, der eine vollständige Grafik erstellt, ist der Gewinner.G

Abhängig von der jeweiligen Permutation scheint eines dieser Spiele einfacher zu analysieren als das andere. Der Vorteil der Graphendarstellung ist, dass klar ist, dass nicht verbundene Komponenten des Graphen separate Spiele sind, und daher auf eine gewisse Reduzierung der Komplexität gehofft wird. Es macht auch die Symmetrien der Position deutlicher. Leider sind die Gewinnbedingungen nicht standardgemäß ... das Permutationsspiel endet immer, bevor alle Züge aufgebraucht sind, was ihm einen etwas miserablen Charakter verleiht . Insbesondere kann der Nim-Wert nicht als die Nim-Summe (binäres XOR) der Nim-Werte der getrennten Komponenten berechnet werden.


Für Disconnect ist es nicht schwer zu erkennen, dass für jeden Graphen und jedes gerade n das Spiel G ˉ K n gleich G ist (wobei ˉ K n der kantenlose Graph auf n Ecken ist). Um das zu beweisen, müssen wir zeigen , dass die disjunktive Summe G + G ˉ K n ist ein zweiter Spieler zu gewinnen. Der Beweis erfolgt durch Induktion am | G | + n . Wenn GGnGK¯nGK¯nnG+GK¯n|G|+nGist kantenlos, dann verliert der erste Spieler sofort (beide Spiele sind vorbei). Andernfalls kann der erste Spieler in beide bewegt , und der zweite Spieler seinen Zug in den andere kopieren kann (Reduzierung auf G ' + G '¯ K n mit | G ' | = | G | - 1 ); oder, wenn n 2 ist, kann sich der erste Spieler in der getrennten Figur bewegen und der zweite Spieler kann dasselbe tun (reduziert auf G + G ˉ K n - 2 ).GG+GKn¯|G|=|G|1n2G+GK¯n2

Dies zeigt, dass jeder Graph äquivalent zu H K p ist , wobei H der Teil von G ohne getrennte Eckpunkte ist und p = 0 oder 1 die Parität der Anzahl von getrennten Eckpunkten in G ist . Alle Spiele in einer Äquivalenzklasse haben den gleichen Nim-Wert, und außerdem respektiert die Äquivalenzrelation die Vereinigungsoperation: Wenn G H K p und G 'H 'K p ', dann GGHKpHGp=01GGHKpGHKp . Außerdem kann man sehen, dass die Spiele in [ H K 0 ] und [ H K 1 ] unterschiedliche Nim-Werte haben, es sei denn, H ist der Null-Graph: Wenn H + H K 1 gespielt wird , kann der erste Spieler das Isolierte nehmen Scheitelpunkt, lassen Sie H + H und kopieren Sie anschließend die Züge des zweiten Spielers.GG(HH)Kpp[HK0][HK1]HH+HK1H+H

Ich kenne keine verwandten Zersetzungsergebnisse für Reconnect.


Zwei spezielle Arten von Permutationen entsprechen besonders einfachen Heap-Spielen.

  1. Das erste ist eine aufsteigende Folge von Abfahrten , z . B. . Wenn π diese Form annimmt, ist der Graph G π eine Vereinigung von disjunkten Cliquen, und das Spiel Disconnect reduziert sich auf ein Spiel auf Haufen: Die Spieler entfernen abwechselnd eine einzelne Bohne von einem Haufen, bis alle Haufen die Größe 1 haben .32165487πGπ1
  2. Die zweite ist eine absteigende Aufstiegsstrecke , z . B. . Wenn π diese Form annimmt, ist der Graph G c π eine Vereinigung von disjunkten Cliquen, und das Spiel von Reconnect reduziert sich auf ein Spiel auf Haufen: Spieler entfernen abwechselnd eine einzelne Bohne von einem Haufen, bis nur noch ein Haufen übrig ist .78456123πGπc

Ein kleiner Gedanke zeigt, dass diese beiden unterschiedlichen Spiele auf Haufen (wir können sie 1-Haufen und Ein-Haufen nennen , bei denen die Gefahr einer Verwechslung besteht) tatsächlich selbst isomorph sind. Beides kann durch ein Spiel in einem Young-Diagramm (wie ursprünglich von @domotorp vorgeschlagen) dargestellt werden, bei dem die Spieler abwechselnd ein Feld rechts unten entfernen, bis nur noch eine Zeile übrig ist. Dies ist offensichtlich dasselbe Spiel wie 1-Heaps, wenn Spalten Heaps entsprechen, und dasselbe Spiel wie One-Heap, wenn Zeilen Heaps entsprechen.

Ein Schlüsselelement dieses Spiels, das sich auf Trennen und erneutes Verbinden erstreckt, ist, dass die Dauer auf einfache Weise mit dem endgültigen Spielstatus zusammenhängt. Wenn Sie an der Reihe sind, gewinnen Sie, wenn im Spiel noch eine ungerade Anzahl von Zügen übrig ist, einschließlich der, die Sie gerade ausführen werden. Da bei jedem Zug ein einzelnes Feld entfernt wird, bedeutet dies, dass die Anzahl der am Ende des Spiels verbleibenden Felder die entgegengesetzte Parität wie jetzt haben soll. Darüber hinaus hat die Anzahl der Quadrate in allen Zügen die gleiche Parität. Sie wissen also von Anfang an, welche Parität die endgültige Zählung haben soll. Wir können die beiden Spieler Eve und Otto nennen, je nachdem, ob die Endzählung gerade oder ungerade sein muss, um zu gewinnen. Eva bewegt sich immer in Zuständen mit ungerader Parität und erzeugt Zustände mit gerader Parität, und Otto ist das Gegenteil.

In seiner Antwort gibt @PeterShor eine vollständige Analyse von One-Heap. Ohne den Beweis zu wiederholen, ist das Ergebnis das Folgende:

  • Otto mag Haufen und 2- Haufen und kann einen einzigen größeren Haufen aushalten. Er gewinnt, wenn er alle Heap-Größen bis auf eine 2 erreichen kann , zumindest ohne Eva sofort den Sieg der Form zu geben ( 1 , n ) . Eine optimale Strategie für Otto ist es, immer vom zweitgrößten Haufen zu nehmen, außer wenn der Zustand ( 1 , 1 , n > 1 ) ist , wann er vom n nehmen sollte . Otto verliert, wenn zu Beginn zu viele Bohnen in großen Haufen sind.122(1,n)(1,1,n>1)n
  • 12121

Wie bereits erwähnt, ergibt dies optimale Strategien für 1-Heaps, obwohl sie etwas umständlicher auszudrücken sind (und ich möglicherweise einen Fehler bei der Primär-zu-Dual- "Übersetzung" mache). Im Spiel von 1-Heaps:

  • 11(1,1,,1,2)
  • Eva mag keine Lücke zwischen den größten und zweitgrößten Haufen. Sie gewinnt, wenn sie die beiden größten Haufen gleich groß machen kann. Eine optimale Strategie für Eve ist es, immer vom größten Haufen zu nehmen, wenn er einzigartig ist, und niemals, wenn genau zwei der größten Größe vorhanden sind.

Wie @PeterShor feststellt, ist nicht klar, wie (oder ob) diese Analysen auf die allgemeineren Spiele Disconnect und Reconnect ausgeweitet werden könnten.

mjqxxxx
quelle
2
Ich denke, dass diese Art von Spielen kollektiv als "Vertex Deletion Games" bezeichnet wird. Aber ich stimme Ihnen zu, dass die Gewinnbedingung insofern nicht dem Standard entspricht, als sie sich auf die globale Eigenschaft des Graphen bezieht, anstatt auf lokale Eigenschaften wie den Grad von ein Scheitelpunkt.
Tsuyoshi Ito
4
Der konstruierte Graph wird in der Literatur als Permutationsgraph ( en.wikipedia.org/wiki/Permutation_graph ) bezeichnet. Einige strukturelle Eigenschaften könnten helfen.
Yoshio Okamoto
1
@Yoshio: Das ist ein guter Punkt. Das Permutationsspiel ist isomorph zum Graphenspiel, aber die Startgraphen sind nicht willkürlich. Selbst wenn das allgemeine Grafikspiel schwer zu analysieren ist, ist es möglich, dass es einfacher wird, wenn es auf diese Unterklasse von Grafiken beschränkt ist.
mjqxxxx
2
Andererseits ist die allgemeinere Formulierung möglicherweise leichter zu beweisen. Varianten von Vertex-Deletion Spielen sind bekannt PSPACE-hart sein, zum Beispiel: emis.ams.org/journals/INTEGERS/papers/a31int2005/a31int2005.pdf
Jeffε
2
Ich habe eine Frage zu dieser Art von Spiel speziell bei math.SE hinzugefügt ( math.stackexchange.com/questions/95895/… ). Da es sich bei Permutationsgraphen übrigens um Kreisgraphen handelt, lautet die alternative Formulierung wie folgt: Spieler entfernen abwechselnd Akkorde aus einem Anfangssatz; Der Spieler, der eine Reihe sich nicht überschneidender Akkorde hinterlässt, ist der Gewinner.
mjqxxxx
7

ihihihisind 3,3,2,1. Ich habe versucht, die Analyse dieses Spiels in den Kommentaren zu Domotorps Antwort anzugeben, aber (a) ich habe es falsch verstanden und (b) es ist nicht genug Platz in Kommentaren, um einen echten Beweis zu liefern.

st=i2,hi>2hi2

  1. ts2

  2. ts

ts

Um zu beenden, dass dies korrekt ist, müssen wir zeigen, dass der erste Spieler in einem Zug von jeder Position, die nicht zu Kategorie (1) oder (2) gehört, entweder eine Position in Kategorie (1) oder (2) erreichen kann. oder direkt gewinnen.

Es gibt zwei Fälle:

  1. ts1s>0tss=0ts

  2. ts1tsts2

Ich habe versucht, diese Strategie auf das ursprüngliche Spiel zu verallgemeinern, und nicht herausgefunden, wie das geht.

Peter Shor
quelle
1
In meiner Antwort bemerkte ich, dass eine Lösung für diesen Sonderfall auch den Sonderfall mit einer zunehmenden Anzahl abnehmender Läufe löst, indem ich in der "dualen" Position spiele, die durch die Transponierung des Young-Diagramms erhalten wird. Insbesondere wird Evas optimale Strategie "vom größten Haufen nehmen, es sei denn, es gibt genau zwei von dieser Größe" und Ottos optimale Strategie wird "vom kleinsten Haufen nehmen".
mjqxxxx
Ich bin mir sicher, dass dieser Ansatz zu einer perfekten Lösung führen wird, aber im Moment gibt es noch einen kleinen Fehler, zB (3,1) verliert nicht und (3,1,1) ist. Das Problem ist, dass die Definition von 2. diesen Fall ausschließen sollte, da wir eine Ein-Heap-Position in einem Schritt erreichen können. Aber ich denke das ist das einzige Problem mit 2. und es ist hoffentlich nicht schwer es zu korrigieren.
Domotorp
1
Natürlich habe ich diesen Teil am Ende vergessen ... Dann ist dieses Spiel gelöst!
Domotorp
1
Keine vollständige Antwort, aber dennoch die Prämie wert.
Jeffs
3

O(2nn)

@ Jɛ ɛ E Es ist vorgekommen, dass (1,4,3,2) den Wert * 1 und nicht * 2 hat, wie Sie vorgeschlagen haben.

Dmytro Korduban
quelle
Ups, mein Fehler. Die Frage wurde behoben: g (1,3,2) = mex {g (1,3), g (1,2), g (3,2)} = mex {0, 0, * 1} = * 2.
Jeffs
n10n
@maldini: Es gibt Hoffnung, dass das Spiel einige nette Eigenschaften hat, die es möglicherweise handhabbar machen. Ich frage mich, was mit dem auf Grafiken verallgemeinerten Spiel oder dem auf perfekte Grafiken verallgemeinerten Spiel passiert.
Peter Shor
3

Edit 5th of Jan: Tatsächlich ist das unten beschriebene One Heap Game ein Sonderfall des Problems, dh wenn die Zahlen in einer bestimmten Weise aufeinander folgen, dass die erste Gruppe größer ist als die zweite Gruppe, die größer ist als die dritte usw und die Zahlen in jeder Gruppe nehmen zu. ZB 8, 9, 4, 5, 6, 7, 2, 3, 1 ist eine solche Permutation. Deshalb schlage ich vor, diesen Sonderfall zuerst zu lösen.

Haftungsausschluss: Ich behaupte nicht mehr, dass der folgende Beweis korrekt ist, siehe z. B. den Kommentar von Tsuyoshi, der zeigt, dass das Löschen einer Zahl aus einer Permutation ein Diagramm ergibt, das nicht durch Löschen eines Quadrats aus dem Diagramm der Permutation erreichbar ist. Ich habe die Antwort hier gelassen, um zu zeigen, dass dieser Ansatz nicht funktioniert, und weil er ein weiteres einfaches Spiel enthält.

Das Spiel hat dank Young Tableaux eine sehr einfache andere Formulierung. Ich bin sicher, dass es von dort aus wie andere Spiele analysiert werden kann und einen linearen Zeitalgorithmus liefert.

Definieren Sie zuerst das folgende Spiel in Young Diagrams: Wenn das aktuelle Diagramm in jeder Runde horizontal ist (alle Quadrate in einer Linie), verliert der aktuelle Spieler und der andere Spieler gewinnt. Andernfalls entfernt der aktuelle Spieler eines der Felder unten rechts und das Spiel geht zum anderen Spieler über.

Ordnen Sie nun die Zahlenfolge in ein junges Tableau. Der Hauptanspruch ist, dass der Gewinner des Originalspiels der gleiche ist wie der Gewinner des Planspiels, das mit dieser Form beginnt. Beachten Sie, dass das Diagramm der neuen Sequenz immer dann, wenn die Spieler eine Zahl löschen, durch Löschen eines Quadrats in der rechten unteren Ecke des Diagramms erstellt werden kann. Darüber hinaus können Sie ein solches Diagramm erstellen, indem Sie die Nummer aus dem entsprechenden Feld unten rechts löschen. Diese Aussagen folgen aus der Standard-Young-Tableaux-Theorie.

Obwohl dieses Diagrammspiel einfach genug ist, entspricht es dem folgenden Spiel, das standardmäßiger zu sein scheint:

One Heap Game: Die Spieler erhalten einige Haufen mit jeweils ein paar Kieselsteinen. Wenn in jedem Zug nur noch ein Haufen übrig ist, verliert der aktuelle Spieler und der andere gewinnt. Andernfalls entfernt der aktuelle Spieler einen Stein von einem Haufen und das Spiel geht an den anderen Spieler weiter.

Wenn es eine einfache Lösung für das Heap-Spiel gibt (und ich bin der festen Überzeugung, dass es eine gibt), erhalten wir auch eine Lösung für das ursprüngliche Spiel: Legen Sie die Sequenz einfach in ein junges Tableau und wandeln Sie das Diagramm in Heaps um.

Leider sehe ich nicht, welche Heap-Positionen gewinnen bzw. wie die Sprague-Grundy-Werte ermittelt werden. Ich habe ein paar Fälle von Hand überprüft und die folgenden sind die Verlustpositionen mit höchstens 6 Kieselsteinen:

ein Haufen; (1,1,1); (2,2); (3,1,1); (2,1,1,1); (1,1,1,1,1); (4,2); (3,3); (2,2,2).

Kann jemand dieses Spiel lösen?

Edit: Peter Shor kann seine Antwort sehen!

domotorp
quelle
1
Können Sie mindestens ein Beispiel nennen, das zeigt, wie aus einer bestimmten Permutation ein junges Tableau wird und wie dasselbe Spiel (Entfernen von Zahlen, bis eine aufsteigende Reihenfolge erreicht ist) auf dem Tableau gespielt wird? Insbesondere verstehe ich nicht, was es bedeutet, "eines der unteren rechten Quadrate" zu entfernen.
mjqxxxx
5
Hier ist ein Gegenbeispiel zu einer schwächeren Behauptung, dass das Entfernen einer Zahl aus einer Permutation dem Entfernen einer der Zellen unten rechts aus dem entsprechenden Young- Diagramm (anstelle des Young- Tableaus ) entspricht. Sei n = 5, und betrachte eine durch die Permutation [4,1,3,5,2] angegebene Position (d. H. Σ (1) = 4, σ (2) = 1 usw.) und entferne 3 davon. Das entsprechende Young-Diagramm vor dem Zug ist 5 = 3 + 1 + 1, aber das entsprechende Young-Diagramm nach dem Zug ist 4 = 2 + 2, was nicht durch Entfernen einer Zelle aus 3 + 1 + 1 erhalten wird.
Tsuyoshi Ito
5
Und die Permutation [5,4,1,2,3] hat das gleiche Young-Diagramm wie [4,1,3,5,2], aber Sie können das Young-Diagramm 4 = 2 + 2 nicht erreichen. Das Spiel hängt also nicht nur von der Form des Young-Tableaus ab.
Peter Shor
2
Ein Hoch auf konstruktives Missverständnis!
Jeffs
3
@ Jɛ ɛ E: Ja, das ist viel nützlicher als ein Beweis für die bloße Existenz eines Missverständnisses.
Tsuyoshi Ito