Program

Standard Talks, Mornings January 22 and 23 (8:00-13:00): Room - AUDITÓRIO CGD
                             Morning January 24 (8:00-13:00): Room - SALÃO NOBRE


The room EDIFER may be used for discussions

Working Sessions, Afternoons (14:00-18:00): Rooms - CTT, STAPLES, SANTANDER TOTTA, and IAPMEI


List of Participants:
Adam Atkinson, Alda Carvalho, Alexandre Silva, Annamaria Cucinotta, Antoine Dailly, Anwesha Mukherjee, Aviezri Fraenkel, Bernhard von Stengel, Carlos Pereira dos Santos, Craig Tennenhouse, Fionn Mc inerney, Hironori Kiya, João Pedro Neto, Jorge Nuno Silva, Koki Suetsugu, Kyle Burke, Mattieu Dufour, Melissa Huggan, Matthew Ferland, Michael Fisher, Ravi Kant Rai, Richard Nowakowski, Svenja Huntemann, Thane Plambeck, Themis Kavour, Tiago Hirth, Tomoaki Buku, and Urban Larsson.

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)


Antoine Dailly
, LIRIS, University of Lyon, 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.


Anwesha Mukherjee, University of Surrey, United Kingdom

Title: A combinatorial multiple winner contest with package designer preferences

Abstract: We introduce a multiple winner contest in which players, located on a pre-specified graph, expend costly effort,  and a fixed number of adjacent players are selected as winners by applying a lottery contest success function to the summed efforts  from all possible fixed-size connected subgraphs induced by the players. We formalize the generic best response for such a contest  for any arbitrary (connected) network and discuss equilibrium properties for certain regular and irregular networks.


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)


Craig Tennenhouse, University of New England, Maine, United States of America

Title: Towards a short, impartial Tafl variant

Abstract: Tafl games are old precursors to modern chess, and involve asymmetric play. Usually partisan and loopy, they are quite difficult to analyze. We look at a few highly simplified impartial short variants with the hope of applying CGT methods to this ancient and interesting family of games.


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: Dependent sum game: Some variants of Wythoff NIM and Ryuo NIM

Abstract: A Generalized Ryuo NIM for p is a variant of Wythoff NIM. In the game, there are two heaps and each player can move as following:

(i) Choose one heap and take any numbers of stones away.
(ii) Choose both heaps and take stones which are in total less than p away.

The Sprague-Grundy values of this game's positions are obtained by a simple formula. (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. 



Matthew Ferland
, University of Southern California PhD Program, United States of America

Title: Computational Properties of SLIMETRAIL

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)


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.

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.


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)


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)