Solitaire 500 Results

David Nicol

On May 1, 1999, an air-conditioned room deep within the University of Missouri Kansas City's Computing Services department was transformed for a brief eight hours into the mission control center for what may very well have been the first ever programming contest of its kind: the Solitaire 500, described in TPJ #13

As you might recall, all programs entered in the Solitaire 500 ran simultaneously on the same computer. They had to make network connections to a server running on a different computer and solve an identical series of five hundred problems presented by the server. The first to complete the series of problems won

Nineteen entries reached the contest's e-mail inbox before the morning of May first.

ID		Name
1		Theo Van Dinter
2		Joseph A. Diverdi
3		Steven W. McDougall
4		Eero Pajarre
5		Mark Kvale
6		Dave Shield
7		Andreas Gross
8		James P. Williams
9		David Brandt
10		Stephen M. Moraco
11		John Whitmore
12		Edward M. Perry
13		Jack Applin
14		Robert Au
15		Ira Joseph Woodhead
16		Erle Schuyler
17		Yanick Champoux
18		Jeff Norden
19		Peter J. Jones

Seventeen qualified for the competition.

The winner was #4, Eero Pajarre's entry, which averaged only 9.7 rounds per deck in the qualifying trial and earned Eero $100 plus a two year extension on his TPJ subscription. His entry re-optimized for speed in the main contest, and won with an average time per deck of slightly more than three seconds. Developing with precompiled binaries of ActiveState Perl and GNU Emacs under Microsoft Windows 95, Pajarre optimized pickup order for most discards available next round with the help of a precompiled table of eight and twelve card situations. Then with the help of the Benchmark module, he realized that switching to string representations would save time

His canonic() subroutine converts decks represented as strings of card rank letters into patterns for the pre-solved table:

sub canonic ($) {
  my ($d)   = @_;
  my ($res) = "";
  my ($ind) = "";
  my ($c, $i);

  for ($i = 0; $i < length($d); $i++){
      $c="substr($d," $i, 1);
      if ( 0 > index($ind,$c) ) {
          $ind .= $c;
      }
      $res .= chr( ord('0') + index($ind, $c) );
      }

  return $res;
}

Steven W. McDougall's entry #3, a completely commentless six page program that nevertheless reads like a chess match, came in second, taking the $50 prize and a one-year extension to TPJ. By using arrays and array references for his internal representations, McDougall's program was able to generate workable long solutions faster than the next four finishers could generate short solutions. His Partition() subroutine uses bitmasks to determine if the lengths of arrays are divisible by four, to quickly choose good restack orders.

sub Partition {
   my ($stacks, $block4) = @_;
   my $s1 = scalar @{$Tab[$stacks->[1]]};
   my $s2 = scalar @{$Tab[$stacks->[2]]};
   my $s3 = scalar @{$Tab[$stacks->[3]]};
   $block4               & 3 or return @$stacks;
   ($block4 + $s1)       & 3 or return @$stacks[1, 0, 2, 3];
   ($block4 + $s2)       & 3 or return @$stacks[2, 0, 1, 3];
   ($block4 + $s1 + $s2) & 3 or return @$stacks[1, 2, 0, 3];
   ($block4 + $s3)       & 3 or return @$stacks[3, 0, 1, 2];
   ($block4 + $s1 + $s3) & 3 or return @$stacks[1, 3, 0, 2];
   ($block4 + $s2 + $s3) & 3 or return @$stacks[2, 3, 0, 1];
   ($block4 + $s1 + $s2 + $s3) 
                         & 3 or return @$stacks[1, 2, 3, 0];
}

The Wheels game is based on a game of solitaire known as "Perpetual Motion", and some years ago, McDougall wrote a C program to play Perpetual Motion with an animated display of the game state. His second place client was based on this earlier work.

After debugging the loop avoidance strategy, McDougall's program solves approximately eighteen decks per second on his 266 MHz Pentium II PC/NT.

With an algorithm that appeared to win every hand, McDougall focused on minimizing the socket I/O by tacking the instruction to receive the next deck onto the tail of the instruction to win the current deck. At that point his program could process about three hands per second in concert with the demonstration server program.

Jim Williams's third place Expert.pm, #8, was the only entry to have more than one file of program code, and was also the only entry to have full pod documentation. After he settled on an algorithm, Williams made extensive use of the Benchmark and Devel::DProf modules to guide his creation, inlining several pieces of code that had been separate subroutines. His %permutations hash, a hash of arrays of arrays (a HoLoL) to hold the dealt cards, allowed him to quickly construct the decks so as to choose one that would provide at least one discard the following round. Using "early pickups" to prevent missed discards, Williams's entry has the second lowest total number of moves in the contest, after Norden's #18.

Honorable Mentions: Dave Shield's #6 entry made extensive use of regular expressions. Mark Kvale's #5, the winner of the qualifying round, used a two-ply search with an external database of twelve-card situations. Kvale's Simulate() subroutine provides the same functionality as Williams's array-reference based @{$Permutations{$piles}} with this verbose slice:

# create the deck after pickup
@order = split //, $perm;
@deck = ( @{$pile[$order[0]]},
          @{$pile[$order[1]]},
          @{$pile[$order[2]]},
          @{$pile[$order[3]]} );

Jeff Norden's "RACE CAR" (#18), also using a full two-ply heuristic search, achieved the best round count of the contest. However, Norden spent more CPU time than any other entry:

foreach $order (@Pickups) {
  @deck = map ( @{$_,
          @stack[@$pickup_list{$order}]} );
  play_and_score();
}

Theo Van Dinter's #1 entry was the last of the entries that supplied multiple move commands at a time.

From Ira Joseph Woodhead (#15), we learned that $ENV{'USER'} is a more portable construction than 'whoami', and from Stephen M. Moraco (#10) we see the advantage of BEGIN { $Exporter::Verbose = 1; } as a package debugging technique.

Joseph A. DiVerdi (#2) used heuristic search to achieve the second-best move count, but his subroutine sent frequent instructions and therefore used a lot of time waiting for the server to respond.

One entry froze, and a spelling error prevented another entry from qualifying. The other seventeen entries successfully completed the qualifying round, earning their creators Perl Mongers T-shirts. The competition results:

> grep 'OK FI' competition_log

This is the final ps listing before Eero finished, having used the least CPU time of all the entries.

Sat May 1 21:25:00 CDT 1999

__END__

David Nicol (gratuitoushyphens@tipjar.com) no longer wonders what grading papers at the end of the semester must be like.