Monday, December 31, 2012

Happy New Year!!!

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

Happy New Year!!!


Sorry I am a bit lazy, but it is a holiday season!

Lets end this year with a Nim game.

2013=(11111011101)
Lets play a Nim game with three heaps:

*****
***
*


Who will be the winner?

First heap's nimber is 5=(101),
second heap's nimber is 3=(011),
last heap's nimber is 1=(001).
So the nim sum is (101)+(011)+(001)=(111) which is nonzero. Therefore the first player has a winning strategy.

(111)+(101)=(010)=2, so the first player takes 3 and leaves 2 in the first heap.

Lets talk about binary numbers in the next blog.

Sunday, December 23, 2012

Nimbers, the numbers for Nim game

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

In previous posts, we have introduced some simple games. One of them is $G'(n)$, which consists a board with n pieces, two players in turn can take any number of pieces from the block, the winner is the one who takes the last piece.

Looks like a stupid game, right? The first player can take all pieces at his first step and win.

How about G'(3)+G'(7)? G'(2)+G'(6)+G'(5)? G'(11)+G'(6)+G'(8)+G'(3)?

Not so easy now. It is the famous Nim game. Some says that Nim originated from China, but no one can sure.

**
******
*****
The Nim game G'(2)+G'(6)+G'(5) consists of three heaps, each time a player can take away any number of pieces from a heap, the objective is to take the last piece.


To solve Nim, mathematicians have introduced the concept of nimber, which is basically ordinal numbers represented in binary numeral system under the position-wise boolean addition (i.e. 0+0=1+1=0, 0+1=1+0=1).

For example 3+7=(011)+(111)=(100)=4, 5+11=(0101)+(1011)=(1010)=10.

There is also nimber multiplication, which is omitted here.

Before we get into the relation between Nim and nimber, lets investigate the properties of nimber addition:
  1. n+m=0 if and only if n=m
  2. If n has a 1 at the 2k-th position and m is a k-digit nimber, then n+m<n. (The proof is easy: (1...1...)+ (1...)=(1...0...)<(1...1...). )
  3. If the nim sum of several nimbers is a k-digit nimber, then at least one nimber has a 1 at the 2k-th position.
  4. If the nim sum of several nimbers is 0, then replace any one of them by a different nonzero nimber, the new nim sum is nonzero. (Proof: Given n1+n2+...+nr=0. Suppose we replace the first nimber by m, then m+n2+...+nr=m+n1+n1+n2+...+nr=m+n1≠0.)
Now we are ready to study Nim.

For each heap, there are a nimber of pieces. Take the nim sum of the nimbers.
**
******
*****
The Nim sum of G'(2)+G'(6)+G'(5)is 2+6+5=(010)+(110)+(101)=(001).

The objective of the game is to take away all the pieces. At that last moment, the number of pieces is 0. From Property (4), if the nim sum is already 0, take away any number of pieces from a heap cannot keep the nim sum be 0, and therefore cannot win the game.

What if the nim sum, say m is a k-digit nimber?
From Property (3), there is a heap of which the nimber, say n, has a 1 at the 2k-th position. From Property (2), n+m<n. Take away some pieces fromt that heap so that there are n+m pieces left. The nim sum becomes
nim sum of all other heaps+(n+m)=(m-n)+(n+m)=m+m=0.

Therefore, the winning strategy is to maintain the nim sum to be 0. If the nim sum at the beginning is 0, the second player wins; if the nim sum at the beginning is nonzero, the first player wins.

Consider the game G'(2)+G'(6)+G'(5).
2=(10), 6=(110), 5=(101).
2+6+4=(10)+(110)+(100)=(001).
Only 5 have a 1 at the 1-th position. (101)+(001)=(100)=4, so the player has to left 4 in the last heap.

The game becomes G'(2)+G'(6)+G'(4).
The nim sum is 0. No matter the opponent does, he will disturb the balance. Suppose he takes away 3 pieces from the second heap.

The game becomes G'(2)+G'(3)+G'(4).
The nim sum is (101). The player now leaves (100)+(101)=(001)=1 pieces in the last heap.

The game becomes G'(2)+G'(3)+G'(1).

I suppose the readers can figure out the rest.

Thursday, December 20, 2012

Sum of games (2)

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

Suppose G is a first player's game and G' is a second player's game, what is G+G'?
It is still a first player's game. The first player moves on G at the first step. Note that the first player can force the opponent to be the first player on G'. Why? Because G is a first player's game, and so sooner or later the second player cannot make a move on G and have to move on G'.

Suppose G is L's game and G' is a first player's game.
Consider the following game:
  • L(n) consists of a board with n pieces. L can take away any number of pieces at his turn but R can only take away a piece. Obviously, L(1) is a first player's game but L(n) is always L's game.
L(2)+L(1) is a first player's game. No matter L or R makes the first move, he will take away a single piece from L(2) and win the game.
L(3)+L(1) is L's game. If L makes the first move, he will take away two pieces from L(3) and win; if R makes the first move, the new configuration is either L(3) or L(2)+L(1) with L being the first player, so L wins.

Suppose G is L's game and G' is a second player's game.
Suppose R is the first player. If R takes G' then he will lose on both G and G'. However if R takes G which is L's game, then sooner or later he will be forced to make a first move on G' and he will also lose. Suppose L is the first player, then obvious he will make his first move on G and force R to be the first player on G', and then he can win. G+G' is L's game.

In the last two cases, if G is R's game, the argument is similar.

Suppose G is L's game and G' is R's game.
Consider L(n) and R(n), i.e., the game identical to L(n) but the roles of L and R interchanged.
L(2)+R(2) is the second player's game.
L(3)+R(2) and L(2)+R(3) are both first player's games. No matter who moves first, he can change it to L(2)+R(2) with himself being the second player.
L(4)+R(2) is surely L's game. If L moves first, he will make it L(2)+R(2).
L(2)+R(4) is surely R's game.

We can see that L(n)+R(n) is always a second player's game. It is because the second player can make a mirror copy of the first player's move, and therefore he will never be the one who cannot make a legitimate move.
Indeed, if G=(GL|GR) is a game, then we define a new game -G=(-GR|-GL), i.e. the game with the role of L and G interchanged, then G + (-G) is always a second player's game.

Suppose G1=G+(second player's game). We have
  1. If G is a first player's/second player's/L's/R's game then G1 retains the same property.
  2. G1+(-G)=(second player's game).
Technically speaking, the set of second player's games forms an identity element under the addition operations.

Sum of games (1)

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

In the previous two blogs, we see that a nominal game (i.e. player who makes the last move wins) can be defined as G=(GL|GR) where GL (R resp.) is the set of possible configurations after L (R resp.) makes the first move.

Indeed, we can add two nominal games G=(GL|GR) and G'=(G'L|G'R) together and form a new nominal game. Symbolically, it is
G+G'=(GL+G', G+G'L | GR+G', G+G'R)
where the sum is defined recursively.

What does it mean exactly? Indeed, we simply put the two games side by side, and at each step, the player can make a move on either game.

What is the effect on the games?

Suppose both G and G' are games that the second player wins.
If the first player moves on G, then the second player moves on G; if the first player moves on G', then the second player also moves on G'. The second player is still the second winner on both G and G' and therefore he wins on both games. In other words, G+G' is still a second player's game.

Suppose both G and G' are games that L (R resp.) wins.
It is trivial that L (R resp.) is still the winner.

Suppose both G and G' are games that the first player wins.
It is a bit more complicated. Consider the following two games:
  • G(n) consists of a board with n pieces on it. Two players in term takes a piece from the board. The player who takes the last piece wins.
  • G'(n) consists of a board with n piece on it. Two players in term can take arbitrary number (possibly all) of pieces from the board. The player who takes the last piece wins.
Obviously, G(n) is a first player's game if n is odd but a second player's game if n is even, and G'(n) is always a first player's game-the first player can take everything at the first move.

G(1)+G(1)=G(2), so the sum of two first player's games can be a second player's game.
G(1)+G'(2) is, however, a first player's game. At the very first move, the first player will take away a piece from G'(2) and the new configuration is G(2) with himself as the second player. Therefore, he wins.

Can you figure out the remaining four cases?

Tuesday, December 11, 2012

"number" game

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.....?

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.)

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.