Worlds of David Darling
Encyclopedia of Science
   
Home > Encyclopedia of Science

Sprague-Grundy theory




A theory of certain classes of games called impartial games, discovered independently by Roland Percival Sprague (in 1936) and Patrick Michael Grundy (in 1939) and originally applied to Nim. In simple terms, they showed that one could take any impartial game and analyze it in terms of Nim heaps that could grow or decrease in size. The theory was developed further by E. R. Berlekamp, John Conway and others, and presented comprehensively in the books Winning Ways For Your Mathematical Plays and On Numbers. Sprague-Grundy theory has been applied to other combinatorial games, including kayles.


Related category

   • GAMES AND PUZZLES