Sunday, March 18, 2007

Spider Solitaire, Intro

I'll be using spider solitaire as an extended introduction to Haskell programming. I'll ought to post a link to the rules, but you can just pull up an implementation in your favorite OS, and give it a try. In this and subsequent posts, I'll only be discussing the 'hard' version, with all four card suites, because that's the most interesting.

From what I've seen so far, there is no knowledge of some of the fundamental aspects of spider solitaire. It is much less well-studied than chess, go, or such.

What percentage of games (from a randomly dealt deck) are winnable? Not all of them are, even with perfect knowledge of the initial board and reserve pile (talon). What are the tactics that can be used in different situations? What strategies are available? Which ones are best?

I've had winning games run into the 500-move range. So I don't think spider solitaire is easily amenable to pure mathematical analysis. Our other option is empiricism.

Initially, we'll be working on just a basic, text-only version of the game, to get the fundamental playing rules implemented.

Maybe next we'll create a (smart) depth-first search of possible games, and see what percentage are actually winnable.

Then we'll start trying to create some medium term goals for various strategies, such as clearing an entire column on the board. Along the way we'll implement some tactical moves, and deal with imperfect knowledge (i.e. playing the game like a human would).

And of course, source code will be available, since this might make a good introduction to functional programming and Haskell.

No comments: