HSS: A Search for Equality

Just a few minor updates to the Haskell Spider Solitare code.

In preparation for implementing a Zipper and Travel B Tree we need a way of detecting repeated game positions. The Travel B Tree we use will be almost the same, except that each interior node will also have a data value as well, just the leaves.

I talk about the move tree for a given game being finite... but that is
not strictly correct. If you have a Jack, and there are two exposed Queens on the board, you can move the Jack back and forth between the two forever. So we're just going to look at the history and see if we're duplicating a position

There are also a few other little cleanups in the code.

HSS: Generating moves

I've added some functions to generate all possible moves at a given board position for Haskell Spider Solitare (link to source code at right as usual). Here's the relavant bits:

--
-- generate list of all cards that could possibly be moved
--
movable []     _   _   = []
movable (x:xs) col row = if (c_cluster x) == 0
                      then cur_nsm  : movable xs col (row + 1)
                      else []
   where
       cur_nsm = Normal_Spider_Move (Tableau_Location col row)
                                    (-1) -- not valid yet.
                                    Nothing
                                    (row + 1)

all_movable sg = am_helper (tableau sg) 0
   where
       am_helper []   _   = []
       am_helper (x:xs) col = (movable x col 0) ++ am_helper xs (col + 1)

--
-- see where they can move to
--
where_plays sg nsm = wp_helper nsm (tableau sg) 0
   where
       wp_helper _ [] _ = []
       wp_helper nsm@(Normal_Spider_Move from to _ _)
                 (cur_col:rest_cols)
                 colnum =
           (if ((t_col from) == colnum) ||
               (length cur_col) > 0 &&
               not (plays_on_match (from_card sg nsm) (head cur_col))
                   then []
                   else [nsm{sm_to = colnum}] ) ++ rest
               where
                   rest = wp_helper nsm rest_cols (colnum + 1)

where_plays_all nsm_list sg =
       foldr (++) [] (map (where_plays sg) nsm_list)

Comments: I need to settle down with the indentation, and pick either 4 or 8 and stick with it. I am at least trying to stick with 80 columns, which makes blog posting easier too.

I'm not complely happy with the tableau data structure, which is just a list of lists of cards. See how I'm threading through the column number in movable and where_plays? I suppose I could replace that with something like: '9 - (length xs)', but that bothers me a little bit too. The whole integer indexes into lists bothered me a bit with the Common Lisp version too. Not that I'd know how I could change it.

As always, any comments on style, or suggestions to make the code shorter and more clear are welcome.

Next task is to decide how to represent the entire tree of moves. I've just downloaded Purely Functional Data Structures[PDF] by Chris Okasaki, but I haven't dug into that yet. We will want to be able to move up and down through the tree easily.

HSS: 1.1 release

The 1.1 release of Haskell Spider Solitaire has been posted to the usual location (check the links to the right).

The major change is switching the representation of the tableau. All the manipulation of the tableau occurs at the bottom of the board as the human player sees it. Previously, the data representation matched the screen presentation, and that meant manipulating the tails of each column (which are just lists). Following a suggestion by chessguy (thanks, if you're reading this) that has been reversed. So the bottom of each column as seen by the users is at the head of each column list.

So the display of the board is slightly more complicated, but the internal mechanics of moving cards is simpler, and some helper functions have been eliminated.

So the next task is to start exploring the move tree for a particular game. As part of that, I think we'll want to somehow create a hashtable for each board position encountered so far during a game. to prevent repeated positions. I suppose I could assign a number to each unique card, flatten the tableau and stock, and calcuate a hash based on that.

While there are something on the order of 108! divided by 2^56 possible starting positions, and approximately that many possible board positions, you can only see a small fraction of those starting from a particular board position. I also don't know just how big a move tree is for a typical game either. A winning game can easily run 500 moves deep. And it is common to have 3 or 4 possible moves from a given position. But there are a lot of very quick dead-ends, and the deepest games are the winning ones... of which there may only be a low number of total solutions, and a low number of paths to each solution.

I'm sure a mathematician could give accurate answers to at least some of these questions. Since I am not one, I'll turn to empiricism instead. This is where we generate thousands of games, and collect statistics.

Moving to Mercurial

There's been a lot of discussion about version control lately, and here's my little contribution to it.

I've selected Mercurial for the DVCS at work, and that's what I'll be using for my personal projects too. Mostly because I'm not going to learn darcs as well.

The other finalist was git. I was recently watching that Google Talk video featuring Linus Torvalds, and he made a lot of good points (even if you don't like him calling people and entire projects stupid).

We were going to move to Subversion, just because it is the 'better CVS', but we haven't actually started implementing it yet. We aren't really pushing the limits of even CVS yet at work, but we'll be working on some much larger SW projects soon, so now's the time to switch.

For the record, here's what swayed me for Mercurial: cross-platform support (runs on Windows), Trac integration, and written in Python (which will be used for a bunch of our other development tools). By most accounts, it is as fast as git, and doesn't have some of odd corner-case behavior of darcs (which will hopefully be fixed soon).

I have run into one problem with Mercurial already. If you store a repository on a FAT filesystem (my flash drive), it apparently isn't compatible between Windows and Linux. :-(

HSS: 1.0 Release

The source for the latest version of the Haskell Spider Solitaire game is available for download to the right, as usual.

There was quite a bit of re-factoring this time, trying to find a good home for all the different functions.

There is also complete move validation now, and that all works correctly... I think. Fixed some bugs with foundation moves. Other improvements include being able to actually win the interactive game. And no, you don't get fireworks, though I suppose I could call that old BSD /usr/games program that does something similar.

So anyway, since it basically works, let's call it release 1.0.

Next major task is to be able to enumerate all the possible moves from an existing board position. Then we can start experimenting with a tree search to exhaustively try to solve a game. After that, scoring a particular board position... which is going to be a bit difficult.

Misc TODO: Get started on QuickCheck.

HSS: quick update, and interesting papers

Haven't done too much with Spider Solitare in Haskell lately. Added a help command and some other little nicities. Still need to finish the input and move validation.

Been reading the Comparing Approaches to Generic Programming in Haskell which has been interesting.

Also, in a Reddit topic about Chicken Scheme I discuss why I've settled on using Python for the majority of our development projects at my company. Even though I think Haskell is the bee's knees as far as expressiveness and concicseness goes.

HSS: Now barely useable!

We (by we I mean me) are getting close to a 1.0 release for Spider Haskell. Download the source code at the right, as usual.

Mostly just been working on the UI for playing a game on the console. There's barely any input validation. And there's no checking to see if a move is valid at all. So if you want to play, it is on the honor system.

But, all the basics are there, if not completely tested. Undo was easy to implement, because we keep a list of all the previous game states. This was actually one of the stumbling blocks of the original CL version. Because that version was doing in-place modifications, it was a lot of work to implement the undo. We would look at the move history, and manually reverse it. So we had to do things like also keep track of any cards that were revealed by the move.

The two codebases are now roughly the same size. However, there is some duplicated code in the CL version (was starting to re-organize the project before working on it), so that doesn't mean anything.

To do: Do full command validation (don't want a String to Int conversion to blow up), and move validation. And maybe a little in-game help.

And after that, we can start trying to solve Spider Solitare, once and for all. :-)

HSS: Move Validity

More code for the Spider Solitaire game in Haskell, download link at the right as usual.

I haven't made a whole lot of progress, but I'm slowly churning through the functionality that was implemented in the Common Lisp version.

Included with the current version is the calculation of 'card clusters' as I call them. Here's the important bits of that:

-- card clusters
--
-- A cluster is a set of cards which may be moved at once.  Like an 3, 2, 1
-- of clubs, for example.
--
-- In a column of the tableau, clusters are marked from 0 at the bottom
-- on up.  So it is only valid to move cluster 0.  But we keep track of the
-- other clusters in the column for strategic purposes.

compute_cluster :: [Card] -> [Int]
compute_cluster [] = []
compute_cluster xs = reverse $ rv_cards (reverse xs) 0
    where
        rv_cards [] _ = []
        rv_cards [x] y = [y]
        rv_cards (x1:x2:xs) y = y : (rv_cards (x2:xs) new_y)
            where
                new_y = if (plays_on_match x1 x2)
                            then y
                            else y + 1

-- True if c1 plays on c2, False otherwise
plays_on_match Card -> Card -> Bool
plays_on_match c1 c2 =
    case (plays_on c1) of
        Just x -> x == (c_value c2) && (c_suit c1) == (c_suit c2)
        Nothing -> False

I've a bit of a dilemma as far as where to store data. In the CL version, what cluster a particular card was in card data structure itself. I'm debating if this is a good idea or not.

So say we've just made a move, so we're creating a new instance of the Spider_Game data structure, which will have the modified column(s). Do we compute the new columns, and then create a new version of them with the clusters properly filled in? Seems a bit inefficient.

And why exactly am I worried about efficiency at this point? Isn't premature optimization one of the great sins of a programmer?

Side note, I realize there are issues with the layout of the site, and it doesn't work so hot when your pre-formatted text is 80 columns wide, and the blog itself only wants me to post 60-column wide text. I'll need to fix that.

Edit: Trying out this really simple template, which allows wider columns for the blog post itself.

HSS: Pretty Printing and some Moves

More code written supporting the pretty-printing of the playing board. Download link on the sidebar.

Also started implementing some of the moves available. Here's the structure for that:

data Tableau_Location = Tableau_Location { t_col :: Int, t_row :: Int }
    deriving Show

data Spider_Move =
        Regular_Spider_Move {
            sm_from     :: Tableau_Location,
            sm_to       :: Tableau_Location,
            sm_revealed :: Maybe Tableau_Location,  -- Card revealed, by
                                                    -- the move, if any.
            sm_count    :: Int -- number of cards moved
            }
            |
        To_Foundation_Move {
            sm_from     :: Tableau_Location,
            sm_revealed :: Maybe Tableau_Location   -- Card revealed, by
                                                    -- the move, if any.
            }
            |
        Deal_From_Talon
    deriving Show

I'd like to think of a better way to represent the move locations other than integers. Not that it can't be made to work, but using integers seems a little clunky with lists. I'm thinking of changing the tableau to be an array of lists instead.

I haven't actually written the code yet to do the regular game moves, but I can tell it is also going to be a bit clunky.

I should come clean here a little bit... There was a previous version of all this that I wrote in Common Lisp. I only got so far as allowing a human to play the game, there was no solving or AI implemented.

So in part, I've been just re-writing that CL version in Haskell.

However, part of the problem I ran into with that version is that I would have had to do major re-work in order to start implementing the AI. The CL version was written in a very imperative style, and I didn't keep around the old board after making a move. That made writing the undo logic a bit interesting, but I got that working OK.

So anyway, we'll need to keep a more functional style anyway. We're going to have a massive tree of possible moves to keep track of, because there are usually a few possible moves for a given position. The trick, of course, is pruning the branches that will be unproductive.

I think, if I'm doing things right, however, that we'll not be duplicating the card structures except for the ones we're modifying (turning face up, for example). And in a normal spider move, 8 of the 10 columns won't change, so that'll save some memory too.

HSS: James vs. the IO monad

Link to the source in the sidebar.

Primarily added functions to deal out the cards into the game structure. At times it has been a real struggle to think in the FP style. I've written a lot of C in my day, so it is hard for me to give up imperative programming. Sometimes I just want a loop, but instead I'm trying to force myself to use things like recursion instead.

For instance, it took me a little while to understand why I had to do use liftM here:

new_spider_game :: IO ()
new_spider_game = do
        sd <- return shuffled_deck
        nsg <- liftM deal_spider_game sd
        putStrLn $ show nsg

It is also taking me a while to wrap my brain around the idea that once stuff is in the IO monad, it can't escape again (become pure). At some level I've known this for a long time (shortly after reading about Haskell) but my "fingers" (who actually do the implementation) haven't quite accepted that yet.

At any rate, I'm also not sure why I need the 2nd pattern (with the empty list as the 4th argument) for chunk_it:

-- Break up the list into chunks, returning a list of lists
-- and the remainder, if any.
chunk_it :: Int -> Int -> [[a]] -> [a] -> ([[a]], [a])
chunk_it _    0                collect ys = (collect, ys)
chunk_it _    _                collect [] = (collect, [])
chunk_it size (next_count + 1) collect ys =
        chunk_it size next_count (nextchunk : collect) remainder
    where
        (nextchunk, remainder) = splitAt size ys

Theoretically, with the last call to chunk_it will be 0, and so it should end right there. However, I end up with an additional empty list at the head of the talon. Here's how it is called:

deal_spider_game deck =
        Spider_Game tableau talon [] []
    where
        (tableau1, rem1) = chunk_it 7 4 [] deck
        (tableau2, rem2) = chunk_it 6 6 [] rem1
        tableau = map flip_last (tableau1 ++ tableau2)
        (talon, _) = chunk_it 10 5 [] rem2

Oh well, I'll figure it out eventually. Next I need to figure out some clean way to mark the cards that should be face-down as they are being dealt.

Edit: Nevermind, there's the new version deal_spider_game with the last card flipped. Wasn't a big deal... if you've got the right perspective. Originally had modified chunk_it, but that wasn't elegant. Actually, I'm going to modify chunk_it, and get rid of the extra null list argument. Make that a helper function for the real chunk_it.

Haskell Spider Solitare: First Code Drop

OK, here's the first code drop for the spider solitaire implementation in Haskell. Download the zip file here:

http://home.xnet.com/~ansible/haskell/spider_haskell.zip

The code doesn't do much of anything yet, this is mostly setting up some of the data structures, and being able to shuffle the cards. I've started on creating some assertions that can be checked during game play, and that will get more sophisticated over time.

However, there may be better ways to do some of that, and I'm open to suggestions. Like, for example, taking better advantage of the type system.

It would be cool if there was some way to say that this particular kind of list will only ever have ten elements, for example.

Lastly, the moves and move history are just represented as Ints of the row and column. If there's a cleaner way to do that, I'm all ears there too.

Edit: I just tried the code on GHCi v6.4.2 and it doesn't work, not sure why exactly. Was initially developed using GHC 6.6.

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.

Initial Posting

Welcome to my blog.

This blog will mostly cover my exporations in programming. Mostly I am interested in Haskell and E along with object-capability security in general.

Haskell is by far the most beautiful and elegant language I've yet looked at. And I've looked at over 100 in the past 20 years.

The ideas underlying object-capability security are very important, and I want to study the implications of that much further.

I'll also post on other non-programming topics that interest me too. Currently I've been reading a lot about energy issues: oil prices and Peak Oil, alternative energy for homes and transportation, and solar power in general. There's a lot of interesting things happening there.

The name for the blog refers to partial application of functions, which is a fundamental part of functional programming. It is also a homage to my friend Michael Kimmit's blog (when it was running) called A Partially Examined Life.