Strategy-stealing argument

If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.


(Too many unexpected: my baby girl Cherria comes to the world two weeks earlier than expected, and my mail account is hacked...)

I have posted two articles on the game Tic-Tac-Toe. Fields Medalist and leading game theorist John Nash was believed to be one of the two independent inventors of a two-player game called Hex. John Nash is able to prove that the first player has a winning strategy, i.e. the first player always wins if he makes no mistakes. The proof involves the "Strategy-stealing argument":

Consider a two-player game about occupying spaces on a board, no filled space will ever be freed, such that an extra move will never be a disadvantage. Assume that Player II has a winning strategy.

• Player I is about to make the first move. He randomly assumes that Player II has already made a move M0, then he pretends himself as a second player and use Player II's strategy to make a move F1.
  What Player I thinks: M0 F1
  What really happens: F1
• Player II responses by playing S1, Player I then plays F2
  What Player I thinks: M0 F1 S1 F2
  What really happens: F1 S1 F2
• The game continues. Suppose in Step 4, Player II plays M0, Player I again randomly assumes that indeed Player II has played M1 and responses with F5.
  What Player I thinks: M0 F1 S1 F2 S2 F3 S3 F4 M1 F5
  What really happens: F1 S1 F2 S2 F3 S3 F4 M0 F5
• The game continues. Suppose in Step 7, Player II plays M1, Player I again randomly assumes that indeed Player II has played M2 and responses with F8.
  What Player I thinks: M0 F1 S1 F2 S2 F3 S3 F4 M1 F5 S5 F6 S6 F7 M2 F8
  What really happens: F1 S1 F2 S2 F3 S3 F4 M0 F5 S5 F6 S6 F7 M1 F8
• The game continues. Suppose Player I thinks he wins Step 9, i.e.
  M0 F1 S1 F2 S2 F3 S3 F4 M1 F5 S5 F6 S6 F7 M2 F8 S8 F9
  Note that Player II will not be better off if the extra move is not there, i.e. he still loses in the real situation
  F1 S1 F2 S2 F3 S3 F4 M0 F5 S5 F6 S6 F7 M1 F8 S8 F9

As we can see, this is a contradiction as Player II should be the winner. Therefore Player II cannot have a winning strategy.

The argument works on games like Hex, Chomp, Gomoku and Tic-Tac-Toe. However, it does not work on Chess, Chinese checkers and Go. However, it is believed that the first player most likely to be the winner.