Tutorial on Game Theory

Overview :
The most important assumption in a 2 player game is that both the players play optimally ie. at every step they will make a move which maximizes their chances of winning the game. In this article we will give a brief introduction to 2 player impartial games. Impartial games are those games where there is no restriction on any player's moves due to his identity.
We will discuss two different games which are of exactly the same nature and then see how they can be approached.

Problem :
Wythoff's Game.
This is a classic Game theory example. The rules of this game are as follows :
* There are two heaps containing n1 and n2 objects.
* Two players play alternately, they can pick any number of objects from one of these piles or pick 'k' objects from each of these piles(k <= minimum of both the piles).
* The player picking up the last object or set of objects wins.

Since this is an impartial game and both the players play optimally, we can say that given a certain starting configuration its already decided who is going to win the game. Lets understand why this works.
Let  'C1' be the starting configuration of the game. Player 1(plays the first move) makes a move M1, leading to a new configuration 'C2'.
Since player 1 plays optimally, he will consider the move which maximizes his chances of winning the game. If there is atleast one set of sequence from the start which is leading to player 1's victory, then he will anticipate that sequence and play the move which is compliant with that sequence.
While determining that sequence, player 1 also took into consideration that within that sequence, whenever player 2 gets to play, if he has a chance to make the remaining sequence favorable to his victory, he will do that  immediately.
Its important to understand that, given a certain starting configuration, there are only two exhaustive possibilities ie. playing optimally, either player 1 will win or lose. And as described above even if there is one set of sequences where every move is optimal and player 1 is winning, he will consider that move.

Coming back to Wythoff's Game, suppose there was 1 object in the first heap(H1) and 2 objects in the second(H2).
We denote the status of the game by {n1,n2} where n1 is the number of objects in first heap and n2 in the other.
"-->" denotes transition after a move is made.

When the game starts, player 1 has the following moves :
{1,2} --> {0,2} pick one from H1
{1,2} --> {0,1} pick 1 each from H1 and H2
{1,2} --> {1,0} pick 2 from H2

note that, after any of these moves,
exactly in one move, player 2 is going to win.
{0,2} --> {0,0} pick 2 from H2
{1,1} --> {0,0} pick 1 from H1 and H2
{1,0} --> {0,0} pick 1 from H2

So no matter what move player 1 plays, he cannot win this game. There is no sequence which leads to player 1's victory.

Let us consider the case where starting configuration of the game is {2,2}
We have already seen that from {1,2} , the player playing the move cannot win. So if the starting configuration is {2,2}, player 1 picks up one object from H1 and gives the configuration {1,2} to player 2. Now no matter what move player 2 plays, he is going to loose. He could have also sent player 2 to an alternate configuration {2,1} which is symmetrical to the {1,2} and hence leading to the same result.
We call these positions from where victory is guaranteed to be  *winning positions*. And positions from where no matter what move one plays, one always looses to be *loosing positions*. Now we need to figure out all the loosing and winning position for Wythoff's game.
{0,0} is a loosing position because, the other player has played his move and got the other player to the configuration to {0,0}. Now player with his turn has no move to play leading to his defeat.

All those position from which {0,0} can be reached in one move are winning positions, because the player plays that move and wins by definition of the Wythoff's game. So to find whether a position {i,j} is winning or loosing, we draw a 2-D grid.
All configuration of the form {i,i} or {0,i} or {i,0} are winning positions and we mark them in the grid.
'*' indicates yet to be determined.
'L' indicates a loosing position.
'W' indicates a winning position.

L W W W W W W...
W W * * * * * * * .......
W * W * * * * * * .......
W *  * W * * * * *.......
W *  *  * W * * * *......
W *  *   *  * W * * ......
..................................
Considering 0 based indexing in the grid, position i,j in the grid indicates the configuration {i,j} of the game (i remaining in H1 and j remaining in H2).

Its evident from the rules of the game that the player can either move horizontally towards left in the grid(pick from H1) or vertically up in the grid (pick up from H2) or digonally towards 0,0 (pick a certain 'k' number from each heap).
So from position {1,2} ( (1,2) in grid ) he can only move to all positions which are marked 'W'.
Same for position {2,1} ( (2,1) in grid )
Hence they both are loosing positions.

L W W W W W W...
W W L * * * * * * .......
W L W * * * * * * .......
W *  * W * * * * *.......
W *  *  * W * * * *......
W *  *   *  * W * * ......
..................................

Now all those positions from where we can reach either (1,2) or (2,1) in the grid, by making a move according to the rules of the game are winning positions. A move is removing some from one or a certain from both, thus all points in the grid of the form (1+i,2+1) or (1+i,2) or (1,2+i)
or (2+i,1+i) or (2+i,1) or (2,1+i) are  winning positions, since from these, in one move, one can force the opponent to reach a loosing position (1,2) or (2,1). Marking these positions as winning positions :

L W W W W W W...
W W L W W W W ..
W L W W W W W ..
W W W W W * * ....
W W W  W W W *..
W W W   *  W W W
..................................

And accordingly we mark the remaining positions.
To find out for a starting configuration (i,j), its safe to construct a grid of size max(i,j) x max(i,j).
Hence we determine the result of the game given a certain starting configuration.

Referenced articles :
http://sps.nus.edu.sg/~limchuwe/cgt/
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames
http://www.madras.fife.sch.uk/maths/games/
http://en.wikipedia.org/wiki/Game_theory

Sample problem on basic Game Theory :
http://www.topcoder.com/stat?c=problem_statement&pm=6856

Sample problems on advanced Game theory (This tutorial is a very basic introduction to Game theory and it is recommended that one should read the referenced articles before attempting these) :
http://www.topcoder.com/stat?c=problem_statement&pm=2987&rd=5862
http://www.topcoder.com/stat?c=problem_statement&pm=7424
http://www.topcoder.com/stat?c=problem_statement&pm=6239