Chapter 4. Playing games with tree search
This chapter covers
- Finding the best move with the minimax algorithm
- Pruning minimax tree search to speed it up
- Applying Monte Carlo tree search to games
Suppose you’re given two tasks. The first is to write a computer program that plays chess. The second is to write a program that plans how to efficiently pick orders in a warehouse. What could these programs have in common? At first glance, not much. But if you step back and think in abstract terms, you can see a few parallels:
- You have a sequence of decisions to make. In chess, your decisions are about which piece to move. In the warehouse, your decisions are about which item to pick up next.
- Early decisions can affect future decisions. In chess, moving a pawn early on may expose your queen to a counterattack many turns later. In the warehouse, if you go for a widget on shelf 17 first, you may need to backtrack all the way to shelf 99 later.
- At the end of a sequence, you can evaluate how well you achieved your goal. In chess, when you reach the end of the game, you know who won. In the warehouse, you can add up the time it took to gather all the items.
- The number of possible sequences can get enormous. There are around 10100 ways a chess game can unfold. In the warehouse, if you have 20 items to pick up, there are 2 billion possible paths to choose from.