Program
Standard Talks, Mornings - AUDITÓRIO 2, Quelhas
Working Sessions, Afternoons (14:00-18: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:30-8:45 |
Opening ceremony |
||
8:45-9:00 |
Richard Nowakowski, Dalhousie University, Trends in Combinatorial Game Theory |
||
9:00-9:30 |
Yuki Irie, Tohoku University, p-Saturations of Welter's game and the irreducible representations of symmetric groups |
Tomoaki Abuku, University of Tsukuba, On NIM-like games played on graphs |
|
9:30-10: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:00-10:30 |
Michael Fisher, West Chester University, Beatty Games: Big and Small |
Alda Carvalho, ISEL & CEMAPRE-UL, Combinatorics of JENGA |
Valentin Gledel, University of Lyon, The Maker-Breaker domination number |
10:30-11:00 |
Coffee-break |
Coffee-break |
Coffee-break |
11:00-11:30 |
Carlos Pereira dos Santos, CEAFEL-UL & 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:30-12: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:00-12:30 |
Bernhard von Stengel, London School of Economics, Computational progress on the Catch-Up game |
Urban Larsson, Technion - Institute of Technology, Efficiency of cumulative subtraction games as extensive form games |
Matthew Ferland, University of Southern California, Computational Properties of SLIMETRAIL |
12:30-13:00 |
Melissa Huggan, Dalhousie University, The Index: a measure of equality
|
||
13:00-14:00 |
Break for lunch |
Break for lunch |
Break for lunch |
14:00-18:00 |
Working sessions |
Working sessions |
Working sessions |
19.00-23:00 |
Conference Dinner |
Alda Carvalho, ISEL & CEMAPRE-UL, Portugal
Title: Combinatorics of JENGA
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)
(Joint work with Carlos Pereira dos Santos and João Pedro Neto)
Antoine Dailly, G-SCOP, University of Grenoble, France
Title: Connected subtraction games on graphs
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)
(Joint work with Julien Moncel and Aline Parreau)
Bernhard von Stengel, Department of Mathematics, London School of Economics, UK
Title: Computational progress on the Catch-Up game
Abstract: We report on computational progress on the game «Catch-Up» analyzed by Isaksen, Ismail, Brams, and Nealen in 2015. Two players pick and remove numbers from the set {1,...,n} according to the «catch-up» rule that says you pick the next number as long as the sum of your numbers is less than that of the other player. After that (having reached an equal or higher sum), players switch. The player with the higher sum at the end wins. For n=5, for example, the first player wins by first picking 3. With old-fashioned memory-saving coding but large computer memory, we extend the computational analysis for optimal play from maximally n=18 to n=28. The following pattern emerges: When there can be a draw (when n or n+1 is divisible by 4), there will be a draw, and when there cannot be a draw, for n=21 or larger the first player wins with the first picked number no larger than 3. (For n=9,10,14,18 the first player loses, which seem to be the exceptions.) Further computational analysis may help in eventually finding an induction proof to prove this in general.
Title: Computational progress on the Catch-Up game
Abstract: We report on computational progress on the game «Catch-Up» analyzed by Isaksen, Ismail, Brams, and Nealen in 2015. Two players pick and remove numbers from the set {1,...,n} according to the «catch-up» rule that says you pick the next number as long as the sum of your numbers is less than that of the other player. After that (having reached an equal or higher sum), players switch. The player with the higher sum at the end wins. For n=5, for example, the first player wins by first picking 3. With old-fashioned memory-saving coding but large computer memory, we extend the computational analysis for optimal play from maximally n=18 to n=28. The following pattern emerges: When there can be a draw (when n or n+1 is divisible by 4), there will be a draw, and when there cannot be a draw, for n=21 or larger the first player wins with the first picked number no larger than 3. (For n=9,10,14,18 the first player loses, which seem to be the exceptions.) Further computational analysis may help in eventually finding an induction proof to prove this in general.
Carlos Pereira dos Santos, CEAFEL-UL & ISEL, Portugal
Title: Extended Combinatorial Game Theory: the effect of the terminal move
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)
(Joint work with Richard Nowakowski and Urban Larsson)
Fionn Mc Inerney, Université Côte D'Azur, France
Title: The ORTHOGONAL COLOURING GAME on graphs
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 PSPACE-complete 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.
Hironori Kiya, Nagoya University, Japan
Title: Two player TANHINMIN and its extension
Abstract: TANHINMIN is a card-based 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 2-player generalized TANHINMIN, where the size of the deck is arbitrary. We also consider a 2-player generalized TANHINMIN with extra rules. For both, we show that the winner can be decided in polynomial time.
Koki Suetsugu, Kyoto University, Japan
Title: On Wythoff type extension of general subtraction game
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 Sprague-Grundy 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 all-but NIM. We include the case that replaced rules are different for each heap.
(Joint work with Tomoaki Abuku and Ko Sakai)
Marc Heinrich, LIRIS, University of Lyon, France
Title: Partizan subtraction games
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)
Matthew Ferland, University of Southern California PhD Program, United States of America
Title: Computational Properties of SLIMETRAIL(Joint work with Eric Duchêne, Richard Nowakowski and Aline Parreau)
Matthew Ferland, University of Southern California PhD Program, United States of America
Abstract: Computational complexity provides a valuable lens to determine if a combinatorial game is "fun." If a game is computationally intractable, then it lacks a simple algorithm to always determine a winning move. Through reductions, we demonstrate that SLIMETRAIL is PSPACE-Complete.
(Joint work with Kyle Burke)
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.
Melissa Huggan, Dalhousie University, Canada
Title: The Index: a measure of equality
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)
Michael Fisher, West Chester University, United States of America
Title: Beatty Games: Big and Small
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 non-atomic version, where the left and right subtraction sets are given by {α} and {β}, respectively.
We will also report results for the non-atomic 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.
Melissa Huggan, Dalhousie University, Canada
Title: The Index: a measure of equality
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)
Ravi Kant Rai, Indian Institute of Technology Bombay, India
Title: Optimal play in DUIDOKU game
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)
(Joint work with K.S. Mallikarjuna Rao)
Richard Nowakowski, Dalhousie University, Canada
Title: Trends in Combinatorial Game Theory
Abstract: There is more to Combinatorial Game Theory than just solving games. I'll give an overview of the ethos of Combinatorial Game Theory and some of the latest directions of Combinatorial Game Theory research including advances on open problems.
Svenja Huntemann, Carleton University, Canada
Title: Enumerating DOMINEERING
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)
Thane Plambeck, Counterwave inc, United States of America
Title: Shotgun wedding: ECGT + CGT
(Joint work with Neil McKay)
Thane Plambeck, Counterwave inc, United States of America
Title: Shotgun wedding: ECGT + CGT
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.
Tomoaki Abuku, University of Tsukuba, Japan
Title: On NIM-like games played on graphs
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 non-negative 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.
Urban Larsson, Technion - Institute of Technology, Israel
Title: Efficiency of cumulative subtraction games as extensive form games
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 zero-sum 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 2-player symmetric (impartial) CS games. Now, we answer the question, precisely how far does this approach generalize to general-sum extensive form games. The second part of the talk reveals that, in fact n-player 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 self-interest optimal actions are identical to those of the analogous zero-sum variation, if the reward function is increasing.
(Joint work with Reshef Meir)
Valentin Gledel, LIRIS, University of Lyon, France
Title: The Maker-Breaker domination number
Abstract: The Maker-Breaker 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 Maker-Breaker 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 Maker-Breaker domination number of an arbitrary tree. The invariant is also obtained for cycles and bounded for union of graphs.
Tomoaki Abuku, University of Tsukuba, Japan
Title: On NIM-like games played on graphs
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 non-negative 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.
Urban Larsson, Technion - Institute of Technology, Israel
Title: Efficiency of cumulative subtraction games as extensive form games
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 zero-sum 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 2-player symmetric (impartial) CS games. Now, we answer the question, precisely how far does this approach generalize to general-sum extensive form games. The second part of the talk reveals that, in fact n-player 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 self-interest optimal actions are identical to those of the analogous zero-sum variation, if the reward function is increasing.
(Joint work with Reshef Meir)
Valentin Gledel, LIRIS, University of Lyon, France
Title: The Maker-Breaker domination number
Abstract: The Maker-Breaker 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 Maker-Breaker 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 Maker-Breaker domination number of an arbitrary tree. The invariant is also obtained for cycles and bounded for union of graphs.
Yuki Irie, Research Alliance Center for Mathematical Sciences, Tohoku University, Japan
Title: p-Saturations of Welter's game and the irreducible representations of symmetric groups
Abstract: We establish a relation between the Sprague-Grundy function of p-saturations 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 Sprague-Grundy function of p-saturations of Welter's game.
Title: p-Saturations of Welter's game and the irreducible representations of symmetric groups
Abstract: We establish a relation between the Sprague-Grundy function of p-saturations 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 Sprague-Grundy function of p-saturations of Welter's game.
