9
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ So John Nash can't be targeted by spells and abilities his opponents control? Useful, I suppose. $\endgroup$ – corsiKa Jul 4 '14 at 20:32
23
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ According to Wikipedia, Nash's proof applies to symmetrical boards. My qustion is this: Why does it not apply to asymmetrical boards? $\endgroup$ – Christofer Ohlsson Aug 17 '17 at 12:25
  • 1
    $\begingroup$ @ChristoferOhlsson Although the math is more complicated, I believe the essence of the answer to your question is because -- if a game board were asymmetric, either the lemma for not having a draw or the Hex Theorem Proof argument about the ability to draw an unconnected path always would no longer be true in every play. We could, essentially, either have a Draw OR a game where, playing optimally, player 1 did NOT win. $\endgroup$ – RoboBear Nov 12 '17 at 19:04
  • 1
    $\begingroup$ @ChristoferOhlsson As for the math, the concept is to represent the Hex board as a Graph of nodes and edges. After any given play, you can basically look at the board and assign values to the tiles in the game based on how many Xs or Os it has around it. Because of the board symmetry and the alternating play, you are able to deduce that there is always a connected path for one player in the board AND that the first player can always make such a path first, if he or she is optimal. I think Asymmetrical boards break the values assigned to the nodes, which would make the make the argument false. $\endgroup$ – RoboBear Nov 12 '17 at 19:07
  • $\begingroup$ @ChristoferOhlsson On an asymmetrical board, the player who has a shorter distance to connect can win even as the 2nd player. The winning strategy is simple: Respond to (i,j) (where i∈[0,m], j∈[0,n], m<n) with (m-i,m+1-j) (if m+1<j, respond anywhere). Why does this work? Place pieces till the board is full, then consider the boundary of player 1's component containing the [virtual] j=-1 row. Starting from the (0,0) board corner, find the first time the boundary hits the line i+j=m+.5. The reflection of this component (as formed by your responses) extends your side of the boundary to your goal. $\endgroup$ – Matt Nov 25 '17 at 10:26
  • $\begingroup$ @ChristoferOhlsson The reason Nash's proof doesn't work for asymmetric boards is because when you steal the 2nd player's strategy, you have to imagine the board is flipped, so that the black and white goal sides are exchanged. This way, when you follow the other color's strategy and win, you have actually connected your own goal sides and won. An asymmetric board cannot be flipped onto itself, and so when you try to steal the strategy, it could require you to move in places that are not present on the actual unflipped board. Unable to make these moves, your intended winning path may have gaps. $\endgroup$ – Matt Nov 25 '17 at 10:39
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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