MCS-177 Project: Nim with Strategies

Problem

How do you modify the program for playing Nim so that the computer can play using different strategies? In this project, you should work through the exercises in section 6.5 (except for 6.20 and 6.21). Before coming to lab, be sure that you have read and understood sections 6.1-6.3 and the beginning of section 6.5, if you haven't already.

Computer Exercises

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 Mozilla.) 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 whenever appropiate throughout this lab. You should identify when and how both types of tests were done in the appendix of your project writeup.
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.)
Do exercises 6.14-6.19 in the text (except do 6.18 as below). 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 move-instruction ADT, be sure to test each strategy in isolation as well as in the context of the whole application. Also, be sure that every random strategy really is random. If you are unsure about how to test the strategies in isolation, ask!

For 6.18, the connection to Nim is this: An m by n chocolate bar corresponds to a 2-pile Nim game with piles of size m and n. Given this, what does ``make the chocolate bar square'' correspond to in Nim? Lastly, in answer to the question posed in the last sentence of 6.18, feel free to have your strategy make any move you wish when it is posed with a losing position.
Maintaining a modular program is critical to the success of any large programming project. A good way to test to be sure that your program is truly modular is to take out one working module, and swap it for a different, but also working, module. We'll do this, treating the move-instruction ADT as a module:
- Implement another, totally different, representation for a move-instruction ADT. (You should comment out your original.) This entails rewriting all three procedures: make-move-instruction, num-coins and pile-number. (If this is confusing, look at the two implementation of make-game-state on pages 148 and 151.)
- Test to be sure your code works with both move-instruction ADTs that you implemented. You may find that this test exposes a bug in your program if one of your procedure tries to access the move-instruction ADT directly, rather than going through the proper interface consisting of make-move-instruction, num-coins and pile-number.
(Optional) You are encouraged to do exercises 6.20 and 6.21 if you have time, but they are not required.
(Optional) 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?
(Optional) Another possible optional activity is you can change the rules to the game in some way. For instance, what changes to the code would you need to make to play 3 pile nim? Or nim on any number of piles?

Project Report

As you know, we are assigning a specific style and audience for each report. For this project, the style might be called a "Strategy-writers' manual" and the audience should be programmers that want to extend the software system.

Your finished product in this project is a software system that allows users to play a game of Nim against various different strategies. Even though the game is relatively simple compared to games you might actually purchase, the situation is a familiar one: you have created a software system which might later be revised and extended by other programmers. Your task is to write a manual for future programmers describing the structure of the programming system and how they should go about extending that system.

More specifically, you first describe what your system is intended to do -- namely, playing a game of Nim, which you should briefly describe. Then you should explain the structure of your software system for programmers who are competent in Scheme, but are unaware of the system itself. Give a good overview of the structure of the software system, giving special attention to its two ADTs. Try to be brief and precise in describing the ADTs (i.e., the interfaces) and avoid going into details (such as implementation) irrelevant to the "strategy writer".

Furthermore, explain what a strategy is (as a Scheme procedure) and how a programmer should go about writing a new strategy for the system. You may also, if you wish, add suggestions for possible improvements or extensions that could be made to the system. If you do make suggested improvements, they should include specific guidance on what would need to be changed to implement those improvements.

For the purposes of my grading your report, I ask that you also include an appendix all of the procedures you wrote or modified. You should also describe the testing you did on those procedures. This should include examples of the testing, but should also be descriptive of your testing strategy.

You can get some sense of how this project report will be graded by looking at the grading sheet that we use.

Back to MCS 177 home page