Tree Traversal with Tail Recursion

Anyone who has ever tried to build an AI for a Tic Tac Toe game has come across the Minimax algorithm. This algorithm simply iterates through the children of a node and returns the maximum value. This is perfect for Tic Tac Toe because it will iterate through every possible board and return the highest scoring option. This allows you to build a AI that is unbeatable. By design this algorithm uses forward recursion to traverse the tree of boards. This allows you to see all the options available to you and then choose the best one. On a normal 3x3 Tic Tac Toe board, this will work fine. However, when I tried to run the forward recursing Minimax on a 4x4, I quickly received a wonderful stack overflow error. So, lets take a look at it.

(defn- forward [player board game-state-fn]

  (let [state (game-state-fn board)]

    (if (not= state (game-states :playing))

      (* -1 (get-state-score player state))

        (loop [best-score (scores :lose) open-spaces (open-indecies board)]

          (if (empty? open-spaces)

            (* -1 best-score)

            (let [score (forward (get-other-player player)

              (assoc-in board (first open-spaces) player) game-state-fn)]

              (recur (max score best-score) (rest open-spaces))))))))

Note: this is a very naive implementation. It does not apply a heuristic score or perform any sort of branch trimming. Nonetheless, it runs quickly on a 3x3 board. However, with a 4x4 board, it will overflow. My first idea was to try memoizing the recursive call. This did improve the speed of the calls significantly, but it still crashed on a 4x4 board. So, it looks like the best option is to convert this into a tail recursive algorithm. Essentially, we are attempting to perform a in order traversal of an unbalanced tree. Unfortunately, with the current implementation, we have no way to return to our parent once we reach a leaf node. So, I believe we are going to need a basic data structure to hold our tree. Something, like this should suffice.

Tree
  :parent
  :current-node

  :children
  :best-score

This simple object will maintain our tree structure and allow us to traverse the tree without losing our parent. In Clojure this looks like,

(defrecord BoardTree [board parent children best-score])

Using this data structure, we can implement the tail recursive version of Minimax.

(defn- tail [player current-node game-state-fn]

  (if (and (= nil (:parent current-node))

    (= 0 (count (:children current-node))))
      ;base case
      (* -1 (:alpha current-node))
      (let [state (game-state-fn (:board current-node))]
        ;determine if this is a leaf node
 (if (not= state (game-states :playing))
   ;leaf node
   (if (= nil (:parent current-node)) ;it's a leaf and a root
     (* -1 (get-state-score player state))
     (recur (get-other-player player)

              (get-parent-with-max current-node

              (* -1 (get-state-score player state))) game-state-fn))

           ;return from child to the parent
    (if (empty? (:children current-node))
      (recur (get-other-player player)

               (get-parent-with-max current-node

               (* -1 (:alpha current-node))) game-state-fn)
      ;create a new child board and take the child out of the parent's list of children (a.k.a. marking it as visited)
      (let [new-board (assoc-in (:board current-node)

               (first (:children current-node)) player)

                 old-board (update-in current-node [:children] rest)]
        (recur (get-other-player player)

                 (BoardTree. new-board old-board

                 (open-indecies new-board) 

                 Float/NEGATIVE_INFINITY Float/POSITIVE_INFINITY) game-state-fn)                 ))))))

As you can see, this method is slightly more verbose. If this is a little overwhelming, here's the pseudocode version,

tail (current_node) ->
  if current_node.parent is null and all current_node.children are visited:
 return best value of my children
  
  if current_node is leaf:
    if current_node.parent is null:
      return -1 * score
    else:
      current_node.parent.best_score = max(-1 * current_node.best_score, current_node.parent.best_score)
      tail(current_node.parent)
  else:
    if all current_node.children are visited:
      current_node.parent.best_score = max(-1 * current_node.best_score, current_node.parent.best_score)
      tail(current_node.parent)
    else:
      tail(current_node.children.first)

Unfortunately, during my testing I discovered that the tail recursive version is significantly slower. However, it will run on a 4x4 board with out crashing.