View source for Shannon switching game

{{Short description|Pencil and paper connection game}}
The '''Shannon switching game''' is a [[connection game]] for two players, invented by [[Americans|American]] mathematician and electrical engineer [[Claude Shannon]], the "father of information theory", some time before 1951.<ref>{{cite book|last1=Gardner|first1=M.|authorlink=Martin Gardner|title=The Second Scientific American Book of Mathematical Puzzles and Diversions|date=1961|publisher=Simon and Schuster|location=NY|pages=86–87}}</ref>  Two players take turns coloring the edges of an arbitrary [[Graph (discrete mathematics)|graph]]. One player has the goal of connecting two distinguished vertices by a path of edges of their color. The other player aims to prevent this by using their color instead (or, equivalently, by erasing edges).  The game is commonly played on a [[grid graph|rectangular grid]]; this special case of the game was independently invented by American mathematician [[David Gale]] in the late 1950s and is known as '''Gale''' or '''Bridg-It'''.<ref name=lehman/><ref>{{cite journal
 | last1 = Hayward | first1 = Ryan B.
 | last2 = van Rijswijck | first2 = Jack
 | doi = 10.1016/j.disc.2006.01.029
 | issue = 19–20
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 2261917
 | pages = 2515–2528
 | title = Hex and combinatorics
 | volume = 306
 | year = 2006| doi-access = 
 }}</ref>

== Rules ==
[[Image:Shannon_game_graph.svg|right|thumb|Player Cut took 3 turns (dotted edges), player Short took 4 turns (green edges).]]
The game is played on a finite [[Graph theory|graph]] with two special nodes, ''A'' and ''B''. Each edge of the graph can be either colored or removed. The two players are called ''Short'' and ''Cut'', and alternate moves. On Cut's turn, Cut deletes from the graph a non-colored edge of their choice. On Short's turn, Short colors any edge still in the graph.  If Cut manages to turn the graph into one where ''A'' and ''B'' are no longer connected, Cut wins. If Short manages to create a colored path from ''A'' to ''B'', Short wins. The game always terminates after a finite number of moves, and one of the two players has to win. Either Short, Cut, or the player moving first is guaranteed the existence of a winning strategy on any given graph.<ref>{{cite journal|author=Stephen M. Chase |year=1972|title=An implemented graph algorithm for winning Shannon Switching Games | journal=[[Communications of the ACM]] | volume=15 | pages=253–256|doi=10.1145/361284.361293|issue=4|s2cid=21110956|doi-access=free}}</ref>

The ''Short'' and ''Cut'' games are a duality; that is, the game can be restated so that both players have the same goal: to secure a certain edge set with distinguished edge ''e''. Short tries to secure the edge set that with ''e'' makes up a [[Cycle (graph theory)|circuit]], while Cut tries to secure an edge set that with ''e'' makes up a cutset, the minimal set of edges that connect two [[Glossary of graph theory#Subgraphs|subgraphs]].

==Variants==

Versions of the Shannon switching game played on a [[directed graph]] and an [[oriented matroid]] have been described for theoretical purposes;<ref>{{cite journal|last1=Hamidoune|first1=Yahya Ould|last2=Las Vergnas|first2=Michel|author2-link= Michel Las Vergnas |title=Directed switching on graphs and matroids|journal=[[Journal of Combinatorial Theory]]|date=1986|series=Series B|volume=40|issue=3|pages=237–239|doi=10.1016/0095-8956(86)90083-3|doi-access=}}</ref><ref>{{cite conference|first1=A. P.|last1=Cláudio|first2=S.|last2=Fonseca|first3=L.|last3=Sequeira|first4=I. P.|last4=Silva|title=Dynamic, Games and Science: International Conference and Advanced School Planet Earth, DGS II, Portugal, August 28–September 6, 2013|series=CIM Series in Mathematical Sciences|editor1-last=Bourguignon|editor1-first=J.-P.|editor2-last= Jeltsch|editor2-first= R.|editor3-last= Pinto|editor3-first= A.A.|editor4-last=Viana|editor4-first= M. |date=2015|contribution= Shannon switching game and directed variants |publisher=Springer|isbn=978-3-319-16117-4|pages=187–199|doi=10.1007/978-3-319-16118-1_10}}</ref> but no corresponding commercial games have been published.

===Gale===
[[File:BridgeIt2.svg|thumb|A win for red in Gale]]
In this game invented by American mathematician [[David Gale]] and described in [[Martin Gardner]]'s column in ''Scientific American'' Oct. 1958, two grids of differently-colored dots are overlaid at an offset. One player links orthogonally adjacent dots on one grid, and the other player uses the other. One player attempts to link the top of their grid to the bottom, while the other tries to link their left side to the right.  The game is equivalent to the Shannon switching game played on a rectangular grid.  No draw can result; the first player can always win with correct play.

A commercial board game implementing the scheme was marketed in 1960 by [[Hassenfeld Brothers]] under the name Bridg-It.<ref>{{bgg|11052|Bridg-it}}</ref> The game consisted of a plastic board with two interleaved 5x6 rectangular grids of pedestals (one set yellow, the other red), two sets of 20 each red and yellow plastic bridges, and matching pegs to mount them on.  Players alternate placing a bridge across any two adjacent pedestals of matching color until one player connects the two opposite sides of the board marked in the player's color.  A variant of the game is described in the instructions: each player gets a limited number of bridges, say 10.  If neither player has won when all the bridges are placed, a player in his turn, may reposition one of his bridges until a winner results.  The game is long out of production.

An electronic implementation of the Game of [https://ludii.games/details.php?keyword=Gale Gale] is available in the [https://ludii.games/index.php Ludii Games Portal].

==Relationship to other games==
The Shannon switching game can be seen as a special case of a [[Maker-Breaker game]], in which the winning patterns for the Maker are connecting paths.

A weakly-related connection game [[Hex (board game)|Hex]] is played on a grid of hexagons, and has 6-connectivity. Generalized Hex is played on a graph, just like the Shannon game, but instead of coloring the edges, in Hex the players color the vertices. These games have completely different structure and properties.

Another connectivity game played with paper and pencil on a rectangular array of dots (or graph paper) is the children's game of "[[dots and boxes]]".  Players alternate drawing in a vertical or horizontal line connecting any two adjacent dots.  When a line completes a square, the player initials the square.  After all the lines have been filled in, the player who has taken the most squares is the winner.

An extension of Gale, called Qua, is played by three players on a 3D game board cube composed of a grid of N<sup>3</sup> cells. N is an odd number equal to the number of cells along the edges of the game board cube. The initial Qua Cube game board layout and rules are described at its Board Game Geek entry.<ref>{{Cite web|title=Qua|url=https://boardgamegeek.com/boardgame/312939/qua|access-date=2020-08-28|website=BoardGameGeek|language=en-US}}</ref>

==Computational complexity==

An explicit solution for the undirected switching game was found in 1964 for any such game using [[matroid]] theory. ''Short'' should aim for a position in which there exists a set of vertices <math>S</math> including the two distinguished vertices, as well as two disjoint subsets of the remaining unchosen edges supported on <math>S</math>, such that either of the two subsets (together with already chosen edges) would connect all vertices in <math>S</math>. If ''Short'' can make a move that results in a position with this property, then ''Short'' can win regardless of what the other player does; otherwise, ''Cut'' can win.<ref name=lehman>{{cite journal
 | last = Lehman | first = Alfred
 | issue = 4
 | journal = Journal of the Society for Industrial and Applied Mathematics
 | jstor = 2946344
 | mr = 0173250
 | pages = 687–725
 | title = A solution of the Shannon switching game
 | volume = 12
 | year = 1964| doi = 10.1137/0112059
 }}</ref>
<ref name=mansfield>{{cite journal
 | issue = 3
 | last=Mansfield | first = Richard
 | journal = The American Mathematical Monthly
 | pages = 250–252
 | title = Strategies for the Shannon switching game
 | volume = 103
 | year = 1996
| doi=10.1080/00029890.1996.12004732 }}
</ref>

Unlike some other connection games, which can be [[PSPACE]] hard,<ref>{{cite journal | url=http://hex.kosmanor.com/hex/jacm23/t710.html | title=A Combinatorial Problem Which is Complete in Polynomial Space | last=Even|first= S. | authorlink= Shimon Even | journal=[[Journal of the ACM]] |date=October 1976 | volume=23 | issue=4 | pages=710–719 | doi=10.1145/321978.321989| s2cid=8845949 | doi-access=free }}</ref><ref>{{cite journal
 | last = Reisch | first = Stefan
 | doi = 10.1007/BF00288964
 | issue = 2
 | journal = [[Acta Informatica]]
 | mr = 599616
 | pages = 167–191
 | title = Hex ist PSPACE-vollständig
 | volume = 15
 | year = 1981| s2cid = 9125259
 }}</ref> optimal moves for the undirected switching game can be found in [[polynomial time]] per move. After removing from the graph the edges chosen by ''Cut'', and contracting the edges chosen by ''Short'', the resulting graph is a [[minor (graph theory)|minor]] of the starting graph. The problem of testing for the existence of two disjoint trees, each connecting the distinguished vertices, can be represented as a [[matroid partitioning]] problem, which can be solved in polynomial time. Alternatively, it is possible to solve the same problem using [[Network flow problem|network flow]] algorithms.

==See also==
*[[TwixT]], a different and harder connection game on the square grid

==References==
<references/>

==External links==
{{commons category}}
* [https://web.archive.org/web/20080609003516/http://kryshen.pp.ru/games/graphg.html Graph Game], a Java implementation of the Shannon switching game

[[Category:Positional games]]
[[Category:Paper-and-pencil games]]
[[Category:Abstract strategy games]]
[[Category:Connection games]]
[[Category:Claude Shannon]]