Text size
Chapter 02 · Section III · 12 min read
Search and games
How the same search ideas that find roads also play chess, Go, and bagh chal.
A board game is a search problem with an adversary. Each “move” leads to a new board state. Your opponent gets to pick the next move, and they are trying to make you lose. The system has to think several moves ahead.
The minimax algorithm — the backbone of every chess engine until the deep-learning era — searches forward through the tree of possible games. Bagh chal, the Nepali tiger-and-goat game, is small enough that a minimax search can play it perfectly. Chess is not.
This section is a stub. The full version will cover minimax, alpha-beta pruning, and where AlphaGo broke from this tradition.