Sprague-Grundy Theorem
The Sprague-Grundy Theorem is a fundamental result in combinatorial game theory that helps determine winning strategies in impartial games. It states that every position in such a game can be assigned a value called the Grundy number, which indicates whether the position is winning or losing. A position with a Grundy number of zero is losing for the player about to move, while a non-zero Grundy number indicates a winning position.
The theorem applies to various games, including Nim and Chomp, allowing players to analyze game states systematically. By calculating the Grundy numbers for different positions, players can make informed decisions to maximize their chances of winning.