CS 117: Final Project
Overview
This is your chance to choose one of two projects, each described below.
Design document (due Monday, 11/12/01)
As with the longer project earlier in the term, submit a design document
indicating which option you choose, and the following information:
-
Headers for each of the methods that you will need, and in which classes
they belong
-
Descriptions of the data values you'll need within each of the classes
-
Pseudocode for each of the methods
-
Estimates of how long it will take you to write each of these methods.
Consider how long it will take to translate the pseudocode into actual
Java code, then remember to leave lots of time for debugging and testing.
-
Your test plan: how will you test each of these methods individually to
make sure they work?
The final submission (due Monday, 11/19/01 - no grace period!)
In addition to submitting your java files, you should submit the following
items of documentation in the README.TXT file that is part of your BlueJ
project. You may be brief.
-
A description of your program and its features.
-
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.
You may handle input/output via javabook classes, or via the terminal window.
Choose whichever you prefer.
Thoughts on grading
I will grade the projects based on the following factors:
-
How cleanly the program runs... is it bug free? Does it crash?
-
Complexity... a chess program that will beat Garry Kasparov is clearly
cooler than a program that flips a coin.
-
Style.
The first factor above is most important. A program that runs correctly,
error-free, and achieves what it says it will do will receive better grades
than an incredibly smart chess program that crashes and provides unreadable
output. Of course, given two programs side-by-side that run perfectly,
the one that accomplishes more will receive the better grade.
To reiterate: It is most important to submit something that works.
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.
II: 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 (C++ method) called "Shuffle" that you
might be able to adapt for your poker hand generation. Even though it is
written in C++, you shouldn't have any trouble reading most of it. It's
close to Java.
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:
246 B
037 P
105 F
309 PF
etc.
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.