
Introduction 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. We will not be able to play many of the games without decomposing them to smaller parts (subgames), precomputing some values for them, and then obtaining the result by combining these values. The Basics 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:
These properties could be used to create a simple recursive algorithm WLAlgorithm: boolean isWinning(position pos) { moves[] = possible positions to which I can move from the position pos; for (all x in moves) if (!isWinning(x)) return true; return false; } Table 1: Game with 11 coins and subtraction set {1, 3, 4}:
This game could be played also with a rule (usually called the misere play 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 WLAlgorithm. Table 1 will change to this:
It can be seen that whether a position is winning or losing depends only on the last k positions, where k is the maximum number of coins we can take away. While there are only 2^k possible values for the sequences of the length k, our sequence will become periodic. You can try to use this observation to solve the following problem: The Game of Nim Rules of the Game of Nim: 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). 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 n_{1} xor n_{2} xor .. xor n_{k} = 0. How is xor being computed? 6 = (110)2 1 1 0 9 = (1001)2 1 0 0 1 3 = (11)2 1 1  1 1 0 0
Why does it work?
Examples: Example problems: The last one example problem is harder, because it is not so easy to identify where the sizes of piles are hidden. Small hint: Notice the differences between the sizes of piles. If you would not be able to figure it out you can find the solution in the SRM 309 Problem set & Analysis. Composite games  Grundy numbers 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. int grundyNumber(position pos) { moves[] = possible positions to which I can move from pos set s; for (all x in moves) insert into s grundyNumber(x); //return the smallest nonnegative integer not in the set s; int ret=0; while (s.contains(ret)) ret++; return ret; } The following table shows grundy numbers for an 8 x 8 board: We could try to solve the original problem with our WLAlgorithm, 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?
Example problems: Other composite games 1. When it is a player's move he can choose some of the horses (at least one) and move with all the chosen ones. 2. When it is a player's move he can choose some of the horses (at least one), but not all of them, and move with all chosen ones. You can verify correctness of both solutions by verifying the basic properties (from a winning position it is possible to move to a losing one and from a losing position it is possible to move only to the winning ones). Of course, everything works for all other composite games with these rules (not only for horse games). Homework: What would be changed if a player had to move with every horse and would lose if he were not able to do so? Conclusion Other resources:


Home 
About TopCoder 
Press Room 
Contact Us 
Careers 
Privacy 
Terms
Competitions  Cockpit 
Copyright TopCoder, Inc. 2001 