CMS 2015 Summer Meetings, Day 1, Afternoon

(The CGT sessions were only held on the first day, so this is as far as my notes go.)

In the afternoon sessions, I spoke first about placement games on graphs, some variants that could be applied to all of them, and the computational complexity of the resulting games (of which very little is known).

Rebecca Milley went next, and this was the first time I'd ever heard an academic talk about Bowling Kayles!  She introduced a partisan version: Left knocks down 1 pin and Right knocks down 2 neighboring pins.  Rebecca the misere expert naturally considered that angle: who wins under misere play?  (I don't remember if the normal play version is solved.  It seems like it wouldn't be hard to show that Left always wins if there are any pins.) 

Misere games don't have additive inverses, because addition doesn't follow happy group rules.  Specifically, you can have games G and H (G's "inverse") where G + H = 0, but G and H's conjugate don't have the same outcome class when you start adding them to other positions.  (I don't recall how to derive the conjugate; I should learn that!)  In normal play, G+H = 0 means that G = -H, but that's not always the case in misere-land.

Rebecca's Partisan Kayles demonstrates positions with this inequivalence of conjugates and inverses. Consider a single pin (I'll denote this with a capital 'I') added to two single pins (II).  The sum (I + II) is equal to zero. (Playing optimally, both players will get a move, so the first player will win (misere).)  Thus, these two act like inverses.  They don't, however, act like conjugates.  So far, Partisan Kayles is the only known ruleset to fail this misere inverse property!

Richard rounded out the session, speaking more about work with Urban Larsson and Carlos Santos on scoring games.  He introduced DisKonnect, a scoring version of Konane.  (You keep track of the number of pieces you have taken.)  He also considered a method of embedding normal play games into scoring games: just play the game, but at the end, consider the score to be zero.  (I like this!)

Unfortunately, some scoring game positions can't be used to embed normal play games.  The resulting collection of scoring games that can be used, dubbed "guaranteed games", is a well-defined category.  Rulesets here include things such as Blokus, Mancala, and Dots-and-Boxes.

***

As you can see, there are tons of holes in my "reporting" of these talks.  There is much for me to still learn, and many aspects of this field I may never gain a mastery of.  CGT is growing quickly: Misere and Scoring play are taking off, and there are still lots of unanswered questions and lots of new rulesets people are thinking of.  It is definitely a cool time to be a gamester.

CMS 2015 Summer Meetings, Day 1, Morning

Catching up on some quick summaries from the CMS talks from June.  Here's a little thing about the morning talks!

Neil McKay presented a talk about determining whether a game is equivalent to a Hackenbush stalk.  A Hackenbush stalk is a single path of red, blue, and/or green edges (with one of the end vertices being the ground).  This was really interesting, because his talk yields a nice iterative method to do this for any game G. 

Each round, you check whether one of two things is true of G:

• G looks like a hackenbush game connected to the ground by only one green edge.  (G is *-based, meaning it looks like an ordinal sum.)
• G looks like a hackenbush game connected to the groudn by only a red or blue edge.  I believe this part uses the Reduced Canonical Form of G and compares that to G, checking that the difference is dicotic.

If neither is true, then G is not a stalk.  If one or the other is true, then you can reset G by chopping off the bottom of the stalk.  If you ever reach G = 0, then you know G is equivalent to a Hackenbush stalk!

Melissa Huggan next presented work she's done with Brett Stevens on Intersection Restriction games.  The big thing here everyone's excited to hear about is new work on Arc Kayles. She's been working on finding Grundy values on wheel graphs.  (A wheel graph of n spokes is a cycle with n vertices where each vertex also shares an edge with the central hub vertex.)  When some of the outer edges are chosen to be removed, the result is a graph that looks like part of a pizza.

She found a trick to shortcut a bunch of the evaluation: a pizza graph with k vertices has, as options, all of the options of a path graph with k vertices.  Since all nimbers of paths are known, you can use this to bound the nimber of the pizza graph.


Svenja Huntemann talked about some cool work she'd done with Richard N. and Sara Faridi, exploring Doppelganger placement games, specifically strong placement games on graphs.  In a strong placement game, players take turns painting a vertex their color.  This coloring can never be moved or erased, and the strong requirement means that the order of the plays should not matter: each position can be reached by any sequence of painting the colored vertices.

She then goes one step further to talk about distance games: games where the only rule is that vertices can't be painted if they have some distance to other painted vertices.  To specify a distance game, all one needs to do specify the illegal distances of same-colored pieces, S, and the illegal distances of different-colored vertices, D.  For example, Col is the distance game where D = {} and S = {1}; Snort has D = {1}, S = {}; Node Kayles is D = {1}, S = {1}.

For bipartite graphs, we can consider a bipartite flip of the illegal complexes: change the variable for each vertex in one half of the bipartition.  Redefining the game using these rules for illegal states is the same as swapping all odd numbers in the two sets.  If D(G) = {1, 2, 3} and S(G) = {2, 4}, then for H = Bipartite Flip(G), D(H) = {2}, S(H) = {1, 2, 3, 4}.  Doppelganger games, then, are games where the bipartite flip has the same number of legal positions.  I think.  I should ask Svenja again!