Théorie des jeux combinatoires
Org:
Melissa Huggan (Ryerson),
Svenja Huntemann (Concordia University of Edmonton) et
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 zigzag 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 quantuminspired 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 polynomialtime solvable games whose quantum extensions are intractable?
Quantum Collapses in Complexity: Are there PSPACEcomplete games whose quantum extensions fall to the lower levels of the polynomialtime 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 proofsboth 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 PSPACEcomplete games to each level of the polynomialtime hierarchyillustrate 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 nonrectangular 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 SpragueGrundy function from Combinatorial Game Theory. We study a variety of normalplay 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 SpragueGrundy 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 allgrey 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
Pfree deadending 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 deadending games is the most wellstudied misere universe. Consider the subset of deadending games that are `$\mathcal{P}$free': games with outcome $\mathcal{L}$, $\mathcal{N}$, or $\mathcal{R}$, with no followers that are previouswin. 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 deadending games). For example, a leftwin game plus a leftwin game is leftwin, and $\mathcal{L}+\mathcal{N}$ is either $\mathcal{L}$ or $\mathcal{N}$. This talk will prove these and other properties and will discuss inprogress conjectures about the closure and invertibility of $\mathcal{P}$free games.
 CARLOS SANTOS, ISELIPL;CEAFELUniversity 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 SpragueGrundy 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" torsionfree.
This talk is a followup 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.
© Société mathématique du Canada