What does it actually mean to solve a game?
Not to play it well. Not to build an AI that can defeat a human champion. To solve it: to establish, with mathematical certainty, what happens when both players play perfectly-and to produce computational evidence that can be independently checked.
How to Solve a Game is a practical guide to the algorithms, mathematics and engineering behind exact game solving. Beginning with the deceptively simple problem of representing a game correctly, it develops the tools needed to turn enormous game trees into rigorous computational proofs.
The book explores state representation, move generation, search, transpositions and symmetry, retrograde analysis, endgame tablebases, cycles and draws, exact oracles, proof-number methods and machine-checkable certificates. Along the way it examines the crucial distinction between a program that plays brilliantly and one that can actually prove a result.
Fanorona, the traditional strategy game of Madagascar, provides the book's principal laboratory. Its unusual capture rules, branching capture sequences and vast state space expose many of the difficulties that neat textbook examples conceal. Real experiments-including exhaustive solutions of smaller boards, exact endgame databases and attempts to classify positions on the full 5×9 board-show what works, what fails and where computational limits begin to bite.
The discussion ranges more widely across mathematical games and the history of game solving, asking why some apparently enormous games yield to mathematical structure while others remain resistant even to extraordinary amounts of computation.
This is not a guide to making a game-playing AI slightly stronger. It is about something more demanding: converting search into proof.
For programmers, mathematicians, game designers and curious players, How to Solve a Game explains how a finite set of rules can become a computational problem-and how, step by step, that problem can sometimes be reduced to a definitive answer.