Combinatorial Games at Mumbai, January 21-25 2024

## Organizers: Prof. Urban Larsson and Prof. Mallikarjuna Rao, IEOR, IIT Bombay, India.

**ABSTRACT: **This is a 5 days workshop, which starts with a day of game playing 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. For inquiries and registration please email larsson@iitb.ac.in. Please indicate if you are interested in giving a 20-minute talk in the morning sessions.

**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 online talks by Aaron Siegel and Johan Wästlund.

**SCIENTIFIC COMMITEE:** 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.

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.

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), with Nowakowski, and once “Games at Carmel”--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 Santo

Urban Larsson IEOR, IIT Bombay, Mumbai, India email: larsson@iitb.ac.in

See you in Mumbai 2024!

Editing is going on