Permutationsspiel Redux

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(2^n poly(n))$

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 falsch$G_{\pi}$$\pi\in S_n$$(i,j)$$i-j$$\pi(i)-\pi(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}_\pi = G_{R(\pi)}$$(i,j)$$i$$j$

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 $G$$n$$G \cup \bar{K}_n$$G$$\bar{K}_n$$n$$G + G\cup\bar{K}_n$$|G|+n$$G$ist 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 ).$G$$G' + G'\cup \bar{K_n}$$|G'|=|G|-1$$n\ge 2$$G + G\cup\bar{K}_{n-2}$

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 $G$$H \cup K_p$$H$$G$$p=0$$1$$G$$G \sim H \cup K_p$$G' \sim H' \cup K_{p'}$ . 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.$G \cup G' \sim (H \cup H')\cup K_{p\oplus p'}$$[H \cup K_0]$$[H \cup K_1]$$H$$H + H \cup K_1$$H+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$$\pi$$G_{\pi}$$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$$\pi$$G^{c}_{\pi}$

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.$1$$2$$\le 2$$(1,n)$$(1,1,n>1)$$n$
• $1$$\ge 2$$1$$2$$1$

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:

• $1$$1$$(1,1,\dots,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.

$i$$h_i$$h_i$$h_i$sind 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.

$s$$t=\sum_{i\geq 2, h_i>2\,} h_i -2$

1. $t \leq s-2$

2. $t \geq s$

$t - s$

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. $t \geq s-1$$s>0$$t \geq s$$s = 0$$t \geq s$

2. $t \leq s-1$$t$$s$$t \leq s-2$

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

$O(2^n n)$

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

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!