In the first post in this series, we talked about utility. Tic-tac-toe came up, and we discussed how a player should determine what her best move is in a given situation. After all, what's best depends on what her opponent will do (and her opponent's move probably depends on her own next move, etc.).

As I mentioned, there is an algorithm for deciding the best move in any given situation of Tic-tac-toe: the Minimax algorithm. It works as follows.

In a given situation, consider all moves available to you. (At the start of the game, that's 9 moves.) If such a move is a direct win (it creates a row, column or diagonal of 3 of your marks), assign this move utility 1. If a move fills the last open field of the grid, but nobody wins, it's a tie — assign 0 utility to this move.

Is the move neither a win, nor a tie? Then things are more interesting: your opponent will react to this move. So, we consider all possible moves your opponent can do in reaction to the move you're considering.

Is such a countermove a win for your opponent? Assign it utility -1. Is it a tie? Utility 0. Did your opponent not win, and is a counter-countermove by you possible? Consider all those possible counter-countermoves. And so on.

This way, we eventually search through all possible games. But how do we assign utility to moves that don't end the game?

Let's look at an example. Say we start with the following position:

There are 3 possible moves we can play here:

The middle move leads to a win, so we can assign that one utility 1. The other moves don't immediately end the game. Let's work out the tree:

The lowest row is easy: The left and middle grids are a tie (0 utility), and the right one is a win for us (1 utility).

Let's go one row higher:

From left to right:

• the first grid has only 1 possible follow-up (directly below it), and simply gets the utility of that follow-up (utility 0)
• the second grid represents a loss (utility -1)
• the third one is similar to the first (utility 0)
• the fourth one is again similar to the first and third (utility 1)

Time to go even higher!

Again, from left to right:

• The first situation has 2 possible follow-ups, with 0 and -1 utility. Remember: it's our opponent's move here. If she is any good, she'll pick the right follow-up, since that is a win for her. In general (if she's a perfect player) she'll pick the move with the lowest utility for us. Since it's a zero-sum game, low utility for us means high utility for her! Since the right follow-up grid has -1 utility, we can assign that utility to the grid we're considering as well (utility -1)
• The second grid is a win (utility 1)
• By the same logic as the first grid, the third grid gets utility 0: after all, a good opponent will choose the left follow-up grid, since that one has the lowest utility for us

The top level grid gets the utility from the best grid in the second row. After all, it's our turn here! Of course we'll choose a move with high utility. So this one gets utility 1. No wonder: we can directly win when we're in this situation!

This way, we can use Minimax to find the best move in every situation — by constantly assuming our opponent will do the move best for her. But of course, if our opponent doesn't play so well, that can only be to our advantage!

In principle, Minimax can be used for any zero-sum game. In theory, it finds the best move in Chess as well. But there's a huge practical problem here!

At the start of Tic-tac-toe, we can choose from 9 possible moves. After we do this, our opponent can choose from 9 – 1 = 8 possible moves. Then we get to choose from 7, etc. The total number of possible games is therefore 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 9! = 362880. A modern computer can easily search through all these games to find the best move.

The total number of possible Chess games is currently unknown, but it's at least 10¹²⁰ (the Shannon number). That's a 1 followed by 120 zeroes.

Even if we have a supercomputer that searches through a billion (10⁹) games per second, it would still take that computer more than 3 * 10¹⁰³ years to search through all games. A computer that's a billion times as fast as that? 3 * 10⁹⁴ years. We can simply forget this. To let a computer play Chess, we need different techniques (though a limited Minimax can be part of the solution).

Thanks for reading, and stay tuned for the next post on Game theory!

If you would like to support Street Science, consider contributing on Patreon.