First, we’ll create some global variables that define the basic parameters for our game:

 (defparameter *num-players* 2)
 (defparameter *max-dice* 3)
 (defparameter *board-size* 2)
 (defparameter *board-hexnum* (* *board-size* *board-size*))

We’re stating that there will be two players , that the maximum number of dice on a square is three , and that the board will be 2-by-2 . In later versions of Dice of Doom, we’ll increase all of these parameters, to allow for a more challenging game.

Since it’s useful to know the total number or hexagons there are at the current board size, we also define *board-hexnum* . Note that even though the grid is made of hexagons, it is still basically a square grid, since the number of hexagons just equals the square of the side of the grid.

We’re going to represent the game board using a simple list. The hexagons will be stored in this list, starting at the top left, and then moving across and down. For each hexagon, we’ll store a list of two items: a number indicating the current occupant of the hexagon and another number indicating the number of dice at that location.

For instance, here is an example of a game board and the list that encodes it:

((0 3) (0 3) (1 3) (1 1))

Note that most Lisp programmers like to count starting at zero. Therefore, players A and B are represented with the numbers 0 and 1. This list indicates that player A has three dice on the first hexagon and three on the second. Player B has three dice on the third hexagon and one on the fourth.

When we create our AI player, it will need to be able to look at many hexagons on the board very quickly. Because of this, we’re going to create a second representation of our board in the form of an array. Remember that checking a numeric location (for instance, hexagon 2) in a list requires the nth function, which is potentially slow. Arrays, on the other hand, will allow for very fast lookup at a specific location, even with very large board sizes.

The board-array function converts a board represented with a list to an array for us:

(defun board-array (lst)
  (make-array *board-hexnum* :initial-contents lst))

When the game begins, we’ll start with a randomized board. Here’s the function that creates a random board:

(defun gen-board ()
   (board-array (loop for n below *board-hexnum*
                      collect (list (random *num-players*)
                                       (1+ (random *max-dice*))))))

This function is not in the functional style (as the icon indicates), since it will create a different, random result every time it is called. It generates the board as a list, but then converts the list to our speedier array format when it’s done, using board-array .

It generates random values using the Lisp function random. This function produces a different random integer every time, greater than or equal to zero, but smaller than the number passed to it. We use our *num-players* and *max-dice* global variables to generate random values for each hexagon .

Let’s try out the gen-board function:

> (gen-board)
#((0 3) (1 2) (1 3) (0 1))

Remember that the hash mark (#) indicates that we’ve created an array, not a list.

We’ll name our players using letters (just A and B, until we start introducing more players). Here’s a function that converts a player number into a letter:

(defun player-letter (n)
  (code-char (+ 97 n)))

The code-char function converts an ASCII code into the appropriate character. Let’s call it for player 1 to see the result:

> (player-letter 1)
#

Finally, let’s create a function that will take an encoded board and draw it in a pretty way on the screen. It will tilt the board in the same way as our drawings, so it’s obvious which six hexagons neighbor any given hexagon.

(defun draw-board (board)
   (loop for y below *board-size*
          do (progn (fresh-line)
                   (loop repeat (- *board-size* y)
                          do (princ "  "))
                   (loop for x below *board-size*
                         for hex = (aref board (+ x (* *board-size* y)))
                          do (format t "˜a-˜a " (player-letter (first hex))
                                               (second hex))))))

Since the whole purpose of this draw-board function is to write stuff to the console, it’s definitely not functional. Let’s look at this function more closely.

The outer loop runs through all the rows of the board, stored in the variable y . There are two inner loops. The first inner loop adds the indentation to the left side to give the board that tilted look . The second inner loop loops through the columns, stored in the variable x . It then uses x and y to calculate the appropriate hex number, and retrieves that hex from the board array using aref . Finally, it prints the data in the hex .

Here’s the output of the draw-board function, as well as a drawing to compare it with:

> (draw-board #((0 3) (0 3) (1 3) (1 1)))
    a-3 a-3
  b-3 b-1

Now we’re ready to write the code that takes care of the guts of our first Dice of Doom implementation. In writing this code, we’re going to employ a powerful functional programming technique: a function pipeline. This means that our game is going to consist of a succession of functions that operate, one after another, on a big chunk of data, which will hold a representation of our game board, making modifications to the structure along the way. A function pipeline will allow us to build a game rule engine that’s 100% decoupled from the rest of the game code. To understand why this is so cool, let’s first consider some of what’s involved in writing a board game with a smart AI player.

For one thing, any computer implementation of a board game will need code that handles the human player’s moves. This part of the code will need to know the rules of the board game and make sure the human player’s move is legal before letting it happen.

We’ll also need to write the AI code. And in order for the AI player to pick a move, it needs to know all the rules of the board game.

Notice something? Both of these separate parts of our game engine need to understand the rules of the game! Clearly, what we want to do is break our game code into three big pieces:

One piece handles the player’s moves. Another is the code for the AI player. Both of these then talk to some code that understand the rules, sort of a “rule engine.” Is this kind of design possible?

In a traditional, imperative programming style, it would be very difficult to write a program like this. Most imperative game engines duplicate the code that “understands the rules,” because of the complexity of writing fully decoupled components in an imperative language. The reason for this is that a board game requires a lot of context—every move is dependent on what moves preceded it. This means that every time the AI module or player-handling module needs to check the rules, it must tell the “rule code” the current context in detail. Both would need to tell the rule code that “It’s player so-and-so’s turn and the game board looks like such-and-such.” Without this information, the rule code can’t tell whether or not a move is legal.

Passing around this context requires tons of tedious bookkeeping code everywhere, is error-prone, and is inefficient. It’s inefficient because, with a naive design, the player-handling code may check the legality of moves the AI code had already explored and found legal.

Using functional programming, however, we can decouple these three concerns entirely in our program. We will be able to do this without bookkeeping code and in a way that avoids duplication any legality calculations. We will accomplish this by encoding our rule code in a lazy game tree!

In this chapter, we’ll be creating a game tree that is not yet lazy. You’ll need to wait until Chapter 18 to understand lazy programming and what a lazy game tree will look like. That’s also when you’ll be able to fully appreciate how cool this architectural design really is.

The entire rule set for our game is encoded in the following master function:

 (defun game-tree (board player spare-dice first-move)
   (list player
          board
         (add-passing-move board
                            player
                            spare-dice
                            first-move
                           (attacking-moves board player spare-dice))))

The game-tree function builds a tree of all possible moves, given a certain starting configuration. This function will be called only a single time at the beginning of the game. It will then recursively build a tree of all possible moves for the game, down to the final winning positions. The other parts of our game will then elegantly traverse this tree in order to conform to the rules of the game.

In order to calculate the legal possible moves of the game tree from a given context, the function needs four pieces of data passed to it as arguments :

As the game-tree function creates the tree, it will put information about the current board and current player at every branch . The subbranches will then hold all the legal follow-up moves from the current branch:

There are two types of legal moves possible for players: attack a hexagon or pass their turn to the next player (assuming they’ve already attacked at least once already). The passing move is added to the list of legal moves through the add-passing-move function . The attacking moves are added to the list through the attacking-moves function . Let’s look at these functions next.

Here is the function that adds the passing moves to the game tree:

 (defun add-passing-move (board player spare-dice first-move moves)
   (if first-move
       moves
       (cons (list nil
                   (game-tree (add-new-dice board player (1- spare-dice))
                              (mod (1+ player) *num-players*)
                                     0
                                     t))
            moves)))

The job of this function is to add a passing move to the tally of moves, if passing is permitted. The current list of moves is passed in to this function , and then the function will return the expanded list of moves. If the move is the first move in a player’s turn , no passing is allowed, and we just return the unaltered list . Otherwise, we add a new move to the list.

Every move in our game tree consists of two parts:

Of course, we also will need to change the current player, since a new person’s turn is now starting. We do this by adding one to the current player number and taking the modulus of the result, with the total number of players as the denominator . Changing a player in this fancy way will allow the code to work, even when we increase the number of players in the game in future versions.

Here is the function that adds the possible attacking moves to the game tree:

(defun attacking-moves (board cur-player spare-dice)
   (labels ((player (pos)
               (car (aref board pos)))
            (dice (pos)
               (cadr (aref board pos))))
     (mapcan (lambda (src)
               (when (eq (player src) cur-player)
                 (mapcan (lambda (dst)
                            (when (and (not (eq (player dst) cur-player))
                                 (> (dice src) (dice dst)))
                            (list
      (list (list src dst)
            (game-tree (board-attack board cur-player src dst (dice src))
                        cur-player
                        (+ spare-dice (dice dst))
                        nil)))))
                        (neighbors src))))
              (loop for n below *board-hexnum*
                    collect n))))

The attacking-moves function is a bit more complicated than the add-passing-move function. It’s responsible for scanning the current game board and figuring out what moves the current player is legally allowed to perform.

Since it must spend a lot of time figuring out who the player is on a given hexagon, we first write a convenience function called player that returns the player for a given board position . We write a similar function to get the number of dice on a given hexagon .

Next, we need to scan the board top to bottom and find out which squares the current player occupies. For each occupied square, there may be one or more legal attacks starting at that position. Since the number of attacks from any hexagon may vary, we use mapcan to scan the board . Remember that mapcan lets each hexagon we scan return its results as a list. Then mapcan concatenates these lists together. This way, any scanned hexagon can contribute zero to n moves to the list.

Within the lambda function used by the mapcan, which gets called for every hexagon, we first want to check whether the current player occupies this hexagon . Then we want to check all of its neighbors to see if any of them present a viable attack. We do this with another mapcan . We’ll figure out the neighbors to this hexagon by using the neighbors function, which we’ll write shortly .

How do we decide if a hexagon can be an attack destination? Well, it must be a hexagon we don’t already own, plus (as per the rules) the source hexagon needs to have more dice than the destination hexagon . If we have found a legal attack move, we then describe the move . The description is simply a list of the source position and the destination position. We then (as with passing moves) recursively generate another game tree that describes what happens if the move is executed .

Next, let’s create the function that calculates the neighboring hexagons to a given hexagon:

(defun neighbors (pos)
    (let ((up (- pos *board-size*))
          (down (+ pos *board-size*)))
     (loop for p in (append (list up down)
                            (unless (zerop (mod pos *board-size*))
                               (list (1- up) (1- pos)))
                            (unless (zerop (mod (1+ pos) *board-size*))
                               (list (1+ pos) (1+ down))))
                 when (and (>= p 0) (< p *board-hexnum*))
                  collect p)))

Every hexagon on the board may have up to six neighbors, or fewer, if the hexagon is on an edge of the board. We build up a list of possible neighbors in a loop , and then collect the ones with position numbers that aren’t off the edge of the board . Also, since our position numbers wrap from row to row, we need to make sure we don’t look to the left if we’re on the left edge of the board or look to the right if we’re on the right edge of the board .

This function is marked clean (it is in the functional style), but nonetheless contains a loop. Usually, looping goes against the tenets of functional programming. However, many Lispers consider it kosher to use a loop in functional code if all it does is collect some values, since it really isn’t mutating any values or producing any other side effects. So, we will allow ourselves to use such loops in the functional-style part of this game.

Let’s try out our neighbors function:

> (neighbors 2)
(0 3)

As you can see, it correctly tells us that hexagon 2 neighbors hexagons 0 and 3.

Now let’s write our board-attack function:

(defun board-attack (board player src dst dice)
   (board-array (loop for pos
                      for hex across board
                      collect (cond ((eq pos src) (list player 1))
                                    ((eq pos dst) (list player (1- dice)))
                                    (t hex)))))

This is a function that figures out what happens if the hexagon src attacks the hexagon dst. It works by looping across the board, keeping track of the current position and the contents in the hexagon at that position . If the current hexagon is the source hexagon, we just place a single die in that place; as per our rules, a single die is left behind after an attack . If the current hexagon is the destination position, we place the remaining dice there, subtracting the one left behind . In other cases, we just collect the very same hex .

Let’s try out our board-attack function:

> (board-attack #((0 3) (0 3) (1 3) (1 1)) 0 1 3 3)
#((0 3) (0 1) (1 3) (0 2))

As you can see, attacking from hexagon 1 to 3 causes board-attack to properly update the game board, so that one die remains on the old square and two are on the new, conquered square.

To add the reinforcements to the board, we need to scan across the game board, find occupied spots that can accommodate another die, and add the die there. Of course, the number of reinforcements is limited based on how many opponent dice the player captured in the last turn. Because of this, we’ll need to keep a running tally of how many reinforcement dice remain.

The most obvious way to track the remaining dice would be to have a remaining-dice variable, and decrement this every time a die is placed. However, having a die that is decremented (mutated) would not be in line with the functional style.

Therefore, instead, we’re going to write our add-new-dice function using a local recursive function, which will also maintain this running count of dice.

Here is this add-new-dice function:

(defun add-new-dice (board player spare-dice)
   (labels ((f (lst n)
              (cond ((null lst) nil)
                    ((zerop n) lst)
                 (t (let ((cur-player (caar lst))
                          (cur-dice (cadar lst)))
                     (if (and (eq cur-player player) (< cur-dice *max-dice*))
                          (cons (list cur-player (1+ cur-dice))
                               (f (cdr lst) (1- n)))
                         (cons (car lst) (f (cdr lst) n))))))))
     (board-array (f (coerce board 'list) spare-dice))))

The first thing add-new-dice does is define a local function named f . This function will be our list-eater that goes through the hexagons of the board and spits out a new list that includes the reinforcements. Since our board is actually stored in an array for efficiency reasons, we convert our array into a list with the coerce function before calling f .

Inside the function f, we must consider three situations:

Let try adding reinforcements to a board:

> (add-new-dice #((0 1) (1 3) (0 2) (1 1)) 0 2)
#((0 2) (1 3) (0 3) (1 1))

As you can see, add-new-dice properly placed two reinforcement dice for player A (player 0).

We have now written all the code needed to create a comprehensive game tree of our simplified version of Dice of Doom. But be careful! A game tree of most board games is excruciatingly large. Even on a 2-by-2 board, our game may consist of hundreds of possible moves. You’ll want to call the game-tree function only on a game board that is near the end of play, or you’ll be watching helplessly as the CLISP REPL prints out a humongous tree showing all the possible ways in which a game may progress.

Here is a safe board position for you to try out:

> (game-tree #((0 1) (1 1) (0 2) (1 1)) 0 0 t)
 (0
  #((0 1)(1 1) (0 2) (1 1))
  (((2 3)(0
             #((0 1) (1 1) (0 1) (0 1))
            ((NIL(1
                     #((0 1) (1 1) (0 1) (0 1))
                     NIL)))))))

The game tree first lists the current player number , the layout of the board , and then the legal moves for that context. For the initial board position, at the beginning of player A’s turn, there is only one possible move: The player can move from hexagon 2 to hexagon 3, capturing player B’s die in that spot . After that, the player can pass. Player B now has no move available. Since this player’s game tree has no available moves listed , the game has ended, with a win for player A.

Now that we’ve completely captured the universe of Dice of Doom in our comprehensive game-tree function, it’s simple to create a human versus human version of this game. All we need to do is create some functions that travel down the game tree as players choose their moves.

The Main Loop

Here is the function that travels down the game tree, allowing two humans to play Dice of Doom:

(defun play-vs-human (tree)
   (print-info tree)
   (if (caddr tree)
       (play-vs-human (handle-human tree))
     (announce-winner (cadr tree))))

This function, play-vs-human, is the main loop of our game. It accepts a tree describing the starting position of the board.

First, it calls a function named print-info, which will draw the board on the screen, along with other helpful information about the current state of the game . Next, we need to check if any follow-up moves exist. These follow-up moves would be listed starting at the caddr position of the game tree .

If follow-up moves are available, we call the function handle-human, which will interact with the current player to help him pick his new move. This handle-human function will then return the subbranch of the tree that represents the player’s choice. We can then recursively pass this subbranch into play-vs-human to proceed with the game .

If no follow-up moves are available, the game has officially ended. We then call the announce-winner function, which, appropriately, will announce the winner .

Giving Information About the State of the Game

Here is the print-info function, which describes the status of the current node in the game tree:

(defun print-info (tree)
  (fresh-line)
   (format t "current player = ˜a" (player-letter (car tree)))
   (draw-board (cadr tree)))

This function displays two important pieces of information on the REPL. First, it shows who the current player is . Then it prints out a pretty version of the game board with the draw-board function .

Handling Input from Human Players

Next is the function that lets humans choose their next move. It displays a very helpful, numbered menu of all currently available moves for the player to choose from.

(defun handle-human (tree)
    (fresh-line)
    (princ "choose your move:")
    (let ((moves (caddr tree)))
     (loop for move in moves
           for n from 1
            do (let ((action (car move)))
                 (fresh-line)
                (format t "˜a. " n)
                (if action
                    (format t "˜a -> ˜a" (car action) (cadr action))
                    (princ "end turn"))))
      (fresh-line)
     (cadr (nth (1- (read)) moves))))

To display the list of available moves, we use a loop that traverses all the available moves and prints a description about each one . This loop is not functional, since it prints stuff on the screen for the player to read. We print a counting number in front of each move using the variable n, which counts from 1 inside our loop .

Each move has an action value associated with it. If the action is non-nil , then the action is an attack, where the action value describes the source and destination hexagons of the attack. We print such attacking action using the format command .

We use an empty action value to represent the passing move. In that case, we just princ “end turn” to describe this move .

After the available moves have been displayed, we use read to read in the player’s choice. With the nth function, we can then select that branch of the game tree and return it from our handle-human function .

Determining the Winner

The task of announcing the winner can be nicely broken into a clean/functional and a dirty/imperative part.

The clean part concerns the task of calculating the winning player. We want to calculate this in a way that can handle more than just two players, since our game will allow for more in the future. Also, the function must be cognizant of possible ties.

To accomplish this, we’ll write a function called winners that returns a list of one or more players who captured the maximum number of hexagons at the end of the game. If there is a tie, it will simply return all the players who share first place, in terms of the total count of occupied spaces for all players. With this design, the function will work for any number of players and will elegantly handle ties. This is what the winners function looks like:

(defun winners (board)
   (let* ((tally (loop for hex across board
                        collect (car hex)))
           (totals (mapcar (lambda (player)
                            (cons player (count player tally)))
                          (remove-duplicates tally)))
          (best (apply #'max (mapcar #'cdr totals))))
     (mapcar #'car
             (remove-if (lambda (x)
                           (not (eq (cdr x) best)))
                         totals))))

We calculate the winner for a given ending board position in four steps.

• First, we build up a tally of who occupies each hexagon on the board . With the across loop construct, we can traverse the array of the ending board directly and collect the occupier of each hexagon.

• Second, we need to count the total number of squares each player has captured, using this tally. The totals variable will be an alist of player->spaces pairs. We build this alist by finding all players who have at least one entry in the tally with remove-duplicates . We can map across this and then create a count for each occupier .

• Third, we want to find what the maximum number of occupied hexagons for a single player is. We do this by stripping the counts from our alist by mapping cdr across the list . We then apply max to this list to find the largest number of occupied spaces for a single player.

• Finally, we need create a list of all the “best” players. We do this by stripping out all but the best from our totals using the remove-if function . We then just pull out the player numbers for the best players by mapping car across the list of bests .

Next, let’s write the dirty announce-winner function:

(defun announce-winner (board)
    (fresh-line)
   (let ((w (winners board)))
     (if (> (length w) 1)
       (format t "The game is a tie between ˜a" (mapcar #'player-letter w))
       (format t "The winner is ˜a" (player-letter (car w))))))

This function is rather simple. First, we calculate the winners by calling our earlier function . Then we check if there is more than one winner (a tie). For ties, we print a special message . Otherwise, we just announce a single winner .

> (play-vs-human (game-tree (gen-board) 0 0 t))
current player = a
    b-2 b-2
  a-2 b-1
choose your move:
1. 2 -> 3
1
current player = a
    b-2 b-2
  a-1 a-1
choose your move:
1. end turn
1
current player = b
    b-2 b-2
  a-1 a-1
choose your move:
1. 0 -> 2
2. 0 -> 3
3. 1 -> 3
1
current player = b
    b-1 b-2
  b-1 a-1
choose your move:
1. end turn
2. 1 -> 3
1
current player = a
    b-1 b-2
  b-1 a-1
The winner is b