The overall goal of this post is to prove that every impartial game is equivalent to a game of nim. While this result is often called the Sprague-Grundy theorem, the theorem doesn’t actually say anything about this conclusion. After proving the theorem, I’ll explain why a game’s equivalence to nim immediately follows.
Nim is a simple game, in which 2 players take turns removing objects from piles until there are no more objects left. This post will define basic terms for combinatorial game theory, detail the rules of nim, and explain how to win the game.
Games are the perfect mix of chaos and strategy: they are dynamic, since players’ decisions affect them, but there often exists an optimal way to play. This post discusses
- why we can solve some games but not others.
- how we solve these games.
- different processes developed along the way.
The solvability of tic-tac-toe, set take-away, Connect 4, checkers, and chess will be examined in further detail.