Der Shannon, der Spiel schaltet, ist ein abstraktes Strategie-Spiel für zwei Spieler, die von Claude Shannon, und (mindestens in seiner allgemeinen Form des rechteckigen Bratrostes) unabhängig erfunden sind, erfunden von David Gale; es ist auch als Gale, Bridg-es und Vogel-Käfig bekannt gewesen.

Regeln

Das Spiel wird auf einem begrenzten Graphen mit zwei speziellen Knoten, A und B gespielt. Jeder Rand des Graphen kann entweder gefärbt oder entfernt werden. Die zwei Spieler werden Kurz und Kürzung und abwechselnde Bewegungen genannt. Auf der Kürzung 's Umdrehung löscht er vom Graphen einen nichtfarbigen Rand seiner Wahl. Auf dem Kurzen 's Umdrehung färbt er jeden Rand noch im Graphen. Wenn Kürzung schafft, den Graphen in denjenigen zu verwandeln, wo A und B nicht mehr verbunden werden, gewinnt er. Wenn Kurz, schafft, einen farbigen Pfad von bis B zu schaffen, er gewinnt.

Es gibt auch Versionen des Shannons, der Spiel schaltet, das auf einem geleiteten Graphen und einem orientierten matroid gespielt ist. Eine Lösung ist für jedes solches Spiel mit matroid Theorie verschieden von einer ähnlichen Spielhexe ausführlich gefunden worden, die PSPACE hart ist.

Das Gewinnen von Algorithmen

Das Spiel endet immer nach einer begrenzten Zahl von Bewegungen, und muss einer der zwei Spieler gewinnen. Entweder Kurz, Kürzung oder der Spieler, der sich zuerst bewegt, wird die Existenz einer Gewinnen-Strategie auf jedem gegebenen Graphen versichert.

Die Kurzen Spiele und Kürzungsspiele sind eine Dualität; d. h. das Spiel kann neu formuliert werden, so dass beide Spieler dieselbe Absicht haben: Einen bestimmten Rand-Satz mit dem ausgezeichneten Rand e zu sichern. Kurze Versuche, den Rand-Satz zu sichern, der mit e einen Stromkreis zusammensetzt, während Kürzung versucht, einen Rand-Satz zu sichern, der mit e einen cutset, den minimalen Satz von Rändern zusammensetzt, die zwei Subgraphen verbinden.

Links

• Graph-Spiel, eine javanische Durchführung des Shannons, der Spiel schaltet
• Bridj-es, eine PHP Durchführung des STURMS