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, we know that there are "number" games n+1=(n| ) and -(n+1)=( |n).
It is easy to see that in all positive integers, L will be the winner. Indeed, for any games of the form ((X| )| ), L will be the winner, as R can never be able to make a move.
How about negative integers ( |n)? If L is the first player, he loses as he cannot make a move. If R is the first player, the next configuration is the game n, and R is the loser. Therefore the second player will always be the winner.
Lets consider ( |-n). Who wins?
If L is the first player, he loses. If R is the first player, the next configuration is the game -n with L makes the first move -- but for the game -n, the one who makes the first move loses--and so L loses again. It is a game that R wins.
Lets consider (n|-m). Who wins?
If L is the first player, the next configuration is n, and so L wins. If R is the first player, the next configuration is -m with L makes the first move, and so R wins. It is a game that the first player wins.
Lets consider a little bit more complicated ( |n,-m). Who wins?
If L is the first player, he loses. If R is the first player, he can choose the next configuration to be n or -m (and L makes the first move): If R chooses n, he loses; if R chooses -m, he wins.
It is a game that there is no definite winner, but R has a winning strategy - choosing -m if he is the second player.
Lets consider (n|n, -m). Who wins?
If L is the first player, he wins. If R is the first player, he wins only if he chooses -m.
It is a game of which the first player has a winning strategy.
Lets consider (( |n,m),( |-n)|n, -m). Who wins?
Again, it is a game that the first player has a winner strategy: If L is the first, he should choose ( |n,m); If R is the first, he should choose -m.
It is not that complicated, right.....?
Tuesday, December 11, 2012
Saturday, December 8, 2012
zero game
If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.
John Conway,Elwyn Berlekamp and Richard Guy together invented a theory for general two-player games. The term "general" here means that the game may not be identical to the two players, meaning the two players can have different game options.
Let we say the two players be L and R. A game is defined as an ordered pair (GL | GR), where GL (resp. GR) is the set of all possible configurations if L (resp. R) is the one who make a move.
A zero game 0=( | ) is the game that the first player automatically loses, because neither L nor R has a valid move.
( | 0) is the game that L must lose. If L is the first player, he has no valid move. If R is the first player, the configuration will become 0, and L being the next player has no valid move.
(0 | ) is the game that R must lose.
The star game *=(0 | 0) is the game that the second player will lose.
We have 0 game. We also have other "number" games:
1=(0 | )
2=(1 | )
3=(2 | )
4=(3 | )
....
-1=( | 0)
-2=( | 1)
-3=( | 2)
-4=( | 3)
....
It is possible to include all the numbers, some represents games with infinitely many configurations.
Invented by John Conway, the concept of games as numbers where first introduced to the public through a story book by Donald Knuth: Surreal Numbers: How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness. It is a rare case that a new concept is introduced this way. The name Surreal Number is given by Donald Knuth and is adopted by John Conway.
Like other number systems, the surreal numbers can add, subtract, multiply and divide.
A little exercise: For games 1,2,3,..., -1,-2,-3,...., which player (L, R, first player, second player) is the winner?
(Please also remember the name Donald Knuth, he is the creator of TeX, the standard typesetting system for most mathematical publications.)
John Conway,Elwyn Berlekamp and Richard Guy together invented a theory for general two-player games. The term "general" here means that the game may not be identical to the two players, meaning the two players can have different game options.
Let we say the two players be L and R. A game is defined as an ordered pair (GL | GR), where GL (resp. GR) is the set of all possible configurations if L (resp. R) is the one who make a move.
A zero game 0=( | ) is the game that the first player automatically loses, because neither L nor R has a valid move.
( | 0) is the game that L must lose. If L is the first player, he has no valid move. If R is the first player, the configuration will become 0, and L being the next player has no valid move.
(0 | ) is the game that R must lose.
The star game *=(0 | 0) is the game that the second player will lose.
We have 0 game. We also have other "number" games:
1=(0 | )
2=(1 | )
3=(2 | )
4=(3 | )
....
-1=( | 0)
-2=( | 1)
-3=( | 2)
-4=( | 3)
....
It is possible to include all the numbers, some represents games with infinitely many configurations.
Invented by John Conway, the concept of games as numbers where first introduced to the public through a story book by Donald Knuth: Surreal Numbers: How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness. It is a rare case that a new concept is introduced this way. The name Surreal Number is given by Donald Knuth and is adopted by John Conway.
Like other number systems, the surreal numbers can add, subtract, multiply and divide.
A little exercise: For games 1,2,3,..., -1,-2,-3,...., which player (L, R, first player, second player) is the winner?
(Please also remember the name Donald Knuth, he is the creator of TeX, the standard typesetting system for most mathematical publications.)
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:
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.
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:
- The first player captures the middle space in his first move.
X - Then he mirrors the second player's moves.
O X X O X X O X - 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.
Tuesday, November 27, 2012
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.
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.
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 |
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.
Wednesday, November 21, 2012
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.
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.
(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
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.
Thursday, November 8, 2012
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.
The answer for (b) is: There is a winning strategy for the first player.
His very first move:
His second move, with Os indicate the possible moves of the second player:
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.
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:
|
|
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.
Monday, November 5, 2012
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.
(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.
Subscribe to:
Posts (Atom)