Workshop in Combinatorial Game Theory at IIT Bombay, India, November 4-8 2019



pic



LECTURER Dr. Urban Larsson, National University of Singapore


ABSTRACT

This is a 5 days workshop, consisting of 5 lectures on the basics of Combinatorial Game Theory (CGT). We start Monday November 4 (2pm-4pm) and continue Tuesday November 5 - Friday November 8 (2.30pm - 4.30 pm). No prerequisite is required apart from a basic mathematcal curiosity, probably with an inclination towards combinatorics and computer science.

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.

LECTURER'S SHORT BIO

Urban Larsson is a Research Fellow at National University of Singapore, host Yair Zick, and before that he was a postdoctoral fellow at the Industrial Engineering and Management dept. at the Technion (and awarded an Aly Kaufman fellowship). Before that he was awarded a Killam postdoctoral fellowship at Dalhousie University (Canada) 2014-2016, which included lecturing, and before that he was a responsible lecturer in mathematics 2013-2014 and Ph.D. student (ending 2013) at Chalmers & University of Goteborg (Sweden). His main research areas are Game Theory, Number theory, Computer Science and Algorithms, and some of his main contributions find bridges between Combinatorial games and neighboring fields. He publishes regularly (with 13 peer reviewed published papers in international journals in 2017-2018). Urban, has presented his research at about 100 international conferences and seminars, he is an Associate Editor for International Journal of Game Theory, and he is the Editor of Games of No Chance 5 (in press), and the next issue Games of No Chance 6 (still collecting submissions). He has co-organised three workshops in Combinatorial Game Theory--Twice “Games at Dal” (Dalhousie University), with Nowakowski, and once “Games at Carmel”--and he was/is member of the program committee for CGTC I, II and III, the third was held in Lisbon January 2019, organized by C. P. dos Santos (University of Lisbon). 
Urban Larsson 
  The School of Computing, 
  National University of Singapore, 
  Singapore
  URL:  www.urbanlarsson.mine.nu
  email: urban031@gmail.com

Slides: