Ein Spiel auf mehreren Grafiken

12

Betrachten Sie das folgende Spiel auf einem gerichteten gewichteten Graphen G mit einem Chip an einem Knoten.

Alle Knoten von G sind mit A oder B markiert.

Es gibt zwei Spieler Alice und Bob. Das Ziel von Alice (Bob) ist es, den Chip zu einem Knoten zu verschieben, der mit A (B) markiert ist.

Anfangs haben Alice und Bob mA bzw. mB Dollar.

Befindet sich ein Spieler in einer Verlustposition (dh die aktuelle Position des Chips ist durch einen entgegengesetzten Buchstaben gekennzeichnet), kann er den Chip zu einem benachbarten Knoten bewegen. Ein solcher Umzug kostet einige Dollar (das Gewicht der entsprechenden Kante).

Der Spieler verliert, wenn er sich in einer Verlustposition befindet und kein Geld hat, um dies zu beheben.

Betrachten Sie nun die Sprache GAME, die aus allen gerichteten gewichteten Graphen G (alle Gewichte sind positive ganze Zahlen), der Anfangsposition des Chips und den Großbuchstaben von Alice und Bob besteht, die in der unären Darstellung angegeben sind

so dass Alice eine Gewinnstrategie bei diesem Spiel hat.

Die Sprache GAME gehört zu P . In der Tat wird die aktuelle Position des Spiels durch die Position des Chips und die aktuellen Hauptstädte von Alice und Bob definiert, sodass eine dynamische Programmierung funktioniert (hier ist es wichtig, dass die Anfangsbuchstaben in der unären Darstellung angegeben werden).

Betrachten Sie nun die folgende Verallgemeinerung dieses Spiels. Betrachten Sie mehrere gerichtete gewichtete Graphen G1,Gn mit einem Chip an jedem Graphen. Alle Knoten aller Graphen sind mit A und B markiert. Jetzt gewinnt Bob, wenn alle Chips mit B markiert sind, und Alice gewinnt, wenn mindestens ein Chip mit A markiert ist.

Betrachten Sie die Sprache MULTI-GAME, die aus allen Graphen G1,,Gn , Anfangspositionen und Großbuchstaben mA und mB (in der unären Darstellung) besteht, so dass Alice beim entsprechenden Spiel gewinnt. Hier ist es wichtig, dass Großbuchstaben für alle Graphen gleich sind, es handelt sich also nicht nur um mehrere unabhängige GAMEs.

Frage Wie komplex ist die Sprache MULTI-GAMES? (Gehört es auch zu P oder gibt es einige Gründe dafür, dass dieses Problem schwierig ist?)

UPD1 Neal Young schlug vor, Conways Theorie zu verwenden. Ich weiß jedoch nicht, ob es möglich ist, diese Theorie für mehrere Spiele mit gemeinsamem Kapital zu verwenden.

UPD2 Ich möchte ein Beispiel zeigen, das zeigt, dass MULTI-GAME nicht sehr einfach ist. Lassen Sie Alice ihr Kapital mA in einige n Terme aufteilen. mA=a1+a2+an (Sie wird ai Dollar für den i ten Graphen verwenden). Definieren Sie bi als minimale Zahl, so dass Bob im i ten Spiel gewinnt, wenn Alice und Bob ai bzw. einen bi Dollar haben. Wenn b1+bn>mB (für eine Aufteilung vonmA=a1+a2+an ) gewinnt Alice. Das Gegenteil ist jedoch nicht der Fall. Betrachten Sie zwei Kopien des folgenden Diagramms (anfangs befindet sich der Chip links oben A): Geben Sie hier die Bildbeschreibung ein

Für einen Graphen gewinnt Bob, wenn mA=0 und mB=2 oder wenn mA=1 und mB=3 . Für das Spiel mit zwei Kopien dieses Graphen verliert Bob jedoch, wenn mA=1 und mB=5 . In der Tat muss Bob 4 oder 5 Dollar ausgeben , um beide Chips auf einen mit B gekennzeichneten Knoten zu verschieben . Dann kann Alice mindestens einen Chip zu einem mit A gekennzeichneten Knoten verschieben. Danach hat Bob kein Geld mehr, um seine Position zu retten.

UPD3 Da die Frage nach beliebigen Graphen schwierig erscheint, sollten Sie bestimmte Graphen berücksichtigen. Bezeichnen Sie die Knoten eines Graphen Gi als 1,k . Meine Einschränkung ist folgende: Für jedes Paar i<j existiert eine Kante von i nach j und es gibt keine umgekehrte Kante. Es gibt auch eine Beschränkung für die Kosten von Kanten: Für i<j<k die Kante j bis k nicht größer als von i bis k .

Alexey Milovanov
quelle
4
Was macht in MULTI-GAME einen Zug aus? Der Spieler macht einen Zug in jeder Grafik? Oder wählt man ein Diagramm, um einen Zug zu machen? Haben Sie untersucht, ob Conways Spieltheorie (Heizen und Kühlen) hier gilt? (Einige Referenzen finden Sie hier: en.wikipedia.org/wiki/… )
Neal Young
@Neal Young Der Spieler wählt eine Grafik, um einen Zug zu machen.
Alexey Milovanov
FWIW, wenn ich mich recht erinnere, berücksichtigt Conways Spieltheorie, wie man Spiele spielt, die auf diese Weise aus anderen Spielen zusammengesetzt sind (in jedem Zug wählt der Spieler eines der Teilspiele aus, in die er einziehen möchte). Ich weiß jedoch nicht, welche Relevanz seine Theorie für die Komplexität der Berechnungen hat.
Neal Young
1
@NealYoung Danke, aber meines Wissens besteht das Problem darin, dass die Spieler für alle Spiele gemeinsame Hauptstädte haben. Ich finde nicht, wie es durch Conways Theorie behoben werden kann ...
Alexey Milovanov
Ist Alice (Bob) gezwungen, den Chip zu bewegen, wenn er sich auf dem Knoten A (B) befindet? Was sind die Gewinnbedingungen für das Multi-Game? Gewinnt B auch, wenn sich alle Chips auf B-Knoten befinden, A aber noch etwas Geld hat? Sie sagen, dass A gewinnt, wenn sich mindestens ein Chip auf A befindet, sodass A einfach versuchen kann, zwei Chips in einem mit A gekennzeichneten Knoten in den "weniger teuren" zwei Graphen zu belassen. Sobald B einen der beiden Chips von Knoten A entfernt, bringt Alice ihn zurück (und ignoriert die anderen Grafiken)
Marzio De Biasi

Antworten:

0

Update: wahrscheinlich falsch, vorerst als Aufzeichnung der Erkundung einer Allee. Zeige Kommentare.

Update 2: definitiv falsch.

Betrachten Sie einen Graphen der Form (B) -1-> (A) -1-> (B), dh G=(V,E) , wobei V={1,2,3} , E={(1,2),(2,3)} , die Eckpunkte 1, 2, 3 sind mit B, A bzw. B gekennzeichnet, und den Kanten werden alle Kosten von 1 zugewiesen.

Definieren Sie eine 3-Spiele-Instanz von MULTI-GAME, indem Sie mA=mB=2 , G1=G2=G3=G , wobei alle drei Spiele auf Scheitelpunkt 1 beginnen. Alice kann dieses Spiel eindeutig nicht gewinnen.

Die folgende Wiederholung schlägt jedoch für M[3,2,2] fehl : Es gibt keine Aufteilung von Bobs Geldern 2u,u zwischen den ersten beiden Spielen und dem dritten Spiel, so dass für alle Aufteilungen von Alices Geldern v,2v sowohl M[2,2u,2v]=B und W[3,u,v]=B . Wennu=1 oderu=2 , dann istM[2,2u,2]=A ; und wennu=0 dannW[3,u,2]=A .

Ich sehe keinen unmittelbaren Weg, um diesen Ansatz zu retten. Durch Umkehren der Quantifizierungsreihenfolge für u und v schlägt die Wiederholung für die Instanz in Update 2 des Fragenposts fehl.


Bei einer MULTI-GAME-Instanz mA,mB,G1,,Gn,

Vorberechnung

W[k,x,y]={Aif Alice wins GAME on Gk with initial funds x for Alice and y for Bob,Botherwise

für alle Spiele und alle xmA , ymB .

M[k,x,y]kxmAymBM[k,x,y]=BA

M[1,x,y]=W[1,x,y]

und

M[k+1,x,y]=Bif and only ifvu,W[k+1,u,v]=BandM[k,xu,yv]=B.

M[n,mA,mB]=A

gdmclellan
quelle
Ihr Algorithmus ist falsch. Betrachten Sie die Grafik auf dem Bild in meinem Beitrag. Betrachten Sie das MULTI-GAME mit zwei solchen Grafiken. Hier ist W [1,0,2] = W [2,0,2] = B und W [1,1,3] = W [2,1,3] = B. Für MULTI-GAME mit m_A = 1 und m_B = 5 gewinnt Alice
Alexey Milovanov
u
@AlexeyMilovanov mit Änderungen an den Quantifizierern sollte die Wiederholung für das Beispiel durchlaufen werden. Aber Sie haben mich an diesen Ansatz gezweifelt. Es scheint, als müsste Bob möglicherweise eine einzige Verteilung von Geldern festlegen, die alle Ausschüttungen übertrifft, die Alice sich vorstellen kann. Trotzdem bin ich mir nicht sicher, ob ich von der Kernidee hier überzeugt bin: dass es bei diesem Problem nicht wirklich um GAME geht. Ist etwas über das damit verbundene Problem bekannt, bei dem jede GAME-Instanz durch eine einfache Tabelle a la W oben ersetzt wird?
gdmclellan
Tabelle W definiert nicht den Gewinner. Ich weiß nicht, ob es für einen anderen Tisch gilt ...
Alexey Milovanov
@AlexeyMilovanov Tabelle W bestimmt per Definition den Gewinner von GAME-Instanzen, die für ein bestimmtes Eingabediagramm isoliert sind. Ich bin mir nicht sicher, warum du etwas anderes sagen würdest. Ich habe meine Antwort jedoch mit einem Gegenbeispiel aktualisiert, falls nach wie vor Zweifel bestehen, dass sie falsch ist.
gdmclellan
0

[n]n+1n0i+1i0i<n00n[n]n00

Gαβα[i]ββ[j][k]j<kαββ[j][k][k][i]{i{jk}}

Steven Stadnicki
quelle
1
Die Beweise in der Arbeit scheinen große Werte von i, j und k in den Spielen zu verwenden. Beachten Sie, dass hier angenommen werden kann, dass alle Gewichte höchstens die Hauptstädte der Spieler sind, die in unär dargestellt wurden.
Antti Röyskö
@ AnttiRöyskö Ich muss mir dann den Beweis genauer ansehen; Ich glaube, dass das Ergebnis zur PSPACE-Vollständigkeit von Go-Endspielen das Ergebnis der These verwendet und auch eine unäre Zählung voraussetzt (da dort i / j / k aus den Größen der Board-Regionen stammen).
Steven Stadnicki
αβ0
αβα[i]>[j]j+1[i][j]
αβn