| Table of Contents | Next |
Know when to forgo an advantage.--Benjamin Disraeli
Strap yourself into your program's cockpit. Gentlemen, start your sockets! boom the echoing bullhorns. The connections rev up and block for the server's signal. A green flag waves and your program is off! It's the first (and possibly last) annual Solitaire 500, a no-algorithms-barred competition to have your program be the first to organize and discard 500 shuffled decks of cards.
Speed matters. A glance at any of the Usenet programming newsgroups reveals innumerable examples of arguments over fine points of programming, seemingly authoritatively settled when someone benchmarks example code. There is a lot of interest in speed, but execution speed is rarely made a criterion in programming contests. Bucking the hardware-industry-inspired trend against fast software, the Solitaire 500 is a race. Entries that survive a qualification round will compete against one another to find which can finish an identical series of puzzles first.
The game is called "Wheels." It is solvable, predictable, and can take hours to play by hand. A deck of cards is won when all thirteen sets of four cards have been matched and discarded.
To play Wheels, lay four cards from the top of the deck left to right, face up. The cards now mark the location of the four game piles, which for the purposes of this contest are numbered 0,1,2,3. If the top (visible) cards on any two piles match in rank, (e.g. two of the four cards you see are sevens) the card to the right may be moved to cover the matching card to its left (e.g. you may move a seven from pile 2 on top of a seven on pile 0 or 1.) This step may be (and often is) repeated.
When it is no longer possible (or desirable) to group like cards, another four cards are dealt face up atop the four piles. If all four freshly dealt cards match in rank, they are moved to the discard pile where they remain for the rest of the game. When the entire deck is dealt into the four game piles and the last moves made, the piles are stacked together, flipped over, and another round begins. The order in which the piles are restacked is up to you. Wheels has two opportunities for player decisions: You choose when to move matching cards to the left and you choose how to restack your cards. That's all there is to it.
Discarding, rare in the first few rounds, happens regularly in later rounds. Chaos magically transforms into order at a satisfyingly increasing rate as the cards become better grouped and there are fewer cards to deal out in each round. Unless you get stuck in an endless loop, all the cards will eventually be discarded, and you can break out of endless loops by either choosing not to make legal moves, or varying the order in which the game piles are picked up. Those choices can also be used to find an optimal strategy: When playing by hand, you'll inevitably experience a sense that had you left just one more card in some pile last round, several sets could have been discarded this round. D'oh!
Unlike the "Stones" contest from TPJ #7, when entries were subroutines called by a larger program managing one-on-one matches, all entries in the Solitaire 500 will run simultaneously. In a perfect world we'd give each program their own identical computer to run on. Or the contest would be held over the Internet, with contestants responsible for their own hardware and connection, and a single central server with limited bandwidth to equalize the advantages of fast connections or computers. But this is not a perfect world, and all of the entries in this contest will be timesharing the single CPU of the "arena" machine and communicating with the server via TCP/IP streams. (The "arena" machine is a POSIX-compliant single processor computer with enough RAM and swap space to accommodate all of the qualifying entries. It should comfortably handle two dozen simultaneous entries. In the event of an overwhelming turnout, the entries may be assigned to multiple identical arenas in a round-robin. Whatever it takes, the contest will be run in a timeshared virtual memory environment and all entries will communicate via TCP/IP with the server program running on a different computer.) The server will run on a different machine to prevent the server from stealing the contestants' cycles. Working sample code implementing the networking layer of your client program is provided.
The Stateful Wheels Protocol has two states: authentication and play. On connecting, the server issues a login request, which must be answered with a valid username:password string, followed by a newline.
In the play state, the server keeps track of the client's game, and only allows legal moves.
All lines are terminated with newlines, so that lines can be read using <SOCK> on both ends without changing $/. After the client has authenticated itself, the play state begins, with the initial stack of decks. Note that a client can have only one socket open at a time. If a client disconnects and reconnects, the game is preserved.
Play consists of instructions from the client to the server, each containing one or more commands. and the server's responses. Recognized commands include:
status: get the current status of your game
lay: shift four cards from the deck in hand to the piles
discard: when the four top cards match, get rid of them
NN: move a card from the top of one pile to the top of a lower numbered pile (N is one of 0,1,2,3)
NNNN: pick up all four piles and place them on the bottom of the deck.
win: after discarding all thirteen sets from a deck, start next deck
sync: a command matching /^sync\w+/ results in the command being returned to the client, to help with any data buffering problems that may occur.
close: close the socket, should you want to.
dump: print the game state--where all the cards are--into the server log, for client debugging.
To discourage fast, light, brute force clients that rely on the server's error codes for all their move selection, a maximum of one move-containing instruction for each client will be allowed during each second. Also, a one second pit stop will be required for each illegal move. An entry that issues "lay lay lay lay lay lay lay lay lay lay lay lay lay\n" for its first instruction, proceeds to solve the whole deck, and issues its solution in a single newline-terminated write to its socket will incur no delay at all, as the computation will surely take longer than one second.
Every server response will be either a status line (if your move is successful) or an error message (if it's not). The status line always begins OK, and then shows the four visible top cards, the time in seconds since the beginning of the game, what round we're on, what move we're on, how many sets are left in the deck in hand, and which deck we are using of all the decks in the current puzzle. (Decks start with thirteen sets, because there are 4 * 13 = 52 cards in a deck.) The following log excerpt is based on a test run of the "pace car"--a default client you can find on the TPJ web site--on a set of eight decks, after it had solved decks one, two, and three, and discarded three sets from deck four.
Server: OK 3h Js Kd Ks time 883 round 77 move 1271 3 sets left in deck 4 of 8 decks Client : 32 Server: OK 3h Js Ks 3c time 884 round 77 move 1272 3 sets left in deck 4 of 8 decks Client : 30 Server: OK 3c Js Ks 2h time 885 round 77 move 1273 3 sets left in deck 4 of 8 decks
The King of Spades in pile 3 was moved on top of the King of Diamonds in pile 2 with the NN instruction 32, revealing the Three of Clubs in pile 3 which could then be moved on top of the Three of Hearts in pile 0 with the NN instruction 30.
Client : lay Server: OK Kc Kh 4s 4c time 883 round 77 move 1273 2 sets left in deck 4 of 8 decks Client : 32 Server: OK Kc Kh 4c 2h time 884 round 77 move 1274 2 sets left in deck 4 of 8 decks Client : 21 Server: ERR cannot move 21
The King of Hearts is in pile 1, not pile 2.
Client : status Server: OK Kc Kh 4c 2h time 886 round 77 move 1274 2 sets left in deck 4 of 8 decks Client : 10 Server: OK Kh Js 4c 2h time 887 round 77 move 1275 2 sets left in deck 4 of 8 decks Client : lay Server: OK 8s 8h 8d 8c time 887 round 77 move 1275 1 sets left in deck 4 of 8 decks
All four Eights came out together, so they can be discarded. Multiple instructions can be given on the same line to save packets.
Client : discard lay Server: OK Kh Js 4c 2h time 887 round 77 move 1275 1 sets left in deck 4 of 8 decks Server: OK Ac As Ad 4d time 887 round 77 move 1275 0 sets left in deck 4 of 8 decks
Assuming we've really been doing our homework, we can issue a whole stream of instructions and they will be executed in order. To prevent deadlocks caused by miscounting the number of responses coming back, a sync command is provided.
Client : 21 10 32 10 3012 lay syncA Server: OK Ac Ad 4c 4d time 888 round 77 move 1276 0 sets left in deck 4 of 8 decks Server: OK Ad As 4c 4d time 888 round 77 move 1277 0 sets left in deck 4 of 8 decks Server: OK Ad As 4d 2h time 888 round 77 move 1278 0 sets left in deck 4 of 8 decks Server: OK As Js 4d 2h time 888 round 77 move 1279 0 sets left in deck 4 of 8 decks
Empty piles are represented with underscores.
Server: OK __ __ __ __ time 888 round 78 move 1279 9 sets left in deck 4 of 8 decks Server: OK Js 9c 9d 9s time 888 round 78 move 1279 9 sets left in deck 4 of 8 decks Server: OK, synching syncA client : blat Server: ERR what is "blat"? I know: status lay win discard NN NNNN sync... close client : win Server: ERR there are still cards in this deck
If you want to test your client, use the server at http://www.tipjar.com/games/solitaire/wheels/server. An accompanying card-shuffling utility is at /wheels/shuffle.
The server keeps whoami:password data in its invocation directory, in a file called passwd. You'll need to create this file to test your program--or, better yet, just comment out the password-checking code.
Entries must make use of the SWP_SERVERNAME, SWP_SERVERPORT, and SWP_PASSWORD environment variables (as demonstrated in the pace car client) to connect to the server.
Again, http://www.tpj.com/contest.html has the source code for the pace car, as does http://www.tipjar.com/games/solitaire/wheels. Its networking options are configured with environment variables containing the location of the server and the password to use on connection. The default is to communicate on localhost, port 5200, so that both server and client can run on the same machine for testing.
At the beginning of the race the server will be started with a fresh decks.dat file containing shuffled decks. "Gentlemen, start your sockets!" will be called out and the entry programs will be started on the arena machine and allowed to authenticate. The Connect() subroutine from the pace car, based on example clients in the perlipc documentation bundled with Perl, may be used in all entries. On race day the correct environment variables will be provided to the entries so that they can locate the server, connect, authenticate, and play the game.
Once the TCP connection is made, the Connect() function reads the server's greeting message, gives the server a username/password pair, and nips misconfiguration in the bud by dieing unless the server sends back a line beginning OK. If program flow returns from a call to Connect(), the dynamic socket handle SOCK is connected to the server and the race commences.
The pace car operates with almost no intelligence at all, dealing cards and then attempting all possible moves until none of them gets an OK response. When it has dealt the whole deck, which it knows about by checking $Count, it picks up the cards in a random order. It avoids endless loops by counting the number of rounds it has gone without discarding and skipping possible moves more and more often as the number of rounds without a discard increases. I have not proven that this method of loop avoidance always finishes, but it has completed all the decks I've dealt it so far.
The pace car could easily be improved upon and made into a viable contestant. Any move selection algorithm would be an improvement. The loop avoidance strategy could be revised. A second thread could be started to handle communications. Extensive advance planning could be done with virtual game states, heuristics, and breadth-first searches. An optimal mix of lexical and dynamic variables could be explored.
Please try to keep the disk space used by your entry under 50 megabytes. In case of disk space problems, entries growing beyond that ample limit (enough to store hundreds of thousands of game states without resorting to the Huffman tables discussed by Mark-Jason Dominus last issue) may be disqualified.
50 Trial laps. A sequence of fifty shuffled decks will be prepared and loaded into the server. The "pace car" will be started, and its time, number of moves, and number of rounds to complete all fifty decks will be measured. Each entry will then be measured similarly. The 24 entries with the lowest round count qualify for the race. If there are more than 72 entries, the best third will qualify.
Race. The server will be loaded with a sequence of 500 shuffled decks, and move and error delays will be enabled. Once all entrants have established their sockets, the server will begin normal operation. The winning entry will be the first to issue a legal win instruction on the last deck.
Prizes. Here is the list of prizes we know about at press time. More may follow, watch http://www.tipjar.com/ games/solitaire/wheels.html for the latest updates.
First prize: Two year subscription to TPJ, and $100.
Second prize: One year subscription to TPJ, and $50.
All qualifying entries: Perl Mongers T-shirts.
Honorable mentions will be awarded based on readability, elegance, creativity, attitude, or anything else deemed worthy.
Only one entry per entrant is allowed. Entries must be received before May 1, 1999. Entries written entirely in Perl may be submitted as plain text email. More complex entries can be (optionally gzipped) tar files, MIME-attached to mail sent to programmingcontest@tipjar.com.
Entries can also be submitted on 3.5 inch floppies (include your name and address on the label) and mailed to:
Wheels Contest
David Nicol
P.O. Box 45163
Kansas City MO 64171
USA
Your entry will be copied into a user directory on the arena machine. If you include an INSTALL script (say, to install any modules you might include with your entry), it will be run. Your entry must include a script called entry.pl that will be invoked via perl entry.pl for the trial lap and race. The SWP_SERVERNAME and SWP_PASSWORD environment variables will be set for your entry to use as in the example. Please include a README file listing any external utilities used by your entry so that links may be added if needed. The complete log of the race and time trials will be made available on the TPJ web site, including periodic runs of ps on the arena machine and the source code of all entries.
Entrants maintain copyright on their entries but grant TPJ the right to edit, annotate, and publish their attributed entries both on the Internet and in print, now and in the future. This contest is not open to any board members or employees of David Nicol Consulting or their immediate family.
__END__
When David Nicol isn't fighting crime in a spandex costume, he provides an Internet commerce resource for non-profit organizations, maintains part of the University of Missouri Kansas City computer network service infrastructure, and uses coffee to stomp out ennui. E-mail him at david@tipjar.com.