Edgardo Carreras | Blog

Tic Tac Toe in Clojure - Part 3 AI

August 25, 2021

Let’s build an unbeatable AI for the game tic-tac-toe! Let’s use the minimax algorithm commonly used in AI applications for zero-sum games.

This is the pseudocode for Minimax Algorithm

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

So lets start with determining if the node(board state), is terminal (game over). Well, we already have game-over? method, but we need to score the game for each player. In other words we want to score the game state for each player, we’ll return 10 for the player if they won, 0 if they haven’t, and -10 if they lost.

This is how the test look:

(describe "score"
          (it "scores 0"
            (should= 0 (score empty-board O))
            (should= 0 (score empty-board X))
            (should= 0 (score (assoc
                                [0 0] O [0 1] O [0 2] X
                                [1 0] X [1 1] X [1 2] O
                                [2 0] O [2 1] X [2 2] O)
          (it "scores 10"
            (should= 10 (score (assoc
                                [0 2] O [1 1] O [2 0] O)
            (should= 10 (score (assoc
                                [0 0] X [0 1] X [0 2] X)
          (it "scores -10"
            (should= -10 (score (assoc
                                 [0 2] O [1 1] O [2 0] O)
            (should= -10 (score (assoc
                                 [0 0] X [0 1] X [0 2] X)
(defn score [board player]
    (= player (get-winning-player board))
    (= (get-opponent player) (get-winning-player board))

It took a few iterations to get to implement the score. We were missing a lot of pieces of the puzzle for the score function to work. We needed a function to tell who was the winning player, and another function that return the opposing player.

Test and implementation of these utility functions.

(describe "get-winning-player"
          (it "should return X"
            (should= X (get-winning-player (assoc
                                             [0 0] X [0 1] X [0 2] X))))
          (it "should return O"
            (should= O (get-winning-player (assoc
                                             [0 0] O [0 1] O [0 2] O))))
          (it "should return nil"
            (should= nil (get-winning-player empty-board)))

(describe "get-opponent"
          (it "O"
            (should= O (get-opponent X)))
          (it "X"
            (should= X (get-opponent O)))
(defn get-winning-player [board]
  (->> player-symbols
       (map #(if (game-has-wining-play? board %) % nil))
       (filter identity)

(defn get-opponent [player]
  (->> player-symbols
       (filter #(not (= player %)))

All right, so now we have a first implementation of the scoring function, and some very helpful utility functions. Next we’ll implement the Minimax function.

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.

© 2024, Edgardo Carreras