It turns out that for a two-player board game, a simple method exists to model what an opponent will do. We simply accept the truism “What is good for my opponent is bad for me.” This means we can use the following approach to model a move for the opponent:

This algorithm for estimating what an opponent will do is identical to the one used for the primary player, except that in step 3, we pick the move with the minimum instead of maximum rating. The benefit of this approach, called the minimax algorithm, is that we use the same point ratings when working out the opponent’s moves that we use for the primary AI player, but then just tweak the third step a little to adjust.

This is crucial: It turns out that if we can avoid calculating separate ratings for ourselves as for our opponent in the game, then searching down the game tree for good moves becomes dramatically easier and faster.

Now we’re ready to put the minimax idea into practice, like so:

(defun rate-position (tree player)
    (let ((moves (caddr tree)))
     (if moves
        (apply (if (eq (car tree) player)
                #'max
              #'min)
              (get-ratings tree player))
       (let ((w (winners (cadr tree))))
          (if (member player w)
             (/ 1 (length w))
           0)))))

The rate-position function generates a numeric point rating for a given branch of the game tree. In order to do this, we first need to figure out if there are any moves available from the given position (that is, the current move is not an ending move in the game).

If moves are available, we’ll need to look at all the subsequent moves to decide how to rate the current position. We accomplish this by calling get-ratings , a function that will return the point rating of each follow-up move. As per minimax, we will then pick either the best (max) or worst (min) rating of all the follow-up moves, depending on whether the move being rated is for the AI player or its opponent.

If, on the other hand, there are no follow-up moves, we’ll need to check who the winner is for the current board position . If the player isn’t among the winners of this position, we can give the position the minimum rating of 0 . Otherwise, we’ll divide one by the number of winners to determine our rating . By doing this, we also give a meaningful rating for ties. If the player is the sole winner, the rating, using this formula, will be the maximum value of 1. For a two-player tie, the rating will be a sensible 0.5.

Here is what the get-ratings function looks like:

(defun get-ratings (tree player)
  (mapcar (lambda (move)
          (rate-position (cadr move) player))
        (caddr tree)))

This function simply maps rate-position across each available follow-up move for the given branch of the tree.

Earlier, we wrote a function called handle-human that interacted with a human to decide on a move in the game. Here is an analogous function, handle-computer, that interacts with our AI player to choose a move:

(defun handle-computer (tree)
   (let ((ratings (get-ratings tree (car tree))))
     (cadr (nth (position (apply #'max ratings) ratings) (caddr tree)))))

This handle-computer function is quite straightforward. First, we get the ratings of each available move . Then we pick the move that is rated the highest .

Finally, let’s create a function that handles the main loop for playing against the computer. This one is analogous to our earlier play-vs-human function:

(defun play-vs-computer (tree)
   (print-info tree)
   (cond ((null (caddr tree)) (announce-winner (cadr tree)))
       ((zerop (car tree)) (play-vs-computer (handle-human tree)))
       (t (play-vs-computer (handle-computer tree)))))

As with the play-vs-human function, play-vs-computer first prints out information about the current state of the game . If no more moves are available, it then calls the announce-winner function .

Next, we need to check who the current player is. By convention, we’ll have the human be player A (player 0). If the player number is 0, we call our old handle-human function to let the human decide on her move . Otherwise, we treat the player as an AI player and use the handle-computer function to decide on a move .

We have now written a fully functional AI engine for Dice of Doom!

The following is an example game playing against the computer AI. The computer plays an optimal game and wins.

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