CS 61C, Spring 2008
Due Wednesday, February 6th @ 11:59pm
Last Updated 2/1 @ 2:00am
TA: Casey Rodarmor
For this homework you will write a program which solves a strategic two player game called Nim. By solve, I mean that your program will determine whether a given game position is a win or a loss for the player who has the next move.
Solving a game like this is usually a matter of constructing something called a game tree and laboriously descending its many branches until the outcome of the game is determined (or you run out of memory). However, in Nim there is a great shortcut which will let us avoid all that business: just a little clever math and that'll be that. I'll explain about that, but first have a look at the usage string of the program that you're about to write...
casey@agave [~/hw2] ./nim
usage: nim n1 [n2 ...]
This program solves games of Nim. Nim is a two player game played with
an arbitrary number of heaps, each containing an arbitrary number of
stones. The two players take turns removing any number of stones from
any one pile. The player who removes the last stone wins.
Input is taken from the command line in the form of a list of numbers,
each representing a heap of stones.
For example, to solve a game of Nim with three heaps containing one,
two, and three stones, respectively, the following command line should
be used:
nim 1 2 3
If the game is a loss for the first player, "loss!" is printed. For a
win, "win!" is printed, followed by a list of available winning moves.
Pretty simple, huh? I suggest grabbing a buddy and playing a few games. Try with piles containing one, two, and three stones. If a buddy is not at hand, there are many good online apps. However, only one stays true to the traditional roots of Nim, and is played with hamsters.(Make sure you choose 'last turn WINS' to play the normal form of Nim. If you choose 'last turn LOOSES [sic]' that's the misere form that we suggest in Extra for Experts below.)
...
Did you win? Excellent! So, now that you're an expert at the game, here's a page that explains the clever math I mentioned.
Did that make sense to you? Me neither! Try reading it a couple more times, and then I'll try to summarize.
...
Okay, so basically the big takeaway from that page is that if we convert the numbers of stones in every pile to binary and add them together with no carry between columns, we'll get a number that tells us if the game is a win or a loss. This strange operation is called has a two names, the first is nim-addition.
That number is called the game's 'indicator'; as a special case you can see that the indicator for a losing position (one with no stones), is 0. Try playing a move on few simple positions, and I mean actually line up the binary numbers for positions with both zero and non-zero indicators. You'll find that for every game with a zero indicator, every legal move will result in a position with a non-zero indicator. In the case of a game with a non-zero indicator, there is at least one move which leaves the position with a zero indicator. Do you buy that?
Now, this is important because the losing position has an indicator of zero. That means that if you start, and the game has a non-zero indicator, you can always make a move which gives the position a zero indicator. And since your opponent (if there are even any moves left) must give you back a position with a non-zero indicator. As long as nobody makes a mistake, the indicators after every move will keep flopping back and forth, between zero and non-zero. Then, because it's a two player game and every move brings us closer to the end, you can see that a position with a non-zero indicator will turn out to be a win, and a position with an indicator of zero will be a loss.
"Um, okay," I hear you say, "but what about this crazy no-carry binary nim-addition?" Never fear. It turns out that nim-addition is exactly a bit-by-bit exclusive or, the '^' operator in C.
So now we're set; you're ready to start coding and kicking butt, right? Well, no. Here's where we get to the "these characters in this order, or death!" part of the spec.Output from a losing game should be as follows:
casey@agave [~/hw2] ./nim 1 1
loss!
casey@agave [~/hw2]
Output from a winning game is similar, but includes a list of all initially available winning moves:
casey@agave [~/hw2] ./nim 5 4 1 3 2 7
win!
winning move: remove 2 from the 5 pile
winning move: remove 2 from the 4 pile
winning move: remove 6 from the 7 pile
casey@agave [~/hw2]
If there are multiple identical winning moves, print them all:
casey@agave [~/hw2] ./nim 2 2 2
win!
winning move: remove 2 from the 2 pile
winning move: remove 2 from the 2 pile
winning move: remove 2 from the 2 pile
casey@agave [~/hw2]
The first number is the number of stones to remove, and the second is the number of stones in the pile. Winning moves should be printed in the same order as the piles they remove stones from appear on the command line.
Actually, it's a little confusing to call them 'winning moves'. They're really like non-losing moves... The game is currently a win for you, and you want to print out those moves which will ensure that it's still a win when it's your turn again.
Your program should never crash due to strange or malformed input.
When no arguments, a non-number (an argument not consisting entirely of the digits 0 through 9), or a negative number are given, your program must print the usage string given above. It is provided in usage.txt.
Zero is a valid argument, it represents an empty pile of stones.
Your program will not be tested on numbers larger than can fit in an int.
Output should not contain any extraneous whitespace. For example, the output from a losing game should be exactly "loss!\n", and not "loss! \n" or "loss!\n ".
It is an error to display insufficient enthusiasm, so don't omit the exclamation points!
Don't get too excited! Excess exclamation points will be penalized!!!
All your code should be in a single C file called 'nim.c'. It must build without any warnings or errors using
When you're ready to submit (and trust me, submission is inevitable), put nim.c in an empty directory. cd into that bad boy and run Although it may seem like a crusty old man that just wants to be left alone, GDB is in fact your friend. It is entirely possible to get by for a long time debugging with print statements, but if you put the energy in up front to learn how to use GDB, life will be much easier in the long run. Get online! People have been writing buggy C programs for as long as the internet has been around. It's turned into great resource for figuring out the language. If you find that your solution is getting huge, slow down and make sure you're headed in the right direction. Lots of code is often a sign that things are getting off track. As a reference, my solution is around 25 lines. (That doesn't include comments, blank lines, and And last but not least, one of the best pieces of advice there is: have something that works from square-one and keep it working. If you code up a gigantic program without testing it every step of the way, you'll probably wind up with a big mess that you'll have to throw out. Just take it easy, start with an empty The force is strong within you, young padawan... Go forth and program! It's linked above, but this is the key page:
Solving Nim Not enough? Still feeling like your C foo is shaky? Alright, I've got the problem for you. In this homework's Extra for Experts you'll extend your program to solve misere Nim. The misere form of a game like this is the same game, but with the win condition reversed. In misere Nim, the player to remove the last stone loses. If you would like to practice, here's a great misere Nim app; or you can play Hamster Nim, but select 'last turn LOOSES [sic]'. At first, this might seem like a simple problem, but there's a catch: all that sweet math we used doesn't apply to misere Nim--we need a new technique. In order to switch between misare and normal-play Nim, your program should now recognize an optional '-m' flag, given before all other arguments: Make sure you update the default usage string exactly as follows to indicate your support for misere play: In order to solve the misere form, you're going to actually look at the game as a game tree. Wikipedia has an okay description of game trees. Here's a page that actually has
an example using misere-play Nim. The nodes of a game tree represent positions in a a game, and transitions to child nodes represent possible moves from that position. In a Nim game tree, all nodes will have a value of win or loss. How do you look at a node and determine if its value? Easy, look at the children of that node. If the children of that node are all wins, your node is a loss. Why? Because when you make a move, you'll be handing your opponent a winning position. But, if there's a loss node in there then your node is a win, because you can make that move and hand your opponent a losing position. Okay, but where does it all stop? Simple, go down the tree until you hit a node which you can evaluate directly. In the case of misere Nim, that's going to be the board with no stones, and that's going to be a win. At this point it might be painful to implement a data structure that represents a game tree, but the good news is that you can do it with recursion, 61A style. For refrence, here's a sweet misere Nim solver in Scheme. It's in nim.scm and gamesman-mini.scm. Brian Harvey would be proud. It's important to keep in mind that gamesman-mini.scm is a general solver, and nim.scm is like a plugin module. A specialized solution is almost always easier to code than a general one, and you will find it much easier if you focus on the specifics of Nim. Of course, if you are feeling particularly ambitious, the sky is the limit. ◊gcc -Wall -g -std=c99 -o nim nim.c.submit hw2.Survival tips
#include <assert.h> and use it! I didn't know assert() existed in C for a while, and I don't want you to miss out like I did. assert.h provides assert(), which takes a true/false value as an argument and crashes your program if it's false. Sweet, huh? You use it when you think that something will always be true, so you "assert" that it is: assert(gravity == DOWN). The idea is that if your assertion is false, something has gone terribly wrong; so wrong, in fact, that you want bail right there so you can fix your program.#includes.)main() that returns 0, compile it, run it, and then start adding to it. Don't go more then 10 minutes without compiling and making sure that your program is doing what you expect. And take care of those compiler warnings!References
Extra for experts
casey@agave[~/hw2] ./nim 1
win!
winning move: remove 1 from the 1 pile
casey@agave[~/hw2] ./nim -m 1
loss!
casey@agave[~/hw2]
casey@agave [~/hw2] ./nim
usage: nim [-m] n1 [n2 ...]
...