“In the autumn of 1912, Ernst Zermelo stood before a small gathering of mathematicians in Cambridge and announced a result that would haunt the twentieth century. Chess, he declared, was solved, at least in principle. One of the two players, White or Black, must possess a winning strategy, or else both can force a draw. The game is finite; the tree of possibilities, though vast, terminates. Therefore, by the iron logic of mathematical induction, the outcome is determined before the first pawn moves.
The audience received this news with the peculiar mixture of satisfaction and unease that accompanies theorems of pure existence. Zermelo had proved that an answer existed without providing any hint of what that answer might be. His proof was what mathematicians call non-constructive: it demonstrated the existence of a winning strategy the way one might prove that a prime number greater than a googolplex exists: true, certainly, but utterly unhelpful to anyone hoping to find it.
This was Zermelo’s curse, and it would echo through the decades that followed. The chess tree contains more positions than atoms in the observable universe. Knowing that a perfect strategy exists tells us nothing about how to play well. The game is finite, but it might as well be infinite for any creature bound by time and matter. The gap between existence and construction, between knowing that an answer is there and actually finding it, would become the central drama of a field that did not yet have a name.”
Paths, Trees, Flowers, Conflicts captures the golden age of combinatorial optimization (and graph theory), the winding path towards recognizing that not all puzzles are easy to solve just because they are finite. Part 1, from Zermelo to Harary, is out now.
#econtwitter #MLtools
carnegietech.substack.com/p/…