Now
that we have learned about the basics of combinatorial game theory, we can learn
a little bit about the history of the subject. Although it has roots in 16th
and 17th century gambling and probability studies, the majority of
our understanding of combinatorial game theory comes from work done in the past
century. In its nascency, combinatorial game theory concentrated on impartial
games under normal play. It wasn’t until the publication of J.H. Conway’s On Numbers and Games (1976) and E.R. Berlekamp,
J.H. Conway and R.K. Guy’s Winning Ways that
the depth and breadth of the subject was fully considered. Since this early work, combinatorial game
theory has truly blossomed into a sophisticated field of study.
The
history of combinatorial game theory can be divided into three main “threads,”
as Richard Nowakowski calls them, which include: impartial games, partisan
games, and impartial misère games. Let’s start with a glance at the history of impartial
games. The study of impartial games likely began with Charles L. Bouton, who
published an early solution to the game of Nim in 1902. Bouton’s work soon
sparked an interest in Nim among other mathematicians.
Several variations of the game soon
followed. For example, Willem A. Wythoff developed a Nim variant which came to
be known as Wythoff’s Nim. In Wythoff’s Nim, there are two heaps of counters,
and a player can either take as many counters as they wish from one pile, or
they may take an even number of counters from each pile. Rufus Isaacs created
his own spinoff, known as Wythoff’s Queens, in which a chess queen is moved
closer to one corner of a grid. These games gave rise to elegant mathematical
findings, but game theory purists—Nowakowski among them—argue that these
variations were detrimental to the theory because the games could not be
reduced to components.
Emanuel Lasker, however, sent
combinatorial game theory in the “right” direction with the development of
Lasker’s Nim—the same as Nim, except a player may elect to split a heap in two,
rather than take counters. Lasker set the stage for Roland Sprague and Patrick
Grundy to develop the notorious Sprague-Grundy Theorem in 1939. The Sprague-Grundy theorem demonstrated
that all impartial games are equivalent to heaps in Nim. This theory has
obvious utility in impartial games, but it can also be applied to other types
of games.
Now let’s turn our attention to partizan
games under normal play. Recall that partisan games are games in which rules
are different for each player. For example, in tic-tac-toe someone designates
their moves with Xs while their opponent uses Os, or in Checkers red and black
pieces are used (these aren’t combinatorial games, of course). In 1953, John Milnor published the first theoretical
paper on partizan play, which marked the beginning of a burgeoning subject in
game theory. Milnor explored desirable “hot”
positions, and tried to explain the “mean value” of a given position. Olof
Hanner’s own version of the mean value of a game followed shortly thereafter in
1957, based on his interest in the combinatorial game Go.
Milnor and Hanner’s early work
helped John H. Conway to develop the concept of disjunctive sums of games, as
well as the surreal number system. Conway published his findings in On Numbers and Games in 1976. It wasn’t
long before Berlekamp, Conway and Guy co-authored and published Winning Ways in 1982. These two
publications serve as the foundation for combinatorial game theory as we know
it today.
This leads us to the last “thread”
in the history of combinatorial game theory: impartial misère games. The story
behind impartial misère games is actually quite short. Misère games have long
been an enigmatic branch of combinatorial game theory. Both On Numbers and Games and Winning Ways touch on the subject and a paltry number of papers followed. The trouble with misère games is
that almost all games are unique; this means that misère games seldom share
common strategies, unlike games under normal play.
In the last decade or so, Thane
Plambeck and Aaron Siegel have shed new light on misère games. The two have
published a number of publications on the subject. According to Nowakowski, “the
history of misère games is only now being written."
Works Consulted:
Nowakowski, R.J. (2009). The History of Combinatorial Games.
1-13.
N.A. (2015). “Combinatorial Game Theory.”
Wow! Nicely written, your vocabulary was great! It was cool to see some background information to the games we've been studying for a couple of weeks now. I found it particularly surprising that the variation games were considered "detrimental" by some theorist. The word detrimental seems a little extreme, but more importantly I was intrigued because to me the variation games made the combinatorial games more interesting, as well as creating a larger field to be studied; something you would think the theorist would be excited about!
ReplyDeleteI was intrigued that the Sprague-Grundy Theorem was developed in 1939 – right around the same time Hitler and the Nazis were rising to power in Europe. Even more interesting Roland Sprague was German, while Patrick Grundy was English. After doing a quick google search I found that the two men did not work together on the Theorem, rather they made their discoveries independently. Sprague discovered the theorem in 1935, while Grundy made the discovery in 1939. It would be interesting to know if Grundy was influenced by any of Sprague’s work, or if he was not even aware of it – which wouldn’t be surprising given the time. Over the summer I saw The Imitation Game (great movie highly recommended). It would be interesting to explore if any Game Theory was used in WW2, and if so what is was used for.
ReplyDelete"It would be interesting to explore if any Game Theory was used in WW2, and if so what is was used for."
DeleteYassss, excellent question which we will DEFINITELY explore, both when we talk about pursuit games and when we talk about decision theory. Exciting stuff.
Hey Seneth, I should say thank you because I was inspired by your comment and decided to do a final project exploring the use of Game Theory in Wars. I think that should be an interesting topic!
Delete