Negamax in Clojure
This morning I realised that I’ve written a blog post after getting an unbeatable computer player to work in every language I’ve done Tic Tac Toe in (proof: First use of minimax, Minimax in Java, Negamax in Ruby). Now that I’ve got a working solution in Clojure, it is time to blog it.
I was a little worried about implementing minimax in Clojure, as in some of my previous implementations I’ve relied on state, a luxury we don’t have in Clojure. In functional programming you pass data into a function, and it returns different data. That is all you’ve got. If you don’t use your data that you get back immediately, it is gone. I thought my implementation would be quite different, but it ended up being quite similar to what I’ve done before.
This function is called with the choose-space function (line 42) with the board state passed in. The board state is a hash-map with the size of board (ie. number of rows/columns) and a list of moves in sequential order of a zero indexed board (so position 0 is the top left, position 4 is the middle, position 8 is the bottom right) eg. { :size 3 :board [4] } (more info).
choose-space calls negamax and passes in the board-state, a starting depth of 0, a starting colour of 1, and the computer’s marker (X or O). This marker is determined by the state of the board on the initial function call — if there is an even number of moves (0 is considered even) it is X, if it is an odd number of moves it is O. In this implementation, X always goes first.
negamax first checks if the game is over — if so it assigns a score to this outcome based on a won game and the depth of the recursive algorithm. The fewer emulated moves until the player can keep the opponent from winning the better. This score is multiplied by the colour which is only ever 1 or -1, depending on which player has made the last move in it’s emulated scenario.
If the game is not over the score-spaces function is called. This takes each available space on the board, and emulates a move there. It then recursively calls the negamax function again.
Once the recursive call has finished, assuming the depth is not zero, negamax returns the highest of the potential scores (assuming the player it is playing against is also unbeatable. This is the negamax-score. Clojure has a built in function called zipma which takes takes two lists, and ‘zips’ them together into a map, with the first list as the key, and the second as the value. In this instance the first list is the list of available spaces, and the second is the corresponding negamax scores.
The one time that the depth is zero and the game is not over negamax chooses the space with the most chance of minimising a loss. This is what is returned by the choose-space method and ultimately the choice that the computer makes.
I’d actually started out using the Minimax algorithm, but then I started thinking about Alpha Beta Pruning and decided to rewrite it. This was actually painless, and my tests surprisingly stayed green. There isn’t too much of a difference between the two.
In my ruby experience, alpha beta pruning is significantly easier on Negamax, but it isn’t in Clojure. Clojure doesn’t have an obvious way to return from a function call early, the way you can in some other languages by just putting a return statement in.
My mentors have let me know that if I use reduce and reduced I can do exactly what I want, so now I just need to find the time to do this. I’m really excited that I got this to work, and can’t wait to get it working with Alpha Beta Pruning!
