Workshop in Combinatorial Game Theory at IIT Bombay, India, November 4-8 2019
Combinatorial games are 2-player games, such as CHESS, CHECKERS and so on, with perfect information (no hidden information as in some card games), no chance moves (no dice), and where the players move alternately. Combinatorial Game Theory (CGT) often considers 'additive' rulesets in which positions consist of independent subpositions.
In the normal-play convention, the player with the last move wins. The analysis of NIM, by Charles Bouton, was published in the early twentieth century. After this appeared the Sprague–Grundy theory for impartial combinatorial games (players follow the same rules). This was a fundamental step; the important concept of disjunctive sum of games was established, and this idea was already present in the game of NIM, where the central tool is that of «nim-sum» (addition in binary without carry). Impartial games have exactly two outcome classes in optimal play, either the Previous (P) or the Next (N) player wins, and there is a recursive algorithm to determine which class a given position belongs to, starting with the terminals that are P-positions.
The next big step was in the 1950s, by John Milnor, with the notion of game comparison in so-called «positional games», and this theory was inspired by the famous eastern game of GO.
Later, in the 1970s, John H. Conway expanded the normal play theory to include partizan games, where players may abide to different rules, and so there are exactly 4 outcome classes; the players are called Left (L) and Right (R), and the outcome classes are (by convention) partially ordered with L wins (independently of who starts) greatest and R wins smallest, while P and N are incomparable. The work first appeared in the classical work On Numbers and Games, followed up in the 1980s with Conway, Berlekamp and Guy’s Winning Ways, for your Mathematical Plays. The class of combinatorial games played with normal-play convention, together with the disjunctive sum, is a partially ordered, abelian group. The negative of a game is obtained by swapping the players, and to compare two games G and H it is a main theorem of CGT that it suffices to play the game G-H and note who wins in optimal play. We will study some classical partizan rulesets such as HACKENBUSH, CLOBBER and DOMINEERING, and learn how to play well in a disjunctive sum of such games. See the below slides for some more details on this topic.
Other conventions as misère-play (last player loses), scoring‑play (the player with the largest number of points at the end wins), cyclic-play (games with cycles and loops), etc., are in general much harder, and we will only mention some recent work to broaden the notions of combinatorial games.
Another quite distinguished path of CGT started with the game of WYTHOFF NIM (Wythoff 1907) and it is usually played with a single Queen of CHESS on a large CHESS board. Two players alternate to move the Queen towards the lower left corner, using its standard moves from CHESS, and the player who cannot move loses. This is a classical impartial game in combinatorial game theory, and it became popular because the winning strategy has an appealing explicit formula description which involves the Golden Section.
A multitude of variations and generalizations of this game are known today, with branches in diverse fields--such as Biology (Phyllotaxis), Cellular Automata, Combinatorics on Words, Mechanism Design, Combinatorial Number Theory and Physics (Renormalization)--and usually with both surprising and appealing mathematical properties. Other classical combinatorial games for which Fibonacci numbers and the Golden Section appear in the description of optimal play are EUCLID'S GAME and FIBONACCI NIM. This part of CGT typically involves some elementary Number Theory, such as numeration systems and combinatorics on words. We will review some such methods.
We will give enough background that the participants will be able to continue exploring the subject on their own, and perhaps use it as a teaching tool in mathematics and Computer Science classes. Moreover, we will mention some open problems in the field, and point at interesting research directions.
Urban Larsson The School of Computing, National University of Singapore, Singapore URL: www.urbanlarsson.mine.nu email: firstname.lastname@example.org