In my last post I mentioned that my Minimax algorithm would overflow whenever I tried to calculate moves on a 4x4 board. I attempted to solve this problem by converting the Minimax algorithm to a tail recursive algorithm. This worked fine, however, it was really slow. So, I needed to search for another way. Another apprentice here suggested that I pass in a depth limit to my algorithm. So, I refactored my original forward recursive algorithm and have it working. Through some trial and error I have found that in order to maintain unbeatably, the max depth must be at least 5 on a 3x3 board and 7 on a 4x4 board. So, here is my fast and scalable Minimax in Clojure,

(defn- forward [player board alpha beta game-state-fn max-depth depth]

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

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

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

(if (>= depth max-depth)
(scores :draw)

(loop [alpha alpha open-spaces (board/open-indecies board)]

(if (or (empty? open-spaces) (>= alpha beta))

(* -1 alpha)

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

(assoc-in board (first open-spaces) player)

(* -1 beta) (* -1 alpha) game-state-fn max-depth (inc depth))]
(recur (max score alpha) (rest open-spaces)))))))))

## No comments:

## Post a Comment