4x4 Tic-Tac-Toe (II)

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

In the last blog, I have asked the following question:

If we consider the Tic-Tac-Toe game on a 4x4 board, then (a) is it possible to end in a draw? (b) does anybody have a nonlosing or winning strategy?

The answer for (a) is yes. The following is a possible draw game.

X	O	X	O
X	O	X	O
O	X	O	X
O	X	O	X

The answer for (b) is: There is a winning strategy for the first player.
His very first move:

	X

His second move, with Os indicate the possible moves of the second player:

O O O O X O O O X O O O O O

O         X X O O

Now we see, no matter how the second player corresponds, the first player is able to finish an unbroken row or an unbroken column of three X's.

It is trivial that the winning strategy is not unique. Moreover, this winning strategy works for a more strict version of Tic-Tac-Toe, meaning we don't allow diagonal row of X's.

In 1913, German mathematician Ernst Zermelo published a paper on game theory. He proved his famous Zermelo's theorem--

For any finite two-player games of perfect information in which the players move alternatingly and in which chance does not affect the decision making process, one of the players will always have a non-losing strategy. If the game cannot end in a draw, then this non-losing strategy is a winning strategy.

A finite game means the game will end in a finite number of steps. Perfect information means everyone knows all the possible consequences of any moves. There is no chance involved, therefore it excludes games like Contract Bridge and backgammon.

By Zermelo's Theorem, we know there will be non-losing strategies for Chess and Go. However, no one have yet found those winning strategies.
In 2007, scientists develop a never-losign program for English Draughts, making it the most complicated game ever solved. A list of solved games can be found here.