1901 Bouton (nim: losing iff nimsum 0, also misere analysis)
1913 Zermelo (chess: B wins, W wins, both draw)
1936 Sprague, 1939 Grundy (each impartial game is a nimber)
Conway, Berlekamp, RK Guy (kaboom)
1974 Knuth surreal numbers part 1
1976 Conway on numbers and games part 1
197? C? BCG? canonical form theorem
prune dominated, reverse reversible: give you unique canonical form
2007, 2019 Albert, Nowakowski, Wolfe Lessons in Play: intro to CGT
20??, 20??, 2016 Haff, Garner, Intro to CGT
2017 DeVos, Kent, Game Theory: A Playful Intro
for any impartial g, exists non-negative integer k: g = *k
exercise: prove Sprague-Grundy for nim
use Bouton's theorem
if necessary, use canonical form theorem
thm: nim(position p) = *nimsum(p)
e.g. prove nim(1 2 6) = *nimsum(1 2 6) = *5
nim(1 2 6) options?
026 106 116 120 121 122 123 124 125
induction: *4 *7 *6 *3 *2 *1 *0 *7 *2
so nim(1 2 6) = g = {*0, *1, *2, *3, *4, *6, *7}
does g equal *nimsum(1 2 6) = *5 ?
exercise: yes (show 2nd player wins g + *5
which options of nim(1 2 6) are dominated? reversible?
def'n: for a set S of nonnegative integers, mex(S) is min nonneg excluded int
let g impartial = *g1, *g2, ..., *gt
then g = *mex(g1, g2, ..., gt)
exercise: prove lemma