Games at Dal 2015: Morning Talks

We just finished the first day of the Games at Dal 2015 conference.  This is my first time at Dalhousie University (my first time in Halifax, in fact) and it's very wonderful here!

Today was the only day of talks; the rest is working sessions.  I'm going to break the talks into two posts: morning and afternoon.  Hopefully I can say something intelligent about everything I saw today.  Things got very deep very quickly!

Carlos Santos started off talking about work with Alda Carvalho on a new variant of Green Hackenbusht: Oak.  Oak includes not only (all-green) pieces growing off the ground (trees/plants), but also underground "roots" for each of the above-ground plants.  These roots are colored with brown edges, and have a more significant impact than the green edges:

• If any green edge is removed, those green edges no longer connected to the ground are removed, as normal.
• If any part of any root is removed, then all of the green edges connected to that root are removed, as well as any root pieces no longer connected to the ground.

Carlos explained a bunch about ordinal sums (this is a topic that probably deserves it's own post) including that for the game G:H, just knowing the value of G is not enough to fully evaluate the sum: the entire form of G is necessary.  (0 behaves differently than *2 + *2 as G in the ordinal sum.)  The same is not true of H; the value is sufficient.

Carlos and Alda found another sum, the gin sum which can be used to efficiently determine the appropriate value of the sums for these Oak positions.  The calculation is similar to the regular XOR sum, though certainly distinct.


Aviezri then spoke about using Fibonacci words in games, work done with Lior Goldberg.  The games they considered are generalized versions of Wythoff's Nim using Beatty sequences to determine the P-positions.  One version of this is: (parameterized by t)

• 2 heaps, as in Wythoff's Nim
• On turn, take either:
• any (positive) amount of sticks from one heap (also as in Wythoff's Nim), or
• k (> 0) from one heap and m (> 0) from the other, where | k - m | < t

The normal Wythoff's Nim, then, is this generalized version with t = 1.  It has been known for a long time that for each value of t, there is a pair of Beatty sequences (increasing sequences that partition the natural numbers) a's and b's that describe the P-positions.  (For each i, (a_i, b_i) is a P-position.)

The more recent work here considers adding invariant moves to the game that don't influence the location of the P positions.  This means adding a pair (x, y) so that the current player can always choose to subtract x and y from the two piles (as long as both piles are big enough) without actually affecting the winning/losing positions.  They proved an algorithm exists to find these in regular Wythoff's Nim.  Conversely, they investigated Forbidden Subtractions: invariant moves that cannot be added without changing the P positions.


Next came Neil McKay, continuing on his presentation from the CMS summer meetings on Hackenbush stalks: paths with green, red, and blue edges.  He got deeper into basics on ordinal sums (again, I should just make a big post on that) and then took off on explaining the nice properties of Hackenbush stalks.  Here his goal is to evaluate sums of stalks.

I'm surprised to learn just how difficult this is!  Unfortunately, sums of stalks are not closed, even though a sum of stalks is equal to a number plus a sum of dicot stalks.  There are some other benefits:

• If x is an integer and H is a dicot, then x : H = x + H
• o (* : G + * : H) = o(G + H) 
• The atomic weight, aw, of a dicot works nicely: aw(G + H) = aw(G) + aw(H).  (I am not keeping up with CGT concepts as they become popular; I don't know what the atomic weight is.)

I'm aware that Hackenbush is known to be NP-hard, but I'm surprised to find that there is no known polynomial algorithm for Hackenbush stalks... or even Hackenbush flowers!  A H.B. flower is *k : z, where z is an integer.


Gabriel Renault got deep into some new Misere conepts looking at invertibility and dead ends in universes with no P-positions: work done with Rebecca Milley.  There are three really big definitions involved here:

• A (Left/Right) End is a position with no moves for Left or Right, respectively.
• A (Left/Right) Dead End is a position where all followers (and the position itself?) are Left/Right Ends.  (Edit: yes, a position is its own follower.)
• A dead ending is a position where all end followers are dead ends.  (Edit: added italicized end.  Thanks, Gabriel!)

Gabriel and Rebecca decided to focus on universes without any P-positions, which allowed them to find some neat properties about equivalence and comparisons.  Conveniently, these P-less universes arise out of sums of dead ends.  (Unfortunately, dead-endings don't automatically work.  E.g. *, which is a dead ending, but is itself a P position.)


I hope to post about the other two talks from the afternoon tomorrow. :)