Tuesday, September 8, 2015

A Very Brief History of Combinatorial Games

          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.”

4 comments:

  1. 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!

    ReplyDelete
  2. I 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
    Replies
    1. "It would be interesting to explore if any Game Theory was used in WW2, and if so what is was used for."

      Yassss, excellent question which we will DEFINITELY explore, both when we talk about pursuit games and when we talk about decision theory. Exciting stuff.

      Delete
    2. 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