# Tic Tac Toe in Clojure - Part 4 MiniMax Algorithm

August 26, 2021

Yesterday we started looking into implementing the Minimax Algorithm. We started with the scoring algorithm

```
(defn score [board player]
(cond
(= player (get-winning-player board))
10
(= (get-opponent player) (get-winning-player board))
-10
:else
0)
```

But our scoring algorithm should return `nil`

if the game isn’t over yet so we can keep recursing the minimax
until the game is over.

```
(defn score-board [board player]
(let [winning-player (get-winning-player board)]
(cond
(= player winning-player)
10
(= (get-opponent player) winning-player)
-10
(game-over? board)
0
:else
nil)))
```

Ok now we have a proper scoring function. Let’s move ahead with the minimax implementation.

Looking again at the minimax pseudocode:

```
function minimax(node, depth, maximizingPlayer) is
if depth = 0 or node is a terminal node then
return the heuristic value of node
if maximizingPlayer then
value := −∞
for each child of node do
value := max(value, minimax(child, depth − 1, FALSE))
return value
else (* minimizing player *)
value := +∞
for each child of node do
value := min(value, minimax(child, depth − 1, TRUE))
return value
```

Ok, so it took me a while to wrap my head around this recursive algorithm. My initial algorithm didn’t implement the depth of the recursion as I was trying to figure out the requirement of depth I found out the hard way. Say the algorithm finds a winning play in the next play, without the depth implementation the minimax would score the immediate winning play the same as a potential winning play down the line.

Ok so let’s write some test for this.

```
(describe "minmax"
(it "returns 10"
(should= 10 (minimax
(assoc
empty-board
[0 1] X [0 2] X)
X
0
true)))
(it "returns -10"
(should= -10 (minimax
(assoc
empty-board
[0 0] nil [0 1] X [0 2] X
[1 0] O [1 1] O [1 2] X
[2 0] X [2 1] O [2 2] O)
X
0
false)))
(it "returns -9"
(should= -9 (minimax
(assoc
empty-board
[0 0] X [0 1] nil [0 2] O
[1 0] nil [1 1] O [1 2] nil
[2 0] X [2 1] nil [2 2] X)
O
0
true))))
```

Notice that if we score the board where X is about to lose we get a -10, if we score a board where X is about to win we get a 10. We also test that we score a -9 when O is about to lose in the next two turns.

Here’s our minimax code:

```
(defn minimax [board player depth maximizing?]
(let [score (score-board board player)
moves (get-empty-indexes board)]
(cond
(not (nil? score))
score
(true? maximizing?)
(->> moves
(map #(play board % player))
(map #(minimax % player (inc depth) false))
(apply max)
(#(- % depth)))
:else
(->> moves
(map #(play board % (get-opponent player)))
(map #(minimax % player (inc depth) true))
(apply min)
(#(+ % depth))))))
```

Ok lets now create a function that allows us to use this function lets call it `get-best-move`

.

Lets start with some sensible tests:

```
(describe "get-best-move"
(it "should return best move"
(should= [0 0] (get-best-move
(assoc
empty-board
[0 0] nil [0 1] X [0 2] X
[1 0] O [1 1] O)
X)))
(it "should return best move"
(should= [2 2] (get-best-move
(assoc
empty-board
[0 0] X [1 1] O)
X)))
(it "should return best move"
(should= [2 2] (time (get-best-move
empty-board
X)))))
```

In the test I check that the `get-best-move`

not only returns the winning play but also the best defensive play.

Here is the implementation:

```
(defn get-best-move [board player]
(loop [moves (get-empty-indexes board)
scores {}]
(cond
(empty? moves)
(key (apply max-key val scores))
:else
(recur
(drop 1 moves)
(assoc scores
(first moves)
(minimax
(play board (first moves) player)
player
0
false))))))
```

For each move available I score them and return the key with the maximum value.
I really love how `max-key`

made this so much easier.

So our algorithm works but… It is really slow when the board has a lot of empty spaces!

```
(time (get-best-move empty-board X))
;"Elapsed time: 154998.704009 msecs" 🤯🤯🤯🤯
```

Next we’ll look into how to optimize our algorithm. We’ll look at utility tree and alpha-beta pruning.

<3

#### Want to hear more from me?

Signup to my newsletter!

#### CarrerasDev Newsletter

A free email newsletter on how to create high-performing development teams.

Written by **Edgardo Carreras**.