Minimax
What is the best move if my opponent also plays their best?
Looks ahead through every reply to a fixed depth, assuming both sides play their best, and backs the scores up the tree to pick a move.
MAX chooses. At the root, MAX keeps the largest of 3, 2 and 1. The value is 3, so the move to play is the one that leads to the first ▽.
A game is a tree. The position is the root, every legal move is a branch, and each branch leads to a position where the other side has moves of its own. Minimax walks that tree down to a chosen depth and scores the positions at the bottom with an evaluation function, or with win, draw and loss when the game has ended.
Then it works back up. On its own turn a side takes the child with the highest score for itself (the max step). On the opponent’s turn it assumes the lowest score for itself, because that is what the opponent will choose (the min step). The value that reaches the root is what best play is worth, and the move that leads to it is the one to play.
Worked example, on the tree above. MAX (△) is to move and has three options; each leads to a position where MIN (▽) has three replies. The nine leaves score 3, 12, 8 | 2, 4, 6 | 5, 1, 9. MIN answers each option with its worst reply for MAX: 3 in the first, 2 in the second, 1 in the third. MAX then compares 3, 2 and 1 and takes the first option. Its value is 3: not the 12 that is visible in the tree, because a sensible MIN would never allow it.
That is the whole idea: assume the opponent always makes the reply that is worst for you, and pick the move that is best under that assumption. You are not predicting what the opponent will do; you are guaranteeing the least you will get.
It is exact when it can reach the end of the game, as in tic-tac-toe. Everywhere else the answer is only as good as the evaluation and the depth.
Loading the demo…
Connect Four with minimax selected. Raise the search depth and watch the number of positions it reports grow.
- 01List the legal moves in the current position.
- 02For each move, play it and ask the same question for the opponent, one level shallower.
- 03At depth 0, or when the game is over, return the position’s score from the point of view of the side that is choosing.
- 04On your own turn keep the largest score returned; on the opponent’s turn keep the smallest.
- 05At the root, play the move whose score was best.
function minimax(position, depth, me):
if game_over(position): return result_score(position, me)
if depth == 0: return evaluate(position, me)
scores = [minimax(play(position, m), depth - 1, me) for m in moves(position)]
if turn(position) == me: return max(scores)
else: return min(scores)
function best_move(position, depth):
me = turn(position)
return argmax over m in moves(position) of minimax(play(position, m), depth - 1, me)b is the number of legal moves per turn and d the depth. Connect Four has about 7 moves a turn, so depth 6 is around 117,000 positions. A game with about 10 moves a turn reaches a million at the same depth.
- Finds the best move within its horizon, every time.
- One piece of code plays any two-player game that can list moves, report a result and score a position.
- Deterministic: the same position gives the same move.
- The cost grows exponentially with the depth.
- When the game cannot be searched to the end, the quality rests on the evaluation function.
- It examines many branches that cannot change the answer, which alpha-beta pruning removes.
- 01Tic-tac-toeSearches the whole game, so it plays perfectly. The plain minimax option shows how many positions that takes.
- 02OthelloA fixed-depth search scored by corners, edges and mobility.
- 03Connect FourUp to seven moves deep, scored by counting the lines of four each side can still complete.