JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Solving Two-Person Games with Perfect Information | Reply
Problem

The games we will talk about are two-person games with the perfect information, no chance moves, and a win-or-lose outcome. In these games, players usually alternate moves until they reach a terminal position. After that, one player is declared the winner and the other the loser. Most card games don't fit this category, for example, because we do not have information about what cards our opponent has.

First we will look at the basic division of positions to winning and losing. After that we will master the most important game -- the Game of Nim -- and see how understanding it will help us to play composite games.

The Basics

A simple example is the following game, played by two players who take turns moving. At the beginning there are n coins. When it is a player's turn he can take away 1, 3 or 4 coins. The player who takes the last one away is declared the winner (in other words, the player who can not make a move is the loser). The question is: For what n will the first player win if they both play optimally?

We can see that n = 1, 3, 4 are winning positions for the first player, because he can simply take all the coins. For n=0 there are no possible moves -- the game is finished -- so it is the losing position for the first player, because he can not make a move from it. If n = 2 the first player has only one option, to remove 1 coin. If n = 5 or 6 a player can move to 2 (by removing 3 or 4 coins), and he is in a winning position. If n = 7 a player can move only to 3, 4, 6, but from all of them his opponent can win…

Positions have the following properties which can be used to implement the algorithm:
  • All terminal positions are losing.
  • If a player is able to move to a losing position then he is in a winning position.
  • If a player is able to move only to the winning positions then he is in a losing position.

Table 1: Game with 11 coins and subtraction set {1, 3, 4}:

n 0 1 2 3 4 5 6 7 8 9 10 11
position L W L W W W W L W L W W


This game could be played also with a rule that the player who takes away the last coin is declared the loser. You need to change only the behavior for the terminal positions in the algorithm. Table 1 will change to this one:

n 0 1 2 3 4 5 6 7 8 9 10 11
position W L W L W W W W L W L W


Concrete Problem: PowerGame, SRM 384, Division II, Level 3

Alan and Bob are playing a game with two piles of sticks. The two players alternate turns, and Alan gets the first turn. During each turn, the player must remove exactly n^2 sticks from each pile, where n is some positive integer. The value of n does not have to be the same for each pile. For example, he can remove 1^2 = 1 stick from the first pile and 3^2 = 9 sticks from the second pile. The first player who cannot make a valid move is declared the loser.

The first pile initially contains size0 sticks and the second pile contains size1 sticks. Suppose both players play optimally. One of them has a winning strategy (no matter how his opponent plays he can always win) and he wants to win as fast as possible. The other player wants to lose as slowly as possible.

Return a String formatted as "<WINNER> will win after <NUMBER> moves" (quotes for clarity), where <WINNER> is the name of the winner and <NUMBER> is the total number of turns in the game. The total number of turns is the sum of all the successful turns taken by Alan and Bob.
Constraints: size0 and size1 will each be between 1 and 10000, inclusive.

Solution

We need to find only number of moves, because players alternate turns. So if the total number of moves is odd Alan will win and if it is even Bob will win. At the beginning we can try to solve the problem if we have only one pile of sticks. This can be solved by Dynamic Programming.
When we are calculating the number of moves the game will last if the size of the pile is x:
  • We will try all possible moves, i.e. moves to x - k^2 for all k>0
  • If it is possible, we want to move to position from which the game lasts even number of moves (from such position we win and our opponent loses). If there are more such positions we will choose the smallest one, because we want to win as fast as possible.
  • If it is possible to move only to positions from which the game lasts odd number of moves, we will lose. We want to lose as slow as possible so we will choose the maximum.
Players must play in both piles in their turns, but their strategy in particular piles does not have any reason to change. Therefore the pile with lower overall number of moves will determine the winner.

 public class PowerGame {
 
 public int numberOfMoves(int size) {
    // generate possible moves 
    int power=2;
    int[] moves = new int[105];
    int count = 0;
    boolean big=false;
    for (int i=1;i<105&&!big;i++) {
        int num=1;
        for (int j=0;j<power;j++) num*=i;
        if (num>size) big=true; else {
            moves[count]=num;
            count++;
        }
    }
    // find length of the game in this pile
    int[] length = new int[size+1];
    length[0]=0;
    int INF=999998;
    for (int i=1;i<=size;i++) {
        int smallestEven=INF;
        int largestOdd=-1;
        for (int j=0;j<count;j++) if (i-moves[j]>=0) {
            int pos = i - moves[j];
            if (length[pos]%2==0) {
                if (length[pos]<smallestEven) smallestEven = length[pos];    
            } else {
                if (length[pos]>largestOdd) largestOdd=length[pos];
            }
        }
        if (smallestEven!=INF) length[i]=smallestEven+1;
        else length[i]=largestOdd+1;
    }
    return length[size];
 }
 
 public String winner(int size0, int size1) {
    int length0 = numberOfMoves(size0);
    int length1 = numberOfMoves(size1);
    int minimum = length0<length1 ? length0 : length1;
    String name=(minimum%2==1)?"Alan":"Bob";
    return name+" will win after "+String.valueOf(minimum)+" moves";
 } 
 
}
 


to be continued in the next post ...
Re: Solving Two-Person Games with Perfect Information (response to post by rasto6sk) | Reply
More advanced - The Game of Nim

The most famous mathematical game is probably the Game of Nim. This is the game that you will probably encounter the most times and there are many variations on it, as well as games that can be solved by using the knowledge of how to play the game. Usually you will meet them as Division I 1000 pointers (though hopefully your next encounter will seem much easier). Although these problems often require a clever idea, they are usually very easy to code.

Rules: There are n piles of coins. When it is a player's turn he chooses one pile and takes at least one coin from it. If someone is unable to move he loses (so the one who removes the last coin is the winner).

<img src="http://www.topcoder.com/i/education/algorithmGames_01.png"/>

Let n1, n2, … nk, be the sizes of the piles. It is a losing position for the player whose turn it is if and only if n1 xor n2 xor .. xor nk = 0.

How is xor being computed?
  • xor of two logic values is true if and only if one of them is true and the second is false
  • when computing xor of integers, first write them as binary numbers and then apply xor on columns (i.e. bit-wise)
  • you do not need to worry about it much, since xor is built in most of the programming languages

Why does it work?
  • From the losing positions we can move only to the winning ones. If xor of the sizes of the piles is 0 then it will be changed after our move (at least one 1 will be changed to 0, so in that column will be odd number of 1s)

  • From the winning positions it is possible to move to at least one losing. If xor of the sizes of the piles is not 0 we can change it to 0 by finding the left most column where the number of 1s is odd, changing one of them to 0 and then by changing 0s or 1s on the right side of it to gain even number of 1s in every column.
Example:
Position (1, 2, 3) is losing because 1 xor 2 xor 3 = (1)2 xor (10)2 xor (11)2 = 0
Position (7, 4, 1) is winning because 7 xor 4 xor 1 = (111)2 xor (100)2 xor (1)2 = (10)2 = 2

Composite games - Grundy numbers

Example game: N x N chessboard with K knights on it. Unlike a knight in a traditional game of chess, these can move only as shown in the picture below (so the sum of coordinates is decreased in every move). There can be more than one knight on the same square at the same time. Two players take turns moving and, when it is a player's, turn he chooses one of the knights and moves it. A player who is not able to make a move is declared the loser.

<img src="http://www.topcoder.com/i/education/algorithmGames_02.png"/>

This is the same as if we had K chessboards with exactly one knight on every chessboard. This is the ordinary sum of K games and it can be solved by using the grundy numbers. We assign grundy number to every subgame according to which size of the pile in the Game of Nim it is equivalent to. When we know how to play Nim we will be able to play this game as well.

Let S be a set of grundy numbers of positions to which we can move from the curent position. Then grundy number of the current position is the smallest non-negative integer which is not in S.

The following table shows grundy numbers for the above game for an 8 x 8 board:

<img src="http://www.topcoder.com/i/education/algorithmGames_02.png"/>

We could try to solve the original problem with the basic algorithm, but it would time out because of the large number of possible positions.
A better approach is to compute grundy numbers for an N x N chessboard in O(n^2) time and then xor these K (one for every horse) values. If their xor is 0 then we are in a losing position, otherwise we are in a winning position.

Why is the pile of Nim equivalent to the subgame if its size is equal to the grundy number of that subgame?
  • If we decrease the size of the pile in Nim from A to B, we can move also in the subgame to the position with the grundy number B. (Our current position had grundy number A so it means we could move to positions with all smaller grundy numbers, otherwise the grundy number of our position would not be A.)
  • If we are in the subgame at a position with a grundy number higher than 0, by moving in it and decreasing its grundy number we can also decrease the size of pile in the Nim.
  • If we are in the subgame at the position with grundy number 0, by moving from that we will get to a position with a grundy number higher than 0. Because of that, from such a position it is possible to move back to 0. By doing that we can nullify every move from the position from grundy number 0.


Conclusion

Don't worry if you see a game problem during SRM -- it might be similar to one the games described above, or it could be reduced to one of them. If not, just try to think about it on concrete examples. Once you figure it out the coding part is usually simple and straightforward.

Example of SRM problems for NIM and Grundy numbers

SRM 384: Chess Training
SRM 338: CakeParty
SRM 309: StoneGameStrategist
SRM 216: Roxor

Other resources

Collection of many mathematical games (http://www.madras.fife.sch.uk/maths/games/)
Introductory combinatorial game theory (http://sps.nus.edu.sg/~limchuwe/cgt/)
Winning ways for your mathematical plays by Elwyn R. Berlekamp, John H. Conway, Richard K. Guy
Composite Mathematical Games by Rastislav Lenhardt (http://www.comlab.ox.ac.uk/files/2735/Composite_games.pdf)
Re: Solving Two-Person Games with Perfect Information (response to post by rasto6sk) | Reply
The format has to be made more Cookbook-ish by converting it to Problem-Solution-Discussion format. I'd slightly change the order in which you give examples and definitions.

Start "Solution" with general difinition of losing and winning positions as well as noting that the rules of the game define each terminal position as either winning or losing (currently you give these three rules after the example but the first of them is applicable only to this particular example). Actually, this might be all of "Solution" part, since from now on the recipe is based on examples which belong to "Discussion".

Then give an example of one-pile game - I think LastStone is perfect for this purpose, its example 0 is your example. You don't need to include problem statement in the recipe itself, just give name and link to the statement. Give the solution as well.

Proceed to more complicated example with different definition of winning and losing positions, PowerGame will do. And to more compicated example, the game of Nim (don't we have a problem which is pure Nim?), again with solution. Finish with Grundy numbers, again with example of TC problem solved.
Re: Solving Two-Person Games with Perfect Information (response to post by rasto6sk) | Reply
This is a great article about games on acyclic graph + Grundy numbers!

Games of general graph (with cycles probably) are also important. Though they are not so common in TC problems. They can be solved easily with slight BFS modification.
Should we include it?
Re: Solving Two-Person Games with Perfect Information (response to post by rasto6sk) | Reply
I think the first example can be done in a simpler way (without this 'move' array and 'big' boolean). Instead of
  for (int j=0;j<count;j++) if (i-moves[j]>=0) {
just do
  for (int j=0;j*j<=i;j++) {


(I have not tested this, but IMO the current long solution distracts readers too much from the important part)

Why "grundy number" is written in lowercase? Grundy is a last name. (Wikipedia also lists the name "nimber", I think this second name should also be given)


This is the same as if we had K chessboards with exactly one knight on every chessboard. This is the ordinary sum of K games and it can be solved by using the grundy numbers. We assign grundy number to every subgame according to which size of the pile in the Game of Nim it is equivalent to. When we know how to play Nim we will be able to play this game as well.


I think this section could be written better. I would include a definition of the "ordinary sum" and its important property (something like: Ordinary sums of simpler games can be solved easily using Grundy numbers. Grundy number is calculated like this: ... A position is losing iff Grundy number is 0. Grundy number of the ordinary sum of G1 and G2 is XOR of Grundy numbers of G1 and G2).

(BTW I think we have met in Oxford.)
Re: Solving Two-Person Games with Perfect Information (response to post by Eryx) | Reply
As deadline is approaching this recipe needs to be finished, but I am currently really busy with my phd. If anyone wants to become a co-author and finish and polish particular parts, I will be more than happy with it.

2Eryx, yes we met in Oxf.
RSS