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.