Réunion d'hiver SMC 2020

Ottawa, 7 - 11 juin 2021

Théorie des jeux combinatoires
Org: Melissa Huggan (Mount Allison University) et Rebecca Milley (Memorial)
[PDF]

KYLE BURKE, Plymouth State University Computational Hardness of Undirected Geography Nimbers [PDF]: The outcome class of Undirected Geography positions is known to be solvable in polynomial time using maximum matchings. We show in this talk, however, that determining the nimber value of N-positions is PSPACE-complete. The authors are aware of no other easy impartial rulesets with hard nimbers. The reduction from Directed Geography provides hardness even on planar graphs and graphs with at least a maximum degree of four. As a corollary, we show that it is PSPACE-hard to find a single Undirected Geography position equivalent to the sum of two others. Additionally, it is hard to find the outcome class of the sum of Undirected Geography position, as well as the generalized variant with multiple tokens.
MICHAEL FISHER, West Chester University Blocking Pebbles [PDF]: In this talk we introduce the game of Blocking Pebbles. The ruleset for this game was inspired by the related graph theoretic notion developed by Lagarias and Saks. Blocking Pebbles is played on a directed acyclic graph with some starting arrangement of blue and red pebbles assigned to the vertex set. On her turn, blue may either (1) pick up at least two blue pebbles on some vertex and move all but one (throw one away as a "toll”) to an out-neighbor; or (2) pick up at least one blue pebble and move it to an in-neighbor. In either type of move, blue is not allowed to move pebbles to a vertex containing any number red pebbles. Red’s moves are similar.
We will look at several game values achievable as Blocking Pebbles positions. We will also briefly comment on the impartial version, and report on the game’s complexity.
MELISSA HUGGAN, Mount Allison University No number avoidance here [PDF]: When do all positions of a game have values that are numbers? In this talk, we will show that two properties are necessary and sufficient. Furthermore, if the stronger property holds for all positions, we can conclude that the values are integers.
This is joint work with Alda Carvalho, Richard J. Nowakowski, and Carlos Pereira dos Santos.
SVENJA HUNTEMANN, Concordia University of Edmonton Temperature of Placement Games [PDF]: The temperature of a game gives an indication of the urgency to move in a component. In recent work with Richard Nowakowski and Carlos Santos, we introduced a technique to bound the temperature of a game based on its confusion interval. We will show how to apply this technique to placement games, such as Domineering or Snort. Further, recent progress on improving the bound will be discussed, as well as work on bounding the temperature of Snort specifically.
NEIL MCKAY, UNB Saint John Sums of games where the players have the same incentives [PDF]: It is common for a standard starting position, say $G$, of a partizan \emph{play} game to have the property that $G = -G$, so that neither Left nor Right has an advantage. This condition implies that the players have the same incentives too. However, this is a weaker condition. In this presentation of joint work with Alexander Clow we show that many (but not all) Hackenbush positions have this weaker property, even though they are Left-win or Right-win. We discuss conditions under which this property is preserved in disjunctive and ordinal sums of games in general.
ALEX MEADOWS, St. Mary's College of Maryland A version of Gale's Nim on four heaps [PDF]: Two customers go to a bookstore that has four shelves for books. The bookstore remains open as long as there are at least three shelves with books on them, and closes once there are two empty shelves. The two customers take turns buying any positive number of books that they wish from one bookshelf. The winning customer is the last customer to buy books while the Bookstore is open. This is also known as the game Gale's Nim (4,2). We show that the winning strategy for this game can be expressed as a Nim-like rule using the base 4 representation of the number of books on each shelf (rather than base 2 as in Nim).
This is preliminary work, joint work with Alyson Conover.
REBECCA MILLEY, Memorial Univesrity The invertible dead-ending positions [PDF]: In recent years, misere game research has focussed on play that is restricted to a given subset or `universe' of games. One universe is the set of dead-ending games: these games have the property that if a player currently has no available move, then they will never again have a move. This universe includes well-studied rule sets such as Hackenbush, Domineering, and others. Since no nonzero games are invertible in full misere play, and few are invertible even in restricted play, an important open problem in the study of dead-ending games is to classify the invertible positions. This talk will prove that a position is invertible modulo dead-ending games if and only if it is `$\mathcal{P}$-free': i.e., if neither the game nor any of its followers are previous-win.
RICHARD NOWAKOWSKI, Dalhousie University A Survey of Ordinal Sums [PDF]: Games whose forms appear complicated often have hidden structure that, once glimpsed, help to make the game analysis easier. One such is when a game is the ordinal sum of two games. Hackenbush trees is the best known example, but only recently have other games been described this way. I'll give a quick survey of these.
CARLOS SANTOS, ISEL-IPL;CEAFEL-University of Lisbon Affine normal play: a complete analysis of Whackenbush [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 so-called entailing moves that break the alternating play axiom and/or restrict the other player's options within the disjunctive sum components. To deal with that, it is possible to rebuild the normal play axioms by using so-called terminating games, or infinities, which is dubbed Affine Normal Play (Larsson, Nowakowski, Santos, 2021). At the first Combinatorial Games Workshop at MSRI, John Conway proposed that an effort should be made to devise some game with entailing moves that is non-trivial, but susceptible to a complete analysis - all attempts which have been tried turn out to be not very interesting. Here we analyze the entailing ruleset Whackenbush, a ruleset played like the classic Blue-Red-Hackenbush with an extra carry-on rule: if, by moving, a player drops one or more opponent’s edges, they have to play again. This is the first complete solution of a partizan ruleset with entailing moves.

haut de la page