Conrad Barski’s Land of Lisp develops a simple
board game from chapter 15 onwards, as an example of using
functional-style programming in Common Lisp. The game, Dice of Doom, uses a
hexagonally-tiled board where two or more players occupy various cells on the board
and can attack each other subject to some rules.
In this series we’ll rewrite the game using Haskell.
The source code for this can be found on Github: Dice of Doom
The Original Lisp Game
The source code for the Lisp version can be
Alternatively use dice_of_doom_v1.lisp that accompanies this source.
Download this file.
To run it you’ll need a working CLisp
or SBCL environment. We’ll use CLisp to test the run:
(Note: to quit during play, press CTRL-C and then (quit) at the CLisp prompt.)
The above 3x3 board looks like this:
The rules of the game are as follows:
Two players (named A and B) occupy spaces on a hexagonal grid. Each
hexagon in the grid will have some six-sided dice on it, owned by the
During a turn, a player can perform any number of moves, but must
perform at least one move. If the player cannot move, the game ends.
A move consists of attacking a neighboring hexagon owned by the
opponent. The player must have more dice in her hexagon than the
neighboring hexagon in order to attack. For now, all attacks will automatically
lead to a win. In future variants, we’ll actually roll the dice for a
battle. But for now, the player with more dice just wins automatically.
After winning a battle, the losing player’s dice are removed from the
board, and all but one of the winning player’s dice are moved onto the
newly won hexagon.
After a player is finished making her moves, reinforcements are added to
that player’s dice armies. Reinforcements to the player’s occupied hexagons
are added one die at a time, starting from the upper-left corner, moving
across and down. The maximum number of dice added as reinforcements
is one less than the player took from the opponent in her completed turn.
When a player can no longer take her turn, the game has ended. The
player who occupies the most hexagons at this point is the winner. (A tie
is also possible.)
Play a few rounds to get used to the mechanics.
NOTE: If you’re playing around with this, don’t set the board size
to anything bigger than 3. The initial version of the Lisp game is very
inefficient and it will hang for a long time.
Setting up the Data Types in Haskell
The Lisp implementation uses integer values to represent the state of the board:
An array (not a list) of tuples is used, mainly for performance reasons. This is
often done in Haskell for the same reasons - constant-time access to a resource.
The first item in the tuple is the player (0 or 1) owning the cell, and
the second item is the number of dice (1, 2 or 3) in that cell.
We could do something similar in Haskell:
But this is Haskell, and we should use the type system to our advantage:
Note that I’m putting more state into the board than the Lisp version - including
the board dimensions and the number of dice conquered in an attacking move.
Generating a Random Board
The Lisp code in the book marks out the sections of the code that have
a “clean, functional” style vs. those that have a “dirty, imperative” style.
The Lisp code to generate a randomly populated board is not functional, and
has the “dirty, imperative” icon:
Haskell allows us to mark the code directly as “dirty”, “imperative” or “unsafe”. We do
this using the IO monad.
Code is in DiceOfDoom-a.hs
Note: unlike the original code, the board size, number of players and number of dice are
passsed in as parameters.
We can test this in the repl:
Drawing The Board
The data types given so far use the default implementation of the Show typeclass.
We’ll change that now to represent the board in the same way as the Lisp code.
Drawing the board is another “unsafe” function, but I’ll split it into
two functions: one does the IO, the other generates a string representation of the board.
First we’ll remove the default implementation of the Show typeclass for Player and Cell
and replace them with a custom version:
As in the Lisp version, player 0 is denoted by ‘a’, player 1 by ‘b’ etc.
This now gives us:
To get the exact same as the Lisp program output, we define showBoard for the string
representation and drawBoard as the bit that does IO:
We break down the list of cells into rows, number the rows (starting at the highest number
and working down to 1), zip these together to form a tuple of (row number, cells in row),
then indent depending on the row number (highest numbered rows are indented more) and
concatentate the cells on each row together.
Testing this we have:
Code is in DiceOfDoom-b.hs
Generating a Game Tree
A game tree is a tree of all possible moves from an intial board configuration.
As an example, consider the example game on page 321. I’ve added the
2x2 board configuration used on that page as a new parameter in the Lisp code:
(Note: this is the same as the test2x2Board in the Haskell source.
You can play out this game in CLisp:
We’re interested in the game tree, as produced by the game-tree function. Let’s take
a look at what it produces:
Ignore the errors and just look at the output. Whoa!
Each node in the game tree contains the current player (0 or 1), the current board state and a
list of possible moves. Each move leads to another node on the tree.
The above can be summarised as follows, where we show players A and B:
It’s better to see it in a diagram:
Compare this with the game tree for the same board but with B playing first:
If B plays first, there are no moves possible and the game ends with B
The code do to this is split over a few functions:
The last two functions recurse back to the first.
Calculating Attacking Moves
Let’s look at the attacking-moves function. Given a board and a player, finding out the
list of attacking moves involves finding all the cells for that player, and for each
cell finding the list of attacking moves to the opposition’s cells that are in the
neighbourhood of the player.
The neighbours of a cell can be determined as follows:
Trying this out we have:
Note that the Lisp code deals with positions of cells in the array. We’ll
use that for the moment as well, but might change it later.
It’s useful to map the positions of cells with the actual cells. From that we
can find the cell positions for a player:
We’ll need a function to see if one cell can attack another:
Putting this altogether, we have a function to get all the possible attack
moves for a player on a particular board:
Trying it all out:
Code in DiceOfDoom-c.hs.
When an attack is made, the state of the board changes, so we’ll need to write a function
that returns this new state.
The Lisp code for this is board-attack. It constructs a new board from the old board
looping through the cells and seeing if one is being attacked or is the attacker. The
Haskell version is similar:
After a player’s completed turn, which might include several attacks, reinforcements
are added by dividing the conquered dice among the player’s cells, starting from the
top and moving from left to right.
Note: The Lisp function is add-new-dice - this is the tail-call optimised one introduced
later in Chapter 15.
Just like the Lisp function, we use a local function to recurse through the board cells:
Passing Moves vs Attack Moves
One of the rules of the game is that a player cannot pass on their very
first move - they must make an attack if they can. After their first move
they player has the option of passing or attacking again.
The Lisp code uses NIL as a pass value. We don’t really have an equivalent
in Haskell. Instead, we introduce a new data type for all moves:
We can re-write the code using the new data type:
(Code in DiceOfDoom-d.hs).
Here it makes sense to rename the attack function to makeAMove. A passing move just returns
the same board.
When a player passes, the next player takes their turn. Remember, there could be any number of
players playing, not just A or B.
Putting It All Together - The Game Tree
The Lisp code uses an ordinary list to represent the game tree. In Haskell, we
can use the Date.Tree type, where the nodes in the tree reprsent
the game state:
The first part is the root of the tree. The second part, the empty list, is the sub-tree.
In GHCI, this displays as:
The next move is A attacking from 2 to 3. This is added to the tree:
To produce the game tree we get the current root node, find all
possible moves (including a ‘Pass’ move if it isn’t the player’s first turn)
and for each one of these moves, re-generate the board. The ‘Pass’ move
will switch players, adding reinforcements if available. We also switch if
there are no moves possible. We recursively do
this until we’ve exhausted all possible moves. If we can’t make a move
on our first turn, the game ends.
Note that the Haskell version here is a bit different in structure from the Lisp version. The
logic is the same, but I personally don’t like functions that recursively call other
functions - I prefer to keep everything in one. This is why the attackMoves function
doesn’t generate part of the game tree - it just calculates the attacking moves.
We can test it out. First, if player B starts off on the 2x2 board, there are no further
The Board’s Show instance has been implemented to just show cells and conquered dice:
Next, if player A starts off, we get a fuller game tree:
Code in DiceOfDoom-d.hs
Playing - Human vs Human
We’ve got all the pieces now to allow a human play against another human.
Given a node in a game tree, we
Print the current game state
If there are no child nodes then the game has ended - announce the winner.
If there are child nodes, print out the possible moves, let the player make that move and recurse.
There can be more than one winner in a game - a draw is possible in a 2-player
game and a draw is possible between 2 or more players in a N-player game.
Handling the human input is another ‘dirty’ function. Given a game tree,
tell the human what their options are and ask for input, returning the
subtree that they chose:
The code uses Data.Map to create a map between choices numbers and the child nodes in the tree.
Let’s give it a shot:
That’s it for part 1. In the next part we’ll work on the AI player, and
start worrying about performance and optimisation.