Paritätsspiel

Ein Paritätsspiel ist ein unendliches Spiel mit perfekter Information zwischen zwei Spielern auf einem gerichteten Graphen. Die Knoten des Graphen sind zwischen den Spielern aufgeteilt, so dass jeder Spieler für seine Knoten entscheiden kann, wie von diesen weitergezogen werden soll. Außerdem ist jedem Knoten als Priorität (manchmal auch Farbe genannt) eine natürliche Zahl zugeordnet.

Ein Paritätsspiel mit acht Knoten. Kreisförmige Knoten gehören Spieler 0, rechteckige Knoten Spieler 1. Auf der linken Seite ist in Blau der Gewinnbereich von Spieler 0 markiert, auf der rechten Seite in Rot der Gewinnbereich von Spieler 1. Die farbig hervorgehobenen Pfeile markieren jeweils eine Gewinnstrategie.

Den Weg, welcher durch die Züge der beiden Spieler beschrieben wird, nennt man eine Partie. Eine endliche Partie verliert der Spieler, der am Zug ist, wenn keine Züge mehr möglich sind. Bei einer unendlichen Partie bestimmt die Parität der höchsten Priorität der Partie, welcher der beiden Spieler gewinnt.

Varianten in der Definition

Äquivalente Varianten der Definition von Paritätsspielen sind:

• Statt der höchsten Priorität bestimmt die kleinste Priorität den Spieler. Hierbei spricht man von Min-Paritätsspielen. Sofern es eine maximale Priorität $P$ gibt, können die Prioritäten $\Omega$ der beiden Varianten über $P-\Omega$ ineinander überführt werden.
• Es wird gefordert, dass die beiden Spieler immer abwechselnd ziehen, die Mengen der Knoten der Spieler somit eine Bipartition der Knoten bilden. Zwischen zwei Knoten eines Spielers kann jedoch stets ein Knoten des anderen Spielers eingefügt werden, bei dem dieser keine Wahl hat.

Klassifikation innerhalb der Spieltheorie

Spieltheoretisch lassen sich Paritätsspiele durch die folgenden Eigenschaften charakterisieren:

Paritätsspiele sind ...

• Nullsummenspiele: Wenn ein Spieler gewinnt, verliert der andere und umgekehrt.
• sequentiell: Die Spieler ziehen abwechselnd.
• Spiele mit perfekter Information.
• unendlich.
• diskret.
• zufallslos.

Lösen eines Paritätsspiels

Ein Paritätsspiel zu lösen, bedeutet, für jeden Knoten des Paritätsspiels festzustellen, welcher der beiden Spieler eine Gewinnstrategie besitzt, wenn eine Partie an diesem Knoten beginnen würde. Die Mengen der Knoten, von denen aus die Spieler gewinnen können, nennt man die Gewinnbereiche. Die Knoten eines Paritätsspiels können in die beiden Gewinnbereiche zerlegt werden.

Es gibt Algorithmen, die diese Zerlegung in exponentieller Zeit finden. Es ist jedoch ein ungelöstes Problem der Informatik, ob es auch Algorithmen mit polynomieller Laufzeit gibt, die diese Gewinnbereiche ermitteln können.