From TheBestLinks.com
The Shannon switching game is an abstract game for two players, invented by 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.
Related links
Top visited
0 of
0 links
[no links posted yet]
>> place link >>
Discussion
Last posted
0 of
0 messages
[no messages posted yet]
>> post message >>
Watch
You can
add this article to your own "watchlist" and receive e-mail notification about all changes in this page.
