Combinatorial Games at Mumbai, January 21-25 2024
ORGANIZERS: Prof. Urban Larsson, Prof. Mallikarjuna Rao, Anjali Bhagat and Prem Kant, IEOR, IIT Bombay, India.
ABSTRACT: This is a 5 days workshop, which starts with a day of game playing (poster) on Sunday 21st January 2024. Various topics on Combinatorial Game Theory (CGT) will be covered in the morning sessions 22st-25th. In the afternoons there will be workshops, where participants explore various topics in the field. No prerequisite is required apart from a basic mathematical curiosity, probably with an inclination towards algorithms and discrete mathematics. Registration has now been closed. The talk schedule is full. For inquiries email larsson@iitb.ac.in.
INVITED SPEAKERS: Prof. Carlos P. dos Santos, Center for Mathematics and Applications (NovaMath), FCT NOVA, Portugal, and Prof. Kyle Burke Florida Southern College, USA. In addition, there will be amazing talks by the participants, and online talks by Aaron Siegel and Johan Wästlund.
The conference venue is VMCC room no 31. Please find the map to the Main Gate (109), Guest House (G3) and the VMCC venue (85).
We start with registrations 10 am on Sunday and at 2.30 pm there is an open day. We start 9 am on Monday to Thursday. We finish 6pm all days except Thursday 3pm.
Please find the schedule and the talk abstracts. Here are some links to slides from the conference and more.
SCIENTIFIC COMMITTEE: Carlos P. dos Santos, Center for Mathematics and Applications (NovaMath), FCT NOVA, Portugal; Kyle Burke Florida Southern College, USA; Simon Rubinstein-Salzedo, Euler Circle, USA; Miloš Stojaković, University of Novi Sad, Serbia; Johan Wästlund, Chalmers University of Technology, Sweden. Aaron Siegel, author of Combinatorial Game Theory and programmer of CG-suite, USA.
Here are some lecture notes from a recent class I taught at IIT Bombay. The strongest students from this class will present their projects at the conference. My Ph.D. students, Prem Kant, Ankita Dargad and Anjali Bhagat will of course present their projects too. At the conference we will invite participants to contribute research paper to a forthcoming volume of Games of No Chance, MSRI CUP: here is the classical first volume, edited by Nowakowski. We are in the final stages of producing the 6th volume in the series, and this conference could initiate a future 7th volume. The deadline for submission will be two years from now.
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 follow different rules, and so there are four 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 Conway's 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. Classical partizan rulesets are AMAZONS, HACKENBUSH, CLOBBER and DOMINEERING. Nowadays the standard CGT reference is Aaron Siegel's book Combinatorial Game Theory. See also the currently five volumes of Games of No Chance, available online at MSRI's homepage.
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), bidding play (e.g. Richman auctions) etc., are in general harder to analyze.
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.
ORGANIZER'S SHORT BIO
Urban Larsson is an Associate Professor at IEOR, IIT Bombay, and before that he was a Research Fellow at National University of Singapore, 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 about 20 peer reviewed published papers in international journals in 2018-2023). Urban has presented his research at more than 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 of the next issue, Games of No Chance 6. He has co-organised several workshops in Combinatorial Game Theory--twice Games at Dal (Dalhousie University, Canada) with Nowakowski, Games at Carmel (Technion, Israel), once at Ohio State University with Roldan Roa, and once at IIT Bombay--and he is a member of the program committee for CGTC I, II, III and IV, the forth was held at the Azores in January 2023, organized by Prof. C. P. dos Santos.
Urban Larsson
IEOR, IIT Bombay, Mumbai, India
email: larsson@iitb.ac.in
See you in Mumbai 2024!
Editing is going on