When you hear about a computer thinking a hundred moves ahead, or twenty or whatever, what exactly do you imagine that it is doing? How does knowing all the possible moves help it win? Even if the computer knows what all the possible moves are from a given move, how does this help it decide what to do? There are a lot of possible answers to these questions, but a lot of them make use of an algorithm called MinMax. Said algorithm is going to be the topic of discussion today.
The principle idea of MinMax is incredibly simple. The title says it all. The MinMax algorithm will choose the choice which minimizes the maximum possible value for your opponent. That is to say, you make the move that will make your opponents best move as bad as possible. You look at what the game is like after each different move you could make, and you choose the move that gives the opponent the worst options. If the game only lasts two moves, one move for you and one move for them, then this is easy, but if its like most games, and lasts longer than two moves, then we need some way of figuring out what the opponents best move is. Thankfully, we have this great algorithm called MinMax that can help us out with that. So, in order to find out what the opponents best move is, we assume the opponent is also using MinMax, and that the best move for them, is the one that leaves us with the worst possible best move.
This might sound a bit confusing, so lets break it down with a few simple examples. Lets pretend we have a really simple game. It lasts three moves. You go, then your opponent, then you go again. The game takes place on a very simple board, with only five spaces, all in a line. Each space has a number on it. There is a single piece, and each turn the piece can be moved one space, or kept still. The piece starts in the very middle, and when the game ends, you get a number of points equal to the number on the board where the piece is. You want as many points as possible, your opponent wants you to get as few. The board looks like this [10,-10,0,-1,1]. So the piece starts on the zero square, and can move left or right each turn. The first choice then would be to either stay on zero, go to the negative ten, or go to the negative one.
So, lets start with the MinMax algorithm. We want to pick the move that minimizes our opponents best move. We need to know what our opponents best move is if you go to the -10, what it is when we go to the negative 1, and what it is when we stay on the zero. So, for each option, we pretend like we did it, then look at what our opponent would do.
If we go to -10, our opponents will then use MinMax to find the best move. The opponent’s choices are to go to the 10, stay on the -10, or go to the 0. They will choose the move that leaves us with the worst possible best move. So lets look then at their first choice, to go to 10. If they go to 10, then on our last turn we have the option of staying on 10 or going to -10. Obviously our best move would be to stay on 10. So, if they go to 10, then we get 10 points. If they stay on -10, then on our last turn we have to choose between 10, -10, 0. Again, we are going to choose 10. Finally, if the opponent moves to the 0, then our options are -10, 0, -1, which means we will pick 0. So our opponent wants to minimize our best moves value, so they will choose to go to 0, because that move makes our best move 0, while the other two moves make our best move 10.
Now we know what our opponent is going to do if we go to -10. We then repeat that procedure for staying still, and going to -1. It turns out this is a really terrible game, because our first move doesn’t matter at all. All three moves will end up having the opponent move us back to 0. As such, there is no optimal move for our first move and we can pick one arbitrarily. Then our opponent will make the best move from their position, and we end it by going to 0, which will always be the best move for us. Its a game that will always be a tie if both players play to their best, just like tic-tac-toe.
Now that we have seen an example of how it works, you can kinda see how it might work in a longer game. Assuming you have the power to check all the possibilities, the MinMax algorithm will always find the move that puts you in the best position you can get at the end of the game. The problem of course is having the computation power to do that. In our little tiny game, we only had 3 options each turn, and only 3 turns, but it still took a paragraph or so to write out all the different ways that game could play out. As the number of turns one has to look ahead increases, the computational complexity increases exponentially, making it almost impossible for even a really good computer to look more than a dozen or so moves ahead in a reasonably complex game. If you can’t look ahead to the end of the game, how do you decide which moves are good or bad in MinMax then? In our example game we were able to MinMax all the way to the final score and work our way back up from there, but if we are applying this to Chess or something, and twelve moves in the future no one has won or lost, how do you use this?
The answer is something called a heuristic. A heuristic is like a mathematical guess. Its turning a situation that you don’t understand perfectly and turning it into a number. In Chess, if you wanted a number to determine how good you were doing, you could use pieces captured as a heuristic. A game where you have taken three pawns is better than one where you have taken one. A game where you took a knight and bishop is better then one where you only took a bishop and two pawns. You can assign the captured pieces point values, and when you get as deep as you can go, maybe six or twelve moves in, then you just use the heuristic as your point value. Obviously if the game will end in the next twelve turns this will override the heuristic, and you will use the real values, but once the computer has thought as deeply as it can with MinMax, it has to pick a value to compare the different possible game positions, in order to decide what is a good place or a bad place to be. These are not perfect, and it can lead to the computer making bad decisions if the opponent understands the heuristics and could manipulate them somehow, but its generally the best that can be done.
Actual competitive programs are generally a bit more complicated than this, with ways of modeling certain chains of moves as one move because they always play out the same, and different things like that, but the basic principles I just talked about make up the MinMax algorithm, something you can use to make a reasonably smart computer program to play any given games. As long as you can come up with a way to guess how good the board position is with a heuristic, you can use MinMax and the computer will find the best possible position according to that metric.
The only real limiting factor on the effectiveness of the MinMax algorithm, aside from the exponentially growing computation requirement, is the fact that it assumes the opponent is just as good as it is. If you have some special knowledge of ways the opponent might make a mistake, then potentially you could come out of a game better than the MinMax algorithm would have if they played the same person. Still, if you are playing on the highest level, you have to assume your opponent is going to do really close to the best thing, so it is rare that this ends up mattering. If you were convinced the opponent was literally the worst player ever, and would always make the worst move, then you could probably write the MaxMin algorithm to find the best way to play against them, maximizing the worst possible move on the assumption they will play it.
Anyways, this is just another look into the way computers can think about different problems, and while its probably a little dry, I think it can give you a method to think about games as well, and think about how computers are playing them.
Walking through the Rain 