Spiked Math Games  // Math Fail Blog  // Gauss Facts  // Spiked Math Forums  // Spiked Math Comics

puzzle-001

MPF - Hex - February 10, 2012
• Currently 4.7/5
• 1
• 2
• 3
• 4
• 5
Today  is Math Puzzle Friday (MPF), Yay! Every Friday I'll describe a riddle, game, logic puzzle, etc., that I find interesting and want to share with you. Some of you will surely have heard of the puzzles discussed and may already know the solutions, but to those who haven't, I hope you find them enjoyable!

Make sure you play with your math friends, or else you may be left behind:

Today's puzzle is the game of Hex. The rules are simple. It's a two player game played on an m x n board filled with hexagons, as depicted below on the left.

Problem 1: Prove that the game can never end in a tie (for every m x n Hex board). This fact was proved by John Nash - remember the movie A Beautiful Mind?

Problem 2: Who has a winning strategy on n x n (symmetric) boards? What about m x n (m not equal to n) boards?  [Tip: Perhaps start with small values of m & n.]

A few small Hex boards to play around with.

http://en.wikipedia.org/wiki/Hex_%28board_game%29

#1:I think if the red sides are not connected, then there must be a line connecting the blue sides...Is there such a topology theorem?

And as the players take turns, it is also impossible for them to both win at the same time :)

Any significance to the number 47 on the new player ?

Poor 47 is the mathematical doufus.

And he never changes his shirt.
Or maybe he has, and I just didn't recognize him.

... or maybe he has 47 shirts, all the same.

The new Spiked Maths is awesome!

I'd pose the proof to #1 the other way around; if two opposite sides are connected, the other two sides are separated, as each position can only hold one color.

In addition, if the entire board is filled, it's impossible not to connect two facing sides. I'm a biologist - not a mathematician - so I don't know how to write down the proof to this in equations. It seems obvious when looking at the boards, though. If forced to, I'd probably go about it in a 'proof by exhaustion' manner for boards up to a certain size.

Based entirely on intuition, I'd say #2 goes as follows;

For symmetric boards, or asymmetric boards where the smallest dimension is 1 or 2, the player that moves first always wins. Take the center and you're practically done.

For asymmetric boards whose smallest dimension is >2, the player trying to connect the longest edges (i.e., the ones separated by the smallest amount of hexagons) always wins.

For the second question:
- nxm, the player with the smallest line to do win.
- nxn, the first player win

#1:
The only way of creating a tie is to destroy the chain of the other player, which improves your own situation (you have to "cut" the left and right side of the fares hexagon, and this, obviously, reduces the "steps to go" to your aim). Therefore it is not possible to create a tie.

#2:
It's kind of obvious that you win the game on any nxn board if you start (to make this up there is an extra rule not mentioned here). On any nxm board the player with the shorter path has a better chance to win I guess... have to prove it in silence tonight.

For n by n, win by playing symmetrically to the opponent. If n is odd the first player does this by taking the center cell (no symmetric matching cell); for even n, the second payer retains the symetry.

I don't know what I was thinking there. Since each side has different (possible) winning paths symmetry is not germane.

Hmmm... I've played this before (on a symmetric 15*15) and did not know that there was a winning strategy for the game. It seems a lot of people have been content with the following "proof":
The first player wins. QED
I see one suggestion to play symmetrically. However, if you only copy someone's moves then then the copied player can easily force the copier to lose. For instance, if player one takes center and player two starts a bead along the top row then player one, playing symmetrically, cannot hope to win. Perhaps the answer is obvious but I've yet to see it for large boards. I will admit that there are very good local strategies for offense and defense:
Offense: Play in hexes which have two common neighbors - i.e. which have two corners connected by an edge.
Defense (as a counter): Play in hexes 3 spaces away in a given direction (across hex bodies, not edges). This way you are following the first rule for offense two turns in advance and thus preventing your opponent from using it.
As of yet I know no global solution, but I'd like to see it!

Ok... sorry for double posting... Can you reduce this to one reply? Last post, I promise.

For Robert. You want to know about the winning strategy? Game Strategy would use the alpha-beta method. see at http://en.wikipedia.org/wiki/Alpha-beta_pruning

Ok.... so basically you play a move in your mind, then you play as your opponent and respond to yourself, respond to your response. This way you get a sort of optimization to which moves you can win with... (It is essentially thinking ahead in chess.) Alternatively, you can backchain: start with a guaranteed win position for you. Then you find a position which would guarantee the guaranteed win. And continue until you reach the move. For example: reaching the center first is a win. Then find a way to reach the center before he does and continue

Sorry for the symmetry comment...

There is a fairly straightforward proof that the second player cannot have a winning strategy: if such a strategy is claimed, the first player makes a random move then he applies the strategy while ignoring his random move. Whenever the strategy calls for him to occupy the random move cell, he makes another random move. [I first encountered this proof in Martin Gardner's write0-up on Hex, one of hs first columns for Scientific American.]

One proof that first player win on a nxn is:
One of the player has to win (exo 1), so now let assume that the second player has a winning strategy, what can do the first player (as the board is symmetric) is: chose a random hypothetical move for the second player (so now the first player is hypothetically playing second), so he can use the winning strategy, whenever the second player does actually this move, player 1 can chose another random move for the second player and then play the winning strategy, so the first player could win, so player 2 has no winning strategy. Furthermore, as one player has to win, it has to be player 1! (Note that we do not have the winning strategy, but it exists).

For a nxm game, the player with the shortest path, even if he plays second can reduce the game in a nxn (n

This is very close to a general proof I thought out nearly 50 years ago for a large number of games. Those where after a finite number of moves one of the two players must have won, and where there is no zugzwang (sp?). Zugzwang is a term in chess for a position which is good but any move makes it bad. If these don't happen in a finite two person game where the second player has a strategy then the first player must have a strategy to win, because the first player can get a better position... .

zugzwang doesn't apply to Hex, since an extra piece on the board is never a liability. So the general proof that the first player has a winning strategy is:

1. Assume the second player has such a strategy. The first player then plays randomly, thereafter playing by the second player's strategy. He must win, so the assumption is wrong, and hence only the first player should have a winning strategy.

For the n x n boards the number of possible moves is n ^2 Making it a perfect square
All perfect squares end in either 0,1,4,5,9 meaning that there is both even and odd perfect squares.
when the first player moves the number of possible moves changes to n^2 - 1 then the next moves leaves n^2-2 possible moves.
Now assuming the two players are of equal skill level all possible moves will most likely be filled Leaving the winner is determined by the size of the board and who goes first. In a n x n board where n^2 is an odd number the first player will win.
Conversely if n^2 is even then the second player has the advantage.
I have not completely worked out a proof for this I'm just looking at it intuitively.

On a 2x2 board, it is easy to see that first player wins...

I do not really understand this sentence:
"Now assuming the two players are of equal skill level all possible moves will most likely be filled"

Do you assume that the winner is the last one to play? I had the feeling that if both play perfectly the game ends way before all the board is filled in, I even think that the number of moves for the first to win is in O(n), I have no proof for that, but I think I have the idea of the strategy to win, and I will probably do less than 2n moves. (I might be wrong).

Anyway, I am pretty sure the first player always win :D.

The last move made in the game is the winning move.
I realize now that in my statement
"Now assuming the two players are of equal skill level all possible moves will most likely be filled"
I was unclear. What I mean by that is if they are both of equal skill level they both would each know the same strategies. This would give you a more of a defensive game on both sides. This would most likely lead to a game board where nearly every empty space or possible move is filled.

When I used the statement "if n^2 is even then the second player has the advantage."
What I meant by advantage is who has the most possible moves.

Clearly there are cases in the smaller boards where the first player will always win. But as the boards get larger the advantages begin to change with the size of the board. This advantage shift is why the game was originally played on m x n board because this is a rectangular board which can have any number of possible moves, or open spaces, Where a n x n board is confined to the patterns of the perfect squares.Perfect squares have so many patterns and restrictions that predicting square games is much easier than rectangular games. Sorry if this explanation is still confusing. I am trying to keep it simple without going into combinatorics and "zero game" strategy. I have only just begun to study combinatorics myself so I am not the best to explain those theories.

First player has always more possibilities than second player...

And when the board become bigger, the winning strategy for the first player may be harder to find (but I don't think so, because I guess there is a pattern), but it still exists (cf my proof above, unless there is an error, in this case, thanks to tell me where :D ).

Alright im seeing a lot of proofs for the second method...

This is the simple proof from classic backchaining:
Lets start with a 2x2 board: The first person who moves wins.

So now we move to the simple 2x3 board (The person who has the longest side moves first): The first person moves, thereby reducing the problem to a 2x2 board: The second person moves "first" now in this new 2x2 board, taking the win.

A simple 3x3 board: First person moves and reduces it to a 2x3 board. Second person moves reducing it to a 2x2 board. First person moves and wins.

etc....

For any nx1 board where n is greater than 1. Person with the shortest side places 1 piece and always wins

For any (n+m)x(1+m) board using the back chaining shown above (left as a practice problem to the reader) you will reach an nx1 board. The 1+m side wins.

For any Y < Z
A YxZ board can be expressed as a (n+m)x(1+m) board therefore the player with the shortest side always wins.

This proves #2:
For any Y<Z and a YxZ board: the shorter side always wins
For any NxN boards: first person always ends

because given 2 constants: X and Y, X is always equal to Y or X is greater than or less than Y. Every board has a solution. Therefore there can not be any ties.

I agree about the idea, not about the way you present it:
the first player cannot move wherever he wants, actually there is only 3 moves that can lead to a win, all the 6 others lead to a winning configuration for player 2.

I agree to say that if he plays smartly, we can reduce the problem to a smaller board, and then prove he has a winning position, but the way you present it let me think that the first player can do whatever he wants (and not only in the first move, but for every move, which mean if he plays at random she/he still wins :D).

If you weren't implying that he can move (at least for the first one at random), explain what move he has to do to reduce to a smaller board, and in another hand, when you present the problem for a 2x3, you should proof that whatever move she/he does, that reduce the problem to a 2x2, it is not obvious (even if it is obvious that the second player mays always win), because if she/he plays in the middle of the game, some move for the second player lead to a winning configuration for player 1.

assume the 2x3 board. assume someone starts on the short side as the first player. then the second player needs to play the other corner of the short side, if not the first player gets a 2-stone path and wins.

now a 2×2 field remains, with the first player having the first move. so the first player
wins on a 2×3 field, when he does on a 2×2 (which is easy to see).

now assume we have a n×m winning board m > 2 wlog. n > m, and extend it to (n+1)×m.

the first player sets a stone on a corner. the second player needs to cut the path
along the short edge, because this is the fastest winning strategy, when the other
one is the first player.

But then still some fields of the additional row remain, so we cannot reduce it to
the n×m case easily.

i would suppose the next best move of the first player is now to play the corner of the
remaining n×m field, starting a new attempt to use another path along the short edge.
the second player again needs to cut the path. so they continue, until the first player
sets the stone which completes the path along the long edge.

now we can assume, the other player does not cut the short path on first try, but cuts
the long path in one move. now the first player would play the next stone on the short
path. the second player now cuts the short path (on non-trivial boards).

Now the first player plays a sidewards move. now he can again try to connect the other
end of the short path, which will be faster than anything the second player can achieve.
the second player can always either cut the path up or the path to the side, without
building a useful chain himself. so the first player will always either reach the end of
the short edge or the end of the long edge.

because he started in a corner, its not important which edge is reached first.
So the first one always wins.

Ok this is a reply: we are mathematicians. We don't find the win... we prove that it is possible.... its like, when we wake up and see a fire in the wastebasket: we convince ourselves that it is possible to put the fire out and then go back to sleep. If we wake up and don't see a fire in the wastebasket, we put the wastebasket on fire thereby reducing the situation to a previously solved problem and then go to sleep. =)

I appreciate the humor and I know that one simply has to prove 'that a win exists' and not how to do it. However, up until that point I had seen no adequate proofs for the existence of a win. Since then some comments have been made which seem closer to a proof, though I haven't taken the time to test their validity.
I would really like a proof by construction or induction here. Both are easy to understand and the first actually provides a winning strategy. Lastly, some assumptions I've seen for 'optimal' moves are not very optimal and players would not necessarily play in that manner. In my experience the best defensive strategy is local, not global - no right minded second player would burn down one column as the first player burned down an opposite row, just because the column is a shortest path, as it's clear that first player wins! (On an nXn board, mind you - I don't really care much about non-symmetrical boards as they most certainly give an advantage to the player going the shortest route.)

As for no game ending in a tie, it seems simple: the only way to block a full board from having a red winning route is for blue to have a line across the whole board from edge to edge--which means blue wins.

You could have the board split evenly across the middle, neither red nor blue makes a crossing.

No, because they go between different pairs of sides. If it were split that way, one or the other would still connect their sides.

I have read an article which uses the fact that Hex can never end in a tie to prove the Brouwer Fixed Point Theorem.

Wouldn't this be a tie?(blue went first)
rbrbr
brbrb
rbbbr
brbrb
rbrbr

rbrbr
brbrB
rBBBr
Brbrb
rbrbr

is a path for blue, blue wins!

Whoops that was supposed to be:
rbrbr
brbrR
rbbbr
brbrb
rbrbr

In that case red goes first and
rbrbR
brbrR
brbRb
rbRbr

Is a winning combination for red
rbbbR

Sorry, the line that came up last in my post is the third row.

There was a commercial game under the (probably copyrighted) name Bridge-It that is isomorphic to a larger board Hex using the rules as Mike detailed them. An essential feature is that each player has a predefined edge color to work with.

Something similar was the first exercise for our graph theory class. There was a certain planar graph and two people had the goal to connect two vertices assigned to them by coloring edges with their color subsequently. The idea of the strategy is that you take one edge and have to find two spanning trees which share this edge and no other edge. Then, if the other person takes an edge, it cuts one of the two spanning trees into two components. Then there is a unique edge of the other spanning tree which connects those two components and one has to choose that edge. If there is no edge left, you have a spanning tree, so in particular, your two edges are connected.

Some additional resources may be found here:
http://web.mit.edu/sp.268/www/hex-notes.pdf

Welcome to Spiked Math!

Hello my fellow math geeks. My name is Mike and I am the creator of Spiked Math Comics, a math comic dedicated to humor, educate and entertain the geek in you. Beware though, there might be some math involved :D

New to Spiked Math?
View the top comics.

New Feature: Browse the archives in quick view! Choose from a black, white or grey background.

Now you can discuss the comics in the

Apps

by Pablo and Leonardo

Android app
by Bryan

Available on:
Swoopy app

Other Sites: