Saturday, December 1, 2012

Tic-Tac-Toe related games

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

On the web, I have crossed over two 3D versions of Tic-Tac-Toe. One is called FourSight, it is played on a four-layer of 4 by 4 boards, the objective is to be the first one joining a line of 4 X's or O's. Another one is played on a three-layer of 3 by 3 boards, the objective is to seize as many lines as possible.

It is easy to see, for these two and many other similar games, an extra piece is always an advantage. Then using Nash's Strategy-Stealing Argument mentioned in a previous post, the first player has a strategy that he will never lose. The fun for those games for me, as a mathematician, is to find the winning strategy.

Now consider the original Tic-Tac-Toe, but the player who first gets a line of 3 is declared to be the loser. Is the new game always ended in a draw as the original one? Or does one of the players have a winning strategy?

FourSight from www.mathsisfun.com

Note that in the new game, an extra piece is a disadvantage. Therefore, it is unlikely that the first player has a winning strategy. However, the first player has a simple drawing strategy:
  1. The first player captures the middle space in his first move.
             
        X    
             
  2. Then he mirrors the second player's moves.
    O       
        X    
           X
    O       
    X X O
           X
  3. In this way, the first player is sure that he will get a line of 3 only after the second player gets it. Unless the second player is careless, the game will always end in a draw.


In combinatorical game theory, there are two types of two-player games: The normal game, where the player who makes the last move wins; the misère game, where the player who makes the last move loses.

The original Tic-Tac-Toe is a normal game, the new version is the misère game. There is a rich theory on normal games, but relatively few on misère games. We will have a look of the mathematical background in the coming posts.