Breaking Down Minimax
This blog post is a documentation of how I wrote (read: fixed) my minimax algorithm for Clojure tic-tac-toe. I had written it and believed I had figured it out, but it took quite a few iterations before I was able to troubleshoot the issue. Since this is not an intro to minimax (and there are many other blog posts that do an excellent job explaining — see here and here), I’m going to operate out of the assumption that you know what it does and how to generally implement it!
As a primer to how I’ve organized my code, check out the game’s namespaces and their relationships (see diagram below). The direction of the arrow signifies dependency. As you can see, `Game` serves as the high-level module (it is the entry point, after all) and `Board` is one of the lower-level modules. Nice rainbow effect.
(ns tic-tac-toe.computer-player
(:require [tic-tac-toe.board :refer [get-empty-cells
mark-cell]]
[tic-tac-toe.game-state :refer [get-winner
switch-player
tie?
win?]]))(declare score-moves)
At the top of each file, I declare namespace and require methods from other namespaces. Rather than having access to all of methods in `board` and `game-state`, I am only requiring the ones I need. The reason why I’m requiring these two namespaces is purely for the minimax algorithm, which emulates an actual game between players and scores them based on whether they result in a win or draw. After all, we’re trying to create a smart AI player who has the ability to project the best move!
You’ll also see that I wrote `(declare score-moves)`. According to ClojureDocs, using `declare` defines a variable name with no binding, making it useful for forward declarations. Since I call `score-moves` on line 40 before defining it on line 44, this is helpful.
See below for my minimax code (you can also see it here, if you want to read it with the line-by-line description further along in this blog post). By no means is this perfect; it’s definitely a work-in-progress and I’d love to see how I can tighten this:
Lines 1–3: This method checks to see if the player’s marker matches the computer’s marker.
Lines 5–10: We’re getting into minimax territory, but this method only runs if a win on the board has been verified. It calculates a score of a winning move for the computer player. If the winner is the computer, it will deduct the depth number (in other words, the number of turns that have passed) from 10, a rather arbitrary number. If the winner is the opponent, it will deduct 10 from depth, which will most likely result in a negative or really low number. The reason why we have depth is we want to optimize for the quickest win. The higher the depth number, the more number of turns, the lower our score.
This is what my 3x3 tic-tac-toe board looks like:| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
Lines 12–16: This method sorts through the hash-map of keys and values representing the empty/available cells and scores, respectively. If the current player is the computer, it will return the key-value pair with the highest value. Otherwise, it will return the pair with the lowest value and look something like this `[1 10]`, with 1 being the cell and 10 being the score.
Lines 18–20: This method returns the score, which is the value of the pair. If the pair was `[1 10]`, it would return 10.
Lines 22–24: This does the same thing as the above method, except it returns the cell (I call it a move), which is the key of the pair. If the pair was `[1 10]`, it would return 1.
Lines 32–27: I am talking about this method first because it may make sense in light of `get-score`. In `score-moves`, we are build a hash-map of moves and scores. What’s really cool about Clojure is you’re able to call multiple functions and assign them into their respective variables through `let`. As you can see, we’re using `get-empty-cells` to get all of the available moves and storing them into a vector called `moves`. The current player is determined by the first element in the `players` collection. To get each move’s score, we pass in `moves` into a higher-order function (`map`) and iterate through each move — marking the appropriate cell. Once done, we use this nifty function called `zipmap` which takes two vectors and make them into a hash with corresponding values. (I know, how glorious!).
For example:
(def moves [1 2 4 6])
(def scores [10 9 7 5])(zipmap moves scores)
=> {1 10, 2 9, 4 7, 6 5}
Lines 26–30: This method is the heart and engine of minimax. This is where the scoring happens based on the cell number. If the board that is passed in has a win, then it calls `calculate-win` which we’ve covered. If the board has a tie, the score is a 0 since there is neither a win nor loss. Otherwise, it starts exploring intermediate values. The way it does this is by recursively calling `score-moves` and getting the best score out of all of the possible game states. Note that I am switching the player and incrementing the depth level by one each time `score-moves` is called. This was my original error; I did not filter out the best score and was not getting a fully-operating minimax.
Lines 39–44: This is the entry point to the minimax algorithm! Here, I am setting variables such as the depth, the current player, and calling `score-moves` with appropriate arguments passed in. In the body of the function, I call `best-move`, passing in the current player and hash-map of scored moves. This, as you may recall, will return the move or cell number. You should note that if there are multiple moves with the same score in the hash-map, it will return the last one.
And congratulations, you survived minimax! For extra credit, you can incorporate memoization to expedite the game. This blog post was super helpful. TL;DR: Clojure has a built-in function, aptly named `memoize`, to store the results of function calls and return the cached result. You can do it by adding one line of code.
