Bridg-It - Revision history

Mglaezer: /* References */

2026-02-24T05:29:55Z

‎References

Selinger: /* References */ Added Gardner reference.

2024-08-04T13:56:03Z

‎References: Added Gardner reference.

Selinger: added link

2023-05-30T04:11:23Z

added link

Selinger: /* References */ Fixed reference

2022-01-28T05:32:13Z

‎References: Fixed reference

Selinger: /* References */ Added reference

2022-01-28T05:21:03Z

‎References: Added reference

Selinger: /* Every opening move is winning */ punctuation

2021-11-14T16:51:25Z

‎Every opening move is winning: punctuation

Selinger: Added "every opening move is winning".

2021-11-14T16:50:23Z

Added "every opening move is winning".

Selinger: Added a reference (which I used for the winning strategy).

2021-11-14T05:17:15Z

Added a reference (which I used for the winning strategy).

Selinger: /* Winning strategy */ Typo

2021-11-14T04:55:26Z

‎Winning strategy: Typo

Selinger: Described an explicit winning strategy for Bridg-It.

2021-11-14T04:54:58Z

Described an explicit winning strategy for Bridg-It.

← Older revision		Revision as of 05:29, 24 February 2026
Line 90:		Line 90:

	* Martin Gardner. [https://www.jstor.org/stable/10.2307/24944798 Mathematical games: Four mathematical diversions involving concepts of topology]. Scientific American, Vol. 199, No. 4 (October 1958), pp. 124–129.		* Martin Gardner. [https://www.jstor.org/stable/10.2307/24944798 Mathematical games: Four mathematical diversions involving concepts of topology]. Scientific American, Vol. 199, No. 4 (October 1958), pp. 124–129.
		+
		+	* [https://mglaezer.github.io/bridgit/ Web implementation of the winning strategy and practice companion for Bridg-It game].

	[[Category: Other games]]		[[Category: Other games]]

← Older revision		Revision as of 13:56, 4 August 2024
Line 88:		Line 88:

	* [[Ryan Hayward]] and Bjarne Toft. Hex: The Full Story. CRC Press, 2019. ISBN 978-0367144227. Sections 6.4, 8.1, and 8.2 discuss Bridg-It.		* [[Ryan Hayward]] and Bjarne Toft. Hex: The Full Story. CRC Press, 2019. ISBN 978-0367144227. Sections 6.4, 8.1, and 8.2 discuss Bridg-It.
		+
		+	* Martin Gardner. [https://www.jstor.org/stable/10.2307/24944798 Mathematical games: Four mathematical diversions involving concepts of topology]. Scientific American, Vol. 199, No. 4 (October 1958), pp. 124–129.

	[[Category: Other games]]		[[Category: Other games]]

@@ Line 1: / Line 1: @@
 [[Image: Connecto.png|right|250px]]
-'''Bridg-It''', also known as '''Gale''', is a connection game, similar to [[Hex]]. It was invented by the mathematician David Gale, and was described, under the name "Gale", in Martin Gardner's October 1958 column in ''Scientific American''. A version was later marketed by Hasbro under the name "Bridg-It".
+'''Bridg-It''', also known as '''Gale''', is a connection game, similar to [[Hex]]. It was invented by the mathematician [[David Gale]], and was described, under the name "Gale", in Martin Gardner's October 1958 column in ''Scientific American''. A version was later marketed by Hasbro under the name "Bridg-It".
 == Rules ==

@@ Line 87: / Line 87: @@
 * Sandy Dean, [https://digitalcommons.unl.edu/cgi/viewcontent.cgi?article=1009&context=mathmidexppap The Game of Bridg-It]. M.A. thesis, Department of Mathematics, University of Nebraska-Lincoln, July 2008.
-* Section 6.4 of [[Ryan Hayward]] and Bjarne Toft. Hex: The Full Story. CRC Press, 2019. ISBN 978-0367144227.
+* [[Ryan Hayward]] and Bjarne Toft. Hex: The Full Story. CRC Press, 2019. ISBN 978-0367144227. Sections 6.4, 8.1, and 8.2 discuss Bridg-It.
 [[Category: Other games]]

← Older revision		Revision as of 05:21, 28 January 2022
Line 86:		Line 86:

	* Sandy Dean, [https://digitalcommons.unl.edu/cgi/viewcontent.cgi?article=1009&context=mathmidexppap The Game of Bridg-It]. M.A. thesis, Department of Mathematics, University of Nebraska-Lincoln, July 2008.		* Sandy Dean, [https://digitalcommons.unl.edu/cgi/viewcontent.cgi?article=1009&context=mathmidexppap The Game of Bridg-It]. M.A. thesis, Department of Mathematics, University of Nebraska-Lincoln, July 2008.
		+
		+	* Section 6.4 of [[Ryan Hayward]] and Bjarne Toft. Hex: The Full Story. CRC Press, 2019. ISBN 978-0367144227.

	[[Category: Other games]]		[[Category: Other games]]

@@ Line 71: / Line 71: @@
 === Every opening move is winning ===
-The above explicit strategy shows that every vertical opening move on the bottom row is winning for Red. It is not difficult to generalize this to show that in fact ''every'' opening move is winning. One just needs to start with a different partition of the grey edges into a spanning tree and an almost-spanning tree.
+The above explicit strategy shows that every vertical opening move on the bottom row is winning for Red. It is not difficult to generalize this to show that in fact ''every'' opening move is winning. One just needs to start with a different partition of the grey edges into a spanning tree and an almost-spanning-tree.
 A consequence of this is that it does not make much sense to apply the [[swap rule]] to Bridg-It. No matter the opening move, the opponent should always swap.

@@ Line 38: / Line 38: @@
 == Winning strategy ==
 An explicit first-player winning strategy for Bridg-It is known. In fact, we can describe a strategy by which Red will connect ''all'' vertices by red paths, not just the top and bottom. It can be described as follows. We use 6x6 Bridg-It as an example, but the same strategy works for any (square) size.
@@ Line 66: / Line 68: @@
 The game continues in this way until there are no more grey edges. At this point, all three graphs are the same. Since one of them is a tree, all three of them are, i.e., Red has connected all vertices.
 == Commercial version ==

← Older revision		Revision as of 05:17, 14 November 2021
Line 74:		Line 74:

	* A Java implementation of Bridg-It by Roland Illig, using the name "Connecto": http://roland-illig.de/lang.java.connecto.html		* A Java implementation of Bridg-It by Roland Illig, using the name "Connecto": http://roland-illig.de/lang.java.connecto.html
		+
		+	== References ==
		+
		+	* Sandy Dean, [https://digitalcommons.unl.edu/cgi/viewcontent.cgi?article=1009&context=mathmidexppap The Game of Bridg-It]. M.A. thesis, Department of Mathematics, University of Nebraska-Lincoln, July 2008.

	[[Category: Other games]]		[[Category: Other games]]

@@ Line 39: / Line 39: @@
 == Winning strategy ==
-An explicit first-player winning strategy for Bridg-It is known. In fact, we can describe a strategy by which Red will connect ''all'' vertices by red paths, not just the top and bottom. It can be described as follows. We use 5x5 Bridg-It as an example, but the same strategy works for any (square) size.
+An explicit first-player winning strategy for Bridg-It is known. In fact, we can describe a strategy by which Red will connect ''all'' vertices by red paths, not just the top and bottom. It can be described as follows. We use 6x6 Bridg-It as an example, but the same strategy works for any (square) size.
 We first re-formulate Bridg-It as an edge Shannon game. When seen in this way, the game is played on the following graph:

← Older revision		Revision as of 04:54, 14 November 2021
Line 36:		Line 36:

	Bridg-It is a special case of the Shannon (edge) switching game, for which an optimal move can be found in polynomial time using matroid theory. In other words, the game is solved.		Bridg-It is a special case of the Shannon (edge) switching game, for which an optimal move can be found in polynomial time using matroid theory. In other words, the game is solved.
		+
		+	== Winning strategy ==
		+
		+	An explicit first-player winning strategy for Bridg-It is known. In fact, we can describe a strategy by which Red will connect ''all'' vertices by red paths, not just the top and bottom. It can be described as follows. We use 5x5 Bridg-It as an example, but the same strategy works for any (square) size.
		+
		+	We first re-formulate Bridg-It as an edge Shannon game. When seen in this way, the game is played on the following graph:
		+
		+	[[Image: Bridg-it0.png]]
		+
		+	The two players, Red and Blue, alternate. On Red's turn, Red colors one of the grey edges red. On Blue's turn, Blue erases one of the grey edges. Red wins if there is a red path connecting the top and bottom. This formulation is equivalent to the original Bridg-It; the only difference is that Blue erases edges, rather than crossing them out.
		+
		+	To describe Red's strategy, we keep track of three graphs. All three graphs have the same vertices. Initially, they are the following:
		+
		+	[[Image: Bridg-it1.png]]
		+
		+	The middle graph is the one the actual game is played on. The left and right graphs have the same red edges as the middle graph, but each grey edge is only present in exactly one of the left or right graphs. We note that the left graph is a tree (i.e., there is a unique path between any two vertices), and the right graph is the union of two trees (i.e., it has exactly two connected components, each of which is a tree).
		+
		+	Red plays as follows. Each time it is Red's turn, Red checks which of the two graphs (left or right) is disconnected. Red then picks an edge in the opposite graph (right or left) that connects the two disconnected components of the disconnected graph. (Such an edge always exists because the opposite graph is connected). Red colors this edge red in all three graphs (and in particular makes a move in the middle game). After Red's move, both the left and right graphs are trees.
		+
		+	[[Image: Bridg-it2.png]]
		+
		+	When it is Blue's turn, Blue erases one of the grey edges in the middle graph. We erase the corresponding grey edge in the left or right graph as well. Therefore, at the end of Blue's turn, exactly one of the left or right graphs is disconnected (a union of two trees), and the other is a tree.
		+
		+	[[Image: Bridg-it3.png]]
		+
		+	Now Red checks again which of the graphs is disconnected (it is again the right one). Red picks an edge from the left graph that will reconnect the right graph, and colors it red in all three graphs.
		+
		+	[[Image: Bridg-it4.png]]
		+
		+	The game continues in this way until there are no more grey edges. At this point, all three graphs are the same. Since one of them is a tree, all three of them are, i.e., Red has connected all vertices.

	== Commercial version ==		== Commercial version ==