It took some time, but I have finished the Minimax player. I’ve tested it and it seems to be unbeatable, as you would hope. The main reason it took so long is because it is pretty slow, at least in the original naive version.
The code for the version I am discussing is tagged blog-928.
I won’t discuss the minimax algorithm in too much detail here except to say that I keep a note of the depth of the tree for two reasons.
- So I can have an imperfect machine that can’t analyse the whole noughts and crosses game space.
- To adjust the scores based on depth. If the player has a choice of two ways to win, I want it to take the quickest victory. If there is no way to win, I want it to play for the draw but take as long as possible to get there. (NB as I was writing this, it occurred to me that all draws are exactly nine moves long, so prolonging a draw is nonsense.)
My initial naive effort was far too slow. In debug mode, it took more than 50 seconds to figure out what its first move should be. It was a lot faster in release mode but still took several seconds to make its first move. Subsequent moves were quicker because the depth and breadth of the tree was smaller.
I used the time profiler to to shave off some seconds by optimising the function that calculated if anybody had won. This saved about 33% of the time to calculate the first move. We were still at over 30 seconds in debug mode. After this, it didn’t seem obvious where I could find more time, at least not using the time profiler, so I started looking art the algorithm itself (actually, any good programmer will tell you that using a better algorithm will always give much better results than micro optimising).
The first thing I looked at was how I evaluated each move. With a given noughts and crosses grid, I created a list of the results of each of the nine possible moves and then categorised them.
- illegal moves were discarded
- if there were any wins, one was immediately returned as the best move
- if the result was a draw, I returned it – you can only get a draw on the very last move
- the rest of the moves were “carry ons”, so each one was evaluated by recursively calling minimax on the grid resulting from the move.
I first tried filtering the nine possible moves by discarding all moves that were not on an empty square. This had a huge effect: it cut down the time needed to make the first move by another 50%.
Next, I hardwired the possibilities for the first move to be either muffle, top left corner or top middle square. All other moves are equivalent to one of these but rotated. This saved about another 70%.
Finally, I created a means of transforming a grid by a rotation so that I could transform a game where only one move had been made into a game where that move was either in the centre, top left or top middle. That way, I could eliminate several possibilities in each case as being reflections of other possibilities. For example, if the first move was in the centre, the only possibilities you need to check for the second move are top left and top middle. All the others are just rotations of one of those two. This gave me about another 30%. In debug mode, the first move was down to 3 seconds. In release mode, it appears almost instantaneous.
We also now have a user interface so you can play games against the machine. The video shows two games of me against Minimax. In the second one I make a deliberate mistake so as not to hurt its feelings.
Sincere Flattery 