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 session 21st-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 minutes talk in the morning sessions. Prof. Carlos P. dos Santos, Lisbon, Portugal, is invited speaker.
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), 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.
Speakers Bio:
Carlos Pereira dos Santos graduated and held a master and PhD degree in Mathematics at the University of Lisbon. Currently, he is a researcher of the Centre for Functional Analysis, Linear Structures and Applications, invited assistant professor at High Institute of Engineering of Lisbon, and a teacher trainer and researcher in Colégio de São Tomás, a private school in Lisbon. Carlos primary research is in the field of Combinatorial Game Theory (CGT) with several papers in international journals and presented at major conferences devoted to the subject. His PhD was under the guidance of Richard Nowakowski from Dalhousie University, a 39th top expert in that topic. He published the book «Mathematics from The Da Vinci Code» about Recreational Mathematics co-authored with Luis Tirapicos and Nuno Crato. He participated in the project «Games with History» and «Games from Around the World» (Visão/Público) with João Pedro Neto and Jorge Nuno Silva. During ten years, he was Vice-President of the Ludus Association, one of the most relevant Portuguese institutions dedicated to recreational mathematics. He has been a member of scientific committees of pioneering projects such as the «Portuguese Championship of Mathematical Games» and the «Recreational Mathematics Colloquia». He was managing editor of the Recreational Mathematics Magazine. He co-authored with Carlota Simões the project Astronomia Cantada n’Os Lusíadas. About Mathematics Education in Portugal, he researches subjects related to elementary mathematics. Also noteworthy is the fact that, for three years, he has made the management of the Training Centre for Teachers of the Portuguese Mathematics Society and, after, he was the director of the Training Centre for Teachers of the Ludus Association. He organised and developed dozens of courses on various topics. Carlos Santos is a big fan of the Singapore Math, and he is managing editor of the “Jornal das Primeiras Matemáticas”. He regularly collaborates in the Projeto ProSucesso (Azores Regional Government, University of Azores), particularly in the Projeto Prof. DA (Qualified teachers in solving learning difficulties). Regarding hobbies, Carlos Santos is an International Chess Master. He was the Portuguese Champion in 1998 and 2000, and he was 5th in the under-18 World Championship in 1989.