Shannon switching game

The Shannon switching game is an abstract strategy game for two players, invented by Claude Shannon. It is commonly played on a rectangular grid; this special case of the game was independently invented by David Gale and is also known as Gale or Bridg-It.[1][2]

Rules

The game is played on a finite graph with two special nodes, A and B. Each edge of the graph can be either colored or removed. The two players are called Short and Cut, and alternate moves. On Cut 's turn, he deletes from the graph a non-colored edge of his choice. On Short 's turn, he colors any edge still in the graph. If Cut manages to turn the graph into one where A and B are no longer connected, he wins. If Short manages to create a colored path from A to B, he wins.

There are also versions of the Shannon switching game played on a directed graph and an oriented matroid. A solution has been explicitly found for any such game using matroid theory,[1] unlike a similar game Hex, which is PSPACE hard.[3]

Generalized Hex is played on a graph, just like Shannon game, but instead of coloring the edges, in Hex, the players color the vertices. Viewed in this way, Hex and Shannon game are closely related, yet their complexities differ greatly.

Winning algorithms

The game always terminates after a finite number of moves, and one of the two players has to win. Either Short, Cut, or the player moving first is guaranteed the existence of a winning strategy on any given graph.[4]

The Short and Cut games are a duality; that is, the game can be restated so that both players have the same goal: to secure a certain edge set with distinguished edge e. Short tries to secure the edge set that with e makes up a circuit, while Cut tries to secure an edge set that with e makes up a cutset, the minimal set of edges that connect two subgraphs.

References

  1. 1 2 Lehman, Alfred (1964), "A solution of the Shannon switching game", Journal of the Society for Industrial and Applied Mathematics, 12 (4): 687–725, JSTOR 2946344, MR 0173250.
  2. ↑ Hayward, Ryan B.; van Rijswijck, Jack (2006), "Hex and combinatorics", Discrete Mathematics, 306 (19-20): 2515–2528, doi:10.1016/j.disc.2006.01.029, MR 2261917.
  3. ↑ Reisch, Stefan (1981), "Hex ist PSPACE-vollständig", Acta Informatica, 15 (2): 167–191, doi:10.1007/BF00288964, MR 599616.
  4. ↑ Stephen M. Chase (1972). "An implemented graph algorithm for winning Shannon Switching Games". Communications of the ACM. 15 (4): 253–256. doi:10.1145/361284.361293.
Wikimedia Commons has media related to Shannon switching game.
This article is issued from Wikipedia - version of the 7/11/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.