JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Solving Two-Person Games with Perfect Information
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 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=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.)