(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.

## No comments:

## Post a Comment