Hex/Bridg-It

Before diving in, let's dip our toes into a little graph theory!

Review of Graph Theory

Spanning tree- is a subset of a graph, G, where each vertex connects with all other vertices in G without creating a cycle.

A                                        B

Figure 1: A shows a picture of a regular graph and B shows a picture of a spanning tree of the original graph

https://www.tutorialspoint.com/discrete_mathematics/images/minimum_spanning_tree.jpg

Disjoint spanning trees- two spanning trees are said to be disjoint if they have no common edges.

If you have any questions about spanning trees, let me know in the comments section and I will try to help clarify any confusion!

The Game of Bridg-It

Bridg-It is a two player board game that consists of two rectangular arrays of dots, one array for each player.  The players take turns placing an edge between two adjacent dots with their designated color.  Edges may not cross.  The object of the game is to create a continuous path of bridges from one side of the board to the other where their assigned color is but we also want to try and prevent the opponent from achieving the same goal.  The first person to create a bridge to the other side wins. 

Click here to play Bridg-It online and follow the directions to the right of the page.  This version isn't perfect but try it out to get a feel for how the game is played!

Before moving on, see if you can come up with any conjectures!  Do you see a pattern when you play, or a particular winning strategy?  Feel free to write them in the comments section!

Figure 2: Sample Bridg-It game

https://matemelga.files.wordpress.com/2013/08/bridgit.jpg

How might spanning trees apply?

Bridg-It consists of multiple spanning trees.  When given the game board, think about creating two disjoint spanning trees where there are no common edges between them.

To start, let’s create two edge-disjoint spanning trees in player 1’s graph (say he is blue) and allow the sides to be a single combined post or vertex.  This is an easy way to think about the game because the bridge only needs to connect with a single vertex of each side in order to win.  Note that it doesn’t matter which vertex it connects to. 

Next, we can connect all the vertices in the graph forming one original spanning tree.  When constructing the second spanning tree, we need to make sure not to share edges with the original spanning tree.  Below is a picture of how to go about this.

Figure 3: example of two disjoint spanning trees for player 1’s graph

http://digitalcommons.unl.edu/cgi/viewcontent.cgi?article=1009&context=mathmidexppap.

Before beginning the game we can take away the circular edge of the original spanning tree connecting both posts since this is not part of the game.  Once the game has started, player 1 makes an arbitrary move and chooses an edge.  After playing this edge, player 1 is essentially using the edge in both trees making it a double edge. 

Player 2 cannot cut a double edge.  In other words, they cannot block both the original and second spanning trees (since they only have one move).  So they can only block the edge from one tree leaving the other tree connected for player 1 to continue their path. 

When player 2 makes their move, they are essentially “taking away” an edge from one of the spanning trees of player 1.  (This can be confusing so stay with me!!)

The strategy for player 1 is to block and defend the strategy of player 2.  In doing this, player 1 keeps creating double edges.  These double edges slowly form a tree that connects the opposite sides of the board to give player 1 a guaranteed win. 

Of course this goes without saying that player 1 can lose if they create a cycle or do not properly defend against player 2.  However, player 1 has the upper hand if they take use of this spanning tree advantage.

Phew!!!

Do you have an understanding of what’s going on?  If so, great!  If not, try reading this section over a couple of times.  If you are still confused, let me know!  I do plan on going over this in class :)

The game of Hex

Hex is another connection game that is almost identical to Bridg-It.  Is is a two player game and is typically played on an 11x11 board with numerous hexagons that form a rhombus shape.  Both players are assigned a different color (i.e. red and blue).

The players take turns placing their colored hexes on the board and the pieces can only be placed on unoccupied spaces.  The object of the game is to have a path of hexes going to the opposite side of the board marked by their color.  The first player to complete their chain of pieces from one side of the board to the other is the winner.

Figure 4: sample of a hex game where the blue player wins

https://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Hex-board-11x11-(2).jpg/250px-Hex-board-11x11-(2).jpg

Ultimately, Hex and Bridg-It are the same only Hex uses hex pieces and Bridg-It uses lines or bridges.

Note that the application of spanning trees above can also be applied to Hex, however it is visually easier to see when applying it to Bridg-It.

Click here to play the game of Hex!

Strategy-Stealing Argument

In combinatorial game-theory, this argument shows that in many two player games (including Bridg-It and Hex), the second player cannot have a definite winning strategy and that there cannot be a draw/tie.  This is represented in a proof by contradiction.

Below is essentially an informal proof of this argument.

Proof by Contradiction:

1. Since either the first of second player wins, then one of them must have a winning strategy.

2. Assume the second player has a winning strategy.

3. Now the first player can “steal” or implement that strategy.  Let the first player make an arbitrary move.  Afterwards, he plays the winning strategy of the second player assumed above.  In playing this strategy, if he has to play on the cell where an arbitrary move was made, he makes another arbitrary move.  In this way, the first player plays the winning strategy with one extra piece always on the game board.

4. This extra piece will not interfere with the first player’s imitation of the winning strategy because an extra piece is always an asset in the game.  Hence, the first player can win.

5. Since we have contradicted our original assumption that there is a winning strategy for the second player, we therefore conclude that there must be a winning strategy for the first 

player.

Hold up!  You mean to tell me that player 1 can just steal player 2’s strategy!?  Oh yeah…it’s like taking candy from a baby (that baby being player 2)!

http://makeagif.com/H9nFey

Since the first player is guaranteed to win, sometimes players use the pie rule (swap rule) to make things fair.  This allows the second player to choose whether to swap positions with the first player after the first player makes the first move.

Applying strategy-stealing to other games

What makes strategy stealing so important is that we can apply it to games we have already seen!  We have actually seen this in 2-pile Nim!

http://www.reactiongifs.com/r/2013/02/shocked.gif

…I didn’t see that coming!  Just kidding.  It seems like everything that we have talked about thus far in Game Theory relates back to Nim!

In my presentation, we will see just how the strategy-stealing argument applies to 2-pile Nim.

Conclusion

The strategy-stealing argument is very important because we can apply it to many other two-player games that cannot end in a draw.  Thus, we know strategy-stealing can be applied to Hex, Bridg-It, and Nim but what about other games?

Food for thought:  If you find yourself playing Bridg-It or Hex with a friend, you most definitely want to go first!  If you have a general understanding of spanning trees, you can use this to your advantage when playing these two games.  Understanding how to use two disjoint spanning trees is a key strategy that can help you win.

Questions that might strike your fancy:

1. Can you think of any other two player games that the strategy-stealing argument applies to?  If so, how might it apply?

2. How might the strategy-stealing argument be applied to 2-pile Nim?

3. Are there any differences in how strategy-stealing might be applied to 2-pile Nim versus Hex and Bridg-It?

And…We’re done!!

https://m.popkey.co/9b305c/y6wJ7.gif

Citations

Wikipedia. Wikimedia Foundation, 2017. s.v “Hex (board game).” Accessed February 7, 2017. https://en.wikipedia.org/wiki/Hex_(board_game).

Sandy Dean. “The Game of Bridg-It.” July 1, 2008. Accessed February 7, 2017. http://digitalcommons.unl.edu/cgi/viewcontent.cgi?article=1009&context=mathmidexppap.