The last version of Dice of Doom was a slightly more efficient version of our first iteration that used caching techniques to memoize and tail-call optimize the ridiculously inefficient first version…
This version will make use of a few techniques to make it even more optimized!
But it still recursively calculated the entire game tree before playing, which is not particularly efficient.
We can fix this by only calculating the branches we need, by only creating them when something tries to look at them. This is lazy evaluation.
We can implement it with the following macro:
(defmacro lazy (&body body)
(let ((forced (gensym))
(value (gensym)))
`(let ((,forced nil)
(,value nil))
(lambda ()
(unless ,forced
(setf ,value (progn ,@body))
(setf ,forced t))
,value))))And for the force function we will use on he above macro:
(defun force (lazy-value)
(funcall lazy-value))Now lets make a lazy list implementation:
The building block of Lisp lists are cons cells, so the first macro
we will need to define is, of course, lazy-cons:
(defmacro lazy-cons (a d)
`(lazy (cons ,a ,d)))And to fetch the contents of these slots, we can create lazy car
and cdr functions:
(defun lazy-car (x)
(car (force x)))And:
(defun lazy-cdr (x)
(cdr (force x)))For the end of a list, we need a lazy nil if we wish to terminate
it:
(defun lazy-nil ()
(lazy nil))And a lazy null to check for the end of a list:
(defun lazy-null (x)
(not (force x)))Now we have all we need to implement a lazy list… Lets create a function to convert an existing list into a lazy list:
(defun make-lazy (lst)
(lazy (when lst
(cons (car lst) (make-lazy (cdr lst))))))If we have a lazy list, we may also need a means to convert back to a
normal one, or to take arbitrary values from it.
Here is how we would take some number of values from a lazy list:
(defun take (n lst)
(unless (or (zerop n) (lazy-null lst))
(cons (lazy-car lst) (take (1- n) (lazy-cdr lst)))))Or to fetch an entire list from a lazy list:
(defun take-all (lst)
(unless (lazy-null lst)
(cons (lazy-car lst) (take-all (lazy-cdr lst)))))Now lets work a bit on a list API:
We do a lot of things with normal lists, and it would be a boon to us if we could do something similar with lazy lists, so here are a few implementations of lazy versions of some of our previously used list functions:
A common task with lists is mapcar, here is a lazy version:
(defun lazy-mapcar (fun lst)
(lazy (unless (lazy-null lst)
(cons (funcall fun (lazy-car lst))
(lazy-mapcar fun (lazy-cdr lst))))))(defun lazy-mapcan (fun lst)
(labels ((f (lst-cur)
(if (lazy-null lst-cur)
(force (lazy-mapcan fun (lazy-cdr lst)))
(cons (lazy-car lst-cur) (lazy (f (lazy-cdr lst-cur)))))))
(lazy (unless (lazy-null lst)
(f (funcall fun (lazy-car lst)))))))(defun lazy-find-if (fun lst)
(unless (lazy-null lst)
(let ((x (lazy-car lst)))
(if (funcall fun x)
x
(lazy-find-if fun (lazy-cdr lst))))))(defun lazy-nth (n lst)
(if (zerop n)
(lazy-car lst)
(lazy-nth (1- n) (lazy-cdr lst))))Now that we have ourselves a usable lazy library, lets get to the game modifications!
First thing we need to do is load our previous work, the last version of our game and our lazy library:
(load "dice_v1.5.lisp")
(load "lazy.lisp")Then make the board a little larger:
(defparameter *board-size* 5)And make *board-hexnum* recalculate again:
(defparameter *board-hexnum* (* *board-size* *board-size*))Now that we have increased the board size, we can further optimize our game by changing a few of our functions to utilize the lazy functionality we introduced above:
(defun add-passing-move (board player spare-dice first-move moves)
(if first-move
moves
(lazy-cons (list nil
(game-tree (add-new-dice board player
(1- spare-dice))
(mod (1+ player) *num-players*)
0
t))
moves)))(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) (dice dst)))
(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))))
(lazy-nil)))
(make-lazy (neighbors src)))
(lazy-nil)))
(make-lazy (loop for n below *board-hexnum*
collect n)))))(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)
(cadr (lazy-nth (1- (read)) moves))))…and the actual play function:
(defun play-vs-human (tree)
(print-info tree)
(if (not (lazy-null (caddr tree)))
(play-vs-human (handle-human tree))
(announce-winner (cadr tree))))We have a neat lazy version of our game, but the AI will still have a problem with it: It is designed to look through an entire game tree to determine the best move for itself.
Now that the board is larger, this would be ridiculously intensive, so we must limit how far the AI can look.
We won’t be doing this by modifying the AI however… Merely by creating a function that limits the depth of the game tree it can see:
(defun limit-tree-depth (tree depth)
(list (car tree)
(cadr tree)
(if (zerop depth)
(lazy-nil)
(lazy-mapcar (lambda (move)
(list (car move)
(limit-tree-depth (cadr move) (1- depth))))
(caddr tree)))))With this new depth, we can change how far ahead the computer thinks ahead, so we can use it to emulate a “difficulty” in a way:
(defparameter *ai-level* 4)Using this, we can tweak our handle-computer function to use this
limiting function first:
(defun handle-computer (tree)
(let ((ratings (get-ratings (limit-tree-depth tree *ai-level*)
(car tree))))
(cadr (lazy-nth (position (apply #'max ratings)
ratings)
(caddr tree)))))With this all done, we can make a simple tweak to play-vs-computer:
(defun play-vs-computer (tree)
(print-info tree)
(cond ((lazy-null (caddr tree)) (announce-winner (cadr tree)))
((zerop (car tree)) (play-vs-computer (handle-human tree)))
(t (play-vs-computer (handle-computer tree)))))This computer will no longer play a perfect game, but we can improve it a bit with some heuristics:
(defun score-board (board player)
(loop for hex across board
for pos from 0
sum (if (eq (car hex) player)
(if (threatened pos board)
1
2)
-1)))This function’s job is to see how well a certain board position is, if the player in question is winning by a little, or a lot.
The better the situation, the higher the score.
The threatened function is not yet implemented, but it will
determine if a hex is in a position where it can be taken over or not.
Its definition follows:
(defun threatened (pos board)
(let* ((hex (aref board pos))
(player (car hex))
(dice (cadr hex)))
(loop for n in (neighbors pos)
do (let* ((nhex (aref board n))
(nplayer (car nhex))
(ndice (cadr nhex)))
(when (and (not (eq player nplayer))
(> ndice dice))
(return t))))))With these added heuristics, we can update get-ratings and our
rate-position function:
(defun get-ratings (tree player)
(take-all (lazy-mapcar (lambda (move)
(rate-position (cadr move) player))
(caddr tree))))(defun rate-position (tree player)
(let ((moves (caddr tree)))
(if (not (lazy-null moves))
(apply (if (eq (car tree) player)
#'max
#'min)
(get-ratings tree player))
(score-board (cadr tree) player))))And that’s that!
Though we can still make the game more efficient using something called “alpha-beta pruning”, where we trim the game tree further.
How Alpha Beta pruning works is that we remove branches that won’t affect the outcome of the minmax algorithm any. We do this by removing branches that we know the AI won’t look at because they are underneath a node that is guaranteed not to choose.
Minmax chooses the most optimal for the current player and the least optimal for the opposing player, so because we know this, we can discern that if there is a value in a tree below a higher value than the minimum we’ve already found for a minimum check, we know minmax won’t traverse that section of the tree, so we can prune it.
Vice versa applies for the max checks on a tree.
So, with that in mind, the suggested implementation for the max nodes is:
(defun ab-get-ratings-max (tree player upper-limit lower-limit)
(labels ((f (moves lower-limit)
(unless (lazy-null moves)
(let ((x (ab-rate-position (cadr (lazy-car moves))
player
upper-limit
lower-limit)))
(if (>= x upper-limit)
(list x)
(cons x (f (lazy-cdr moves) (max x lower-limit))))))))
(f (caddr tree) lower-limit)))The promised ab-rate-position will traverse a tree to get the
maximum values of its child nodes, and we use a list-eater to iterate
through all of the child nodes of the current branch of the tree,
which allows us to store the maximum value we can find in the tree
that doesn’t get eaten by a minimum opponent value.
Now lets look at the suggested implementation for the function concerned with the minimum value it can find:
(defun ab-get-ratings-min (tree player upper-limit lower-limit)
(labels ((f (moves upper-limit)
(unless (lazy-null moves)
(let ((x (ab-rate-position (cadr (lazy-car moves))
player
upper-limit
lower-limit)))
(if (<= x lower-limit)
(list x)
(cons x (f (lazy-cdr moves) (min x upper-limit))))))))
(f (caddr tree) upper-limit)))We could have combined these into one function, but this way is more educational because we can actually see what is different between the two functions.
With this in place, we also need to tweak our rate-position
function:
(defun ab-rate-position (tree player upper-limit lower-limit)
(let ((moves (caddr tree)))
(if (not (lazy-null moves))
(if (eq (car tree) player)
(apply #'max (ab-get-ratings-max tree
player
upper-limit
lower-limit))
(apply #'min (ab-get-ratings-min tree
player
upper-limit
lower-limit)))
(score-board (cadr tree) player))))This is the function that actually traverses the tree and performs
the min and max comparisons based on score-board at the lowest
point in the game tree we look at.
With this in place, we need to update the computer to handle the new pruning we implemented above:
(defun handle-computer (tree)
(let ((ratings (ab-get-ratings-max (limit-tree-depth tree *ai-level*)
(car tree)
most-positive-fixnum
most-negative-fixnum)))
(cadr (lazy-nth (position (apply #'max ratings) ratings) (caddr tree)))))And that’s it! We have a lazy and optimized version of Dice of Doom that can be played on a space that would be utterly impossible without our optimizations.