## Sunday 6 December 2009

Following on from here I've made some progress on modelling the game of Klondike Solitaire in Haskell.

The code is really ugly and is definitely not idiomatic Haskell - if you can show me how to improve it then that would be much appreciated - it's the only way I'll learn!

There are several concepts in the game of Solitaire. There are:

• Tableau - A set of seven stacks of cards. Cards can be transferred between each stack as long according to some rules.
• Foundation - The foundation consists of four bases, each representing one suit of cards. The game finishes when all the cards have been placed in order (from Ace to King) onto the foundation.
• Deck - The cards not in the foundation or the tableau are in the deck.

Each item in the tableau has a number of shown cards and some hidden cards.

`  data Slot = Slot       {        shown :: [Card]       , hidden :: [Card]       }deriving (Show,Eq)  data Tableau = Tableau [Slot] deriving (Show)`

One problem I had was that I wanted to represent a Tableau as being exactly 7 slots. I could do this with a tuple, but then my 7 element tuple would need lots of special functions instead of just using the list functions. There are packages for fixed size lists, but I wanted to try and do something minimal.

Foundations are simpler to model. A foundation consists of four bases.

`  data Base = Base Suit [Card] deriving (Eq,Show)  data Foundation = Foundation Base Base Base Base                    deriving (Show)`

I think I'm missing something - how can I change the definition of Foundation so that each base is represented by a different suit?

Finally, a `Game` consists of all of the elements described above.

`  data Game = Game       {        deck :: [Card]      , foundation :: Foundation      , tableau :: Tableau      } deriving (Show)`

In order to make progress in a `Game`, a series of Move's must be made. The possible moves are enumerated below:

`  data Move = TurnDeck            | ToFoundation Slot             | DeckTo Slot            | DeckUp            | MoveCards Slot Int Slot             | MoveCard Slot Slot            | GameOver              deriving (Show,Eq)`

Once the basic data structures are in place (even if they can surely be improved), it's simple to sketch out the remaining functions.

`  -- Make a move  move :: Game -> Move -> Game  -- Enumerate all the possible moves from the given game state  getMoves :: Game -> [Move]  -- Play a game using the given playing function and return the list of moves  playGame :: Game -> (Game -> [Move] -> Move) -> [Move]  -- Replay the list of moves  replayMoves :: Game -> [Move] -> Game  replayMoves = foldl move`

My goal will be to write a function that picks the best move from the given choices of type `Game -> [Move] -> Move` and see how many games it solves. If any!

Before I go much further though, I need to spend some time working out how much more of the logic I can force inside the type system. For example, currently `Foundation` allows bases of the same suit; they should be different. Similarly, `Tableau` is just a list of slots. I know that if I just use `map` on this list to transform it, the list stays the same size, but it's not enforced by the type system (for example, I could use `concatMap` and change the size). Can I define that shown cards must always be lists of cards in alternating colours and successive values?

There's some more code on my git hub repository.