I’m sure you’ve probably noticed one obvious flaw in our game so far: Despite the fact that it is called Dice of Doom, it actually is completely devoid of any randomness! The dice are never rolled, and the larger stack will always automatically win, which makes for a pretty lame dice game. Now we’re finally going to rectify this flaw.
In this version of the game, during an attack, both piles of dice are rolled, and whoever rolls the highest number wins the battle. Ties are a victory for the defender. If the attacker loses, that player must surrender all dice from the attacking hex except one.
In the lingo of AI programming, this means we will add chance nodes to our game tree. The way we’re going to implement this is pretty simple.
Every move in our lazy list of moves up to now has always had exactly two items in it: a description of the move (a list of the source and destination of the attack, or nil for a passing move) and the new node of the game tree for when the move has been taken. Now we’re simply going to add a third item to a move, which contains the game tree for an unsuccessful attack. This means that each move in our move list will double as a chance node, with two possible follow-up nodes for the next game tree, depending on whether an attack is successful.
Let’s update our attacking-moves function to add this extra item to the move so that each move acts as a chance node.
(defun attacking-moves (board cur-player spare-dice)
(labels ((player (pos)
(car (aref board pos)))
(dice (pos)
(cadr (aref board pos))))
(lazy-mapcan (lambda (src)
(if (eq (player src) cur-player)
(lazy-mapcan
(lambda (dst)
(if (and (not (eq (player dst) cur-player))
(> (dice src) 1))
(make-lazy (list (list (list src dst)
(game-tree (board-attack board cur-player src dst (dice src))
cur-player
(+ spare-dice (dice dst))
nil)
(game-tree (board-attack-fail board cur-player src dst (dice src))
cur-player
(+ spare-dice (dice dst))
nil))))
(lazy-nil)))
(make-lazy (neighbors src)))
(lazy-nil)))
(make-lazy (loop for n below *board-hexnum*
collect n)))))The only thing new in this updated version of attacking-moves is right here , where we add a third item as we create a new move in the game tree. The board in this alternate branch of our chance node is constructed by calling the function board-attack-fail, which we will write next.
The board-attack-fail function does exactly what you would expect: It takes a board and returns a board that has all dice but one removed from the hex from which a failed attack originated.
(defun board-attack-fail (board player src dst dice)
(board-array (loop for pos from 0
for hex across board
collect (if (eq pos src)
(list player 1)
hex))))Here, we simply loop over the board and return each hex unmodified , unless it happens to be the source hex for the attack. In that case, we remove all dice from that hex but one .
Next, we need to write some functions to actually roll the dice. Here is a function that rolls a pile of dice:
(defun roll-dice (dice-num)total))
First, it calculates a total count of a pile of rolled dice by looping once for each die. For each die, it generates a random number from 1 to 6. Then it stores the total sum in the total variable . Next, the roll-dice function prints a descriptive message about the roll . Finally, it returns the total .
Since we’re never going to roll a pile of dice in isolation, let’s create another function that pits two piles of dice against each other:
(defun roll-against (src-dice dst-dice) (> (roll-dice src-dice) (roll-dice dst-dice)))
This simply calls roll-dice twice and compares the total of the two rolls. We’ll want to use this function as we travel along our game tree to pick either the winning or losing move as a turn is chosen by either the human or the computer.
In the context of our game engine, rolling dice simply means picking either the winning or losing branch of the chance node after the human or computer has chosen a move. This action is performed by the pick-chance-branch function:
(caddr move)))))
This function takes the current board and also the move that contains the chance node that needs to be resolved . When the path inside the move is not null, we call roll-against with a count of dice in the source and destination hexes along the path of attack . We check for a null path because that means the move was a “pass,” which doesn’t require any dice rolling.
If the dice roll for the attack is successful, we remove the first child tree from the chance node within the move . If the attack is unsuccessful, we return the second child of the chance node .
Now we need to make sure that the pick-chance-branch function is called when the human or computer chooses a move. First, let’s take care of the human:
(defun handle-human (tree)
(fresh-line)
(princ "choose your move:")
(let ((moves (caddr tree)))
(labels ((print-moves (moves n)
(unless (lazy-null moves)
(let* ((move (lazy-car moves))
(action (car move)))
(fresh-line)
(format t "˜a. " n)
(if action
(format t "˜a -> ˜a" (car action) (cadr action))
(princ "end turn")))
(print-moves (lazy-cdr moves) (1+ n)))))
(print-moves moves 1))
(fresh-line)
(pick-chance-branch (cadr tree) (lazy-nth (1- (read)) moves))))All we’ve done here is to add a call to pick-chance-branch at the end of our previous handle-human function, at the point we need to return the child branch of the game tree that holds the next state of the game .
We update the handle-computer function in the same way:
(defun handle-computer (tree)
(let ((ratings (get-ratings (limit-tree-depth tree *ai-level*) (car tree))))
(pick-chance-branch
(cadr tree)
(lazy-nth (position (apply #'max ratings) ratings) (caddr tree)))))Again, we’ve simply added a call to pick-chance-branch at the end of the function .
It is now possible to play our updated Dice of Doom game. However, at this point, the computer player will play a very poor game, because the AI does not yet understand that the chance nodes exist. It will simply assume that every attack will always be successful, making it much too foolhardy to play a decent game. We need to improve our AI so that it takes into account the rolling of the dice as it makes its decisions.
For the AI to be able to deal with the dice rolls that are now important to our game, it must know a little something about the statistics of dice rolls. The following table gives it the needed statistical information:
(defparameter *dice-odds* #(#(0.84 0.97 1.0 1.0)
#(0.44 0.78 0.94 0.99)
#(0.15 0.45 0.74 0.91)
#(0.04 0.19 0.46 0.72)
#(0.01 0.06 0.22 0.46)))This table contains the odds of winning for each possible pairing of dice in our game. The columns represent the attacking dice, starting with one die. The rows represent the destination dice, starting with two dice (the minimum dice needed for an attack).
This table tells us, for instance, that a roll of two attacking dice against one defending die has an 84 percent chance of winning. Four attacking dice against three defending dice have a 74 percent chance of winning.
If you remember, the core function in our AI code is the get-ratings function, which gives a point score to the list of possible follow-up moves. We need to modify how it calculates the score of each possible move to take the odds of success of the dice roll into account. We are now going to make use of our *dice-odds* table, as well as the point scores of the successful or failed outcomes of each attack, to interpolate a combined score for each available move:
(defun get-ratings (tree player)
(let ((board (cadr tree)))
(labels ((dice (pos)
(cadr (aref board pos))))
(take-all (lazy-mapcar
(lambda (move)
(let ((path (car move)))
(if path
(let* ((src (car path))
(dst (cadr path))
(odds (aref (aref *dice-odds*
(1- (dice dst)))
(- (dice src) 2))))
(+ (* odds (rate-position (cadr move) player))
(* (- 1 odds) (rate-position (caddr move)
player))))
(rate-position (cadr move) player))))
(caddr tree))))))In our updated get-ratings function, we look up the odds of each attack succeeding from our table . Then we multiply the odds with the rating for the winning child tree . Additionally, we add in the odds of losing the attack (one minus the odds of winning) multiplied by the rating for the losing board position . We now have an updated get-ratings function that understands chance nodes and accounts for them appropriately when generating the score for a move.
For our game AI to be fully compatible with chance nodes, we need to make one additional small change. Our tree-trimming function needs to know about the two branches of the chance node within each move, so it can properly trim both the winning and losing alternatives for each move:
(defun limit-tree-depth (tree depth)
(list (car tree)
(cadr tree)
(if (zerop depth)
(lazy-nil)
(lazy-mapcar (lambda (move)
(cons (car move)
(mapcar (lambda (x)
(limit-tree-depth x (1- depth)))
(cdr move))))
(caddr tree)))))We mapcar across the tail of each move, so trimming is performed on both branches of any chance nodes.
Note
Version 4 of Dice of Doom will not have alpha-beta pruning. Performing proper alpha-beta pruning in the presence of chance nodes is very complex.