Minimax
If you haven’t read my other entries on how I started this Tic Tac Toe adventure, I’ve included links to the previous blogs at the bottom of this post. This blog entry is all about the Minimax algorithm and how I learned it to build an unbeatable AI in Tic Tac Toe. I faced a lot of challenges getting to the end result, but ultimately it provided another stepping stone towards becoming an effective programmer.
What is Minimax?
My initial run-through of building out this game, I looked up how to build an unbeatable AI and came across the Minimax algorithm… I thought “OK, let’s wrap up the tents, this circus is leaving town”. It looked entirely too complex and complicated for what my peabrain could handle. Luckily, it wasn’t a requirement of the project and I was able to do without!
HOWEVER! In my rebuild of the game with Ruby, one of the challenges was to incorporate Minimax… Dun dun DUNNNN.
So what is it? It’s an algorithm that minimizes the loss of the worst-case scenario. It’s applied to the zero-sum game theory where for every situation involving a winner, there’s a loser. With games such as Tic Tac Toe or chess, there are moves that can be predicted and therefore measured. That’s not the case with Scrabble, where the predictability of what the opponent will choose to do is unimaginable.
In Tic Tac Toe, there are two players: X and O. Since I designate the computer as O, the computer(O) is the maximizing player. You can designate it either way as long as you remember which is which. I could just as easily have made O the minimizing player. What does all that mean?
Maximizing vs. Minimizing Player
Let’s say you have a board like so:
It’s currently player O’s turn, there are two options at play here, square 2 or square 8. As the maximizing player, I want to venture on the path that produces the highest result. Right now, there are no points only two paths. Let’s see what happens when you place the O in position 2.
It’s now X’s turn and when they place their token on position 8, they will win. This is to O’s extreme disadvantage, as the purpose of the game is to not lose. However, if O had chosen position 8 over position 2:
Then X has no choice but to pick position 2, which will result in a tied game (which fulfills the purpose of no losing). The computer has to walk through each of those scenarios and pick the path that it can benefit the most from. When the O chooses the path on the right, it results in a loss, so the option is assigned -10, whereas if the O chooses the left path, it results in a tie which is assigned 0. The maximizing player wants to choose the path that will lead to the highest optimal score, so the computer will choose the left path.
In the above situation, there are only one of two choices the computer has to make. Imagine the number of scenarios the computer has to go through at the very beginning of the game!
Assume that each square and circle represents a potential Tic Tac Toe board. From the top, the maximizing player has to choose the play that will result in the highest possible score, which in the picture above is -7. Towards the bottom, levels 3 and 4, we assume that the minimizing player is going to choose the play that will result in the lowest possible score, which is why it chooses 10 over +∞, or -7 over -5.
There are a number of ways to go about this, and there are many resources on how to achieve the same result. The method I chose to go with was to return the best_score. The minimax method would go through each of the open squares that a player could place their token. If there was no winner, the minimax method would take the new board and recursively call on itself until there was a winner or there was a tie. This method returns the best possible score for the computer, but that hardly helps the computer choose which square to choose.
The optimal_move method is pretty much the same as the minimax method, but it pulls the best_move once it finds the best_score from the minimax. Now the computer knows which move to play that will, at worst, result in a tie.
Challenges of Minimax
I had a really difficult time making any sense of Minimax. It seemed a very abstract concept to implement to a game that is somewhat simple. In my previous building of the game, I wrote out the logic and I could see the strategy of my own logic form the unbeatable level. You can’t really write out the logic of minimax and see the iterations of the logic (there are 255,169 unique games). I spent a day just staring at my screen, I was so lost in my own code and confused about what I wanted the method to return. Don’t get me started on recursion! It took a lot of step by step walkthroughs, pairing sessions and revisions. I know there are better ways of building this method, I didn’t factor in the breadth of the analysis, nor did I consider ways to prune.
More than anything, this was another lesson in learning a new concept and allowing myself time. I knew how to build the Tic Tac Toe game, I knew the bare bones syntax of Ruby, I knew what the end result looked like. I didn’t know minimax, but I’d been in this situation of “not knowing” before, so I was optimistic, until suddenly I wasn’t. I was hard on myself and doubtful of my ability to complete the challenge. But the strange thing is that all the tutorials I initially read and couldn’t understand were becoming clearer and less abstract.
All this to say if none of this minimax stuff makes any sense, it’s OK. It took me a lot of cycles of rereading tutorials, rewatching videos and relying on the advice of senior engineers to get through it. Good luck!
TDD Tic Tac Toe pt 1: TDD Immersion
TDD Tic Tac Toe pt 2: Building the Game
TDD Tic Tac Toe pt 3: Unbeatable