MCS-177 Lab: Nim with Strategies

Introduction

For this lab, you will work through most of section 6.5 in the text. Since this section has many exercises (a number of which are challenging), and there are only three lab days for this assignment, we give you a Scheme file which will get you started. Also, for this lab only you needn't complete a formal lab writeup. Instead, you will provide code and a section on testing.

Prelab

It is crucial that you read sections 6.1-6.3 and the beginning of section 6.5 before coming to lab.

In lab

Using your favorite method, save the file ~mc27/labs/nim/nim.scm somewhere under your home directory, and then evaluate everything in it in DrScheme. (Note: The easiest way to save the file is to go to the link, and then do a Save As... under the File menu in Netscape.) This file contains the Nim program and the game-state implementation from the book, except that computer-move and human-move are modified as indicated in exercise 6.13(c).
In order to make the Nim program work, you will need an implementation of the move-instruction ADT (exercise 6.13(b)). For your convenience when doing the implementation of the move-instruction ADT, we have included ``stubs'' for the three ADT operations near the bottom of the file; the constructor is called make-move-instruction and the two selectors are called num-coins and pile-number. You should write them correctly by removing the error expressions which they currently contain and replacing them with the actual procedure bodies.
Keep in mind that make-move-instruction just constructs a move-instruction object, while next-game-state actually performs the move.
Once you have implemented the move-instruction ADT, you can test your implementation in two ways. First, you could test the ADT in isolation with expressions such as:
```
   (num-coins (make-move-instruction 4 2))
```
Second, you can test the ADT in the context of the whole application by playing Nim games with the computer by evaluating, for example, the expression:
```
   (play-with-turns (make-game-state 5 8) 'human)
```
Both kinds of tests are critical in any large application, so be sure to do both kinds of tests throughout this lab.
Play a couple of games so that you get a hang of how the interaction works. (You needn't include transcripts of your game playing in the lab writeup.)
Implement another, totally different, representation for a move-instruction ADT. (You can comment out the last one.) This entails rewriting all three procedures: make-move-instruction, num-coins and pile-number. You'll be asked at the end of the lab to make sure your program works with either implementation.
Do exercises 6.14-6.19 in the text.
When working with the random procedure, keep in mind that each time you use it you may get a different result; if you want to use the same randomly chosen integer twice, you should hold onto it, for example by naming it with a let, as you won't be able to regenerate it.
Again, as with the game-state ADT, be sure to test each strategy in isolation as well as in the context of the whole application. If you are unsure about how to test the strategies in isolation, ask!
Test to be sure your code works with both move-instruction ADTs that you implemented at the start of the lab.
You are encouraged to do exercises 6.20 and 6.21 if you have time, but they are not required.
One other optional activity is to error-proof your Nim program, so that if the user enters an invalid move, the program handles the error appropriately. Ideally, you should have the program detect the invalid move, and then ask the user to enter a valid move instead. How can this be done most easily?

Postlab

For this lab, no formal writeup is required. You should include all the code you wrote (or changed), and a specific and clear explanation of how you tested your procedures.

As always, the code should be clear with names well chosen, and you may need to comment any code which is hard to understand. You may assume the reader knows your assignment.