2022 CMS Summer Meeting
St. John's, June 3 - 6, 2022
Org: Melissa Huggan (Mount Allison University), Svenja Huntemann (Concordia University of Edmonton) and Rebecca Milley (Memorial)
[PDF]
- ALEX CLOW, St. Francis Xavier University
Chomp on Hexagonal Grids & Other Lexicographic Products of Impartial Poset Games [PDF]
-
This talk discusses \textsc{Chomp} on a hexagonal grid (or \textsc{HoneyComb Chomp}), a poset game that generalizes the well known game of \textsc{Chomp}, played on a square grid. We note that a hexagonal grid is the lexicographic product of a square grid and a total order of size $2$. In order to understand \textsc{HoneyComb Chomp} we develop a theory of lexicographic products of impartial poset games. This theory allows us to determine the value of a follower of a lexicographic product of impartial poset games given only the value of a corresponding follower of the left factor in the initial product. This reduces calculating the nimber of a position in \textsc{HoneyComb Chomp} to calculating the nimber of a corresponding \textsc{Chomp} position. Furthermore, this corresponding position is easily constructed in polynomial. This is joint work with Dr.Neil McKay.
- VALENTIN GLEDEL, Umeå University
Phantom Arc-Kayles [PDF]
-
Combinatorial games are finite, two players games, with perfect information. On the other hand, "economical" game theory is about games that can have many players, simultaneous moves and probabilistic strategies. With phantom games, for which we introduce a general formalization, we try to build a bridge between combinatorial games and economical games by removing the perfect information component of combinatorial games and thus introducing probabilistic strategies. Inspired by the games Phantom Go and Kriegspiel, phantom games have two players and a referee. The two players have no information about the other player moves, and only the referee knows about the exact state of the game. When one of the player tries a move, the referee either confirms that the move is legal considering the state of the game, and the move is then played, or the referee says that the move is not actually legal and ask the player to try another move.
After defining the concepts of strategies and probability of winning for phantom games, we will study the example of Phantom Arc-Kayles. Arc-Kayles is a game played on a graph, where the two players iteratively select an edge of the graph to remove it and all its incident edges. The player that play the last move wins the game. For the phantom version, we give results for paths and cycles with few vertices, union of paths and cycles. To conclude this presentation, we will give a few open problems for this topic.
- MELISSA HUGGAN, Mount Allison University
A partizan deletion game [PDF]
-
This game is played on a graph with coloured edges. There are two players who alternately delete edges of their assigned colour; blue for Left and red for Right. A player gains a point for every vertex that they isolate. This is a partizan version of the game called "Le Pic Ar\^{e}te".
In this talk, we will discuss progress on solving this game for paths. We present reductions that break down any path into a disjunctive sum of purely alternating paths, waiting moves, and a score. From here, we will discuss good moves and how to compute the score of the game. This is joint work with Michael H. Albert and Richard J. Nowakowski.
- SVENJA HUNTEMANN, Concordia University of Edmonton
Nofil played on Steiner Triple Systems [PDF]
-
Nofil is an impartial game in which players chose points of a combinatorial design. A player who chooses the last point of a block loses the game. Many games reduce eventually to playing on a graph and Nofil is then equivalent to playing Node Kayles on this graph. We show that every Node Kayles position could appear in a game of Nofil played on a Steiner Triple System. Thus Nofil on STS is PSPACE-complete for randomized reductions.
This is joint work with Melissa Huggan and Brett Stevens.
- REBECCA MILLEY, Grenfell Campus, Memorial University of NL
Game tree decomposition: which games are sums of other games? [PDF]
-
Combinatorial games are usually studied in the context of a specific winning condition (e.g., normal play or misere), and individual game trees are simplified according to the rules of that winning condition and / or universe of play. In this talk (joint work with Neil McKay and Michael Fisher), we study game trees without reference to winning condition - the only permitted simplification is the removal of duplicate options - and we ask, "When is a game literally equal to the disjunctive sum of two other (nonzero) games?" We present an algorithm for determining when a given game $G$ is "composite" and for finding the nonzero $H$, $K$ such that $G$ is literally equal to $H + K$.
- LEXI NASH, Concordia University of Edmonton
Enumeration, values, and stacking of distance games [PDF]
-
Distance Games are a class of combinatorial games in which pieces are placed on a board such that they are the proper distances from previously placed pieces. This talk will give a brief overview of three topics of interest related to distance games. The first is the enumeration of positions of the games \textsc{Col}, \textsc{Snort}, and \textsc{Cis} played on stars and cycles, as well as generalizations of these games played on paths. The second is studying a new operation on these games, called ``stacking''. Lastly we discuss finding values for some of theses games.
This is joint work with Svenja Huntemann and Khoa Bui.
- THOMAS WOLF, Brok University
Comments on Playing the Dots and Boxes Game [PDF]
-
The Dots and Boxes game is long known and analyzed in detail by Elwyn Berlecamp and others in ”Winning Ways, vol 2” and in ”The Dots-and-Boxes Game: Sophisticated Child’s Play”. A number of computer programs exist. For not too large board sizes, computer programs of David Wilson allow optimal play and the determination of the game value for each move.
In the talk rules for determining the order of so called ’loony’ moves are presented, as well as rules for deciding when to take control. No restrictions on loops are imposed.
A new derivation of the Long Chain Rule is valid in the presence of loops. It allows a more correct interpretation of its statement.
The overall decision tree for selecting the next move is formulated in a non-technical language accessible to school students.