Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am reading a book on Combinatorial Game Theory that describes a proof by John Nash that Hex is a 'first player' win, but I find the proof very confusing. This proof uses a strategy-stealing argument.

At one point it says:

With this (first) move Left becomes Second.

How can making the first move make you Second?

At the end it says:

At some point, if this strategy calls for Left to place a stone where the extra sits; then she will simply make another arbitrary placement. Thus Left can win in contradiction to the hypotheses.

I don't understand this at all. Why would the game call for a placement on "extra" if that spot is already occupied by a stone? Can someone explain this proof to me in a way that I can understand?

Here's the proof:

The proof is by contradiction. Let Left make the first play of the game, and assume that Right has a winning strategy. With Left's first move she puts a stone on any cell, a placement called "extra". With this move Left becomes Second, and she henceforth follows the winning strategy that is available to Right. At some point, if this strategy calls for Left to place a stone where the extra sits; then she will simply make another arbitrary placement. Thus Left can win in contradiction to the hypotheses.

share|improve this question
2  
So John Nash can't be targeted by spells and abilities his opponents control? Useful, I suppose. –  corsiKa Jul 4 at 20:32

2 Answers 2

up vote 13 down vote accepted

The point is that in the game Hex, it never hurts to have an extra piece on the board.

So, suppose there is a strategy for the second player, but you are stuck with being the first player. What should you do?

Well, you can place a stone on the board, and then pretend in your own mind that it isn't there! In other words, you are imagining that the other player will now make the first move. In your mind, you are imagining that you are the second player now, and you can follow the winning strategy for the second player.

The only time you could have trouble is if your winning strategy tells you to place a move at the position you are pretending is empty. Since it's not really empty, you can't really make a move there. But luckily, you have already moved there, so you can imagine that you are making a move there right now -- the stone is already there, so you can imagine that you are just putting it there now. But in reality you still need to make a move, so you can do the same thing you did at the beginning -- just place a stone at some random position, and then imagine that you didn't.

The real state of the game is always just like your imagined state, except that there is an extra stone of yours on the board, which can't make things any worse. It limits the opponent's options, but if you have a winning strategy, it will work for any moves the opponent makes, so this isn't a problem either.

The conclusion is that, if there were a strategy for the second player to win, then you could "steal" that strategy as outlined above to win even when you are the first player. This is a contradiction, because if there were really a winning strategy for the second player, then the first player would not be able to guarantee a win. Therefore, there is not in fact any strategy for the second player to win.

share|improve this answer
    
Thanks for blowing my mind! –  Jason C Jul 5 at 6:46

The point is just that having an "extra" piece on the board can't help your opponent.

Assume that Right (the second player) has a winning strategy. A strategy is a function $\Phi(A, B)$ that chooses what move to make when Left has pieces at the positions in $A$ and Right has pieces at the positions in $B$. Then Left can steal this strategy as follows. On the first move, Left puts a piece at any position and calls that position $x$ ("extra"). On every subsequent move, when Left has pieces at $A$ and Right has pieces at $B$, Left considers the position $y=\Phi(B, A \setminus \{x\})$ (that is, the move Right would have made in his position if he ignored the extra piece). If $y\neq x$, then Left puts a piece at $y$ (and keeps calling the same piece "extra"). If $y=x$, then Left puts a piece at any empty space $x'$ and sets $x=x'$ (i.e., he changes which piece he is calling "extra"). This is a winning strategy for Left. But since Left and Right cannot both have winning strategies, we have a contradiction, and conclude that our assumption must be false: Right cannot have a winning strategy. Therefore Left must have one.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.