Friday, November 11, 2011

Minimax Depth

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