Go Ist Pspace Schwer
GO ist PSPACE-schwer
Beitrag zum Seminar ¨
uber Algorithmen und Komplexit¨
at
Freie Universit¨
at Berlin, SS 07
Von Frederik Hermans
24. Mai 2007
1
Einf¨
uhrung
GO ist ein asiatisches Brettspiel f¨
ur zwei Spieler. Lichtenstein und Sipser haben
1980 gezeigt, dass das Problem, f¨
ur eine beliebige GO-Situation den Gewinner fest-
zustellen, PSPACE-schwer ist [1]. Dieser Beweis ist Gegenstand des Vortrags.
Die Komplexit¨
atsklasse PSPACE umfasst diejenigen Entscheidungsprobleme,
deren L¨
osung auf einer Turing-Maschine polynomiell viel Platz ben¨
otigt. PSPACE-
schwere Probleme gelten gemeinhin als so schwer, dass sie in der Praxis im Allge-
meinen nicht l¨
osbar sind.
Der Beweis wird durch eine Reihe von Reduktionen gef¨
uhrt. Zun¨
achst wird das
PSPACE-schwere Problem TQBF auf das Spiel GG reduziert, GG wird auf eine
planare Version des Spiels (PGG) reduziert, und dieses schließlich auf GO.
2
TQBF ist PSPACE-schwer
Definition. QBF ist die Menge der quantifizierten Booleschen Formeln.
QBF = {Q1v1Q2v2 . . . Qnvn : F (v1, v2, . . . , vn)},
wobei Qi Quantoren sind (∀ oder ∃), vi Boolesche Variablen sind und F eine
Boolesche Formel in konjunktiver Normalform ist.
Definition. T QBF ist die Menge der quantifizierten Booleschen Formeln aus
QBF , die wahr sind.
Satz. Das Problem, f¨
ur eine gegebene Formel aus QBF festzustellen, ob sie in
T QBF liegt (also wahr ist), ist PSPACE-schwer [2].
3
GG ist PSPACE-schwer
Definition. GG (Generalized Geography) ist ein Spiel f¨
ur zwei Spieler, das auf
einem gerichteten Graphen mit ausgezeichneter Startecke gespielt wird. Die Spie-
ler w¨
ahlen abwechselnd von der augenblicklichen Ecke eine ausgehende Kante und
markieren die Endecke. Das Spiel wird an der markierten Endecke fortgesetzt. Der-
jenige Spieler verliert, der am Zug ist und keine Kante mehr w¨
ahlen kann (weil die
1
Endecken aller ausgehenden Kanten bereits markiert sind oder weil die augenblick-
liche Ecke keine ausgehenden Kanten hat).
Satz. Das Problem, den Gewinner eines GG-Spiels festzustellen, ist PSPACE-
schwer.
4
Planares GG ist PSPACE-schwer
Satz. Das Spiel GG ist auch dann PSPACE-schwer, wenn es auf einem planaren,
bipartiten Graphen gespielt wird, in dem jede Ecke h¨
ochstens Grad 3 hat.
Jeder gerichtete Graph, der wie bei der Reduktion TQBF ≤ GG beschrieben
konstruiert wurde, l¨
asst sich systematisch in einen planaren, bipartiten Graphen
mit Eckengrad h¨
ochstens drei ¨
uberf¨
uhren [1, 3].
5
Die GO-Regeln
GO wird auf einem Brett gespielt, auf dem ein Gitter mit n×n Linien eingezeichnet
ist. Die Schnittpunkte des Gitters heißen Felder. Zwei Spieler - Schwarz und Weiß -
ziehen abwechselnd, indem sie einen Spielstein auf ein freies Feld setzen oder passen.
Im Laufe des Spieles entstehen auf dem Brett Gruppen von gleichfarbigen Steinen.
Eine Gruppe ist eine maximale Menge von gleichfarbigen Steinen, die benachbart
sind.
Schlagen Wenn eine Gruppe von schwarzen Steinen vollst¨
andig von weißen Steinen
umgeben ist, wird die Gruppe der schwarzen Steine vom Brett entfernt (ent-
sprechend f¨
ur eine Gruppe von weißen Steinen).
Selbstmord Es ist nicht erlaubt, einen Stein so zu setzen, dass er nach dem Spielzug kein
freies, benachbartes Feld mehr hat. Eine Ausnahme hiervon: Wenn durch
das Setzen des Steines die umliegenden Steine geschlagen werden, ist der Zug
erlaubt.
Augen Es gibt bestimmte Gruppen, die nicht geschlagen werden k¨
onnen. Das sind
genau die Gruppen, die in ihrem Inneren mindestens zwei einzelne, nicht be-
nachbarte freie Felder haben. Das Schlagen einer solchen Gruppe ist durch die
Selbstmord-Regel ausgeschlossen. Eine unschlagbare Gruppe wird auch eine
Gruppe mit Augen genannt. Die freien Felder in der unschlagbaren Gruppe
werden Gebiet von Schwarz bzw. Weiß genannt.
Spielende Das Spiel ist beendet, wenn beide Spieler passen. Es werden alle Steine ent-
fernt, die nicht zu einer unschlagbaren Gruppe geh¨
oren. Die Punktzahl des
Spielers Schwarz ist die Differenz zwischen der Anzahl der freien Felder im
Inneren seiner unschlagbaren Gruppen und der Anzahl der schwarzen Steine,
die im Verlaufe des Spiels geschlagen wurden. Analog wird die Punktzahl f¨
ur
Weiß berechnet. Der Spieler mit der h¨
oheren Punktzahl gewinnt.
In der Praxis gibt es noch eine weitere Regel, die sogenannte Ko-Regel, die
direkte Wiederholungen der selben Spielsituation ausschließt. Diese Regel ist f¨
ur
den Beweis nicht relevant, also lassen wir sie aus. Eine vollst¨
andige Erkl¨
arung aller
GO-Regeln findet sich in [4].
2
6
GO ist PSPACE-schwer
Satz. Das Problem, f¨
ur eine beliebige Situation eines GO-Spiels den Gewinner zu
bestimmen, ist PSPACE-schwer.
Literatur
[1] D. Lichtenstein, M. Sipser GO is Polynomial-Space Hard
Journal of the ACM, Vol 27, No 2, April 1980, pp 393-401
[2] A. R. Meyer, L. J. Stockmeyer Word problems requiring exponential time
Preliminary Report Proc 5th Annual ACM Symp Theory Cmptg, Austin, Texas,
1973, pp 1-9
[3] D. Lichtenstein Planar formulae and their uses
SIAM Journal of Computing, Vol 11, No 2, May 1982, pp 329-343
[4] The Japanese Rules Of Go
http://www.cs.cmu.edu/∼wjh/go/rules/Japanese.html
3
Anhang
¡¡¡¡¡¡¡¡¡¡¡¡¡
¡¡¡¡¡¡
¡¡¡¡¡¡
¡¡¡¡¡¡
¡
¡
¡
¡¡¡¡¡¡
¡¡¡¡¡¡
¡¡¡¡¡¡
¡¡¡¡¡¡
¡¡¡¡¡¡
¡¡¡¡¡¡
(a) Globale Struktur der GO-Situation
(b) L¨
ucke
in
der
weißen
Gruppe
¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡¡
¡¡¡
¡
¡
¡
¡¡¡
¡¡¡
¡
¡
¡¡¡
¡¡¡
¡
¡
¡
¡
¡
¡
¡¡¡
¡¡¡
¡
¡
¡
¡
¡
¡
¡¡¡
¡¡¡
¡
¡
¡¡¡
¡¡¡
¡
¡
¡¡¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡
¡¡¡¡¡¡¡
¡¡¡¡¡¡¡
¡¡¡¡¡¡¡
¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡
¡
¡
¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡
¡
¡
¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡
(c) Konfiguration f¨
ur eine Ecke vom Typ
(d) Konfiguration f¨
ur eine Ecke vom Typ
Auswahlm¨
oglichkeit Spieler 1
Auswahlm¨
oglichkeit Spieler 2
¡¡¡¡¡¡¡¡¡¡¡¡¡
¡
¡¡¡¡¡¡¡¡¡
¡
¡¡¡¡¡¡¡¡¡
¡
¡¡¡¡¡¡¡¡¡
¡
¡¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡
¡
¡
¡¡¡¡¡¡
¡¡¡¡¡¡
¡
¡
¡
¡¡¡¡¡¡
¡
¡
¡¡¡¡¡¡
¡
¡
¡
¡¡¡¡¡
¡¡¡¡¡
¡
¡
¡
¡¡¡¡¡
¡
¡
¡
¡
¡¡¡¡¡
¡
¡
¡
¡
¡
¡
¡¡¡¡¡
¡
¡
¡
¡
¡
¡¡¡¡¡
¡¡¡¡¡¡¡
¡¡¡¡¡¡¡
¡
¡
¡¡¡¡¡
¡¡¡¡¡¡¡
¡¡¡¡¡¡¡
¡
¡¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡
¡¡¡¡¡¡¡
¡
¡¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡
¡¡¡¡¡¡¡
¡
¡¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡
¡¡¡¡¡¡¡¡¡¡¡¡¡
(e) Konfiguration f¨
ur eine Ecke
(f) Konfiguration f¨
ur eine
vom Typ Zusammenf¨
uhrung
Ecke vom Typ Test
4
