This homework is due Thursday, December 12 (last class).

Read as much as you can (or need to) in Ferguson's notes on Game Theory. Here's a local copy. (pdf, 46 pages)

I hope to cover the first four sections - through page I-28. We've already done a lot of that.

1. Ferguson, problem 1.5.4 (page I-6).

   What is the Sprague-Grundy function in each case?

   Generalize (a) and (b) if you can. I suspect there's a single theorem that covers all subtraction games for which S is finite.

   Note that my additions mean that this problem includes Ferguson Exercise 3.5.2 (page I-18).

   Note that in a subtraction game for which 1 is not a member of S, both the empty pile and the pile with one element are P positions, since no move is possible.

2. Ferguson Exercise 2.6.1 (page I-11). (This is easy.)

3. Ferguson Exercise 2.6.3 (page I-12). (This is easy too.)

4. Ferguson Exercise 3.5.4 (page I-19). (I have no idea whether this is hard or easy.)

5. (Very optional, for cs310 students). Use the game framework from cs310 to write a program that computes the Sprague-Grundy function for games where that's appropriate. You'll want to disallow games for which draws are allowed. You might need to disallow games in which players don't alternate making moves - I'm not sure. Perhaps the neutral distinction between P and N positions makes this problem go away.