SHANNON SWITCHING GAME

(Redirected from Bridg-It)

The 'Shannon switching game' is an abstract strategy game for two players, invented by "the father of information theory", Claude Shannon, and (at least in its common rectangular-grid form) independently invented by David Gale; it has also been known as ''Gale'', ''Bridg-It'', and ''Bird Cage''.
The game is played on a finite graph with two special nodes, ''A'' and ''B''. Each edge of the graph is colored 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 from the graph any 0-colored edge 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 always 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. A solution has been explicitly found for any such game using matroid theory, unlike a similar game Hex, which is PSPACE hard.