[Update: A big thanks to @ajlopez for linking to this post on Clojure Daily. If anyone has any feedback please feel free to ping me. The full code is here.]

Five months ago I wrapped up the minimax algorithm for my Ruby tic-tac-toe game and did my best to explain it without any code. I never ran through the code because, honestly, it wasn’t that pretty and I didn’t feel it communicated the intention of the algorithm as well as I hoped.

However, this past week I took on the algorithm in Clojure and although my functions aren’t optimized for performance yet, I think they are much simpler and hopefully somewhat clearer.

The goal of the minimax algorithm is to find the best move from a series of available moves. In order to do this you make all of the available moves and then hand it off to the scoring algorithm. If any of those moves result in a win or a loss than the algorithm returns the score. However, if none of those moves complete the game then you score all the next available moves for your opponent and assume that they will make the best one. If those moves don’t result in a win or loss then the board is handed back to the scoring algorithm, which now scores for the original player… and so on and so forth until all the scenarios have been played out and scored.

My Clojure solution came out like this:

(defn minimax-score [player opponent board depth]
  (or (value board player opponent depth)
    (let [values (map #(minimax-score opponent player
                  (place-move % (:piece opponent) board) (inc depth))
    (available-spaces board))]
    (best-score opponent values))))

(defn minimax-move [maxplayer minplayer board]
  (let [values (map #(minimax-score maxplayer minplayer (place-move % (:piece maxplayer) board) 1)
                    (available-spaces board))
        moves (available-spaces board)
        move-values (zipmap moves values)]
  (best-move move-values)))

In the minimax-move function I use map to call the minimax-score function on all of the available moves. Then I zipmap the moves to their scores and pick the move with the best score.

In the minimax-score function I take in a board with the two players and the depth, and then I either return the value of the board (which is based on the winner and the depth), or I find out all the values of the existing moves (calling the same minimax-score on each one) and return the highest value.

Although this code is nice and simple, unfortunately without optimization it still takes a while. If the computer has to make the opening move on an empty board it takes about 25 seconds to play out all the scenarios. Although that’s about three minutes faster than my unoptimized Ruby code, it’s still not acceptable. My next step is to try and take advantage of any built-in optimizations that the Clojure language may offer before using something like alpha beta pruning. It’ll be good to dive even deeper into the language.