CS 117 Final Project

Due 5:00PM Tuesday, March 18, 1997

The Project

Some games are asymmetrical, where one player has an easy job. For example, when you play hangman, one person just has to think up a suitably random word and respond to the other player's guesses. This job is very easy for a computer to perform, and as a result, there are hundreds of versions of hangman on the computers of the world. One could argue that games like hangman are really one-person games. Other games like this are Mastermind and its low-cost relative Bagels.

Other games are symmetrical, or very nearly so. Chess, Go, Tic-tac-toe, Dots and Boxes, Battleship, and Cribbage are examples of games in which both players are faced with a nearly identical challenge.

For your final project, you will write a program that plays a game. Your goal, however, is not necessarily to make the game fun to play, but rather to make the computer play it well. The heart of your project will be the computer's strategy for playing the game you choose. For example, you could program the computer to play Tic-Tac-Toe by picking a random open square, but you would end up with a program that never wins and almost always loses to an experienced player. On the other hand, if you understand Tic-Tac-Toe, you can program a computer to play it perfectly (always tying when playing a perfect opponent, and winning whenever the opponent makes a mistake).

You can write your program to play against a human player. In this case, you should pay enough attention to the user interface to make sure a new user will be able to figure out how to play. The user will also need to be able to see the current state of the game at any time.

On the other hand, you could write your program so that it plays against itself, and collects statistics on how many games are won by which strategy. For example, it might be interesting to know how many wins, ties, and losses a "play in a random square" Tic-tac-toe strategy would achieve against a "block my opponent if I can, and otherwise play in a random square" strategy. If you take this approach to your program, make sure the program prints out the collected data in an intelligible way, and also make sure to discuss the results of your investigations in the documentation you hand in with your program (see below).

A third approach to game-writing would be to write a program that learns how to play well by playing (and presumably losing) a lot of games. This is tough, but very interesting. Let me know if you're thinking of doing this.

Either way, you should try to program modularly. Again considering Tic-tac-toe, you will probably want to write the following routines, (among others) or something similar:


{=================================================
	GameOver returns true if the game is over,
	and false otherwise.  If the game is over,
	the identity of the winner is stored in the
	variable parameter "winner".
 =================================================}
 function GameOver( theBoard : BoardType; var winner : integer ) : boolean;


{=================================================
	CanIBlock returns true if the given player
	has a move that will block a win by the
	other player, and false otherwise.  If
	a block is available, the square in which
	the player should play is stored in the
	variable parameter "where".
 =================================================}
function CanIBlock(  me : integer;
                    theBoard : BoardType;
					var where : integer ) : boolean;

Both of these functions assume player identities are stored in integer variables, and CanIBlock assumes the squares on the board are numbered by integers. If you have a different scheme for identifying players or squares, modify this accordingly. The point is that well-designed functions can simplify the code dramatically. I recommend that you start with a piece of paper and no computer, and think about what sorts of functions and procedures you want to write, before you write them.

A little advice

Don't start late.

Have a careful plan of the small steps you will take in travelling from no program to the final program. Design your program modularly, so you can make the modules work one at a time.

For each stage of development, write your main program first. By writing a clear, high-level main program that calls as-yet-unfinished procedures and functions, you get a good overview of your program's logic, and you thus automatically break your program into more manageable pieces (the procedures and functions called by the main program).

Don't go to sleep without a program that compiles and runs without crashing. It doesn't have do anything--just don't try to do so much at once that you can't wrap up the day's work into a running, partially complete, program.

Make copies of your program before making changes.

Grading criteria

You must meet the deadlines listed below.
Your final program must compile and run. If it does not compile, I won't grade it at all. If it compiles, but crashes a lot, you will get a low grade. I would much rather see a functioning program that does not do everything than a program that tries to do everything but does none of it successfully. Top-down design will help you meet this criterion.
An A program will work very well, and have good documentation, easy-to-read and well organized code, and a simple-to-use user interface. A C- program will have documentation, and will, more or less, allow a user to play the game to completion. A B program will fall somewhere between.

The Schedule

The following are due by Tuesday, March 4. Send them to me by e-mail at jondich.

A brief description of what your program is intended to do. Here, you should tell me what game you will be programming, and the strategy or strategies you plan to implement.
A list of the order in which you will implement the features of your program.
A list of function/procedure interfaces that you plan to implement.

The only essential item of the above is the description of the program, but the more you can tell me about your thinking, the more help I can give you. I will try to respond to your e-mail within 24 hours of the time you send it. I'll let you know if I have suggestions on how to make your programming task simpler.

Due 5:00 Tuesday, March 18 (via HSP)

Your fully commented source code, named final.p (or final1.p, final2.p, etc. if you decide to submit a later version).
A description of the program (the description from the November 15th part of the assignment would be fine), and a description of the status of the program (what works, what doesn't, the results of your investigations if you used your program to compare game strategies, etc.). Please put these in a file named finalDoc.txt.

Miscellaneous

Feel free to talk to each other and learn from each other, and compare approaches to the problems posed by these programs. I ask, however, that all your code be your own. If you take a significant idea from another person, please give explicit credit to that person.

Talk to me. I can help. I will hold regular office hours during reading and exam days. I will post my hours on my office door.

Start early, keep in touch, and have fun.

Jeff Ondich, Department of Mathematics and Computer Science, Carleton College, Northfield, MN 55057
(507) 646-4364, jondich@carleton.edu