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 found here.

Alternatively use `dice_of_doom_v1.lisp` that accompanies this source.

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 occupant.
• 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 winner.

The code do to this is split over a few functions:

• game-tree
• attacking-moves

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.

### Attacking

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:

### Reinforcements

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:

In GHCI:

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 moves possible:

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.