Chapter 10. (Dice of Doom)

Each such node contains the current state of the board and the list of possible moves. Each move is a two-element list that combines an action with the resulting game tree, where an action is just another structure:

(struct action (player position))

It records the player that takes the action and her chosen token placement.

The tree-generating function consumes the two players and produces a complete game tree starting from an empty board:

(define (generate-ttt-tree player1 player2)
  (define (generate-tree board player opponent)
    (ttt board (generate-moves board player opponent)))
  (define (generate-moves board0 player opponent)
    (define free-fields (board-find-free-fields board0))
    (for/list ((f free-fields))
        (define actnow (action player f))
        (define board1 (board-take-field board0 player f))
        (list actnow (generate-tree board1 opponent player))))
;; -- start here --
  (generate-tree the-empty-board player1 player2))

As you can see, the function introduces two auxiliary functions: generate-tree and generate-moves. The first one generates a tree node from the current state of the board and two players, assuming the first player takes an action. The second function generates the list of possible moves from the current board and the two players, still assuming that the first player is the active one.

From the definition, you can see that generate-tree is straightforward. It creates the node from the current board and generates the possible moves with the second function. In contrast, the generate-moves function must iterate over all free fields, which it finds with board-find-free-fields, a function not shown here. For each of the free fields, the loop creates an action for the current player and the free field. Then it computes with board-take-field the effect of the action on the current board. The result of an iteration is a two-element list that pairs the action with the resulting tree, which is determined via a recursive call to generate-tree. When the loop has finished, generate-moves returns an entire list of such two-element lists.

With the two functions in place, it is easy to see how to launch the tree-generating process. We call generate-tree on the empty board and pass along the two players. It takes a while to generate the entire tree, and if you wish to display it, be prepared to take a coffee break. But really, that’s all there is to game trees. The details are a bit tedious, but improving the tree operations’ efficiency is fun, and you’ll see that in the next two chapters.

10.5 Game States and Game Trees for Dice of Doom

Tic-tac-toe is a bit simple for using game trees, but it is a good model for our data design. For Dice of Doom, we need three pieces of data to represent a game state:

(struct dice-world (src board gt))

The first field, src, designates the territory that a player has marked as the source of her attack. It is an index label for one of the territories or #f if no territory has been marked yet. The second field, board, contains a list of all territories. The first element of this list is the territory that the player is focused on. Recall that this means that the player is contemplating it for a move. When she presses the “Enter” key and src is still #f, the in-focus territory becomes the marked one. The third field, gt, is the game tree for the current state of the board.

The definition of dice-world requires two more kinds of data. The first is a territory:

(struct territory (index player dice x y))

The first field, index, is the label that simultaneously describes the territory’s location relative to other territories and acts as a unique identifier. The second field, player, identifies the player who currently owns this territory. In this game, the players are represented by natural numbers. This allows us to cycle through players by adding one to the current player index instead of cycling through a list of names. The third field, dice, is the number of dice on this territory. We include the last two fields, x and y, as the coordinates for drawing this territory. Strictly speaking, these last two fields aren’t necessary, but they tremendously simplify the rendering process.

The second definition we need for dice-world is the game tree, which is a little tricky. We need two pieces of data: one representing an entire game tree and the other representing a move. Plus, we need to keep track of whose turn it is. So the game tree needs three pieces:

(struct game (board player moves))

The first field, board, is the state of the board, which, as you may recall, is a list of territories. The second field, player, identifies the player whose turn it is. The third field, moves, is a list of all possible moves starting at this state of the game. If a player cannot make a move, this list is empty. We refer to such a game tree as the empty game tree, which indicates that the game has ended.

To represent a move, we use two pieces of data:

(struct move (action gt))

The first field, action, describes the attack that a player is going to perform. It is either empty, representing a pass, or a list of two numbers, representing an attack from the first territory against the second territory. The second field, gt, is the game tree that results from executing this move on the current board.

Remember that you can relate this idea to the tree image of tic-tac-toe in 10.4 How Game Trees Work. Each node in the tree represents a game, and a connection between two nodes represents a move. A game represents each of the nodes on that tree, whereas a move represents one of the between-node connections.

Let’s build a small game tree for a simplistic Dice of Doom game on a 2×1 board. To start, we’ll look at the total game tree. For a graphical view, see the diagram below.

The board consists of two territories, owned by players 0 and 1. The game begins with player 0’s turn. Because it is her first move and there is only one other territory on the board, her only option is to attack that territory. After this attack, there are no other territories on the board she can attack, so she must pass. Once she passes, it is player 1’s turn. Our rules state that a player’s first move must be an attack, but that’s impossible because player 1 has no more territories. With no possible moves left, the game concludes.

According to our description of the gameplay, there are three possible states of the board:

(define b0 (list (territory 0 0 2 'x 'y) (territory 1 1 1 'a 'b)))
(define b1 (list (territory 0 0 1 'x 'y) (territory 1 0 1 'a 'b)))
(define b2 (list (territory 1 0 1 'a 'b) (territory 0 0 1 'x 'y)))

The states of the board are listed in consecutive order of gameplay. In b0, player 0 owns a territory with two dice and player 1 owns a territory with only one dice. In b1 and b2, player 0 owns both territories that each contain one dice. Note that the only difference between b1 and b2 is the ordering of the territories in the list. Do you remember when the ordering plays a role?

To build any game tree manually, we must start at the bottom. In this case, it is the game tree with the final board:

(define gt2 (game b2 1 '()))

In this bottommost game tree, it is player 1’s turn and both territories are owned by player 0. Therefore, her list of moves is empty.

The move in the game tree gt2 starts from b2, where player 0 owns both territories. Hence, the move can be only a pass by player 0:

(define mv1 (move '() gt2))
(define gt1 (game b2 0 (list mv1)))

Since a pass cannot be player 0’s first move, player 0 has to make a move that leads to gt1:

(define mv0 (move '(0 1) gt1))
(define gt0 (game b0 0 (list mv0)))

This move represents an attack from territory 0 on 1 and contains gt1, which is the result of the attack. Game tree gt0 contains the starting board, which is the ultimate game tree that we are trying to build. The diagram above graphically explains the game tree. A picture is worth a thousand words.

10.6 Roll the Dice

Now we can finally start making the game:

(define (roll-the-dice)
  (big-bang (create-world-of-dice-and-doom)
            (on-key interact-with-board)
            (on-draw draw-dice-world)
            (stop-when no-more-moves-in-world?
                       draw-end-of-dice-world)))

This function launches the game. It uses the same kind of big-bang expression you have seen throughout the book. The function first creates a random world with create-world-of-dice-and-doom:

(define (create-world-of-dice-and-doom)
  (define board (territory-build))
  (define gamet (game-tree board INIT-PLAYER INIT-SPARE-DICE))
  (define new-world (dice-world #f board gamet))
  (if (no-more-moves-in-world? new-world)
      (create-world-of-dice-and-doom)
      new-world))

The function creates a random board and uses it to create a world with a game tree. If the generated game has no moves for the first player, it will immediately end the game, which we don’t want, so the function tries again. Otherwise, we accept the world as it is.

The rest of the big-bang clauses specify how to handle events, draw the world, determine whether the game is over, and if so, draw an image for the end of the game.

The simplest of these clauses is the ending condition, which we also used in the world creation function:

(define (no-more-moves-in-world? w)
  (define tree (dice-world-gt w))
  (define board (dice-world-board w))
  (define player (game-player tree))
  (or (no-more-moves? tree)
      (for/and ((t board)) (= (territory-player t) player))))

This function checks whether a world’s list of moves is empty or the current player has conquered all territories. In either case, the game is over.

Rendering the final state of the game is also straightforward:

(define (draw-end-of-dice-world w)
  (define board (dice-world-board w))
  (define message (text (won board) TEXT-SIZE TEXT-COLOR))
  (define background (add-board-to-scene w (PLAIN)))
  (overlay message background))

At the end of the game, we generate a string using the function won that overlays the text on the background scene. The text either announces the winning player or acknowledges a tie.

Drawing the game in play is slightly more involved:

(define (draw-dice-world w)
  (add-player-info
   (game-player (dice-world-gt w))
   (add-board-to-scene w (ISCENE))))

The add-player-info function draws information about whose turn it is on a scene. Both add-player-info and add-board consume a scene on which they draw their images.

The remaining big-bang clause specifies the key-handler:

(define (interact-with-board w k)
  (cond [(key=? "left" k)
         (refocus-board w left)]
        [(key=? "right" k)
         (refocus-board w right)]
        [(key=? "p" k)
         (pass w)]
        [(key=? "\r" k)
         (mark w)]
        [(key=? "d" k)
         (unmark w)]
        [else w]))

The first two clauses handle the player changing focus. They call refocus-board, which uses the current world and the direction to rotate the board. The third clause deals with the passing action. It calls pass on the world, which switches the current player and prunes the game tree to the pass move. The fourth case marks a territory. It invokes mark, which will either change the src field of the world to the in-focus territory, if the source for an attack has yet to be selected, or change the src to #f and initiate the attack. Doing so prunes the game tree and switches the board of the world to the board of the new game tree. The fifth clause deals with unmarking a territory. This action switches the src field to #f. The final case says to ignore all other keystrokes.

10.7 Rendering the Dice World

Drawing Dice of Doom requires two functions: draw-dice-world and draw-end-of-dice-world. Both are used in the main function. In turn, the two require three auxiliary functions: add-player-info, add-board, and won. The first two add imagery to a given scene; the last constructs text from the current state of the game, which is then added to the background.

The add-player-info function is simple:

(define (add-player-info player s)
  (define str (whose-turn player))
  (define txt (text str TEXT-SIZE TEXT-COLOR))
  (place-image txt (- WIDTH INFO-X-OFFSET) INFO-Y-OFFSET s))

First, it decides whose turn it is, using an uninteresting auxiliary function, and records this information as a string. Second, it converts this string to a text image, which is finally added to the bottom of the background scene.

The second function, add-board, is much more complicated than add-player-info:

(define (add-board-to-scene w s)
  (define board   (dice-world-board w))
  (define player  (game-player (dice-world-gt w)))
  (define focus?  (dice-world-src w))
  (define trtry1  (first board))
  (define p-focus (territory-player trtry1))
  (define t-image (draw-territory trtry1))
  (define image (draw-focus focus? p-focus player t-image))
  (define base-s  (add-territory trtry1 image s))
  (for/fold ([s base-s]) ([t (rest board)])
    (add-territory t (draw-territory t) s)))

(define (draw-focus marked? p-in-focus p t-image)
  (if (or (and (not marked?) (= p-in-focus p))
          (and marked? (not (= p-in-focus p))))
      (overlay FOCUS t-image)
      t-image))

It consumes a world and a scene. From this data, it constructs an image that contains the board and informs the player whose turn it is. The first five internal definitions extract the relevant pieces from the given data. The local definition of image highlights the in-focus tile under certain conditions, using a simple auxiliary function. Specifically, the function overlays the basic image with the FOCUS frame if the currently acting player has used the arrow keys to focus on either a launching pad for an attack or a target. This special first territory on the board is then used to create the base image. The rest of the result is created by folding over the board with draw-territory.

The function draw-territory consumes a territory and returns the image for that hexagon with all of its dice:

(define (add-territory t image scene)
  (place-image image (territory-x t) (territory-y t) scene))

(define (draw-territory t)
  (define color (color-chooser (territory-player t)))
  (overlay (hexagon color) (draw-dice (territory-dice t))))

The image of the territory is created by overlaying a semi-opaque hexagon of the player’s color onto an image of the dice that occupy this territory. That way, the dice will have the same color as their territory.

The choice of color deserves some attention:

(define (color-chooser n)
  (list-ref COLORS n))

The all-caps variable name COLORS tells you that our code contains a constant definition, and this definition introduces COLORS as a list of colors. The color-chooser takes the nth value in it and calls it the nth player’s color.

Our list of COLORS differs from the way we have made colors before. In order to change the opacity of a color, we cannot use strings such as "red" because that’s 100% opaque. Instead, we use make-color, which takes four numbers between 0 and 255 to create a color. Respectively, these numbers represent the red, green, blue, and transparency values of a color. This means that the first three arguments define what shade the color will have: 0, 0, and 0 would give you black; 255, 0, 0 would give you red; 255, 255, 255, would give you white; and so on. The transparency specifies how opaque the color is, where 0 is transparent and 255 is completely opaque.

Drawing the dice requires the number of dice to draw:

(define (draw-dice n)
  (define first-dice  (get-dice-image 0))
  (define height-dice (image-height first-dice))
  (for/fold ([s first-dice]) ([i (- n 1)])
    (define dice-image (get-dice-image (+ i 1)))
    (define y-offset  (* height-dice (+ .5 (* i .25))))
    (overlay/offset s 0 y-offset dice-image)))

Since each territory must be occupied by at least one dice, draw-dice creates one image of a dice and uses it to place all others atop.

The draw-dice function then folds across the remaining dice, adding dice to the base dice. For this, we must stack the dice using an increasingly larger offset in the vertical direction, as the size of the accumulated image is increased.

We can get the dice image the same way we got the color for a hexagon—by using and looking up some image in a list of images:

(define (get-dice-img i)
  (list-ref IMG-LIST (modulo i (length IMG-LIST))))

When you design image-creating functions, it is always good to experiment in the interactions panel:

> (define (draw-dice dice)
    (define first-dice  (get-dice-image 0))
    (define height-dice (image-height first-dice))
    (for/fold ([s first-dice]) ([i (- n 1)])
      (define dice-image (get-dice-image (+ i 1)))
      (define y-offset  (* height-dice (+ .5 (* i .25))))
      (overlay/offset s 0 y-offset dice-image)))
> (draw-dice 3)

As you can imagine, we experimented quite a bit before we got this image just right.

10.8 Input Handling

Our player uses the keyboard to interact with the Dice of Doom game. As you may recall, she can perform four kinds of actions: switching focus from one territory to another, passing her turn, marking a territory, and unmarking a territory. Hence, handling keyboard inputs requires four functions: refocus-board, pass, mark, and unmark.

The refocus-board function takes in the world and a function that rotates a list either left or right. Its purpose is to rotate the board so that the newly focused territory is on the head of the list that represents the board.

(define (refocus-board w direction)
  (define source (dice-world-src w))
  (define board  (dice-world-board w))
  (define tree   (dice-world-gt w))
  (define player (game-player tree))
  (define (owner? tid)
    (if source (not (= tid player)) (= tid player)))
  (define new-board (rotate-until owner? board direction))
  (dice-world source new-board tree))

To accomplish its purpose, the function rebuilds the world, rotating the board field to the left or right. It uses two auxiliary functions: the locally defined owner? and rotate-until. Depending on the value of the src field, the rotation must look for either a territory of the active player or a territory of one of her opponents. The owner? function implements this comparison process, using a reference to the player from the current game tree.

The rotate-until function works as follows:

(define (rotate-until owned-by board rotate)
  (define next-list (rotate board))
  (if (owned-by (territory-player (first next-list)))
      next-list
      (rotate-until owned-by next-list rotate)))

It consumes a function, a board, and another function. With the owned-by function, rotate-until checks whether the first territory in board is owned by the desired player. With the rotate function, rotate-until executes the actual rotation on a step-by-step basis. Here, rotation can mean only one of two things: rotate left or rotate right.

We rotate the list to the left by appending the first of it to the end:

(define (left l)
  (append (rest l) (list (first l))))

Rotating to the right uses a silly trick:

(define (right l)
  (reverse (left (reverse l))))

It reverses the given list, shifts left, and reverses again. We leave it to you to explore these two functions in the interactions panel and to confirm that they work properly for any non-empty list. As you play the game, you will notice that the game is perfectly responsive, even though this trick looks slow.

The key-handler also processes pass moves. This is done with pass, which consumes a dice-world and uses the game tree to create a new dice-world.

(define (pass w)
  (define m (find-move (game-moves (dice-world-gt w)) '()))
  (cond [(not m) w]
        [else (dice-world #f (game-board m) m)]))

Using find-move, pass tries to find the desired passing move in the list of moves of the game tree. If it is found, the matching game tree is returned; otherwise, find-move produces #f, possibly because passing is disallowed during the first move of a player’s turn. If there is a move, the src field is changed to false, and the rest of the new game state is drawn from the game tree that results from choosing the passing move.

Finding the move is easy. All we need is the list of moves and the list that represents the action to be taken:

(define (find-move moves action)
  (define m
    (findf (lambda (m) (equal? (move-action m) action)) moves))
  (and m (move gt m))

The function uses findf to drive the process. So if findf finds a move, the and expression extracts the corresponding game tree. Otherwise, the function returns #f.

The findf function is another one of those nice higher-order, list-eating functions. This one produces the first element of the list for which the given predicate returns true, or it returns false if nothing is found.

The last actions needed are functions that mark and unmark territories. The function mark consumes the world and either marks the in-focus territory or initiates an attack against the selected territory from the src territory:

(define (mark w)
  (define tree   (dice-world-gt w))
  (define board  (dice-world-board w))
  (define source (dice-world-src w))
  (define focus  (territory-index (first board)))
  (if source
      (attacking w source focus)
      (dice-world focus board tree)))

First, mark deconstructs the given world into its pieces. Second, if the src field of this world is #f, the selected territory is marked. Otherwise, mark attacks by delegating to a helper:

(define (attacking w source target)
  (define feasible (game-moves (dice-world-gt w)))
  (define attack   (list source target))
  (define next     (find-move feasible attack))
  (if next (dice-world #f (game-board next) next) w))

The attacking function makes an attack and compares it against the list of feasible moves. If execute is not in the feasible list, the attempted move is illegal, and the world remains the same. But if the attack is valid, attacking creates a new world from the corresponding game tree and changes the src field to #f so that the player can launch another attack.

The final function in the key-handler deals with unmark requests:

(define (unmark w)
  (dice-world #f (dice-world-board w) (dice-world-gt w)))

The purpose of unmark is to change src to #f so that no territory is the source of an attack.

10.9 Creating a Game Tree

Now that we know how to manipulate the world, let’s build the world. The major element of our world is the game tree, and building the game tree relies heavily on the board representation. We therefore start with the function that creates boards:

(define (territory-build)
  (for/list ([n (in-range GRID)])
    (territory n (modulo n PLAYER#) (dice) (get-x n) (get-y n))))

The territory-build function uses for/list to create the territories. For each territory index, the for loop creates one territory. The structure is assigned to some player, equipped with a random number of dice, and allocated to a particular point on the GUI grid.

Here are the three auxiliary functions:

(define (dice)
  (add1 (random DICE#)))

(define (get-x n)
  (+ OFFSET0
     (if (odd? (get-row n)) 0 (/ X-OFFSET 2))
     (* X-OFFSET (modulo n BOARD))))

(define (get-y n)
  (+ OFFSET0 (* Y-OFFSET (get-row n))))

The functions get-x and get-y probably look a little weird to you, but that’s just because drawing hexagons is weird in the first place. Both of these functions use get-row to determine in which row the territory with index n is located.

(define (get-row pos)
  (quotient pos BOARD))

The Game Tree

With territory-build under your belt, we can explain how to generate a game tree from a given board. Recall that a game tree contains every possible state and move. Its root starts with the given board and explores all possible moves for the current player. When she passes, the tree starts with the board for the next player and explores all possible moves from here. This process continues until it reaches boards that represent a win, loss, or tie.

Generating all possible moves, even in a game as simple as Dice of Doom, is a somewhat tricky task. It’s one of those situations where functional programming excels. Indeed, it is flat-out superior to traditional assignment-based programming, but it is still the most complex code you will find in this book.

What’s tricky is that we need to generate all feasible attacks, followed by one passing move for each turn; everything else is illegal. With functional programming, we can compute all these possibilities because generating one branch of the game tree does not affect any other branch. The following code accomplishes this feat, so bear with us as we explain its complexities.

Since Dice of Doom comes with two kinds of moves, game-tree relies on two locally defined functions: attacks and passes. The first generates a list of trees, each starting with an attack. The second generates a tree that starts with a pass. In both cases, the subsequent moves in the tree are generated by recursively calling game-tree, but in the case of passes, the players’ roles are switched. Now that you know this much, read the code:

(define (game-tree board player dice)
  ;; create tree of attacks from this position; add passing move
  (define (attacks board)
    (for*/list ([src board]
                [dst (neighbors (territory-index src))]
                #:when (attackable? board player src dst))
      (define from (territory-index src))
      (define dice (territory-dice src))
      (define newb (execute board player from dst dice))
      (define more (cons (passes newb) (attacks newb)))
      (move (list from dst) (game newb player more))))
  ;; create a passing move and the rest of the game tree
  (define (passes board)
    (define-values (new-dice newb) (distribute board player dice))
    (move '() (game-tree newb (switch player) new-dice)))
  ;; -- START: --
  (game board player (attacks board)))

Look at the line below the comment that says START. Given the current board, player, and number of dice left in the pool, game-tree begins by building a game structure including the list of all possible moves generated by attacks. Thus, this line implements the restriction that the first move of each turn must be an attack, because we know that attacks does not generate an initial passing move.

The attacks function is the workhorse of game-tree. Using for*/list, it traverses the territories of the board. For each src territory, it looks at each neighbor, dst, as a potential target. If an attack from src to dst is feasible, attacks builds a move structure. To do so, attacks uses the execute function to create the board resulting from a single attack. Having attacked, it’s now possible to pass, so we cons a passing move onto the list of attacks for that branch of the game tree.

The passes function is simpler than attacks. It calls distribute and gets back the reduced number of dice in the pool and the updated board. Using those, it creates the passing move by applying game-tree to the new board, the other player, and the remaining number of dice.

To make passes work in the way we just explained, we need to design the functions switch and distribute. The shorter of these is switch, which changes to the next player:

(define (switch player)
  (modulo (add1 player) PLAYER#))

Because we represent players as numbers, we can use the modulo function to switch players.

The distribute function is more complex than switch. It consumes three values: the current board, the player whose territories get additional dice, and the number of spare dice left in the pool:

(define (distribute board player spare-dice)
  (for/fold ([dice spare-dice] [new-board '()]) ([t board])
    (if (and (= (territory-player t) player)
             (< (territory-dice t) DICE#)
             (not (zero? dice)))
        (values (- dice 1) (cons (add-dice-to t) new-board))
        (values dice (cons t new-board)))))

This function folds across the current board, modifying the player’s instances of territory and the dice pool. Specifically, the loop checks whether each territory is owned by the player, whether it has fewer than the maximum number of dice, and whether there are spare dice left to distribute. If these three conditions are met, it subtracts one dice from the pool of spare dice and adds it to the current territory using this function:

(define (add-dice-to t)
  (territory-set-dice t (add1 (territory-dice t))))

As you can see, this function adds 1 to the number of dice on the territory. Even though we don’t define territory-set-dice here, you can imagine that it creates a new territory from the old values, except for the dice field, which receives the given value.

Why does territory-set-dice create a new territory? In other contexts, we have used mutation to change one field of a structure if all others stay the same. The program can’t mutate territory here because doing so would modify this structure throughout the entire game tree—something we definitely do not want. All that needs to be changed is this particular territory in the current tree node.

Neighbors

The definition of attacks, within game-tree, requires us to implement two functions: neighbors and attackable?. The neighbors function consumes the unique index of a territory and returns a list of indices for the territories that border it. This function gets a little tricky because there are two kinds of hexagons we need to worry about here: the ones on even rows and the ones on odd rows. In order to get the hexagons to fit together, we shift every other row to the left. Accordingly, there are two kinds of calculations needed or, actually, one calculation adjusted for the shift in rows.

Every hexagon has maximally six neighbors: two above, two below, and one on either side. Pictorially, the calculations proceed according to the diagrams in Neighbors. But there is one more thing to consider. If a hexagon borders any of the four edges, it doesn’t have neighbors on some sides, so the math shown will return meaningless results.

Now let’s think about how the neighbors function might create the list of indicies. If it weren’t for border cases, the function would produce a list of six numbers. Hence, this looks like a good first sketch:

(define (neighbors n)
  (list  upper-right
         bottom-right
         upper-left
         lower-left
         right
         left))

As discussed earlier, some of these numbers are added only when certain conditions hold. An easy way to choose whether or not to add something to a list is to define another function:

(define (add b x)
  (if b empty (list x)))

It takes a Boolean and a value and returns either the empty list or the list with just that value. Using add, you can then append as many of these values together as you wish, and the resulting list contains just the right number of elements.

At this point, our neighbors function becomes fairly straightforward:

(define (neighbors pos)
  (define top?      (< pos BOARD))
  (define bottom?   (= (get-row pos) (sub1 BOARD)))
  (define even-row? (zero? (modulo (get-row pos) 2)))
  (define right?    (zero? (modulo (add1 pos) BOARD)))
  (define left?     (zero? (modulo pos BOARD)))
  (if even-row?
      (even-row pos top? bottom? right? left?)
      (odd-row  pos top? bottom? right? left?)))

The algorithms for handling even and odd rows are nearly identical:

(define (even-row pos top? bottom? right? left?)
  (append (add (or top? right?)    (add1 (- pos BOARD)))
          (add (or bottom? right?) (add1 (+ pos BOARD)))
          (add top?                (- pos BOARD))
          (add bottom?             (+ pos BOARD))
          (add right?              (add1 pos))
          (add left?               (sub1 pos))))

Look up the odd-row function—you know where it is.

As you can see, these functions use the row and edge information to append and add lists together to create a list of neighbors. In order, each of the expressions corresponds to upper right, bottom right, upper left, lower left, right, and left.

Attacks

Recall from the discussions of game-tree that we have to show you two more functions: attackable? and execute. The attackable? function checks the validity of an attack using the board, the current player, the source territory, and the index of the destination territory:

(define (attackable? board player src dst)
  (define dst-t
    (findf (lambda (t) (= (territory-index t) dst)) board))
  (and dst-t
       (= (territory-player src) player)
       (not (= (territory-player dst-t) player))
       (> (territory-dice src) (territory-dice dst-t))))

We use this function to determine whether dst has an owner who is not the current player and whether src has more dice than dst.

Before we check all of these conditions, though, we ensure that the dst index actually points to a valid territory on the board. Doing so simplifies the for loop in game-tree and allows us to iterate through all possible indices, regardless of the shape of the board.

The execute function consumes the board, the current player, the src index, the dst index, and the number of dice on the src. From this data, it builds the board resulting from an attack of src on dst:

(define (execute board player src dst dice)
  (for/list ([t board])
    (define idx (territory-index t))
    (cond [(= idx src) (territory-set-dice t 1)]
          [(= idx dst)
           (define s (territory-set-dice t (- dice 1)))
           (territory-set-player s player)]
          [else t])))

The function traverses the board and re-creates the territory structs for the src and dst of the attack. The former now has one dice, and the latter has changed owners. It also transfers dice so that dst receives all but one of the dice from src. The function territory-set-player is just like territory-set-dice in that it changes the player field of the struct.

10.10 The End Game

Naturally, we saved the end of the game for last. As you might remember, the draw-end-of-dice-world function uses won, which takes in the board and constructs text describing the final state of the board:

(define (won board)
  (define-values (best-score w) (winners board))
  (if (cons? (rest w)) "It's a tie." "You won."))

We use the winners function to fetch two values: the most territories owned by anyone and the list of players who own that many territories. If there are more than two winners in the list, the game ends in a tie. Otherwise, it constructs a string describing who won.

Calculating the winners from the board works like this:

(define (winners board)
  (for/fold ([best 0][winners '()]) ([p PLAYER#])
    (define p-score (sum-territory board p))
    (cond [(> p-score best) (values p-score (list p))]
          [(< p-score best) (values best winners)]
          [(= p-score best) (values best (cons p winners))])))

Here, we use for/fold to traverse the list of players. For each player, we get the number of occupied territories. When best is below p-score, the next loop iteration uses p-score as the winning score, and its list of winners contains only p, the unique identifier for the current player. When best is above p-score, nothing changes. Finally, when the two scores are identical, the loop adds p to the list of current winners. Since there are no other possibilities, the loop body covers all cases.

The very last function we need is sum-territory. It consumes a board and a player’s index, and it calculates the number of territories that the player owns:

(define (sum-territory board player)
  (for/fold ([result 0]) ([t board])
    (if (= (territory-player t) player) (+ result 1) result)))

This function is a simple for/fold that runs through the board and adds 1 to its return value every time it finds a territory that is owned by player.

Using this knowledge, Chad can finally beat Dicetromonom and proceed to the next level of DrRacket’s dungeons!

`Kill`—Chapter Checkpoint

In this chapter, you encountered a new technique for manipulating a game using a game tree as a point of control.

Creating a game tree produces a data structure that contains all legal moves from any state.
Running a game becomes a mere matter of making sure turns are played according to the data in the game tree.

Chapter Challenges

Medium. Change our version of Dice of Doom so that the dice are rolled for an attack. Have both the attacker and defender roll the number of dice on their respective territories. If the attacker wins, she takes the territory. If the defender wins, the attacker loses all but one dice on her territory. You may want to get the random numbers from a third-party site, such as www.random.org. Here’s some code for retrieving a bunch of random numbers:
```
(define (get-random-numbers)
 (define n 1000)
 (define src
   (string-append
    "http://www.random.org/integers/?num="
    (number->string n)
    "&min=1&max=6&col=5&base=10&format=plain&rnd=new"))
 (define ip (get-pure-port (string->url src)))
 ;; -- go get them --
 (for/list ((i n)) (read ip)))
```
Medium. After implementing the previous suggestion, create a display that tells you the probability of winning an attack on the selected enemy territory.