CMS 75th+1 Anniversary Summer Meeting

Ottawa, June 7 - 11, 2021

Abstract Submission Form Plenary, Prize and Public Lectures By session By speaker Posters

Combinatorial Game Theory
Org: Melissa Huggan (Ryerson), Svenja Huntemann (Concordia University of Edmonton) and Richard Nowakowski (Dalhousie)
[PDF]

ALEXANDER CLOW, St. Francis Xavier University Red, Blue, Green Poset Games [PDF]

This talk examines Red, Blue, Green (partizan) poset games under normal play. Poset games are played on a poset where players take turns choosing an element of the partial order and removing every element greater than or equal to it in the ordering. The Left player can choose Blue elements (Right cannot) and the Right player can choose Red elements (while the Left cannot) and both players can choose Green elements. Red, Blue and Red, Blue, Green poset games have not seen much attention in the literature, do to most questions about Green poset games (such as CHOMP) remaining open. We focus on results that are true of all Poset games, but time allowing, FENCES, the poset game played on fences (or zig-zag posets) will be considered. This is joint work with Dr.Neil McKay.

MATTHIEU DUFOUR AND SILVIA HEUBACH, UQAM & California State University Los Angeles Circular Nim CN(7,4) [PDF]

Circular Nim CN($n,k$) is a variation on Nim. A move consists of selecting $k$ consecutive stacks from $n$ stacks arranged in a circle, and then to remove at least one token (and as many as all tokens) from the selected stacks. We will briefly review known results on Circular Nim CN($n,k$) for small values of $n$ and $k$ and for some families, and then discuss new features that have arisen in the set of the $\mathcal{P}$-positions of CN(7,4). We will also discuss how some of these new structures appear in the sets of the $\mathcal{P}$-positions of larger games. As time permits, we will discuss aspects of the proof for the $\mathcal{P}$--positions of CN(7,4).

MATT FERLAND, University of Southern California Quantum Combinatorial Games: Structures and Computational Complexity [PDF]

Recently, a standardized framework was proposed for introducing quantum-inspired moves in mathematical games with perfect information and no chance. Going beyond individual games, we explore the tractability of quantum combinatorial games as whole, and address fundamental questions including:

Quantum Leap in Complexity: Are there polynomial-time solvable games whose quantum extensions are intractable?

Quantum Collapses in Complexity: Are there PSPACE-complete games whose quantum extensions fall to the lower levels of the polynomial-time hierarchy?

Quantumness Matters: How do outcome classes and strategies change under quantum moves? Under what conditions doesn't quantumness matter?

PSPACE Barrier for Quantum Leap: Can quantum moves launch PSPACE games into outer polynomial space

We show that quantum moves not only enrich the game structure, but also impact their computational complexity. In settling some of these basic questions, we characterize both the powers and limitations of quantum moves as well as the superposition of game configurations that they create. Our constructive proofs-both on the leap of complexity in concrete Quantum Nim and Quantum Undirected Geography and on the continuous collapses, in the quantum setting, of complexity in abstract PSPACE-complete games to each level of the polynomial-time hierarchy-illustrate the striking computational landscape over quantum games and highlight surprising turns with unexpected quantum impact. Our studies also enable us to identify several elegant open questions fundamental to quantum combinatorial game theory (QCGT).

MELISSA HUGGAN, Ryerson University The Game of Flipping Coins [PDF]

Coin flipping games have been studied for decades. In particular, Berlekamp, Conway and Guy introduced many impartial coin flipping games in their book series Winning Ways for Your Mathematical Plays. In this talk, we will explore a brief history of such combinatorial games, and then introduce a new partizan variant called Flipping Coins.

Flipping Coins is played on a row of coins, laying flat on a table. Each coin has two sides: one side is labelled by T and the other by H. Only one side is facing up for each coin. There are two players called Left and Right. On their turn, Left chooses two coins labelled T, and flips them to H. Right chooses two coins, one labelled H and the other T, as long as they appear in that order within the row, and flips them to T and H respectively. The last player to move wins. We show that the values of this game are numbers, and these are found by applying a reduction, then decomposing the position into an iterated ordinal sum. This unexpected result leads to many questions for future research.

This is joint work with Anthony Bonato and Richard J. Nowakowski.

SVENJA HUNTEMANN, Concordia University of Edmonton Counting Domineering positions [PDF]

In Domineering, two players place dominoes on a checkerboard (or parts thereof), one vertically, the other horizontally. We will demonstrate a technique to recursively determine the polynomial profile of Domineering positions on rectangular boards. The polynomial profile enumerates the positions with a fixed number of pieces from each player and can be used to determine the total number of positions, as well as the positions when only considering strictly alternating play. We will further discuss variations of this technique for non-rectangular boards, maximal positions, and Left and Right ends.

This is joint work with Neil McKay.

URBAN LARSSON, National University of Singapore Game values of arithmetic functions [PDF]

Arithmetic functions in Number Theory meet the Sprague-Grundy function from Combinatorial Game Theory. We study a variety of normal-play games induced by standard arithmetic functions, such as divisors, remainders and relatively prime numbers, and their negations. For the ruleset induced by the division algorithm, we prove that the relative Sprague-Grundy values tend to 0 with increasing heap sizes. Preprint at https://arxiv.org/pdf/2101.07608.pdf

NEIL MCKAY, $\emptyset$ Which games are equalish to 0? [PDF]

Toppling Dominoes is a game played by Black and White on a row of standing black, white, or grey dominoes. On their turn, a player chooses a domino of their colour (or a grey domino) and topples it either left or right, every domino in that direction also topples and is removed from the game. A player unable to move loses.

In an all-grey row, the game ends exactly when neither player has any available moves. Any other game could conceivably end when only a domino of the opponents colour remains. Games that always end with neither player having any available moves are called dicotic and they are equalish to 0. Though very few positions are dicotic, there are many positions equal to dicotic games; we describe these positions. We discuss which simple games are equalish to some Toppling Dominoes position.

REBECCA MILLEY, Grenfell Campus, Memorial University of NL P-free dead-ending misere games [PDF]

In recent years, misere game research has focussed on play that is restricted to a given subset or `universe' of games. The set of dead-ending games is the most well-studied misere universe. Consider the subset of dead-ending games that are `$\mathcal{P}$-free': games with outcome $\mathcal{L}$, $\mathcal{N}$, or $\mathcal{R}$, with no followers that are previous-win. Note that $*=\{\cdot|\cdot\}$ is not $\mathcal{P}$-free. This set of games exhibits a number of algebraic properties from normal play that do not hold in misere play (even when restricted to dead-ending games). For example, a left-win game plus a left-win game is left-win, and $\mathcal{L}+\mathcal{N}$ is either $\mathcal{L}$ or $\mathcal{N}$. This talk will prove these and other properties and will discuss in-progress conjectures about the closure and invertibility of $\mathcal{P}$-free games.

CARLOS SANTOS, ISEL-IPL;CEAFEL-University of Lisbon Impartial games with entailing moves [PDF]

Combinatorial Game Theory has also been called `additive game theory', whenever the analysis involves sums of independent game components. Such disjunctive sums invoke comparison between games, which allows abstract values to be assigned to them. However, there are rulesets with entailing moves that break the alternating play axiom and/or restrict the other player's options within the disjunctive sum components. These situations are exemplified in the literature by a ruleset such as Nimstring, a normal play variation of the classical children's game Dots and Boxes, and Top Entails, an elegant ruleset introduced in the classical work Winning Ways, by Berlekamp Conway and Guy. Such rulesets fall outside the scope of the established normal play theory. Here, we axiomatize normal play via two new terminating games, Inf (Left wins) and -Inf (Right wins), and a more general theory is achieved. We define affine impartial, which extends classical impartial games, and we analyze their algebra by extending the established Sprague-Grundy theory, with an accompanying minimum excluded rule. Solutions of Nimstring and Top Entails are given to illustrate the theory.

AARON SIEGEL The Abstract Structure of Misère Impartial Games, Part 2 [PDF]

Combinatorial games in misère play have been the subject of increasing interest in recent years, yet much still remains unknown about the structure of misère impartial games under classical (Conway) equality. In this talk, I will discuss the abstract structure of the canonical monoid $\mathcal{M}$ of misère games. I will give a proof of Conway's theorem that $\mathcal{M}$ is cancellable; then I will present a few new results, including a proof that $\mathcal{M}$ is "almost" torsion-free.

This talk is a follow-up to a previous talk presented at the online CGT seminar in March 2021. However, the material is mostly independent, and it is not necessary to have attended the prior talk. Some of the work presented in this talk was joint work with John Conway and Dan Hoey.

top of page