My next project for learning Haskell is Fox & Geese. This game has simple rules and mechanics, and it doesn’t need fancy graphics. It is pretty easy to implement a simple version quickly, so I can focus more on Haskell than details of the game. I’ll go over this in a series of posts. In part 1 I’ll talk about how I represent the game board in Haskell, and in later parts I’ll discuss input handling, drawing, and game mechanics.

But first, an overview of fox & geese. It’s similar to checkers, except that it is asymmetrical. The rules are pretty simple:

  • The pieces move along the lines on the board and sit on the intersections, which I’ll call “spaces” even though they should be called “points.”
  • There are only one or two foxes and fourteen to 24 geese (the variations balance the game differently)
  • The foxes can capture the geese by jumping like checkers, but the geese can’t capture the foxes
  • The geese can’t move backwards, but the foxes can move any direction
  • The geese win by occupying the nine spaces at the far side of the board or blocking the foxes so they can’t move
  • The foxes win by capturing enough geese that they can’t win.

Like most old games, there are a number of variations. Later we’ll add options that let the user customize the game to the variation he likes, but for now we’ll stick to two foxes and 24 geese.

And now, the program! It will help to get the source and follow along. The code is available on GitHub; this part will refer to tag v0.1.1. The source code is cabalized, so after you check it out you should be able to do cabal configure and cabal build to build it.

The Board

I decided to represent the board as a map from a position to a piece. Empty spaces on the board aren’t in the map. So, we need a type to represent our pieces in the map, and a type for the spaces.

import qualified Data.Map as Map

– A piece in the game
data Side = Fox | Goose
            deriving (Eq, Show)

– A space on the board, counting from the lower left.
type Position = (Int, Int)

type Board = Map.Map Position Side

I used a qualified import for Data.Map because it has names that conflict with Prelude.

It’s useful to know which spaces in our 7×7 grid actually exist on the board, so let’s make a list of valid positions. First I generate all the positions in a 7×7 grid, then I filter out the invalid ones.

validPositions = filter (not . invalid)
                        [(x, y) | x <- [0..6], y <- [0..6]]
    where invalid (x, y) = or [x < 2 && y < 2,
                               x > 4 && y < 2,
                               x < 2 && y > 4,
                               x > 4 && y > 4]

It’s also helpful to know which positions can be reached from any other position. I call this adjacentPositions, and it’s more complicated than it seems because of the odd board shape, and because diagonal movements are only allowed from certain spaces. First I generate all the possible movements1 with [(x, y) | x <- [-1..1], y <- [-1..1]], then filter out the movements that aren’t valid. The result is offsets in the next code snippet. Then I use those offsets to generate the possible adjacent positions and filter out those that are off the board.

adjacentPositions :: Position -> [Position]
adjacentPositions (px, py) =
    filter onBoard . map addOffset $ offsets
    where onBoard = (`elem` validPositions)
          offsets = filter adjacent [(x, y) | x <- [-1..1],
                                              y <- [-1..1]]
          adjacent delta@(dx, dy) = not (delta == (0, 0) ||
                                         (odd (px + py) &&
                                          dx /= 0 && dy /= 0))
          addOffset (dx, dy) = (px + dx, py + dy)

The Haskell books I’ve been reading call this using lists as non-deterministic values. The idea is that instead of finding one possible move, testing it, finding the next move, etc., we just put all the possible moves in a list and operate on them as one value. It’s something you can do in imperative languages, but functional programming, and especially lazy evaluation, makes it a lot easier to work this way.

Another thing we need to do with our board is find out who is where. If we try to see which piece is at a space on the board, we might get a piece or we might not. This looks like a job for Maybe! The map function lookup already gives us a Maybe value, so we’re good.

getPiece :: Position -> GameState -> Maybe Side
getPiece pos = Map.lookup pos . board

Don’t worry about GameState right now. It wraps together a bunch of stuff that we need for interacting with the game. All that’s important right now is the board, stored conveniently in record notation with the name board. So getPiece first gets the board from the GameState, then it tries to lookup the Position in the map. Maybe it finds a piece, maybe it finds bupkis.

We now have a working representation of a board for a game of fox and geese. We also know which positions on the board are valid, what movements we can make, and we can see what is on the board. In the next post, we’ll build the game mechanics that move pieces around the board.

As always, feel free to fork the project and fix all my glaring mistakes. Just be a dear and let me know about it in the comments.

What are some other ways that you might represent the board in Haskell? Leave a comment and let us know!

Next, learn how to move the pieces in part 2.

  1. You may notice that “all the possible movements” only includes movements to the next space. What about jumps? Patience, we’ll handle those later in game mechanics