|
|
|
|
|
Shannon Switching GameThe 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.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|