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.