Written by Chris Alfeld and Peter Jensen
It is the future, the year is 2098. Competition has been taken outside the human level and into the world of computers. The greatest computer competition of all is the Tricky Eights competition. Based on card games of the twentieth century, Tricky Eights is a simple trick-based card game in which four programs try to out-score each other. The 2098 Tricky Eights Championship is coming up and you are to write the best program you can to compete for first place.
Each high school will submit a program which will act as one of the players in the tricky eights tournament. A play-off will be held to determine which program is the most skilled at winning Tricky Eights games. The score you get on the take home problem will be determined by how well your program does in the tournament.
Tricky Eights is a four player card game, with each player playing on their own. (No team play.) It is played in two phases: In the first phase, players get to choose which cards to add to their hand. In the second phase, players play cards in order to win tricks. Scoring is based upon the number of tricks a player takes, as well as how many 8's the player takes. Tricky Eights is played as a series of rounds, ending when a player reaches a score of 300 or more. In each round there is a dealer.
Tricky Eights is played with a standard deck of 52 cards. At the beginning of each round the current dealer deals 10 cards to each player. The dealer then places the remaining 12 cards face up so that everyone can see them.
(Note that after every game, the dealer is a different player. For the first round this is the north player, second is east, third south, fourth west, and then beginning again with north.)
After the cards have been dealt, each player should have 10 cards and there should be 12 cards laying on the table face up. Starting with the dealer and proceeding clockwise through the players, each player chooses one of the 12 cards, putting it in its hand. After all twelve cards have been taken in this manner, the round proceeds to the card-playing phase.
When play begins, everyone should have 13 cards in their hand. At this point, the object of the game is to acquire as many points as possible by winning tricks. In each 'trick', someone, known as the leader, plays a card face up. Then, going clockwise around the table, the remaining players each play a card. If possible, a player MUST play a card of the same suit as the first card (the leader's card). If a player has no cards of that suit in their hand, they may play any card they wish. (The remaining players must still 'follow' suit.)
Once all players have played a card, the winner of the trick is determined. The player (including the leader) who played the highest card of the same suit as the leader's card wins the trick. (The cards in order of value are 2-10, jack, queen, king, and ace.) Players who did not play the correct suit are NOT considered in determining the winner of a trick, even if their card was higher in value than the trick-winning card. The winner of the trick is now the leader for the next trick. Play continues until all 13 tricks for this round have been played.
The first trick is always started (lead) by the current dealer.
After thirteen tricks have been played, everyone should be out of cards. The round is over. Players are awarded points as follows:
A total of 25 points per round is awarded to the players.
For example, say the north player took the first and last trick, three other tricks, and, in these tricks, took the eight of clubs and the eight of diamonds. North would have made 13 points.
For each player, the number of points earned in this round are added to the number of points earned in the previous rounds. The game is over when a player reaches or passes 300 points. (In the event that two players have the same score above 300, play continues until there is a clear winner.)
Once you have figured out how to play Tricky Eights, your job is to write a program that acts as one of the players. This isn't as tough as it sounds, seeing as we've done most of the hard work for you. We have written a basic contestant program which you will be modifying. (All the input and output is handled for you.) The only thing left to do is to program in some strategy so that your program will win.
Your job is to implement six functions, each of which deal with some small portion of the game. (Some functions may be empty if you choose.) A shell containing the declarations of these functions and full descriptions of them is in shell.cpp. There is also an example random.cpp which implements a very simple contestant. The random player follows the rules but otherwise plays randomly. The shell and the random player are a starting point for your work -- you may modify either of these programs to write your contestant. A good approach to writing your contestant would be to make small, incremental changes to the random program to make it play slightly better each time.
In order to make writing the contestant easier, we have set up global variables to make accessing game related information easier. Information about the current game, the cards in your hand and on the table, and the current play is provided in a global data structure called 'GAME'. It is a structure defined and fully described in acm98.h. This global structure should not be modified. Modifying it may cause your program to produce incorrect output which will disqualify it. For all purposes consider it a read only structure. But you may read the information from this structure and build other structures of your own design. (This is very much encouraged.)
In order to eliminate the problems of having four programs interact with each other, a great deal of code has been provided for you. Some of this code (provided in acm98.cpp and acm98.h) MUST NOT BE MODIFIED. It is not part of the contest to have to write anything dealing with communications, scoring, or play order. But to get your program working, you may need an understanding of what is going on. Any submissions or modifications of these pre-written files will be ignored.
A bit about how the contest will work: Each contestant program in the contest operates in the same manner. It receives information and instructions about the game from the standard input, and it outputs it's play choices to standard out. (Remember, you don't have to worry about programming this.) This means that both C++ and Pascal programs can compete together, because they will communicate in the same way. It also means that you can test your contestant by running it, and typing in some information to see how it responds. The side effect of this is that all of your debugging output MUST GO TO STANDARD ERROR (stderr), any debugging output sent to standard out will interfere with game play.
Fortunately there is an easier way to test your contestant. We have provided a server program, which works just opposite of the contestants. It deals the cards and keeps track of the games, and prints this information to standard out, and it awaits responses from the contestants from standard in. To link these programs together, we have also provided a dispatch program which routes the standard output of the contestants to the standard input of the server, and vice versa. See the later section for details on running these programs.
Here at Tricky Eights HQ we've come up with a couple classes of program playing ability we'd like to share with you. These are simply goals that you should try to achieve at each step, not requirements. The best program submitted may only be slightly better than the pseudo-random player:
In order to run the competition, we have written two programs which will link together four contestants and play a game of Tricky Eights between them. We are releasing these programs for you to use as you develop your contestant program, and it would be a very wise thing to do to make sure your program works using our competition software.
The contest is always run from the command line. Within Windows 95, you will need to start an MS Dos prompt and chage directories to where you have stored your executables before you can run these programs.
te_server.exe: This program is the judge for the game of Tricky Eights. It controls the game by dealing the cards, keeping track of plays, and instructing each player when to play.
You should not have to run this program directly. However, it may
be the case that you wish to examine the input and output from this
program. To run this program, type 'te_server.exe' followed by a
random number seed. Example: 'te_server 13' runs the server and
specifies to deal the cards a specific way. (The random number seed
causes the program to deal exactly the same hand each time the program
is run, this helps greatly in debugging.)
The server program outputs a log of the entire sequence of games. It can be found in 'te.log', and it's output follows a very similar format to that specified in a later section, except that it also contains comments and routing information.
The source code for te_server.exe, te_server.c is available and on your diskette. You should be able to recompile it using any C compiler. We reccommend that Macintosh users do this if they want to run the server on their machine. Just remember to not make any modifications to this program!!!
te_dispatch.exe: This is the program that we will run to link together four contestants to the te_server program. It routes the commands and responses between the various programs.
The syntax for running this program is:
te_dispatch {server} {player 1} {player 2} {player 3} {player 4} {randomseed}
Examples: To run game 1211 between four random players, type:
te_dispatch te_server random random random random 1211
To test your program called 'cardshark.exe' against three random players
using game 332:
te_dispatch te_server cardshark random random random random 332
The source code for te_dispatch is also available, but it is currently customized for compilation using Visual C++ 4.0 and Windows 95.
Note that the te_dispatch and te_server programs will only run together under Windows 95 or Windows NT. Special Unix versions are available in the event that you do not have a PC with Windows 95 or Windows NT.
Also note that unlike the debugging environment, you will not be able to predict which random numbers come next in your program, and a timer will be added to the server to make sure programs do not take too much time to run.
The competition will be a single-elimination tournament. With four players, 300 points a game, and only 25 points a round, it could take a while to run the tournament. In order to finish things in time the Tricky Eights judges are imposing the following limits:
We will expect to receive from you one source code file (which we will compile and link with the acm98 file) and one text file describing your solution/strategy. The deadline and submission instructions are part of the cover letter that we sent to your team advisor.
The code to deal with the protocol is already written (acm98.cpp). However, it may be useful to understand the I/O going on for debugging purposes.
Although the input to a contestant looks rather complex, the contestant responds with extremely simple output, consisting only of cards. Cards are represented by a pair of characters. The first character represents the suit ('c'=clubs, 's'=spades, 'd'=diamonds, 'h'=hearts). And the second represents the face ('2'-'9' = 2 to 9, 't'=ten, 'j'=jack, 'q'=queen, 'k'=king, 'a'=ace).
Examples:
cj - Jack of Clubs
ha - Ace of Hearts
d2 - Two of Diamonds
st - Ten of Spades
Input to each contestant consists of commands. Each line starts with a command followed by some number of arguments. The commands are: starthand, take, aftertake, play, result, endround.
starthand WHO:char HAND:card*[10] POOL:card*[12]
starthand is issued at the beginning of each hand.
The arguments are a single character indicating who the player is
('n'=north, 's'=south, 'e'=east, 'w'=west), the ten cards of the hand,
and the twelve cards in the pool.
Example:
starthand n d9 c8 s3 hq c4 cj h7 dt da s7 s2 ct ha c6 sa d5 ck c9 s5 cq h5 hk
Player: North
Hand:
Diamonds: 9, 10, Ace
Clubs: 8, 4
Hearts: Queen, Jack, 7
Spades: 3, 7
Pool:
Diamonds: 5
Clubs: 10, 6, King, 9, Queen
Hearts: Ace, 5, King
Spades: 2, Ace, 5
take (PLAYER:char CARD:card)x[0..3] WHO:char
take requests that the contestant take a card from
the pool. The arguments consists of the leader ('n'=north, etc.) and
optionally the card that the leader took and any other cards already
taken. The simplest case is that the player is the leader, in which
case the only argument is a character indicating the leader (in this
case the same as the player). If the player is not the leader then
the arguments are set of pairs of who and cards showing what cards
have been taken and who took them.
Examples:
take n
Player is north. Player north is leader and must take a card.
take n d5 e
Player is east. North lead and took five of diamonds, now player
east must take a card.
take w d5 n ct e ha s
Player is south. West is leader and took five of diamonds, north
took ten of clubs, east took ace of hearts, now player south must take a card.
aftertake (WHO:char CARD:card)x4 aftertake is sent. The arguments are
four pairs of who and card summarizing the round of takes.
Examples:
aftertake n d5 e ct s ha w sa
North took the five of diamonds, east took the ten of
clubs, south took the ace of hearts, and west took the ace of
spades.
aftertake n cq e s2 s d5 w c6
North took the queen of clubs, east took the two of spades, south
took the five of diamonds, and west took the six of clubs.
play (PLAYER:char CARD:card)x[0..3] WHO:char
play is identical to take in syntax but indicates
that the player must play a card. Arguments will indicate the leader
and any cards that have been played so far.
Examples:
play n
Player is north. Player north is leader and must play a card.
play n d5 e
Player is east. North lead the five of diamonds, now player east must
play a card.
play w d5 n ct e ha s
Play is south. West lead the five of diamonds, north played the ten
of clubs, and east played the ace of hearts. Now player south must
play a card.
result (WHO:char CARD:card)x4
result is identical to afterplay in syntax and
serves the purpose of summarizing the last trick. Arguments is a set
of four pairs of who and card.
Examples:
resultoftrick w sa n d5 e ct s ha
West led with the ace of spades, north then played the five of
diamonds, east the ten of clubs, and south the ace of hearts.
resultoftrick n s2 e s3 s s4 w sa
North led the two of spades, east played the three of spades, south
player the four of spades, and west the ace of spades.
endround
endround has no official arguments and signifies that the round is over.
Example:
endround
Here's is a commented, paraphrased example of a game:
starthand s h9 h2 s8 ca h4 hj c7 sq st dk s2 ct ha c6 sa d5 ck c9 s5 cq h5 hk sa c6
Player is south. Hand: Clubs: ace Diamonds: 7, King Hearts: 9, 2, 4, Jack Spades: 8, Queen, 10 Pool: Clubs: 10, King, 9, Queen, 6 Diamonds: 5 Hearts: Ace, 5, King Spades: 2, 5, Ace
take n s2 e hk s h5
North took two of spades, east took king of hearts, now player (south) must take. Player responds with take of five of hearts.
aftertake n s2 e hk s h5 w cq
Take report. North took two of spades, east took king of hearts, south took five of hearts, and west took queen of clubs.
take n s5 e c9 s ck aftertake n s5 e c9 s ck w d5 take n sa e c6 s ha aftertake n sa e c6 s ha w ct
The remaining two rounds of takes go by in similar fashion with north taking the five and ace of spades, east taking the 6 and 9 of clubs, south taking the king of clubs and ace of hearts, and west taking the 5 of diamonds and ten of clubs. At this point all players have twelve cards in their hands.
play n d9 e d3 s dk
First trick: North played 9 of diamonds, east followed with three of diamonds, now it is player (south) to play. Player plays king of diamonds.
result n d9 e d3 s dk w dj
The summary of the trick. South won the trick with the king gaining 3 points for the first trick.
play s h9
Since south took the last trick it gets to lead this trick. It leads with the 9 of hearts.
result s h9 w h3 n hq e h8
North takes the trick with the queen of hearts, getting 1 point for the trick and 2 points for taking an eight, for a total of 3 points.
play n c8 e c2 s ca result n c8 e c2 s ca w c5
In the next trick south takes it with the ace, receiving 3 points (1 for the trick, 2 for taking an eight).
play s h2 result s h2 w ht n h7 e hk
This trick is taken by east for only one point.
play e d7 s s8 result e d7 s s8 w dq n dt
Here south had no more diamonds so played a spade instead. West takes the trick with the queen gaining three points (1 for the trick, 2 for the eight).
play w s6 n s3 e sj s sq result w s6 n s3 e sj s sq play s h4 result s h4 w h6 n c4 e d4 play w d8 n da e d2 s hj result w d8 n da e d2 s hj
And the last eight goes, taken by north.
play n cj e c3 s c7 result n cj e c3 s c7 w cq play w s4 n s7 e sk s st result w s4 n s7 e sk s st play e s9 s h5 result e s9 s h5 w d6 n s2 play e c9 s ck result e c9 s ck w ct n s5 play s ha result s ha w d5 n sa e c6
South wins the last trick with the ace of hearts. For taking the last trick south receives 3 points.
end 6 3 11 5
The round ends with north having 6 points, east 3, south the winner at 11, and west 5.
A web page that will contain bug-fixes, updates, and answers to questions is available at http://www.cs.utah.edu/outreach/contest.html.
Please send all questions, etc. to hspc@cs.utah.edu .