We continue our port of the Land of Lisp game “Dice of Doom” from
In this part, we:
Display the game tree graphically.
Fix a bug.
Develop the AI player.
Displaying the Game Tree
As we dive into developing the AI for the game, we’ll need more interesting
game trees to play around with. The game tree in Part 1 wasn’t particularly
good from a game play point of view - B always wins, and reinforcements
never come up.
If we want to look at different trees it would be helpful if we could display
them a bit better. Neither the Lisp nor the Haskell version of the game tree
output is user-friendly.
A very simple initial approach is to use the drawTree function
The problem is that this only works with string trees. We need to convert
our Tree GameState to a Tree String. To do this we use the fact that
Data.Tree is a functor. We can use fmap on the tree to produce another
tree with exactly the same tree structure but with the nodes transformed in
some way. Our transformation function must convert from a GameState value
to a String. We have such as function: show. Let’s change the GameState
data type to have a custom show method:
Note that the winners means the current node’s winners and not the overall
Now to display the tree we use fmap:
We can put this into a drawGameTree function in several ways:
Or, using function composition:
Or, using point-free notation:
Code in DiceOfDoom-f.hs.
Using Graphviz To Display The Game Tree
Displaying the game tree in ASCII is nice, but with a bit more work we can do a
lot better. In Chapter 7 of Land of Lisp, Graphviz is used
to display a graph of the role-playing game. We can do something similar here.
A Graphviz graph is simply:
A list of nodes and what they contain.
What connects the nodes.
Here’s a simple example of the sort of output we would like:
Here the “0”, “1” etc. are just node numbers - we don’t care what they really
are, so long as they uniquely identify a node.
Running this through Graphviz and selecting PNG output:
Numbering a Tree
In order to do this we’ll need to uniquely identify each node in the tree. We
could try to do this while constructing the game tree, but it’s probably
easier to come up with some transformation function that replaces each node
with a pair of the original node and a unique integer:
This is the sort of thing that’s really trivial to do in a non-functional
language: set a counter to zero, traverse the tree, pair the node with the
counter value, increment the counter and recurse. In pure functional languages
like Haskell, it’s a little bit more involved (but not much more), because we
can’t just increment some counter willy-nilly. Haskell provides us with
mechanisms for managing such state. In particular, the State Monad.
Just beware: you might think that numberTree could be implemented using
fmap and some appropriate function, in a similar way that we converted the
tree to a tree of strings. This won’t work. The function used in fmap gets
the contents of the node and not the node itself. The function doesn’t even
know that it’s dealing with a tree. You might also think that you could
just re-build the tree using recursion. This also won’t work. There’s no
getting away from it - we need to use something stateful.
A bit of explanation: the numberTree function evaluates the state produced in
the inner function numTree, which executes in the State Monad. It uses
another function, nextNumber to manage a counter. The important thing here
is that when recusing using state monads, you need to use mapM to map the
stateful function numTree over the list of child nodes.
Testing this we have:
Generating Graphiz Output
With this in place, we can start on our Graphviz output.
Note: There is a package on Hackage,
for producting Graphviz output. There’s also the
However, for this example we’ll just format a bunch of strings as the output.
The function to get the list of nodes with their contents is
showGameGraphNodes. Note that it uses Text.Printf to do some formatting.
We colour the leaf nodes with the winner - blue for B, pink for A and green for a tie.
Getting the relationship between the nodes is similar:
Putting this all together we have:
Automating The Generation of SVG Files
We can test this out in GHCI by running the function and copy and pasting
the Graphviz output into a file, but that’s tedious. Let’s automate the
generation of the graph output by writing a function that runs the Graphviz
dot command for us. The function creates a process for the dot command
and ties the stdin of that proceess to the Graphviz string representation:
Let’s test this out on the 2x2 board used in part 1:
You should see this when you open the SVG file:
Fixing A Bug
The reason I spent a good while getting a nice graphical display of the game
tree is because I discovered a bug in the Haskell code to do with how
conquered dice are gathered. I only found this when looking at a more
complicated game tree (see below).
The bug is in the makeAMove code:
We should be adding the dice conquered in the current move to the board’s
tally of conquered dice:
In the game tree in Part 1 the reinforcement scenario never arose.
That’s fixed in DiceOfDoom-f.hs.
Creating an AI Player
For a two-player game, we use the Minimax algorithm to drive the AI player’s
Let’s consider a more complex 2x2 game where all three possible outcomes can
The board is much more evenly balanced. If we look at the game tree where
player A starts, we see that all three winning combinations are possible for
(Right-click to open in a new tab to see a full scale SVG).
The Minimax Algorithm
For 2-player games, the Minimax Algorithm involves computing a rating for
the position of a player in the tree. We move along the tree as far as we
can go, until we reach a point where there are no more moves. At that point,
we calculate a score based on whether the current player is in the list
of winners for that board position. If the current player is the only one
in the list of winners, the score is 1. If it’s a tie, the score is 0.5, and
if the player isn’t on the list, the score is 0.
The AI code is similar to the playVsHuman equivalent:
We can now play against the AI:
Code is DiceOfDoom-f.hs.
Making Play the Same as the Lisp Version
NOTE If you compare the play against the Lisp version, you will see some
differences. I’d like to make the two versions play the same, because it’s
easier for testing.
The first difference is the way the node is chosen among those with the
same rating. In Haskell we have the following to find the position of
child with the maximum rating:
Trying this out on a list of 1 0 1 0 1 0 we have:
In Lisp, we have:
The Haskell version gives the last maximum found, whereas the Lisp version
gives the first.
Let’s fix this using elemIndex to find the first matching item.
We need the “+ 1” because, for user display purposes, we map the child
movements to 1, 2, 3 … but elemIndex returns a 0-based index. Note
that we should never get to the second part of the case statement, so
putting a “0” in there seems safe.
The next difference is that the Lisp version always presents the “Pass”
option first. In the gameTree function we have:
We can change this to:
While we’re making changes, I don’t like hard-coding player A as the human, so
let’s parameterise it:
Finally, there’s duplicate code used in handleHuman and handleComputer
which I’ve factored that out.
Code in DiceOfDoom-g.hs.
Computer vs Computer
There’s nothing stopping us playing the AI against itself.
That’s it for Part 2. We can now play 2x2 games against an AI opponent. In
Part 3, we’ll take a close look at performance, which will allow us to play
3x3 or larger boards.