Shannon switching game

Last updated

The Shannon switching game is a connection game for two players, invented by American mathematician and electrical engineer Claude Shannon, the "father of information theory", some time before 1951. [1] Two players take turns coloring the edges of an arbitrary 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 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. [2] [3]

Contents

Rules

Player Cut took 3 turns (dotted edges), player Short took 4 turns (green edges). Shannon game graph.svg
Player Cut took 3 turns (dotted edges), player Short took 4 turns (green edges).

The game is played on a finite 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. [4]

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 circuit, while Cut tries to secure an edge set that with e makes up a cutset, the minimal set of edges that connect two subgraphs.

Variants

Versions of the Shannon switching game played on a directed graph and an oriented matroid have been described for theoretical purposes; [5] [6] but no corresponding commercial games have been published.

Gale

A win for red in Gale BridgeIt2.svg
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. [7] 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 Gale is available in the 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 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 N3 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. [8]

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 including the two distinguished vertices, as well as two disjoint subsets of the remaining unchosen edges supported on , such that either of the two subsets (together with already chosen edges) would connect all vertices in . 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. [2] [9]

Unlike some other connection games, which can be PSPACE hard, [10] [11] 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 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 algorithms.

See also

Related Research Articles

<span class="mw-page-title-main">Dots and boxes</span> 2 player paper and pencil game

Dots and boxes is a pencil-and-paper game for two players. It was first published in the 19th century by French mathematician Édouard Lucas, who called it la pipopipette. It has gone by many other names, including dots and dashes, game of dots, dot to dot grid, boxes, and pigs in a pen.

In graph theory, the girth of an undirected graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles, its girth is defined to be infinity. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free.

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

<span class="mw-page-title-main">Hex (board game)</span> Abstract strategy board game

Hex is a two player abstract strategy board game in which players attempt to connect opposite sides of a rhombus-shaped board made of hexagonal cells. Hex was invented by mathematician and poet Piet Hein in 1942 and later rediscovered and popularized by John Nash.

<span class="mw-page-title-main">Bipartite graph</span> Graph divided into two independent sets

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

<span class="mw-page-title-main">TwixT</span> Connection board game in the 3M bookshelf game series

TwixT is a two-player strategy board game, an early entrant in the 1960s 3M bookshelf game series. It became one of the most popular and enduring games in the series. It is a connection game where players alternate turns placing pegs and links on a pegboard in an attempt to link their opposite sides. While TwixT itself is simple, the game also requires strategy, so young children can play it, but it also appeals to adults. The game has been discontinued except in Germany and Japan.

<span class="mw-page-title-main">Sim (game)</span> Two-player paper-and-pencil game

Sim is a two-player paper-and-pencil game.

<span class="mw-page-title-main">Edge coloring</span> Problem of coloring a graphs edges such that meeting edges do not match

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

The Black Path Game is a two-player board game described and analysed in Winning Ways for your Mathematical Plays. It was invented by Larry Black in 1960.

In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time from the determinant of a submatrix of the Laplacian matrix of the graph; specifically, the number is equal to any cofactor of the Laplacian matrix. Kirchhoff's theorem is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph.

<span class="mw-page-title-main">Wheel graph</span> Cycle graph plus universal vertex

In the mathematical discipline of graph theory, a wheel graph is a graph formed by connecting a single universal vertex to all vertices of a cycle. A wheel graph with n vertices can also be defined as the 1-skeleton of an (n – 1)-gonal pyramid. Some authors write Wn to denote a wheel graph with n vertices ; other authors instead use Wn to denote a wheel graph with n + 1 vertices, which is formed by connecting a single vertex to all vertices of a cycle of length n. The rest of this article uses the former notation.

<span class="mw-page-title-main">Signed graph</span> Graph with sign-labeled edges

In the area of graph theory in mathematics, a signed graph is a graph in which each edge has a positive or negative sign.

The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph. The Nash-Williams theorem provides necessary and sufficient conditions for when a graph is k-arboric.

<span class="mw-page-title-main">Dual graph</span> Graph representing faces of another graph

In the mathematical discipline of graph theory, the dual graph of a planar graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

In graph theory, a connected graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.

<span class="mw-page-title-main">Handshaking lemma</span> Every graph has evenly many odd vertices

In graph theory, a branch of mathematics, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. For example, if there is a party of people who shake hands, the number of people who shake an odd number of other people's hands is even. The handshaking lemma is a consequence of the degree sum formula, also sometimes called the handshaking lemma, according to which the sum of the degrees equals twice the number of edges in the graph. Both results were proven by Leonhard Euler in his famous paper on the Seven Bridges of Königsberg that began the study of graph theory.

<span class="mw-page-title-main">Pseudoforest</span> Graph with at most one cycle per component

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

In the mathematical subject of matroid theory, the bicircular matroid of a graph G is the matroid B(G) whose points are the edges of G and whose independent sets are the edge sets of pseudoforests of G, that is, the edge sets in which each connected component contains at most one cycle.

A connection game is a type of abstract strategy game in which players attempt to complete a specific type of connection with their pieces. This could involve forming a path between two or more endpoints, completing a closed loop, or connecting all of one's pieces so they are adjacent to each other. Connection games typically have simple rules, but complex strategies. They have minimal components and may be played as board games, computer games, or even paper-and-pencil games.

<span class="mw-page-title-main">Structural rigidity</span> Combinatorial theory of mechanics and discrete geometry

In discrete geometry and mechanics, structural rigidity is a combinatorial theory for predicting the flexibility of ensembles formed by rigid bodies connected by flexible linkages or hinges.

References

  1. Gardner, M. (1961). The Second Scientific American Book of Mathematical Puzzles and Diversions. NY: Simon and Schuster. pp. 86–87.
  2. 1 2 Lehman, Alfred (1964). "A solution of the Shannon switching game". Journal of the Society for Industrial and Applied Mathematics. 12 (4): 687–725. doi:10.1137/0112059. JSTOR   2946344. MR   0173250.
  3. Hayward, Ryan B.; van Rijswijck, Jack (2006). "Hex and combinatorics". Discrete Mathematics . 306 (19–20): 2515–2528. doi:10.1016/j.disc.2006.01.029. MR   2261917.
  4. Stephen M. Chase (1972). "An implemented graph algorithm for winning Shannon Switching Games". Communications of the ACM . 15 (4): 253–256. doi: 10.1145/361284.361293 . S2CID   21110956.
  5. Hamidoune, Yahya Ould; Las Vergnas, Michel (1986). "Directed switching on graphs and matroids". Journal of Combinatorial Theory . Series B. 40 (3): 237–239. doi:10.1016/0095-8956(86)90083-3.
  6. Cláudio, A. P.; Fonseca, S.; Sequeira, L.; Silva, I. P. (2015). "Shannon switching game and directed variants". In Bourguignon, J.-P.; Jeltsch, R.; Pinto, A.A.; Viana, M. (eds.). Dynamic, Games and Science: International Conference and Advanced School Planet Earth, DGS II, Portugal, August 28–September 6, 2013. CIM Series in Mathematical Sciences. Springer. pp. 187–199. doi:10.1007/978-3-319-16118-1_10. ISBN   978-3-319-16117-4.
  7. Bridg-it at BoardGameGeek
  8. "Qua". BoardGameGeek. Retrieved 2020-08-28.
  9. Mansfield, Richard (1996). "Strategies for the Shannon switching game". The American Mathematical Monthly. 103 (3): 250–252. doi:10.1080/00029890.1996.12004732.
  10. Even, S. (October 1976). "A Combinatorial Problem Which is Complete in Polynomial Space". Journal of the ACM . 23 (4): 710–719. doi: 10.1145/321978.321989 . S2CID   8845949.
  11. Reisch, Stefan (1981). "Hex ist PSPACE-vollständig". Acta Informatica . 15 (2): 167–191. doi:10.1007/BF00288964. MR   0599616. S2CID   9125259.