Shannon switching game

From Free net encyclopedia

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.