The Solitaire 500
listing: the "pace car" client
The Perl Journal article proof
The Wheels demonstration GUI
"Know when to forgo an advantage" -- Benjamin Disraeli
Strap yourself into your program's cockpit. "Gentlemen, start your sockets!" booms 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, following arbitrary but well defined rules, to organize and discard five hundred shuffled standard decks of cards.
Speed matters. A glance into any of the programming language usenet newsgroups reveals innumerable examples of arguments over fine points of programming style seemingly authoritatively settled when someone benchmarks example code using both approaches. There is a lot of interest in speed, but execution speed is rarely made a criterion in programming contests beyond administrative requirements that the program must complete running in a "reasonable" period. Bucking the hardware-industry-inspired trend against fast software, the Solitaire 500 is a race. Entries qualified by having trial runs top ten percent (assuming there are 250 or more entries) compete against each other to find which finishes an identical series of puzzles, while timesharing a single computer, first.
The Puzzle: 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 with a deck of cards, lay four cards from the top of the deck face up on a table, left to right. 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. you can see a deuce, a king and two sevens) the card to the right may be moved to cover the matching card to its left (e.g. you may move the seven from pile 3 on top of the seven on pile 2.) 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.
When all four freshly dealt cards match in rank, they are moved to the discard pile where they remain. When the entire (undiscarded) deck is dealt into the game piles and the last moves made, the game piles are stacked together, flipped over, and another round begins. The order in which the piles are restacked is up to the player. Wheels has two opportunities for player decisions: grouping or not grouping like visible cards, and stacking order.
Discarding, rare in the first few rounds, happens increasingly 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 get discarded, and endless loops can always be broken by a combination of choosing not to make legal moves and 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, one invariably experiences a sense that had one left just one more card in pile three last round several sets would have been discarded this round, when there are groups of four cards which fail to get dealt in the same lay, instead spanning two subsequent lays, perhaps getting severely separated. D'oh!
Clients and servers:
Unlike the "Stones" contest from TPJ #7, when entries were subroutines which were called by a larger program which managed 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 in, or possibly hold the contest over the internet with contestants responsible for their own hardware and connection, with the single central server connected via a limited-bandwidth connection to equalize the advantages of high-speed internet connections. We could issue each contestant a username/password pair and announce when the server will turn on, and at what IP address, and the first to win by any means would be the winner. This is not a perfect world. All of the entries in this contest will be timesharing the single CPU of the "arena" machine and communicating with the server program via TCP/IP streams. The server will run on a different machine to keep the server from taking any of the contestants' time slices. TCP/IP can also be used within the same computer allowing the client and server to both run on one machine for testing. Working example code implementing the networking layer of your client program is provided.
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 newline.
In the play state, the server keeps track of the client's game state, and only allows legal moves.
All lines are terminated with newline, so that lines may be read using <SOCK> on both ends without changing $/. After the client has authenticated into a unique session -- a client may have only one socket open at a time -- the play state begins, with the initial stack of decks, or on reconnection, the same game state the client had when it was last connected.
Play consists of instructions from the client to the server, each containing one or more commands. and the server's responses. Recognized commands include:
Server responses are a status line for all successful moves, or an error message. The status line always begins OK, then the four visible top cards are shown, then the time in seconds since the beginning of the game, then 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 in of all the decks in the current puzzle. Each deck starts with thirteen sets in it. The following log excerpt is based on a test run of the pace car on a set of eight decks, after it had won 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 get executed in the order they are given. To prevent deadlocks caused by miscounting the number of responses coming back, a sync\w* 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
The server implementation follows the above described protocol. The multithreaded server available at http://www.tipjar.com/games/solitaire/wheels/server and its accompanying card-shuffling utility may be used for testing and debugging your SWP client. Its offspring will be the server used in the contest.
The server keeps whoami:password data in its invocation directory, in a file called passwd. You'll need to create this file to use the server for testing 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 successfully connect to the server. These variables will be provided in the .bashrc file for each entrant.
Accompanying this text there is a working example client, the "pace car." Configuration of the client 's networking options is done 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 the server and your entry may both run on the same machine for testing, and no code modifications will be required to connect to the game server, on a different machine, on race day.
At the beginning of the race the server, with a fresh decks.dat file, will be started on the server box. "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 found in the perlipc perl documentation, may be used in all entries. The hostname, if not provided in an environment variable, defaults to localhost to allow testing to take place on a single machine. 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 game playing 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 the $Count variable, it picks up the cards in a random order. It avoids endless loops by counting the number of rounds it has gone without discarding any cards and skipping the opportunity to make moves more and more often as the number of rounds without a discard increases. I have not proven that this method of loop avoidance will work in all cases with mathematical rigor, but it has managed to deal with all the decks I've dealt it so far. If the brute force solver cannot handle the race day 500, the 500 will be reshuffled.
The pace car could easily be improved, in many ways. The loop avoidance strategy could be revised, any move selection algorithm would be an improvement, a second thread could be started to handle communications and 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 disk space used by your entry, including source code and temporary data files if any, 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 Huffman tables ) may be disqualified.
Tying up system resources in ways that do not advance your entry's analysis of the game state, for example spawning multiple busy-waiting processes, may be deemed "unsportsmanlike conduct" and considered grounds for disqualification. There are ample blocking constructs (Lock, Flock, Thread::Queue::dequeue, and so on) available for both interthread and interprocess synchronization. If we run out of process table space, the entry using the most, based on ps Sau being run periodically throughout the race, 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 on arena and its time, number of moves, and number of rounds to complete all fifty decks will be noted. Each entry in turn will be started and their time, number of moves to complete all fifty decks, and number of rounds to complete all fifty decks will be noted. Entries that appear to be stuck in endless loops will have their source code examined, and stuck entries without obvious or explicitly marked loopbreaking strategies may be disqualified before timing out.
Race: The server will be loaded with a sequence of 500 shuffled decks and move and error delays enabled. The twenty-four (or best ten percent if there are more than 250 entries) entries which completed the trial laps with the lowest round count will all be started and allowed to establish their game sockets. 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, according to the server's log.
Prizes: Here is the list of prizes we know about at publication time. More may follow, watch this page for the latest updates.
Only one entry per entrant is allowed. Entries must be received by May 1, 1999. Entries written entirely in Perl may be plain text e-mails. More complex entries may be tar files, gnuzipped tar files, MIME-attached to e-mails to email@example.com
(or ftp uploaded to ....tpj.com ?)
or copied onto 3.5 inch floppy disks and mailed toWheels Contest David Nicol post office box 45163 Kansas City MO 64171 United States of America
Please include your name and the format the disk is in (FAT, tar file, zip file, ext2) on the disk label.
Your entry will be copied or untarred into a user directory created for you on the arena machine. An INSTALL script, should one be included, will be run under your UID, to install any modules (CPAN or custom) you may include with your entry. Your entry must include a script called "entry.pl" which will be invoked "perl entry.pl" at the beginning of the time trial and also the 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 detailing any unix utilities used by your entry, if any, so that links may be added if your system puts them in different places than they are found on the arena. Time permitting, attempts will be made to give entrants a chance to repair install problems, but the contest administrator is not going to debug entries, and no entries or revisions will be accepted after the end of April, 1999.
Nor will any information about any of the entries be revealed before May, 1999.
The complete log of the race and time trials will be made available, including periodic runs of ps Sau on the arena machine, along with the source code of all entries, on the tpj.com ftp site, after the contest.
Legal: Entrants maintain copyright on their entries but grant The Perl Journal the right to edit, annotate and publish their properly 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.
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 firstname.lastname@example.org.
1. The target "arena" machine is a very slightly overclocked P54 with 64 megabytes of memory and 80 megabytes of swap space, running Linux 2.0.36 and a perl with support for posix threads compiled in. I believe that it should be able to comfortably handle two dozen simultaneously running entries, with all making reasonable progress, with regular hits on the swap disk. If I am unable to get the top twenty-four/ten percent of entries to all run at the same time, more swap space will be added, more memory will be obtained or the contest will be moved to an entirely different Posix-compliant machine. Whatever it takes, the contest will be run in a timeshared virtual memory environment with some swap use occuring and all entries will communicate via TCP/IP with the server program running on a different computer.
2. decks.dat is the file containing the shuffled card decks the server is using. Http://www.tipjar.com/games/solitaire/wheels/server and http://www.tipjar.com/games/solitaire/wheels/shuffle are the server program and the tool used to generate decks.dat.
3. Dominus, Mark-Jason, "Bricolage: Data Compression," The Perl Journal, Volume 3, Issue 4 (#12), Winter 1998, pp32-35
4. ps is unix for "process show." The
command line options Sau will show username for all
non-daemon processes, with CPU time displayed as the sum
of the time used by a given process and its child processes. This listing
from the arena will be coerced into the server's log files by adding a
line to arena's /etc/inetd.conf file:
5201 stream tcp nowait root /bin/ps /bin/ps Sau
and adding a thread to the server to periodically connect to the arena's port 5201 and log most of what gets sent back.