Chapter 02 · Section III · 14 min read
Search and games
How the same search ideas that find roads also play chess, Go, and bagh chal — and where deep learning broke the old rules.
A board game is a search problem with an awkward twist. Each “move” leads to a new board state, exactly as in route-finding. But after every move you make, someone else gets to pick the next move — and they are trying to make you lose. The search now has an adversary.
This is the entire reason chess engines, bagh chal solvers, and Go-playing AI are conceptually harder than navigation. You cannot just find a winning move. You have to find a move that wins no matter what your opponent does next.
Bagh chal as a worked example
Bagh chal — the Nepali tiger-and-goat game — is the perfect example, because it is small enough to think clearly about, but adversarial enough to illustrate everything. Four tigers try to capture goats. Twenty goats try to trap tigers. Each player moves one piece at a time on a 5×5 grid of intersections.
To pick a move, the tiger player should ask: if I do this, what will the goat player do? And if they do that, what will I do? And if I do that, what will they do? Each layer of “what would they do next?” doubles or triples the number of futures the algorithm has to consider.
A few layers in, the tiger has a tree of thousands of possible futures, branching at every level. The job of the search algorithm is to walk that tree, evaluate each leaf (“does this end with the tiger winning?”), and trace back the value to the present move.
The minimax idea
The algorithm is called minimax. Its assumption is brutally simple: the opponent plays optimally. Whenever it’s the opponent’s turn, they pick the move that is worst for you. Whenever it’s your turn, you pick the move that is best for you.
Concretely, at every node in the search tree:
- If it is your turn, the value of the node is the maximum of the values of its children. You will pick the best.
- If it is your opponent’s turn, the value of the node is the minimum of the values of its children. They will pick the worst for you.
Walk the tree down to its leaves, mark each leaf as a win or a loss, and then propagate the values up using min and max alternately. The value at the root tells you what’s the best you can guarantee, and which child to walk toward.
That’s it. That’s the algorithm that powered every chess engine from the 1950s until AlphaZero arrived in 2017.
Why chess wouldn’t fit
Bagh chal has a small enough game tree that a modern laptop can search the whole thing and play perfectly. Chess does not. From the opening position, after just five moves by each player, there are roughly 70 million possible board positions to consider. After ten moves each, it is more positions than there are atoms in your hand. You cannot walk that tree.
So minimax was supplemented with two tricks that made chess engines work for fifty years.
Depth limit. Don’t walk all the way to the end. Walk 10 or 12 moves ahead, and evaluate the position with a hand-crafted scoring function — material balance, piece activity, king safety, pawn structure. The evaluation is the engine’s best guess about who is winning if the game stopped here. The minimax values propagate up from those guesses.
Alpha-beta pruning. While walking the tree, keep track of the best move you’ve found so far on each side. If a branch is clearly worse for the player whose turn it is — they would never go there — skip it entirely. This single trick can cut the tree size by a factor of a thousand or more, without changing the answer.
These two ideas, combined with faster computers, are why Deep Blue beat Kasparov in 1997. There was no machine learning in Deep Blue. It was minimax, alpha-beta, and a hand-tuned evaluation function — turbocharged by hardware.
Where Go broke this tradition
Go is bigger than chess. The board is 19×19. There are roughly 250 legal moves at each turn (versus 35 in chess), and games last 200 moves (versus 80). Minimax with alpha-beta does not get you to grandmaster level on Go, no matter how fast your computer.
The breakthrough in 2016 was AlphaGo by DeepMind. AlphaGo combined three ideas: a learned evaluation function (a neural network trained on millions of games), a learned move-suggestion function (another network), and Monte Carlo Tree Search — a kind of randomised search that explores promising branches statistically rather than systematically.
Crucially, the evaluation function was not hand-tuned. The network learned, from millions of self-play games, what a strong position looks like — pattern that humans could not have written down by hand.
A year later, AlphaZero learned to play chess, Go, and shogi from scratch in a few hours, with no human game data at all. It beat the best classical chess engine — Stockfish — by playing moves human grandmasters described as strange and beautiful. AlphaZero did not use minimax. It used learned search.
This is where game-playing AI meets the rest of the course: when the search space is too big for classical algorithms, machine learning takes over as the search guide.
What this means in 2026
Classical search is not obsolete. For routing, scheduling, logistics, and small games, it is still the right tool — faster, easier to explain, easier to debug. For very large state spaces where the structure can be learned from examples, deep learning has taken over.
The lesson is not that one approach replaces the other. It is that the right algorithm depends on the problem. A municipality optimising garbage truck routes in Pokhara should reach for A*, not a transformer. A team building a Go engine should reach for the AlphaZero family. Knowing which is which is the literacy part of AI literacy.
Check your understanding
Quick check
—In the minimax algorithm for two-player games, the algorithm assumes:
What comes next
We close out classical AI here. Chapter 3 turns to a different paradigm entirely: probability and Bayes’ rule, the mathematics that lets a system reason in the face of uncertainty. This is the foundation for almost every machine learning method we will meet from here on.