Combinatorial Game Theory Colloquium II
(Lisbon, 25-27 January, 2017)
Combinatorial Game Theory (CGT) is a branch of mathematics that studies sequential games with perfect information. Combinatorial games include well-known 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 second edition of the CGTC, 25-27 January, 2017, 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 Laboratório de Modelação e Agentes. The Colloquium will be hosted by the Faculty of Sciences, University of Lisbon (for a map of its location press here).
Standard Talks, Mornings (8:00-13:00) – BuildingC6, Room 6.2.56
Working Sessions, Afternoons (14:00-18:00) – BuildingC8, Rooms 8.2.11, 8.2.13, 8.2.17,8.2.19
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, 2017 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 2 (CGTC2) held in Lisbon in January 2017.”.
Urban Larsson AE IJGT, Carlos Pereira dos Santos, Richard Nowakowski
Scientific Committee
Alda Carvalho, ISEL & CEMAPRE
Aviezri S. Fraenkel, Weizmann Institute of Science
Brett Stevens, Carleton University
Carlos Pereira dos Santos, LA & CEAFEL-University of Lisbon
Gabriel Renault, Sopra Steria
João Pedro Neto, University of Lisbon
Jorge Nuno Silva, University of Lisbon
Pedro J. Freitas, CEAFEL-University 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 & UIDEF-University of Lisbon
Carlos Pereira dos Santos, LA & CEAFEL-University of Lisbon
Jorge Nuno Silva, CIUHCT-University of Lisbon
Pedro J. Freitas, CEAFEL-University of Lisbon
Tiago Hirth, LA
Tiago Robalo, LA
Standard Talks, Mornings (8:00-13:00) – Building C6, Room 6.2.56
Working Sessions, Afternoons (14:00-18:00) – Building C8, Rooms 8.2.11, 8.2.13, 8.2.17, 8.2.19
Scoring mean value theorem
Carlos Pereira dos Santos, CEAFEL, University of Lisbon
Abstract: Regarding short Conway’s group, a value of a game can be thought of as an indeterminate cloud, covering the confusion interval. In such a situation it is natural to ask – Is there a fair settlement about the value of a game? The answer is well-known; it is the mean value m(G) (a number), satisfying
n.m(G)-t ≤ n.G ≤ n.m(G)+t (for some fixed perturbation t).
In this work, we discuss the occurrence of a mean value in the guaranteed scoring universe which is, in some sense, two-dimensional due the different nature of moves and points.
(joint work with Richard Nowakowski and Urban Larsson)
Eternal Picaria
Israel Rocha, Dalhousie University
Abstract: Picaria is a traditional board game, played by the Zuni tribe of the American Southwest and other parts of the world, such as a rural Southwest region in Sweden. It is related to the popular children’s game of Tic-tac-toe, but the 2 players have only 3 stones each, and in the second phase of the game, pieces are slided, along speci_ed move edges, in attempts to create the three-in-a-row. We provide a rigorous solution, and prove that the game is a draw; moreover our solution gives insights to strategies that players can use.
(joint work with Urban Larsson)
Solving misère illuNIMati through boomerang games
Gabriel Renault, Sopra Steria
Abstract: IlluNIMati is a partizan variant of NIM in which tokens are triangles with a blue vertex, a green vertex and a red vertex. Only Left may play in a heap where the vertex facing North of the top triangle is blue. Only Right may play in a heap where the vertex facing North of the top triangle is red. They may both play in a heap where the vertex facing North of the top triangle is green. However, after removing any positive number of triangles of a heap, they may turn this heap, choosing which vertex faces North. We consider illuNIMati positions within a bigger set of games, called boomerang games, to solve the misère version.
A two-player pebbling game
Craig Tennenhouse, University of New England
Abstract: Blocking Pebbles is a partizan game based on graph pebbling directed acyclic graphs. We demonstrate some results on oriented trees, and find numbers, nimbers, and some infinitesimals on the out-star.
(joint work with Mike Fisher)
Cricket pitch perfection
R. J. Nowakowski, Dalhousie University
Abstract: A cricket Pitch is a path with bumps (non-negative weights) and a roller that resides at the vertices. Left rolls (one or more edges) to the left and Right to the right reducing each bump by 1. The roller cannot go over a 0-edge, this part is `perfect’. Nowakowski and Ottaway partially solved the game. Nowakowski and (Angela) Siegel give a complete solution in terms of reductions and ordinal sums.
(joint work with Paul Ottaway and Angela Siegel)
The OSLO game of Hives
Paul Ottaway, Capilano University
Abstract: Hives is a one-sided loopy (OSLO) game played on a graph with white and red vertices. On Right’s turn, they may colour any white vertex red as long as the set of red vertices form an independent set. On Left’s turn, they may swap the colour of any two adjacent vertices as long as the red vertices remain an independent set. Note that Left has the equivalent of a pass move by selecting a pair of adjacent white vertices while Right does not have a pass move. The game ends when the red vertices form a maximal independent set. In this talk, we will examine the game values and algebraic structure that exists in Hives, provide strategies for certain classes of graphs as well as decomposition theorems for general graphs.
Atomic weight calculus of Subversion
Michael Fisher, West Chester University
Abstract: In this work we analyze Subversion, a recently proposed all-small combinatorial ruleset. Often, the atomic weight calculus, allowing the recursive computation of the atomic weight of a game G with the atomic weights of its options, is not easy. However, Subversion is an interesting case such that the theoretical difficult cases are reduced to a finite number of cases and organized in a table. With the table, given a Subversion position (a,b), a≥b, using the Euclidean algorithm and the continued fraction representation of a/b, it is possible to compute aw(a,b). An algorithm for that is presented.
(joint work with Neil McKay, Richard J. Nowakowski, Paul Ottaway and Carlos Santos)
Quotients for push-button games
Marc Heinrich, LIRIS, University of Lyon
Abstract: We study a new construction which aims at solving the following question: what happens if we allow players to change the rules of the game during the play? Given two rulesets R0 and R1, we create a new ruleset R0 ⇒ R1 corresponding to the following: the two players play according to rules R0 until one of the players at its turn pushes an imaginary button, changing the rules to R1. We study how several classical impartial games like Nim, Wythoff, Euclid or Cram combine with this construction. By adapting indistinguishably quotients (technique of Plambeck, 2005), we look at how these new rules behave for sums of positions. We show that it is possible to give values to game positions which behave similarly to Grundy values.
(joint work with Eric Duchêne, Urban Larsson, Aline Parreau)
The computational complexity of two card games with theoretical applications
Valia Mitsou, LIRIS, University of Lyon
Abstract: The main theme of this talk is card games that can be naturally reformulated as well-known graph-theoretic games. In particular, we will focus on two different card games: the game of SET and the game of UNO. The objective of the former is to form sets of cards that match in a certain sense, while in the latter the players need to discard their cards following a matching rule (for more details regarding the rules of the two games please visit the following websites: official website of SET, wikihow: how to play UNO). We show natural reformulations of SET as arc-kayles and of UNO as generalized geography and present some complexity results about them.
Octal games on graphs
Antoine Dailly, LIRIS, University of Lyon
Abstract: Octal games are a well-defined family of two-player games played on heaps of counters, in which the two players take turns removing a certain number of counters from a heap, sometimes being allowed to split a heap in two nonempty heaps, until no counters can be removed anymore. We extend the definition of octal games to play them on graphs: heaps are replaced by connected components and counters by vertices. Thus, an octal game on a path of n vertices is equivalent to playing the same octal game on a heap of n counters. We study one of the simplest octal games, called 0.33, in which the players can remove one vertex or two adjacent vertices without disconnecting the graph, on trees. We present a thorough study of the game on subdivided stars and bistars.
New results on circular NIM
Matthieu Dufour, Université du Québec à Montréal
Abstract: Matthieu Dufour and Silvia Heubach have been studying Circular Nim, a variation on the well-known game of NIM. This t:wo player game, described with two parameters and noted C(n,k), is played in the following way: n stacks of tokens are arranged in a circular way, and a move consists of choosing k consecutive stacks of this circular arrangement and then taking at least one token from one or more of the k stacks. In normal play, C(n,1), C(n,n-1) and C(n,n) are trivial. C(4,2) is easy, C(5,2), C(5,3) and C(6,3) are known since (Ehrenborg and, Steingrimsson, 1996) and C(6,4) and C(8,6) were solved by Dufour and Heubach (2012). We will present some more results, conjectures and comments on the misere play of that game.
Aviezri S. Fraenkel, Weizmann Institute of Science
Title: Games derived from a generalized Thue-Morse word
(Joint work with Michel Rigo.)
Melissa Huggan, Dalhousie University
(joint work with Richard Nowakowski)
Clement Charpentier, University Grenoble-Alpes
Title: The coloring game on cactuses
Abstract: The coloring game on a graph G is a game where the two players, Alice and Bob, are taking turns coloring a yet-uncolored vertex of G with a color chosen into a set C. Alice wins if the manage to color G entirely and Bob wins if a vertex in uncolorable at some point. We denote by Xg(G) the smallest number of colors for which Alice has a winning strategy. A graph is (1,k)-decomposable if its edges can be partitionned into two subsets, one inducing a forest and the other inducing a subgraph of maximum degree at most k. For any forest F, χg(F)≤4 (Faigle et al, 1993). We know, thanks to He et al. (2002), that χg(G)≤4+k for any (1,k)-decomposable graph. Montassier et al. (2012) proved that any planar graph of girth at least 8 is (1,1)-decomposable, and so χg(G)≤5. We prove this bound is best possible, even for graphs with arbitrary large girth and for several subclasses of planar graphs, by a result on cactuses. A cactus is a graph whose edges all belong to at most one cycle (which makes them all planars).
Theorem: For every integer g≥3, d≥0, there is a cactus C of girth g with distance between cycles at least d and for which χg(C)=5.
Silvia Heubach, California State University
Title: The game creation operator
(joint work with Matthieu Dufour and Urban Larsson)
Rebecca Miley, Memorial University of Newfoundland
Title: Inverses and reversibility: open problems in restricted misère games
Abstract: Much progress has been made in misère game theory using the technique of “restricted” misère play, where games can be considered equivalent inside a restricted set of games without being equal in general. Restricted misère play exhibits much more structure than general misère play, but there are a number of curious properties that complicate matters: (1) a position can have an additive inverse that is not its negative, and (2) a position can satisfy reversibility through an end (a game with Left but not Right options, or vice versa). These properties do not occur in normal play and general misère play, respectively. This talk presents a survey of recent developments in restricted misère games and discusses open problems related to invertibility and reversibility.
(Based on joint work with Gabriel Renault)
Svenja Huntemann, Dalhousie University
Title: The value set of strong placement games
Abstract: We are interested in what values strong placement games, a class of games including Domineering and Snort, can take under normal play. In studying this question, we take advantage of the one-to-one correspondence between strong placement games and simplicial complexes (with vertex set bipartitioned), and the known structure of the game tree. Among others, we will show that all numbers are possible.
Urban Larsson, Industrial Engineering and Management, Technion
Title: Dots and Boxes and infinities in scoring combinatorial games
Abstract: We study an extension of the Guaranteed scoring universe (presented at CGTC I), where infinities are used (as threats) to terminate a game. A new reduction is obtained, and we use it to find the simplest form for a basic Dots and Boxes position, namely an open ended double box.
(joint work with Richard Nowakowski and Carlos Pereira dos Santos)
Tomoaki Abuku, University of Tsukuba
Title: Analysis of transfinite Welter’s game
Abstract: As well-known, in impartial game, we can judge which player can win in a position of game by its Grundy number. Deciding Grundy numbers in Welter’s Game is fairly complicated even in its original form. In this talk, we analyze the transfinite version of Welter’s Game, namely its extension into the set of general ordinal numbers.
Jorge Nuno Silva, University of Lisbon; Alex de Voogt, AMNH, New York
Title: Towards a first understanding of mancala games through CGT
Abstract: Only few traditional games have been analyzed using combinatorial game theory (CGT), specifically Konane and Tiouk-Tiouk. The class of mancala games shows at least one example of another traditional game to which CGT can be applied. We explored the variant Hawalis, currently played competitively in Oman. The values of the studied end-game positions give insight in the game. This approach looks promising to this variant and potentially other variants of the mancala family.
Alexandre Mena Silva, University of Minho
Title: 3-Player CGT with «podium rule»
Abstract: In the first part of the talk, we briefly discuss the state of art about the research on combinatorial 3-player games. Playing with the «podium rule convention», if a player cannot be last, he tries to be last but one. In his paper «N-person Nim and N-person Moore’s games», S Liu presented a very elegant characterization of the P-positions of 3-player NIM with podium rule (and, in general, for N-player NIM). In the second part of the talk, we show how Liu’s work can be extended, presenting the general reduction process and related canonical forms.
(joint work with Richard J. Nowakowski and Carlos Santos)
Koki Suetsugu, Kyoto University
Title: 3-player NIM with preference
Abstract: In order to analyze multiplayer CGT, we need to consider the objectives of players that are guaranteed to lose. For example, in a 3-player game where one player cannot win, it is still possible that she can determine whether the next player or previous player will win. In this presentation, we assume each player has a fixed “preference”, which is defined as a total ordering of the other players, and each player’s preference is known by all other players. When a player cannot win, she behaves so that the winner will have the highest possible preference value. We present solutions for various forms of preferences in 3-player NIM.
Valentin Gledel, LIRIS, University of Lyon
Title: Non-attacking rooks on a holed chessboard
Abstract: In this game, inspired by the Non-Attacking Queens Game (Noon and Van Brummelen, 2006), two players alternately put rooks on a chessboard with the restriction that no rook should be able to capture another one. The last player to play wins. If the chessboard is a rectangular grid, the problem reduces to a parity game. In this work we consider the case where there is a hole in the chessboard. This problem is much more difficult and leads to the introduction of a game played on graphs that can be sees as a generalization of Arc-Kayles. We solved this latter game for simple graphs and found some general properties.
(joint work with Nicolas Bousquet, Antoine Dailly and Marc Heinrich)
Thane Plambeck, Counterwave, inc
Title: Research topics in Impartial Games
Abstract: A selection of fundamental problems in Impartial games that still bug me and that I wish people would work on.
Dmitry Levandu, National Research University
Title: Formation of coalition structures as a non-cooperative game
Abstract: The paper defines a non-cooperative simultaneous finite game with an arbitrary fixed number of potential deviators. A definition of the game embeds a coalition formation mechanism, which includes a number of deviators, a set of eligible partitions and coalition formation rule. The game has an equilibrium in mixed strategies. The equilibrium encompasses intra and inter group externalities and an individual payoff allocation that make it different from a strong Nash, coalition-proof equilibrium and certain other equilibrium concepts. We offer a non- cooperative stability criterion to describe the robustness of an equilibrium strategy profile with respect to an to an increase in the number of deviators. The criterion may serve to measure self-enforcement property of an equilibrium and focal points of a game.
Tristan Cazenave, Université Paris-Dauphine
Title: Improving Monte Carlo for misere games
Abstract: Monte Carlo Tree Search with random playouts can be much improved in misere games by avoiding losing moves in playouts. We will show on multiple misere games that this simple modification can improve drastically the level of play. We will also consider the combination with playout policy learning.
Conference Dinner
The colloquium dinner is at Paparrucha restaurant.
http://www.lapaparrucha.com/en
The view is superb (Lisbon night)!
The dinner is on January 26, 7:00 p.m.
Gallery Photos
Opening Session
Conference Room
Conference Room view
Conference Dinner
Talk
Break
Group Photo
Institutions
