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.