Slash Boxes
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

Shlomi Fish (918)

Shlomi Fish
AOL IM: ShlomiFish (Add Buddy, Send Message)
Yahoo! ID: shlomif2 (Add User, Send Message)

I'm a hacker of Perl, C, Shell, and occasionally other languages. Perl is my favourite language by far. I'm a member of the Israeli Perl Mongers, and contribute to and advocate open-source technologies. Technorati Profile []

Journal of Shlomi Fish (918)

Thursday July 10, 2008
03:11 PM

Perl and Solitaire Games

[ #36892 ]

This entry will be a technical entry, but on a relatively lighter side: Solitaire games. Solitaire games (also known as "patience" games) are any of several kinds of single-player games played using one or more decks of cards. Despite common belief, the Windows-game called "Solitaire" is actually Klondike, which is only one variant of Solitaire. Freecell is another famous variant of Solitaire.

So anyway, I spent some of the past two weeks working on Games-Solitaire-Verify, which is a CPAN module to verify automated solutions of solitaire games. So far only Freecell is supported, but there's a lot of modularity in place for other variants. The intention of this module is to be used as part of the automated test suite of Freecell Solver, which is a solver for several variants of Solitaire, which lacks a comprehensive test suite.

I should note that I implemented the very first version of Freecell Solver in Perl, but it was horribly slow. Of course, I did some very illogical things speed-wise, like (1) putting all the states into an unsorted array and using linear search to scan it - and (2) constantly deserialising states into objects and data strcutures of individual cards, columns, and boards, and doing the comparison the hard way. So it was dog slow. I ended up re-implementing it as (saner) C code which turned out to be considerably faster than the Perl version. Moreover, my next C version was faster by a factor of about 100 (not because I was smarter, but I was less dumb), and since then I incorporated many other speed optimisations. (There are also several C and Assembly-hosted solvers that are much faster than mine.)

In any case, someone contacted me about the solver on Facebook, and after talking to him on Yahoo Messenger, we decided that he, I and another guy will talk on Freenode on the newly started #solitaire. There, I was quickly quickly joined by tybalt89, who is a master golfer, and who decided to write his own solver for Klondike in Perl. After a while he finished it and so I took a look at the source code.

From my impression it seems like the kind of code a golfer would write: strings instead of objects (with regular expressions and other text processing to manipulate them), a call to shuffle() from List::Util with a random seed, no use warnings, lots of obscure two-letter variable names, a lot of trailing "or" clauses, and it also has $hearts, $clubs, etc. instead of a hash. I talked about it with another master golfer and he said that "golfing rots the brain", and he said a program he gave as a solution to someone's problem had many golfish paradigms as well.

tybalt89 reported that his program is relatively fast, but still fails on many deals.

Meanwhile, I finished writing Games-Solitaire-Verify and released it on the CPAN. Then I decided to test if it could detect than invalid solution was indeed invalid. And it turned out an invalid solution was still reported as valid (!) making the reported verdict useless. What I found out was that the complete solution analysis silently stopped after the first move or two.

I fixed the bug and released a better version (with more tests). Then I decided to extract a few more classes (Games::Solitaire::Verify::Freecells and Games::Solitaire::Verify::Foundations) out of the relatively monolithic ::State class (which represents positions of the board, including those at midplay), and uploaded version 0.02.

I still need to adapt the module to verify solutions of other variants except Freecell, and that's what I'm planning to work on next. But it was good enough to add some system tests to Freecell Solver (using Perl, Test::More and TAP). What I hope is that tests such as this will allow me to revamp , refactor and enhance Freecell Solver with more confidence that I didn't break anything. I'm especially looking forward to the conversion from GNU Autoconf to CMake, which depends on the test suite to make sure it doesn't break anything.

Finally, I also found out that my C-based Freecell Solver program, did not always output things the right way, without trailing whitespace, etc. Since my primary motivation with Games-Solitaire-Verify was to verify the solutions of Freecell Solver, and because I wanted to compare to the precise output, I needed to emulate these mis-behaviours in my Perl code as well. I don't like it very much, but I guess I'd rather emulate Freecell Solver to test it, than fix it and risk breaking something. Nevertheless, my intention is to provide flags for a saner output for both the C and Perl programs in the future.

Happy Solitaire!

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
More | Login | Reply
Loading... please wait.