Shannon switching game
|
|
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.Template:Math-stub