Until now, the number of reinforcements at the end of a player’s turn always equals the number of captured opponent dice, minus one. This reinforcement rule guaranteed that the total number of dice in a game always decreases, so that the game was certain to eventually terminate, and the game tree was always finite in size.

However, since version 2, our game tree has been a lazy tree, so it is perfectly fine if the tree is infinite. Remember that one of the main benefits of lazy evaluation is that you can have data structures that are infinite in size.

Therefore, we are now going to adjust our reinforcement rules to make our game strategically more interesting.

According to our new rules, the number of reinforcement dice will equal the number of tiles in the player’s largest contiguous territory. This adds a lot of strategic depth, because the players must constantly decide whether to risk connecting their territories, or perhaps even to sacrifice smaller, nonviable territories by sending them on suicide missions.

In order to implement this new reinforcement rule, let’s first define the function get-connected, which returns a list of tiles that are owned by the current player and are connected as a cluster of neighbors to the target tile:

(defun get-connected (board player pos)
   (labels ((check-pos (pos visited)
               (if (and (eq (car (aref board pos)) player)
                        (not (member pos visited)))
                   (check-neighbors (neighbors pos) (cons pos visited))
                 visited))
            (check-neighbors (lst visited)
               (if lst
                   (check-neighbors (cdr lst) (check-pos (car lst) visited))
                 visited)))
     (check-pos pos '())))

This function uses the same algorithm for finding connected tiles as we used for calculating connectedness in our Grand Theft Wumpus game in Chapter 8. We traverse through the hexes and their neighbors recursively, while maintaining a visited list.

The get-connected function accomplishes this by defining two recursive local functions. The check-pos function checks a single position and appends any new neighbors accessible from that location to the visited list. The check-neighbors function checks an entire list of neighbors, similarly appending new neighbors to the visited list. These two functions call each other recursively until all neighbors in a cluster are found. To start off this recursive calculation, we call the check-pos function with the target position and an initially empty visited list .

We can now find clusters. However, to find the largest cluster, we need the largest-cluster-size function:

(defun largest-cluster-size (board player)
   (labels ((f (pos visited best)
             (if (< pos *board-hexnum*)
                (if (and (eq (car (aref board pos)) player)
                        (not (member pos visited)))
                   (let* ((cluster (get-connected board player pos))
                         (size (length cluster)))
                   (if (> size best)
                       (f (1+ pos) (append cluster visited) size)
                     (f (1+ pos) (append cluster visited) best)))
                  (f (1+ pos) visited best))
              best)))
          (f 0 '() 0)))

This function defines a local function f, which we’ll use to check every position on the board, while maintaining both a list of previously visited nodes and the size of the largest, best cluster found so far .

As long as the current position number is less than the total number of spots on the board , we continue to check tiles. If the current tile to be checked belongs to the player and also has not yet been visited , we’ll call get-connected to retrieve the cluster of hexes reachable from this spot . Then, if the size of the cluster is larger than the best found so far , we make this the new best size in our recursive call . Otherwise, we proceed by calling f while keeping the previous best size . (The best variable at this point will hold the best value found so far from previous iterations.) No matter what happens, however, the pos variable is incremented with every recursive call to f, so that we eventually cover the whole board.

Finally, we need to update add-new-dice to make use of our new rule for choosing the number of reinforcements:

 (defun add-new-dice (board player spare-dice)
    (labels ((f (lst n)
              (cond ((zerop n) lst)
                  ((null lst) nil)
                  (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)
                         (largest-cluster-size board player)))))

As you can see, the add-new-dice function still receives spare-dice as an argument for compatibility with our old code , but now this argument is simply ignored. Instead, the number of reinforcements added to the board depends on the size of the largest cluster . Otherwise, the add-new-dice is identical to our previous version.

This is all the code we need to enable the new reinforcement rules. Note that, due to the design of our code, the AI player has full access to the game tree. Since the game tree now contains all of this new reinforcement data, the AI will automatically adapt its playing strategy to take into account the new reinforcement rules!