Project #5: Cards, Anyone?
15-212, Spring 1998

The Skinny For most of the semester, we've been working on fundamentals of computer science: OOP, complexity theory, concurrency, etc. In that vein, Java has been more of a tool than a topic. However, the ability to use modern programming languages is also a fundamental skill, and that's what we're going to work on.

In this program, you are going to write the important parts of a computer Gin Rummy player. We've already written the algorithmic parts, like game logic, so you are going to write the three remaining parts: the networking, the graphical display, and the playing strategy.

Once the programs are submitted, we will have a tournament between all of the programs. If the winner of the tournament can beat Sal's player, Sal will take you out to dinner. Sal doesn't think that you can beat his player. Sal is like that.

Program Overview Gin.java is a computer gin player. It will pop up a window, connect to a program running on another computer, and play it in a game of Gin Rummy. As the game proceeds, the program will update its graphical display to indicate the state of the game. The program will actually be playing the game: there are no people involved.

Knowledge is Power The advantage of a modern language like Java is that it has excellent facilities for doing things like networking and graphical interfaces. In fact, you already know most of what you need to know for this assignment; a good manual is all you might need. Unfortunately, Nutshell doesn't cover networking and awt very well. We covered what you need to know about networking and awt in lecture on Thursday, April 16. If you weren't there, get the notes from someone -- you'll need them. The code that we went over in that class is available on the web at /afs/cs.cmu.edu/academic/class/15212-s98/www/project/gin/lecture.

Promises, Shmomises The Gin Rummy program that we have written has 15 classes (see Supplied Files, below), leaving 5 for you to write (as well as any support classes that they might need). Two of these classes are no more than ten lines long. This project is a demonstration of one of the advantages of OOP programming. If we each make a few promises about the structure of our code, we can work independently. And, we will: as bugs are discovered in the game logic, the code will be revised. These changes will not affect your code, so long as you stick to your promises.

These promises come in the form of Java interfaces. Four of the five classes you need to write has an interface: Network, Display, Player, and ExtraState (the fifth is a short class that only has text strings in it). Each of the interfaces is described in a separate section below. What you must do is write your own classes (say, MyNetwork) that adhere to the interfaces, put the name of those classes in Consts.java (see Consts.java, below).

This issue of not being allowed to change your interface plagues the entire field of computer programming. Imagine, for a moment, that thousands of people are using your code, and you find a bug in it. Now, it's not a serious one, but it needs to be fixed. What do you do? Well, the most common case of this is if your code is a langauge like Java, or C. When the people at Sun find a problem with the Java langauge, they have to change it in such a way that they both fix the problem and don't break the code that everybody has written. One of their techniques for doing this is "deprecation", which allows the old code to use the old functions, and advises people writing new code not to use them.

READ THE BULLITEN BOARD We know that some of you avoid reading the board. For this assignment, you need to read 15-212.announce religiously. If the supplied files (i.e., the code that you don't have to read or write) are changed, you will need to know about it, and that's the only way that you will find out.

Rank of Cards
3. King (high), Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2, A. [i.e., QKA is not a valid sequence]

Value of cards
4. Face cards count 10 each; aces, 1; other cards their pip value.

The deal
8. The dealer distributes the cards one at a time face down, alternately to his opponent and to himself until each has ten cards.
9. The undealt remainder of the pack is placed face down in the center of the table, becoming the stock. The top card of the stock is turned face up and placed beside it; this upcard starts the discard pile. 9a. The first upcard is also the knocking card. See Knocking, below.

Object of play
11. To reduce one's count of deadwood to less than the count of the opponent, by forming matched sets consisting of three or four cards of the same rank or three or more cards of the same suit in sequence.

The play
12. Non-dealer plays first, and the turn to play alternates thereafter.
13. In each turn, a player must draw either the upcard (top card of the discard pile) or the top card of the stock, and then must discard one card (which may not be an upcard he has drawn in the same turn) face up on the discard pile.
14. On the first play, if non-dealer does not wish to take the upcard he must so announce and dealer may have the first turn by drawing the upcard; if dealer does not wish the upcard, non-dealer draws the top card of the stock and play proceeds.

Knocking
15. Each hand begins when a legal deal is completed and ends when either player knocks.
16. A player may knock in any turn, [as he discards], if the value of the unmatched cards in his hand (after he discards) will be less than or equal to the value of the knocking card. He need not knock when able to do so. Having knocked, he... spreads his hand, arranged into matched sets and unmatched cards. The opponent then spreads his hand, [and] removes from it any matched sets.
17. The point values of the two players' unmatched cards are then compared, and the result of the hand is scored (see Scoring, below).

Drawn game
18. Neither of the last two cards in the stock may be drawn; if the player who draws the fiftieth card discards without knocking, his opponent may not take the discard and the hand is a draw.

Scoring
19. If the knocker's count is less than his opponent's, the knocker wins the hand; the difference in counts is scored to his credit.
20. If the opponent ties or beats the knocker, he has undercut hum; he wins the hand, and scores 25 points plus the difference in counts, if any, subject to paragraph 21.
21. If the knocker has a count of zero (has all ten of his cards matched in sets) he is gin; ... the knocker wins the hand even if the opponent also has a count of zero; and the knocker receives 25 points plus the difference in counts, if any.

Game
23. The first player scoring 100 points or more wins the game. [If both players are over 100 points, the player with the higher score wins the game.]

Pointers on Gin Rummy

Winning policy is to knock as soon as possible. The only exception is that a player may be forced to wait for a lower count, or to refrain from knocking at all, when he may be undercut. But the player should be deterred only by positive evidence that such is the case; vague apprehension or timidity can cost many points. Knocking at the earliest possible opportunity, even regardless of undercut hazards, will win much more than waiting "a few more draws" to reduce the count or try for gin.

Particularly foolish is waiting in the hope of getting a gin hand. The occasional gin bonus so earned is worth far less than the points lost by giving the opponent opportunity to reduce, or to knock first with a lower count. The only occasion to wait deliberately for gin is an end-situation where it is crystal clear that any lesser hand would be undercut.

The normal policy in discarding is to aim for a hand of two matched sets, with four or less unmatched cards. For example, suppose that the hand after a draw from the stock is:

Queen of hearts
Queen of clubs
Ten of diamonds
Nine of diamonds
Eight of spades
Eight of clubs
Six of clubs
Six of spades
Six of hearts
Two of diamonds
Ace of hearts

Because of the two-set target, the player must collect some low cards -- fourspot or lower. When such cards chance to be drawn, they should be saved, except possibly in the rare cases where the player is forced to aim for three matched sets. Even then, it is risky business letting the opponent have an ace or deuce, especially after six or more draws. Whether to pick up a low discard, merely because it is low, depends on circumstance. Obviously the play is indicated when the hand already has two matched sets. As a general rule, drawing from the stock is preferable when the hand needs to fill a set; yet many good players make it a rule never to pass by the upcard if it is an ace or deuce. The idea in this policy is that the value of the low card in one's own hand is added the value of keeping it out of the opponent's hand.

The normal rule is to take the discard only to complete a set, never to make a mere combination (A combination is a pair of the same rank, or two cards of a suit in sequence or skip-sequence.) Some exceptions arise: One has been noted above, the possible seizure of the upcard when it is an ace or deuce....

The question of what to discard usually narrows to a few cards. The player should save combinations (but not at the cost of letting go equally vital ow cards), together with what low cards he needs for a two-set knock. Yet there is a good deal of art in choosing discards from two or three candidates. At the beginning of a deal, a few discards are perforce "blind." Thereafter, there is some clue as two what cards are safe and what are not. The (relatively) safe discards are those of the same rank, or in sequence, with cards already discarded or refused by the opponent. Also, a card of adjacent rank and a different suit with the opponent's discard is fairly safe. Kings are safer than lower cards, as blind discards, since they can be used in only one possible sequence.

All possible inferences should be made as to what the opponent holds. When he takes a discard, the normal assumption is that he has filled a set. The cards that are dead or are in one's own hand may help to show whether this three of a kind or a sequence. The discards that the opponent does not take also show by elimination what he does not hold. One of the significant pointers is the non-appearance of any cards of a given high rank. The early discarding by both players is often a stream of face cards; when no jacks, say, have appeared within six draws, the player without jacks may infer that his opponent holds a pair. If the game goes to as many as a dozen draws, each player can infer precisely what the other holds.

Two constant purposes are served by all these inferences. First, the player wants to avoid "feeding" his opponent, and also to save cards that are "players" on the opponent's sets. Second, the player wants to know how near his opponent is to knocking. If, for example, the opponent has picked up two discards, the presumption is taht he has filled two sets and needs only some low off cards to knock. The indicated policy is to ditch high combinations, both to "unload" and to avoid giving him a low card.

A Lousy Strategy

The whole point of the game is to make matchess. For this strategy, let's only think about n-of-a-kind matches. Break your hand down into groups of cards that have the same rank (number). Consider a card without a pair to be a group of one card. The ultimate goal is to have two such groups of three and one of four.

1. Always discard a card from one of the smallest group of cards in your hand.
2. Never add to a smaller group if it will force you to get rid of a card from a larger group
3. Always add to a larger group at the cost of breaking up a smaller group (exception: if you already have a group of four, do not add a card to any of your groups of three).
4. Keeping the above in mind, always pick up a card from the pile if it will increase the total number of cards in match. If drawing from the pile will not change that number, or decrease it, then draw from the deck.

This strategy will usually lose, but it's a start, and it can actually beat other dumb strategies. We're interested to see how creative you can be with your own strategies!

A really good strategy might include remembering which cards went by so that you don't make the mistake of waiting for a card that's already passed.

Your Part

Network.java

The init should establish a connection to the opponent's computer, according to the Config.getOpponentMachineName(), Config.getNetworkPort(), and Config.isServer(). That is, if your program is the server, it should open a server socket on the specified port (there is no opponent machine in this case -- you simply wait for connections). If your program is the client, it should connect to a server on the appropriate machine and port. Note that the server must be run first (so that the client has something to connect to).

The send method sends a message and message type (a String and an integer) over the network. In particular, it concatenates the two (see Network.java for details) into a string, and sends it over the socket.

The recieve method attempts to recieve a message of a particular type from the socket. It blocks until something comes through the socket. If a message comes across the socket and is not of the requested type, the method returns null. The messge is stored for the next request. See Network.java for details.

For an example of working network code, see ConnectTest.java in supplied code for this project. If you don't understand all of this network lingo, and didn't go to lecture on Thursday, April 16th, take a look at the section on Networking in Just Java. It's about ten short pages.

Display.java

There are a number of other things that might make the interface somewhat nicer. You might represent the deck of face down cards, or the height of the deck and/or discard piles. You might actually show the knocking card, rather than its value. You might have some way of indicating the movement of cards within your hand, or from your hand to the pile and vice-versa (this last one is extremely difficult). See State.java for other ideas. There are explicit game states for winning, losing, and tying the entire game, and you will know when a hand is over, so you may consider displaying a graphic for those circumstances. Sound is also an option.

The card graphics are provided on the web at /afs/cs.cmu.edu/academic/class/15212-s98/www/project/gin/cards.

IMPORTANT NOTE: Your code must not depend on the size of the cards. This information will be provided in a configuration file at run time. Therefore, your code must be able to deal with cards of different sizes. You may assume that each card in a given deck is the same size.

You have a few choices for implementing this class. In general, we suggest that you make your display class a subclass of Frame, and lay out elements inside of that frame. You will probably want to have other classes to support this one, such as one for displaying a single card, perhaps one to display an entire hand, and one for any other parts of the tableau (the layout of a card game) that you wish to display. Remember that each component of a layout may have components (or even containers) within it. You will probably want to nest components and containers to get the result you are looking for.

Some functions that you might find useful (you can find them in the back of Nutshell, if you'd like to use them) are setHgap(), setVgap(), setBackground(), setFont(), and setForeground(). Also, look at the code that I presented in class, which can be found at the URL listed above.

DRAW YOUR LAYOUT BY HAND, FIRST. Don't sit down at the computer and hack it out -- it will look bad. A two minute sketch will save you a huge headache later. On your sketch, ote what the individual components and containers are, what they contain, what layout they are using, and where they should be relative to each other.

DO NOT USE ANY ABSOLUTE NUMBERS. Your display should work perfectly on any platform, for any window size (remember, the user can resize the window). You may calculate a good initial size for the window, and a Canvas should be exactly the size of the image it is holding, but do not place individual components using absolute numbers. It is perfectly fine if your layout hides things when the window is made too small, but you should be able to display the entire display on roughly half of a 15" monitor (like those in Wean).

This class has only two methods: an initialization, and a method that is called when the game's state changes. The constructor, which takes the game configuration (see Config.java, below) as its only parameter, sets up the display, and perhaps even puts it on the screen. It need not do so, and the display may be empty when initConfig is the size of the card graphics.

The other method, updateDisplayState(), does just that. It's parameter is the new state, and the function's job is to change the display to represent that state. Note that it is your responsibility to force a repaint() on any components that you change in this function.

The method whereDraw() determines whether your player should draw from the pile or from the deck. Note that on the first turn (State.gameStage == State.firstCard), the non-dealing player must either pick up the card on the pile, or pass to the dealer. If the non-dealing player has passed (State.gameStage = State.passedFirstCard), the dealer must either pick up the card on the pile, or pass back to the non-dealing player. Only after this interchange may normal play (State.gameStage = State.gameOn) begin (see rule 14, above). For obvious reasons, you may always assume that there are ten cards in your hand when this function is called.

The second method, whatPlay chooses a card to discard. Note that, in the case that whereDraw() passes on the first car, this function will not be called (i.e., you may always assume that there are 11 cards in your hand when this function is called).

The last method, countUp() is an NP-Complete problem. This function takes a hand of ten cards, determines which cards are in a match (matched, and returns the total number of points out of match. This is not an easy problem -- the search space is enormous. It may be easier to think about the problem if you consider it as an ordering problem, and a dividing problem: First, there are 10! ways to arrange your cards. Second, you need to divide your hand into matches, so the question is where to place the dividing lines (between 3 and 4 and between 6 and 7? or between 4 and 5 and 6 and 8? or between 5 and 6?). Even human players often have trouble with this task.

IMPORTANT NOTE ON SPEED. Of course, each of these function could run for days without finding a good solution. The key here is to find a good solution, fast. Each function call should take no more than a few seconds to run. If your functions take too long, you will be sternly penalized (that's twice that we've said that -- we're serious).

IMPORTANT NOTE ON YOUR STRATEGY. If you implement a better strategy than the one described above (see A Lousy Strategy), you should describe how it is supposed to work in a prose-form comment at the top of your Player class. Your strategy and how you implemeent it is 25% of your grade on this project (see Grading, below.

Supplied Files

Practice makes perfect You may (and it's not a bad idea) revise your player for the tournament. Don't revise your display or network code -- if it doesn't work, we'll use our implementations. The only requirement is that you submit a working player to the proj6 directory by 8pm on May 10th (that's a Sunday).

The brass ring The tournament will be a single elimination tournament. That is, each pair of teams will play a game of Gin Rummy (that is, a few hands) to 100 points. If the winning program can beat Sal's player, he'll take you out to dinner. He doesn't have a car, but if you can get him there, dinner's on him. Of course, if you don't like Sal, he'll pay for you out to dinner on your own.

Timing Delays You may find that your program displays better with timing delays put in particular places. For testing purposes, you may put them anywhere you would like. In your final program, however, you should have no delays in any part of your code. Since the display takes priority over the actual player, a delay in the display will hang the program. If you would like to have moving graphics in your program (not an easy feat), please contact us first.

Testing There will be a working gin player running on gs140.sp.cs.cmu.edu at all times. See README.testing in the supplied code directory for information on how to run and test your program. please call or e-mail Sal (feel free to call him at home, regardless of what time it is -- his number is in his plan file).

Submission You are only to submit the classes that you wrote yourself, including the Network implementation, the Display implementation, the Player implementation, ExtraState implementation, Consts.java, and any support classes that you write. If you feel that you need to change one of the other files, think twice, go home, think again, and then, only if you are sure, ask us why that's not the case.

Human Players I'm sure that somebody is going to argue that a user interface is a perfectly good player -- the human is making the decisions, but it adheres to the interface. This may be true, but is not within the scope of the assignment. Your player must be entirely autonomous.

Grading Programming style plays no part in the grading of this assignment. If your program works, you get the entire 50% for correctness. If it doesn't work, you get none of it. If it works, but breaks rules or fails in cases, you will be penalized. The ramaining 50% is more subjective.

Your playing strategy and it's implementation is 25% of your grade. If you simply implement the Lousy Strategy, above, you get 15 points. The more creative and effective your strategy is, the more points you get, up to the full 25 points. Of course, the better the strategy, the more likely you will win the competition. You may revise your strategy before the tournament, so just make sure that you submit something that works when the assignment is due.

The last 25% grades your display on aesthetics. Does it show all of the required information? Does it resize well? Is any of it in absolute coordinates? Is it readable? Did you add extra features to it that make it particularly nice?

Keep an eye on the class bboard for clarifications and updates.