A number game

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

Consider the following card game:

A set of nine cards numbered 1 to 9. Two players in turns pick up a card. The winner is the player who first have three of his cards add up to 15.

For instance, in the fourth turn Player A gets 1,2,3,9 and Player B gets 4,5,6,7, then Player B wins the game as 4+5+6=15.

Better have a try first before continue to read.




Three classes of 1-9 tiles in Mahjong. [Source: Wikimedia Commons]

If we talk about an IQ game involving 1 to 9, which game comes to your mind?
Let me guess: the magic square! Arrange the nine cards in a magic square.

8	1	6
3	5	7
4	9	2

The above is one of the possible answer.
Now plays the card game again.

Have you noticed that you are just playing Tic-Tac-Toe?
It is a game that you may already dismiss as too childish long time ago.

Old thing can be new again if it is given a completely different look.

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.

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.

4x4 Tic-Tac-Toe (I)

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

(Busy moving. Not moving the blog, but relocate my family :D )

Several years ago, there is a 14 year-old "math genius", who got very high mark in A-level exams. In an entrance interview, a professor asked the kid about a question on a combinatorical game, the kid's response was: It is not mathematics!
As it turns out the kid, under the guidance of his teacher, i.e. his father, are only interested in those problems related to examinations.

Maybe we should not blame the kid too much. Unlike calculus or algebra, combinatorics do not have the feel of advanced mathematics. The structure is loose and there is no satisfactory introduction about it. However, the underlying mindset is the basis for studying computer science, mathematical politics, game theory, etc.

For most of us, the first combinatorical game encountered is the Tic-Tac-Toe. It is easy, and we should figure out (if we are old enough) that we can usually forced a draw. However, it is fairy complicated to write down the non-losing strategy. That is the perfect example that Easy may not be Simple!

How about if we play the Tic-Tac-Toe game on a 4x4 grid instead? The winner is again the first player getting a non-broken row (horizontal, vertical or diagonal) of three X's or O's.

The question is:
(a) Could the game ended in a draw if the players wish?
(b) Is there any non-losing or even winning strategy for one of the players?

We will answer this question in the next blog.