Shannon switching game

Shannon switching game

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".

Rules

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, he deletes from the graph a non-colored edge of his choice. On "Short" 's turn, he colors any edge still in the graph. If "Cut" manages to turn the graph into one where "A" and "B" are no longer connected, he wins. If "Short" manages to create a colored path from "A" to "B", he wins.

There are also versions of the Shannon switching game played on a directed graph and an oriented matroid. A solution has been explicitly found for any such game using matroid theory, unlike a similar game Hex, which is PSPACE hard.

Winning algorithms

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. [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]

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. [ [http://sky.fit.qut.edu.au/~maire/ALL/2004%20connectioin%20game%20book%20appendix%20%20maire-shannon.PDF Frederic Maire: "The Solution of Shannon Game"] , 2004]

References

External links

* [http://kryshen.pp.ru/games/graphg.html Graph Game] , a Java implementation of the Shannon switching game


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Claude Shannon — Claude Elwood Shannon (1916 2001) Born April …   Wikipedia

  • Hex (board game) — Infobox Game subject name=The Game of Hex image link= image caption=A rendering of a Hex game on a 19x19 board players=2 ages=4+ setup time=1 minute playing time=15 minutes (11x11 board) complexity=Low strategy=High random chance=None… …   Wikipedia

  • List of game topics — The list of game topics aims to list articles related to games.#8 bit era 16 bit era 32 bit and 64 bit era 128 bit eraAAbalone (board game) Abandonware Abstract strategy game Acquire Advanced Dungeons Dragons Advanced Squad Leader Adventure game… …   Wikipedia

  • Still Life (video game) — Infobox VG | title = Still Life developer = Microïds publisher = EU MC2 NA The Adventure Company designer = engine = Virtools released = NA start date|2005|4|15(WIN) EU June 3, 2005 (WIN), (Xbox) NA June 6, 2005 (Xbox) genre = Adventure modes =… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Strategy-stealing argument — In combinatorial game theory, the strategy stealing argument is a general argument that shows, for many games, that the second player cannot have a winning strategy (i.e., a strategy that will always win the game for them, no matter what moves… …   Wikipedia

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

  • Computer — For other uses, see Computer (disambiguation). Computer technology redirects here. For the company, see Computer Technology Limited. Computer …   Wikipedia

  • List of The X-Files characters — For Monster of the Week characters, see List of Monster of the Week characters in The X Files. The following is a list of all main and recurring characters (who have appeared three times or more, with a few exceptions) in the American science… …   Wikipedia

  • Ōgon Musōkyoku — Developer(s) 07th Expansion Publisher(s) 07t …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”