Combinatorial Game Theory Colloquium III
(Lisbon, 2224 January, 2019)
Combinatorial Game Theory (CGT) is a branch of mathematics that studies sequential games with perfect information. Combinatorial games include wellknown rulesets like Amazons, Clobber, Domineering, Hackenbush, Konane, Nim, Octal Games, Wythoff’s Nim. After John Conway’s On Numbers and Games (1976), Elwyn Berlekamp, John Conway, and Richard Guy published “the book” Winning Ways (1982). In that work, one can find a unified mathematical theory able to analyze a large class of rulesets. The books Lessons in Play (2007), by Michael Albert, David Wolfe, and Richard Nowakowski, and Combinatorial Game Theory (2013), by Aaron Siegel, are also mandatory reading.
Combinatorial Game Theory Colloquia are held every two years, in Portugal. Associação Ludus will organize in Lisbon the third edition of the CGTC, 2224 January, 2019, with support of Centro de Análise Funcional, Estruturas Lineares e Aplicações, Centro de Matemática Aplicada à Previsão e Decisão Económica, Centro Interuniversitário de História das Ciências e da Tecnologia, and Biosystems and Integrative Sciences Institute. The Colloquium will be hosted by Centro de Matemática Aplicada à Previsão e Decisão Económica (for a map of its location press here).
REGISTRATION
For informations about submissions and registrations, just mail us: cgtc@cgtc.eu
CALL FOR PAPERS
Authors of significant original results related to (presented at) the conference are encouraged to submit them by September 1, 2019 to the International Journal of Game Theory. The papers will be refereed according to the normal high journal standards. Those articles that are accepted will be published together in a single issue of IJGT.
As author comment, please include the line “We are submitting this article to be considered for the issue related to the Combinatorial Game Theory Colloquium 3 (CGTC3) held in Lisbon in January 2019.”.
Urban Larsson AE IJGT, Carlos Pereira dos Santos, Richard Nowakowski
Scientific Committee
Alda Carvalho, ISEL & CEMAPRE
Aviezri S. Fraenkel, Weizmann Institute of Science
Bernhard von Stengel, London School of Economics and Political Science
Carlos Pereira dos Santos, LA & CEAFELUniversity of Lisbon
Eric Duchene, IUT Lyon 1, LIRIS lab.
Gabriel Renault, Sopra Steria
João Pedro Neto, University of Lisbon
Jorge Nuno Silva, University of Lisbon
Martin Mueller, University of Alberta
Pedro J. Freitas, CEAFELUniversity of Lisbon
Richard Nowakowski, Dalhousie University
Thane Plambeck, Counterwave, Inc
Urban Larsson, Industrial Engineering and Management, Technion
Organizing Committee
Alda Carvalho, ISEL & CEMAPRE
Anabela Teixeira, LA, MUHNAC & UIDEFUniversity of Lisbon
Carlos Pereira dos Santos, LA & CEAFELUniversity of Lisbon
Jorge Nuno Silva, CIUHCTUniversity of Lisbon
Pedro J. Freitas, CEAFELUniversity of Lisbon
Tiago Hirth, LA
Tiago Robalo, LA
Standard Talks, Mornings – AUDITÓRIO 2, Quelhas
Working Sessions, Afternoons (14:0018:00): Rooms – CTT, DELTA, IAPMEI, 306
List of Participants:Adam Atkinson, Alda Carvalho, Alexandre Silva, Annamaria Cucinotta, Antoine Dailly, Bernhard von Stengel, Carlos Pereira dos Santos, Cátia Lente, Fionn Mc inerney, Hironori Kiya, João Pedro Neto, Jorge Nuno Silva, Karim Soliman, Koki Suetsugu, Kyle Burke, Marc Heinrich, Matthieu Dufour, Matthew Ferland, Melissa Huggan, Michael Fisher, Ravi Kant Rai, Richard Nowakowski, Svenja Huntemann, Thane Plambeck, Tiago Hirth, Tomoaki Abuku, Urban Larsson,Valentin Gledel, and Yuki Irie.
22/1 – Tuesday  23/1 – Wednesday  24/1 – Thursday  
8:308:45  Opening ceremony  
8:459:00 
Richard Nowakowski, 

9:009:30


Tomoaki Abuku,


9:3010:00  Antoine Dailly, University of Grenoble, Connected subtraction games on graphs 
Thane Plambeck, Counterwave inc, Shotgun wedding: ECGT + CGT 
Svenja Huntemann, Carleton University, Enumerating DOMINEERING 
10:0010:30 

Alda Carvalho, ISEL & CEMAPREUL, Combinatorics of JENGA 
Valentin Gledel, University of Lyon, The MakerBreaker domination number 
10:3011:00  Coffeebreak  Coffeebreak  Coffeebreak 
11:0011:30  Carlos Pereira dos Santos, CEAFELUL & ISEL, Extended Combinatorial Game Theory: the effect of the terminal move 
Koki Suetsugu, Kyoto University, Dependent sum game: Some variants of Wythoff NIM and Ryuo NIM 
Ravi Kant Rai, Indian Institute of Technology Bombay, Optimal play in DUIDOKU game 
11:3012:00  Marc Heinrich, University of Lyon, Partizan subtraction games 
Fionn Mc Inerney, Université Côte D’Azur, The ORTHOGONAL COLOURING GAME on graphs 
Hironori Kiya, Nagoya University, Two player TANHINMIN and its extension 
12:0012:30 
Bernhard von Stengel,


Matthew Ferland, University of Southern California, Computational Properties of SLIMETRAIL 
12:3013:00 

Melissa Huggan, The Index: a measure of equality


13:0014:00  Break for lunch  Break for lunch  Break for lunch 
14:0018:00  Working sessions  Working sessions  Working sessions 
19.0023:00  Conference Dinner 
Combinatorics of JENGA
Alda Carvalho, ISEL & CEMAPREUL, Portugal
Abstract: JENGA is a game of physical skill played with 54 wooden blocks. Each block is three times longer than its width. Players move in JENGA by taking one block from any level (except the one below an incomplete top level), and placing it on the topmost level. The winner is the player who makes the last move (usually, before the tower’s collapse). Assuming perfect players, JENGA may be seen as a pure impartial combinatorial ruleset. Therefore, we can analyze it using the standard CGT approach. That is the main issue of this talk. (Joint work with Carlos Pereira dos Santos and João Pedro Neto)
Connected subtraction games on graphs
Antoine Dailly, GSCOP, University of Grenoble, France
Abstract: We study a generalization of the subtraction games on graphs, in which the players alternate removing connected components from a graph without disconnecting it, and provided the number of vertices in the connected component belongs to a prescribed set of positive integers. We derive general periodicity results for such games, as well as specific results when playing on subdivided stars.
(Joint work with Julien Moncel and Aline Parreau)
Computational progress on the CatchUp game
Bernhard von Stengel, Department of Mathematics, London School of Economics, UK
Extended Combinatorial Game Theory: the effect of the terminal move
Carlos Pereira dos Santos, CEAFELUL & ISEL, Portugal
Abstract: About disjunctive short sum, John Conway wrote the following: The compound game ends as soon as any one of the component games has ended (ONAG, 1976). In fact, this rule is directly related to the idea of terminal moves: moves that imply the end of the play, even if the players still have available options. The end of a component, the capture of a piece (e.g., chess king), a specific goal, are examples of terminal rules related to terminal moves. The game values of terminal moves should be infnite. It is necessary to consider the extended game line in exactly the same way we can consider the extended real number line (with infinities). But an understanding of the algebra is mandatory (game comparison, disjunctive sum, inverses). Success in this task will allow better research on disjunctive short sum of classic Combinatorial Game Theory (e.g., ATARI GO), and better approaches for scoring combinatorial rulesets (e.g. DOTS & BOXES). We will discuss and exemplify some problems behind this idea.
(Joint work with Richard Nowakowski and Urban Larsson)
The ORTHOGONAL COLOURING GAME on graphs
Fionn Mc Inerney, Université Côte D’Azur, France
Abstract: We introduce the ORTHOGONAL COLOURING GAME, in which two players alternately colour vertices (from a choice of m colours) of a pair of isomorphic graphs while respecting the properness and the orthogonality of the colouring. Each player aims to maximize her score, which is the number of coloured vertices in the copy of the graph she owns. It is proven that, given an instance, the normal play convention of this game is PSPACEcomplete and a reduction from the colouring construction game to the scoring version of the ORTHOGONAL COLOURING GAME is given which provides a nice connection between the two. The main result of this paper is that the second player has a strategy to force a draw in this game for any m for graphs that admit a strictly matched involution. This property is defined and then a characterization of the graphs which have it is given which also gives an explicit construction for these graphs. Examples of such graphs are the graphs associated with Latin squares and sudoku squares.
Two player TANHINMIN and its extension
Hironori Kiya, Nagoya University, Japan
Abstract: TANHINMIN is a cardbased partisan game with a totally ordered set of cards. Players in turn discard a card that must be greater than the lastly discarded card, and the player that first discards all the cards in hand is the winner. We consider a 2player generalized TANHINMIN, where the size of the deck is arbitrary. We also consider a 2player generalized TANHINMIN with extra rules. For both, we show that the winner can be decided in polynomial time.
On Wythoff type extension of general subtraction game
Koki Suetsugu, Kyoto University, Japan
Abstract: Cyclic NIMHOFF is a variant of Wythoff NIM. In this game, there are some heaps and each player can move as following:
(i) Choose one heap and remove any number of stones.
(ii) Remove a total of k stones from any number of heaps, provided that k<p.
Fraenkel and Lorberbom found a formula to obtain the SpragueGrundy values of the positions of this game in 1991. (i) is the same move as NIM and in this talk, we replace (i) with the move of other games like subtraction NIM or allbut NIM. We include the case that replaced rules are different for each heap.
(Joint work with Tomoaki Abuku and Ko Sakai)
Partizan subtraction games
Marc Heinrich, LIRIS, University of Lyon, France
Abstract: Subtraction games are combinatorial games played with one heap of tokens where each player can remove a number s of tokens, where s is taken in some fixed set S. We study a partizan version of these games where each player has a different set. We are interested in the asymptotic behavior of the outcome sequence when the number of tokens is large.
(Joint work with Eric Duchêne, Richard Nowakowski and Aline Parreau)
Computational Properties of SLIMETRAIL
Matthew Ferland, University of Southern California PhD Program, United States of America
(Joint work with Kyle Burke)
Beatty Games: Big and Small
Michael Fisher, West Chester University, United States of America
Abstract: A Beatty sequence is a sequence of integers formed by taking the floor of the positive integral multiples of a positive irrational number α. The complementary sequence is formed in a similar manner using β, where β satisfies the equation 1/α + 1/β = 1. For a given α, we investigate the partizan subtraction game with left and right subtraction sets given by {1, α} and {1, β}, respectively. We analyze this family of games using the Atomic Weight Calculus.
We will also report results for the nonatomic version, where the left and right subtraction sets are given by {α} and {β}, respectively.
Octal games are impartial games that involve removing tokens from heaps of tokens. These types of games are interesting in that they can be uniquely described using an octal code. Historically, research efforts have focused almost exclusively on octal games with finite codes. We consider octal games based on infinite octal codes where the heap sizes corresponding to elements of a Beatty α sequence are played according to some fixed removal rule and the heap sizes corresponding to elements of a Beatty β sequence are played according to some other fixed removal rule. Interesting periodicity seems to occur in most cases.
The Index: a measure of equality
Melissa Huggan, Dalhousie University, Canada
Abstract: Playing combinatorial games with simultaneous moves naturally introduces a probabilistic element to game play. This small change to game play forces big changes when we consider the underlying theory of simultaneous play combinatorial games. In particular, understanding how to interpret equality of games has been very challenging. Throughout this talk, I will present a refinement on the expected value, called the Index, which captures the notion of equality for simultaneous play combinatorial games played under continued conjunctive sum with the extended normal play winning convention.
(Joint work with Richard J. Nowakowski and Paul Ottaway)
Optimal play in DUIDOKU game
Ravi Kant Rai, Indian Institute of Technology Bombay, India
Abstract: DUIDOKU game is a competitive game version of Sudoku introduced by Kaushik Basu. We show that DUIDOKU is advantageous to one player, depending on whether the number of cells is even or odd. In other words, we show that one of the players has a strategy that guarantees a win or a draw.
(Joint work with K.S. Mallikarjuna Rao)
Trends in Combinatorial Game Theory
Richard Nowakowski, Dalhousie University, Canada
Enumerating DOMINEERING
Svenja Huntemann, Carleton University, Canada
Abstract: We will demonstrate a quick technique for enumerating the number of DOMINEERING positions on a rectangular board. The method is then modified to count the number of maximal DOMINEERING positions.
(Joint work with Neil McKay)
Shotgun wedding: ECGT + CGT
Thane Plambeck, Counterwave inc, United States of America
Abstract: Everyone knows that Combinatorial (CGT) theorists are the cool people, but Economic Game Theorists (EGT) get the Nobel Prizes and nearly all the money. Therefore, we aim to contrive and present for your consideration some games that require a knowledge of both Nash Equilibria and the CGT temperature theory to play correctly. Like all shotgun weddings, things may get a bit ugly, but it’s the thought that counts.
On NIMlike games played on graphs
Tomoaki Abuku, University of Tsukuba, Japan
Abstract: We study «NIM on graphs», an impartial game played on a finite undirected weighted graph. In the starting position, a piece is placed at a vertex of the graph. Each player alternately moves the piece from the vertex to one of its adjacent vertices and decreases the weight of the edge to any strictry smaller nonnegative integer. The game terminates when one player has no moves and then this player loses. We give the winning strategy and the Grundy values for positions of the game.
Efficiency of cumulative subtraction games as extensive form games
Urban Larsson, Technion – Institute of Technology, Israel
Abstract: This is an extension of a talk on Cumulative Subtraction Games (CS). Zermelo’s backward induction provides a foundational theory for both combinatorial game theory and classical game theory zerosum extensive form games, in that the optimal play can be computed, although the generic complexity provides little hope for the algorithmically inclined, since the number of terminals grow exponentially with the depth of the game tree. Some time ago, we displayed a beautifully short and efficient way to compute such optimal play outcomes, for the class of 2player symmetric (impartial) CS games. Now, we answer the question, precisely how far does this approach generalize to generalsum extensive form games. The second part of the talk reveals that, in fact nplayer Cumulative subtraction games are in bijective correspondence to classical extensive form games. We finish off by proving that, in the case of 2 player symmetric CS games, the selfinterest optimal actions are identical to those of the analogous zerosum variation, if the reward function is increasing.
(Joint work with Reshef Meir)
The MakerBreaker domination number
Valentin Gledel, LIRIS, University of Lyon, France
Abstract: The MakerBreaker domination game is played on a graph G by Dominator and Staller. The players alternatively select a vertex of G that was not yet chosen in the course of the game. Dominator wins if at some point the vertices he has chosen form a dominating set. Staller wins if Dominator cannot form a dominating set. In this paper we introduce the MakerBreaker domination number of G as the minimum number of moves of Dominator to win the game provided that he has a winning strategy. This parameter is compared with the domination number and residual graphs are introduced to determine the MakerBreaker domination number of an arbitrary tree. The invariant is also obtained for cycles and bounded for union of graphs.
pSaturations of Welter’s game and the irreducible representations of symmetric groups
Yuki Irie, Research Alliance Center for Mathematical Sciences, Tohoku University, Japan
Abstract: We establish a relation between the SpragueGrundy function of psaturations of Welter’s game and the degrees of the ordinary irreducible representations of symmetric groups. We present a theorem on these degrees, and using this theorem, we obtain an explicit formula for the SpragueGrundy function of psaturations of Welter’s game.
Colloquium Hotel
Suggestion: Lisboa São Bento Hotel