Optimizing Minimax

Take a look at the following game. Where do you think Minimax will play? Hit “Next move” to find out.

Feeling unsure about you sanity? Is that not what you expected? Let me help you out.

Simply, the AI sees all potential moves from this point as wins for “O”. It chooses the next move arbitrarily from the list of all possible moves. A more “natural” play would be for the AI to prolong the inevitable defeat.

The depth feature is a new addition to the minimax algorithm that implements this. The depth variable tracks the number of turns it will take to reach a particular end state. This value is then used to lead the AI into trying to win games as fast as possible and lose games as slow as possible. This is how it applies the values:

First from the perspective of the maximizer and if the potential game is a positive value (so all paths lead to a win), then the minimax will subtract the depth from the score. Therefore, given a sweep of +10 scores for winning games, the smallest depth value game will be the game that is left with the highest value and so be the game that the AI moves toward. 

If the game is a losing game, minimax will instead add the depth to the score. This means that the highest value amongst a group of losing games will be the one with the  greatest depth. 

This process is the same for the minimizer but with the subtraction of the depths and the addition of the depth reversed.