Komplexität von Hex mit zufälliger Reihenfolge.

Ich habe über eine Hex- Variante nachgedacht , bei der anstelle der beiden Spieler, die abwechselnd Züge machen, jeder Zug, den ein zufällig gewählter Spieler macht, einen Zug macht. Wie schwer ist es, die Gewinnchancen der einzelnen Spieler zu bestimmen? Dieses Problem liegt offensichtlich in PSPACE vor, aber kann es nicht NP-schwer sein, geschweige denn PSPACE-vollständig? Die Schwierigkeiten ergeben sich daraus, wie die Zufälligkeit es einem Spieler unmöglich macht, eine Wahl unter Optionen zu treffen. Wenn dieser Spieler Glück hat, bekommt er genug Züge, um beide Optionen zu nutzen. Wenn der Spieler Pech hat, bekommt der Gegner genug Züge, um beide Optionen zu blockieren. Andererseits kann ich mir dafür keine Polynom-Zeit-Algorithmen vorstellen.

cc.complexity-theory board-games Itai Bar-Natan
quelle

Sei S eine n-Bit-Binärzeichenfolge, die angibt, welcher Spieler an der Reihe ist. Im schlimmsten Fall stellen Sie das Standard-Hex-Spiel wieder her, wenn die Zufallssequenz 010101 ... oder 101010 ... lautet. Ihr Problem ist also mindestens so schwer wie das von Standard-Hex.

Mohammad Al-Turkistany

Es gibt zwei mögliche Interpretationen dieses Spiels. (1) Kurz vor jeder Runde werfen die Spieler eine Münze, um zu bestimmen, wer als nächstes geht. (2) Zu Beginn des Spiels, drehen die Spieler eine Münze

mal (auf einer Größe

board), und verwenden diese Sequenz für ihre Windungen. Turkistany scheint ein Modell anzunehmen (2); Die ursprüngliche Frage ist zweideutig, aber aus einigen seiner Formulierungen schätze ich, dass Itai nach (1) fragt, was einfacher sein könnte als normales Hex.

n^{2}

$n^2$

n

$n$

Peter Shor

In der Tat meine ich die erste Interpretation, dass die Münze direkt vor dem Zug geworfen wird. Zusätzlich bemerkte ich eine weitere Mehrdeutigkeit in meiner Frage: die Genauigkeit, mit der ich die Wahrscheinlichkeit kennen möchte. Der Eindruck, den ich hinterlassen habe, als ich das Problem gestellt habe, ist, dass ich die Wahrscheinlichkeit in vollständiger Präzision wissen möchte, aber ich möchte nur die Wahrscheinlichkeit in logarithmischer Präzision wissen. Wie der Unterschied zwischen PP und BPP scheint der spätere sinnvoller und natürlicher.

Itai Bar-Natan

@Itai: Eine andere Frage. Warum behaupten Sie, dass dies offensichtlich in PSPACE ist? Es scheint mir, dass es sich um ein Schiedsrichterspiel handelt, was bedeuten würde, dass die natürliche komplexitätstheoretische Obergrenze EXPTIME ist. Siehe Feige und Kilian, "Making Games Short".

Peter Shor

@tukistany Nutzlos bedeutet nicht trivial!

Jeffs

Antworten:

Vielleicht möchten Sie sich die Zeitung "Random-Turn Hex and Other Selection Games" von Yuval Peres, Oded Schramm, Scott Sheffield und David Wilson ansehen. Aus der Einleitung:

"Random-Turn Hex ist dasselbe wie gewöhnliches Hex, außer dass die Spieler statt abwechselnder Runden vor jeder Runde eine Münze werfen, um zu entscheiden, wer den nächsten Stein setzt. Obwohl gewöhnliches Hex bekanntermaßen schwer zu analysieren ist, ist die optimale Strategie für Random "Turn Hex ist sehr einfach."

In der Tat war Ihre Intuition richtig: Dies wird in BPP (oder vielleicht P) sein.

Peter Shor
quelle

Ich bin nur erstaunt, dass die Leute tatsächlich daran gearbeitet haben :) Schöne Referenz!

Suresh Venkat

Es ist auch ein wirklich schöner Beweis. Ich glaube, ich habe Scott Sheffield in einem seiner Vorträge erwähnen hören (aber dann habe ich es komplett vergessen, bis es bei Google auftauchte).

Peter Shor

Auf der Website von David Wilson gibt es auch eine Anwendung, mit der Sie Hex nach dem Zufallsprinzip spielen können (gegen die veröffentlichte Strategie, glaube ich): dbwilson.com/#software

Andy Drucker

Bei seinem letzten Besuch in Israel haben Oded Schramm und ich, inspiriert von der PSSW-Zeitung, einige Runden Zufallsschach gespielt, um festzustellen, dass es kein besonders interessantes Spiel ist.

Gil Kalai

Es stellt sich heraus, dass es eine bemerkenswerte Verbindung (aufgrund von David Richman) zwischen Random-Turn-Spielen und Bietspielen gibt , bei denen die Spieler für den nächsten Zug bieten. Siehe arxiv.org/pdf/0812.3677.pdf und users.math.yale.edu/~sp547/pdf/Discrete-bidding-games.pdf. Diese Verbindung ermöglicht ein im Wesentlichen optimales Spielen des Bietens von Hex, wobei die Arbeit von Peres et al. Ich mag das, weil Bieterspiele zumindest scheinbar kein Glück sind und ich denke, Hex-Bieten wäre befriedigender als Hex-Bieten mit Zufallsrunden. (Das Bieten in jeder Runde könnte jedoch eine unglaublich anspruchsvolle Aufgabe sein.)

Andy Drucker