How minimax AI anticipates your every move and beats you at your own favorite game

A few days ago, my friend challenged me to a game of chess. Normally I would decline, but when he suggested that his 6-year-old sister could beat me with her eyes closed, I had to take him up.

There was just one slight problem: I had played about 3 games of chess before and he had played several hundred. Regardless, I accepted his request. After a grueling 20-minute game, I actually ended up winning💪.

You may be asking how I pulled off such an impressive feat.

Was it through sheer will and absolute focus?
Nope.

Was it due to some divine intervention?
I don’t think so.

Was it a result of the AI chess app on my phone that I had hidden on my lap that I set to maximum difficulty, then plugged my friends moves into the AI and moved my pieces in real life based on the moves the AI made on the app?
Yeah, probably 😁.

We live in a time in which AIs are able or will soon be able to perform many tasks better than humans can.

As evident in recent news (like the widely spread news story about Google’s AlphaGo beating the best Go player in the world in 2016), AIs are especially good at playing board games (chess included!)

You may be wondering how exactly computer programs can be so good at something as complex as chess, Othello, or Go. There are a few answers but one of the simplest and most elegant algorithms is called the Minimax Algorithm.

What is Minimax: A demonstration by Min and Max️

So what does the minimax algorithm actually do? It’s easier to understand with an example. Let’s look at a simple game. There are two players. We’ll call them Min and Max. We’ll use the tree chart below for our game.

Let’s imagine a little playing piece sitting in the node at the very top of the chart. Max goes first and gets to decide which of the attached nodes to move the piece too (Can move the piece along the path labeled “L” to the left circular node or along the path labeled “R” to the right circular node). From there Min moves the playing piece to one of the attached nodes on the bottom layer.

Max’s goal is to have the playing piece land on the largest number it can, while Min’s goal is to have the playing piece land on the smallest number it can.

Look at the chart and imagine you are playing as Max. Will you move to the left or to the right to achieve your goal?

Maybe you realized that the best option for Max is to move to the left. Why? Because you know that Min will choose to move to the lowest of the two options it is given. Therefore, if you (Max) choose to move to the right, then Min will choose the lowest of its two options and the playing piece will end up on 2. However, if you move left, then Min’s lowest option is 3 and that is where the playing piece will end up. Since Max wants to maximize the number at the end, it is best for Max to move left.

This example illustrates the basic concept behind the minimax algorithm. If a computer program were playing against you in some game, the program would try to maximize its own success by making decisions (or moves) that take into account the fact that you will try to minimize its success.

That may sound a little bit confusing right now, but don’t worry, you will understand soon.

How Does Minimax Work: A look into the mind of minimax as he plays tic tac toe

We’ve looked at the basic idea of minimax and the thought process involved. Now it’s time to look at how we actually make use of the thought process.

For the sake of example, let’s say Minimax AI is currently in the middle of a tic tac toe game. The board looks like the uppermost board on the picture below and Minimax is playing ❌(Minimax’s turn to go next).

Let’s take a look at what’s going through Minimax’s head as they make a decision as to where to place an ❌.

Minimax: What are all the possible moves that I can make?

In this first stage, the minimax AI tries to figure out what all the moves it can possibly make are. We can see in the second row of tic tac toe boards each of the three moves that minimax can make. Now minimax at least knows what moves to choose from.

Minimax: What moves can my opponent make in response to those moves that I can make? What moves can I make in response to those? Etc.

In this next step, minimax continues to map out the possible states of the game my determining what moves each player could make based on the other player's potential moves. Now, minimax has mapped out all the possible sequences of moves for the remainder of the game (as seen on the chart above).

Minimax: Which of the end states is better for me?

Here is where the real magic starts to happen. Minimax needs to figure out which of those ending states is optimal for him. In order to do this, minimax makes use of heuristics — essentially rules or shortcuts preprogrammed in to help him achieve his goal (in this case winning a game of tic tac toe).

In this example, minimax will assign a value of 1 to a game state in which there are 3 ❌’s in a row (since that would mean he won), and a value of 0 to game state with 3 ⭕’s in a row or no 3 in a row (since that would mean he drew or lost). You can see this on the chart above on the BOTTOM row (don’t worry about the numbers on the other rows yet).

Minimax: Which move should I choose NOW that guarantees me the best outcome LATER?

This is the last (and arguably most important) step where minimax runs the algorithm that we talked about before and determines where to move. So far, we have essentially reduced the space of all states in the diagram above to the diagram below. Each of the nodes on the diagram below represents a state, and the numbers at the bottom represent the values we have assigned to the last states.

This looks familiar, right? Now we can just repeat that same process we did before to see what's the best move for Max. Think back to the number game we played before and think about what Max’s best move here is. Are you starting to get the hang of this?

If you complete the game above as if you were Max (and you are trying to get the highest score), you would choose to go to the rightmost branch. Now if we look at the chart from before, we can see what it actually MEANS to say that we will choose the “rightmost branch.”

So as you can see, based on the minimax algorithm, the AI will choose to put an X in the bottom left corner and eventually win the game! Pretty cool right?

How Can You Use Minimax: What are the applications and limitations of the algorithm?

Along with tic-tac-toe, minimax has numerous other applications. However, although minimax is a world-class tic-tac-toe player, there are certain limitations to the power of the algorithm.

What’s Minimax Good At?

• As we saw in the example above, minimax is great at tic-tac-toe and other simple games
• Due to the nature of the algorithm, minimax excels at any 1v1 competition where there is a specific goal determined for both players
• Minimax can actually be used for more complex games like chess!

The Limits of Minimax & Where to Start Learning More

Minimax clearly excels at games where the winner takes all, also known as zero-sum games. However, there are many games that are not as definite do not have strict winners and losers (called non-zero-sum games). Minimax is not great at these games, but another interesting related algorithm called Maximin is great at these. I would suggest reading about it if you are interested in the topic.

Furthermore, you might imagine that when minimax AI has to look multiple moves ahead in a game like chess, the tree of moves that it has to look at would be incredibly large. This is where a technique called alpha-beta pruning comes in. This technique greatly increases the efficiency of the minimax algorithm and is super interesting to read about.

I hope you now have a basic understanding of how Minimax AI actually works👍. Minimax is great at playing any turn-based 2 player games, especially where there is a predefined goal for the AI to work towards. Although Minimax isn’t ideal in every situation, it’s certainly a viable algorithm and is quite elegant!

If you enjoyed this article, you might want to check out my last article: https://medium.com/altcoin-magazine/will-quantum-computing-destroy-blockchain-23842baafaca

If your interested in AI, follow me on medium and feel free to add me on LinkedIn as well: https://www.linkedin.com/in/adam-majmudar-24b596194/

Thanks👌