Minimax is one of those things that is always going to haunt me. I’ve done it multiple times and when I think I got it I realize I messed up and it isn’t as good as it needs to be–it fails in some edge case that I did not think of.

Though, this time, this time I think I’ve got it down (with 99.99repeating certainty).

For this attempt at Minimax, I broke up the functions into pieces and used hash-maps to make everything more readable, which was a problem as I got confused as to whether I was on the max or min side of things. By breaking all these junctions into functions and names with clearly defined paths, I could trace it easier and test it throughout the process. I took inspiration from a variety of different people’s minimax codes and pseudo-codes I researched throughout the process to figure out the optimal way of doing Minimax. Together, mixed all together with my own changes and tweaks, I am certain as I can be that I’ve arrived at the correct solution.

Here is my (current) code (rest here):

(defn get-available-locations [board]
  (vec (filter number? board)))

(defn player-markers [ai-marker opponent-marker]
  {:ai ai-marker :opponent opponent-marker})

(defn get-score [board player-markers depth]
  (let [winning-player (gf/game-is-won board)]
  (cond (= winning-player (:ai player-markers)) (- 100 depth)
        (= winning-player (:opponent player-markers)) (- depth 100)
        (gf/game-is-tied board) 0)))

(defn apply-max-or-min [minimax-map player-markers current-player-marker]
  (if (= current-player-marker (:ai player-markers))
      (apply max minimax-map)
      (apply min minimax-map)))

(defn get-next-player [player-markers current-player-marker]
  (if (= current-player-marker (:ai player-markers))
      (:opponent player-markers)
      (:ai player-markers)))

(defn minimax [board player-markers current-player-marker depth]
  (if (gf/game-is-won-or-tied board)
    (get-score board player-markers depth)
    (let [next-player (get-next-player player-markers current-player-marker)]
      (apply-max-or-min (map #(minimax (gf/mark-board-location board % current-player-marker)
                                              player-markers next-player (inc depth))
                              (get-available-locations board))
        player-markers current-player-marker))))

(defn scores-for-available-locations [board player-markers]
  (pmap #(minimax (gf/mark-board-location board % (:ai player-markers)) player-markers (:opponent player-markers) 1)
            (get-available-locations board)))

(defn assign-scores-to-available-location [board player-markers]
  (zipmap (get-available-locations board) (scores-for-available-locations board player-markers)))

(defn get-best-move [moves-and-scores]
  (key (apply max-key val moves-and-scores)))

(defn best-move [board ai-marker opponent-marker]
  (get-best-move (assign-scores-to-available-location board (player-markers ai-marker opponent-marker))))

How do I know this works? I don’t

I know this because I added a mass plethora of tests on the smaller functions I could effectively test. For the best-move function, the function that wraps it all together and spits out the move we really want to know works, I tested all the critical board permutations I could think of, from winning to blocking to general intelligent moves for the first turn or two, which I had been neglecting in previous iterations of the tests for it. Basically analyzing it being intelligent in the beginning and selecting win/block moves in a given scenario. Then I played it many times, because my ability to think up edge-cases in tic tac toe is sorely lacking. I tried out all the cases it had failed on in the past and it actually worked this time. And I lost many times and tied even more. The tests from the previous iterations that failed passed. All together, created my certainty.

It works. I feel decent.