CS 117, Fall 2000: Final Project

Overview

This is your chance to choose one of three projects, each described below.

Design document (due Monday, 11/13/00)

As with the longer project earlier in the term, submit a design document indicating which option you choose, and the following information:

Descriptions of the classes and data structures you will need to solve the problem
Descriptions of the purpose for each method and function that you will need
Pseudocode for each of the functions
Estimates of how long it will take you to write each of these functions. Consider how long it will take to translate the pseudocode into actual C++ code, then remember to leave lots of time for debugging and testing.
Your test plan: how will you test each of these functions individually to make sure they work?

The final submission (due Monday, 11/20/00 - no grace period!)

In addition to submitting your project via hsp, you should submit the following items of documentation as well. They should be included in a single text file, and may be brief.

A description of your program and its features.
A description of your program's command-line syntax.
A description and justification of the main data structures your program uses.
A discussion of the current status of your program, what works and what doesn't, etc.

Project Choices

I: A Game

Write a game program. You can approach this with the goal of making the game fun to play, making the computer play well (even if it's not much fun for the user), or both.

Good games to implement include Bagels (see description at the bottom of this document for details), 3D Tic-Tac-Toe, Blackjack, Cribbage, Dots and Boxes, Battleship,....

Let me know if you have questions about the rules or suitability of a particular game.

You may use graphics to display your game, but that is not necessary.

II: Moveable Movies

If you choose to do this project, you will write a program that uses the g2 graphics library (here's an example graphics program) to display a short movie. The content of your movie is up to you, but it need not be complicated.

There's a catch, though. Your code must be organized so that the movie can be shown in a frame of any size or location. In particular, your code should include a function described as follows:

        //
        //      DrawFrame
        //
        //      Draws the Nth frame of the movie inside the rectangle
        //      the coordinates of whose top, bottom, and sides are
        //      given by the parameters top, right, bottom, and left.
        //      Note that no drawing is done outside this rectangle,
        //      and that no assumptions are made about the width, height,
        //      or ratio of width to height of the rectangle.
        //      
        
        void DrawFrame( int window, int N, int left, int top, int right, int bottom );

There are lots of cute tricks you can play with your movie if you organize the code in this way. For example, you could show the movie in two locations on the screen simultaneously by doing something like this:

        for( int i=0; i < nFrames; i++ )
        {
                DrawFrame( window, i, 0, 0, 200, 200 );
                DrawFrame( window, i, 300, 300, 500, 500 );
        }

Or you might show all the frames simultaneously in one window, lined up in a grid so you could compare all the frames at the same time. Or you could draw a fancy border, and show the movie inside it.

You need not do any of these things with your code, but you should definitely test it in rectangles of various shapes and positions.

NOTE: DrawFrame should not call g2_open_X11(). In fact, your main program should call g2_open_X11() once, after which g2_open_X11() should never be called again.

III: Poker Hand Probabilities

Many decks of poker cards include a card showing the probabilities of being dealt various types of 5-card hands. For example, the probability of being dealt a royal flush (Ace, King, Queen, Jack, and Ten, all the same suit) is 1 chance in 649740, or approximately .000001539. If you select this project, your job will be to write a program that approximates the probabilities listed on such a card.

To do this, your program will generate a large number (many millions) of poker hands, and count the number of royal flushes, flushes, straights, full houses, etc. included among those hands. This means that you will need to figure out how to generate a random poker hand, and then how to determine what type of hand it is.

Your program should report probabilities for each of the following types of hands. The term "rank" refers to the card's numerical or letter value.

Royal Flush: A, K, Q, J, 10, all the same suit.
Straight Flush: five cards in a row (Aces are high), all of the same suit, but not including Royal Flushes.
Four of a kind: any four cards with the same rank, plus any fifth card.
Full House: three of the cards of the same rank, and two cards of the same rank. That is, three of a kind and a pair in the same hand.
Flush: any five cards of the same suit.
Straight: five cards in a row (not all of the same suit, since that would be a straight flush).
Three of a kind: three cards of the same rank, plus two other unmatched cards.
Two pair: two cards of any one rank, two cards of any other rank, plus one unmatched card.
One pair: two cards of the same rank, plus three unmatched card.
Other: any hand that doesn't fall into one of the above categories.

This sorting program contains a function called "Shuffle" that you might be able to adapt for your poker hand generation.

Rules for Bagels

Bagels is a two person paper-and-pencil game that is similar to but simpler than Mastermind. One person thinks of a 3-digit number, and the other person tries to guess it. The 3-digit number may have no repeated digits, but it may begin with a zero (so 012, 987, and 361 are legal, but 112 and 303 are not).

The Guesser makes a 3-digit guess. The Responder compares the guess to the actual mystery number, and responds to the guess by some combination of the words "Pico," "Fermi," and "Bagels." The Guesser keeps guessing until the guess is the mystery number. Here are the response rules:

If the guess has no digits in common with the mystery number, the answer is "Bagels" or "B."
If the guess has a digit in common with the mystery number, and the common digit is in the same position in both numbers, the responder says "Fermi" or "F."
If the guess has a digit in common with the mystery number, but the common digit is not in the same position in both numbers, the responder says "Pico" or "P".

For example, suppose the mystery number is 395. Here are a few guesses and responses:

Note that if there are Picos and Fermis in the same response, all the Picos should be reported first. That is, you'd never say "PFP," thus suggesting that maybe the middle digit of the guess was the one in the correct position. Instead, you'd say "PPF," regardless of which digit was the Fermi, and which two were the Picos.

If you want more clarification of the rules of Bagels, let me know.

If you choose this project, you should write a program that will play Bagels with you, both as the Guesser and the Responder. Having the computer act as Responder is fairly straight-forward. Having it act as Guesser is trickier, but fun.