Shannon switching game

From Wikipedia, the free encyclopedia

This article does not adequately cite its references or sources.
Please help improve this article by adding citations to reliable sources. (help, get involved!)
Any material not supported by sources may be challenged and removed at any time. This article has been tagged since January 2007.

The Shannon switching game is an abstract strategy game for two players, invented by "the father of information theory", Claude Shannon.

The game is played on a finite graph with two special nodes, A and B. Each edge of the graph is coloured either 0 or 1. Initially, all edges are colored 0, and A and B are connected. The two players are called Cut and Join, and alternate moves. On Cut 's turn, he deletes any 0-coloured edge from the graph of his choice. On Join 's turn, he changes any edge with the color 0 into 1. If Cut manages to turn the graph into one where A and B are no longer connected, he wins. If Join manages to create a path from A to B consisting solely of 1-colored edges, he wins. The game terminates after a finite number of moves and one of the two players has to win.

The definition of the game can be generalized to include any matroid and a solution has been explicitly found for any such game using matroid theory, unlike a similar game Hex, which is PSPACE hard.