Sunday 6 December 2009

Modelling Klondike in Haskell

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.