Shannon switching game
A connection game invented by Claude Shannon before 1951.
The Shannon switching game is a two-player connection game invented by Claude Shannon, the American mathematician and electrical engineer known as the father of information theory, sometime prior to 1951. Players alternate coloring the edges of any given graph. One player’s goal is to create a path of their own color linking two special vertices; the other player tries to block that path by coloring edges in their own color (or, equivalently, by removing edges). A common version uses a rectangular grid, a variant created independently by American mathematician David Gale in the late 1950s, called Gale or Bridg-It.
**Rules** Play takes place on a finite graph with two designated nodes, A and B. Each edge may be either colored or removed. The two players are Short and Cut, who move in turns. On Cut’s turn, they delete any non-colored edge from the graph. On Short’s turn, they color any remaining edge. Cut wins if they disconnect A from B; Short wins if they create a colored path between A and B. The game always ends after a finite number of moves, with one player victorious. On any given graph, either Short has a winning strategy regardless of who moves first, or Cut has a winning strategy regardless of who moves first. The Short and Cut games are dual: the game can be reframed so both players aim to secure a particular edge set involving a distinguished edge e. Short tries to secure an edge set that, together with e, forms a circuit; Cut tries to secure an edge set that, together with e, forms a cutset (the minimal set of edges connecting two subgraphs).
**Variants** Theoretical versions of the Shannon switching game exist for directed graphs and oriented matroids, but no commercial games based on these have been published.
**Gale** Invented by David Gale and described in Martin Gardner’s *Scientific American* column in October 1958, this game uses two offset grids of differently colored dots. One player connects orthogonally adjacent dots on one grid, the other on the other grid. One player tries to link the top of their grid to the bottom, the other tries to link left to right. This is equivalent to the Shannon switching game on a rectangular grid. No draw is possible, and the first player can always win with perfect play. A commercial board game called Bridg-It was released in 1960 by Hassenfeld Brothers. It featured a plastic board with two i
- inventor
- Claude Shannon
- field
- Mathematics, electrical engineering, game theory
- nationality
- American
- known_for
- Inventing the Shannon switching game, father of information theory
- year_invented
- Some time before 1951
- related_game
- Gale (Bridg-It), invented by David Gale in the late 1950s
Lore & Background
The Shannon switching game was invented by Claude Shannon, an American mathematician and electrical engineer known as the 'father of information theory', some time before 1951. The game is played on a finite graph with two special nodes, A and B. The two players, Short and Cut, alternate moves: Cut deletes a non-colored edge, while Short colors any edge still in the graph. Short wins by creating a colored path from A to B; Cut wins by disconnecting A and B. The game always terminates with a winner, and on any given graph, either Short has a winning strategy regardless of who moves first, or Cut has a winning strategy regardless of who moves first.
The game is commonly played on a rectangular grid; this special case was independently invented by American mathematician David Gale in the late 1950s as the game Gale (also known as Bridg-It). An explicit solution for the undirected switching game was found in 1964 by Alfred Lehman, who showed the game is equivalent to a matroid intersection problem.
Reader's Guide
The Shannon switching game is significant as an early connection game that formalizes a duality between Short and Cut players, where Short tries to secure an edge set forming a circuit with a distinguished edge, and Cut tries to secure a cutset. The game can be seen as a special case of a Maker-Breaker game. An explicit solution using matroid theory was found in 1964: Short should aim for a position with a set of vertices including the two distinguished ones and two disjoint subsets of unchosen edges such that either subset (with already chosen edges) connects all vertices in that set; otherwise, Cut can win. Unlike some connection games that are PSPACE hard, optimal moves for the undirected switching game can be found in polynomial time per move, using matroid partitioning or network flow algorithms. The game's legacy includes electronic implementations on the Ludii Games Portal and an interactive Bridg-It demonstration on GitHub, as well as extensions like Qua, a three-player game on a 3D cube grid.
Did You Know?
- The Shannon switching game was invented by Claude Shannon, the 'father of information theory', some time before 1951.
- The game is commonly played on a rectangular grid; this special case was independently invented by American mathematician David Gale in the late 1950s and is known as Gale or Bridg-It.
- A commercial board game implementing the scheme was marketed in 1960 by Hassenfeld Brothers under the name Bridg-It.
- An explicit solution for the undirected switching game was found in 1964 using matroid theory.
More in Connection games 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record