Heaps vs. Heaps

I've been teaching Plymouth State's Data Structures course every semester and hope to keep teaching it for a while.  Each project covers a different data structure... and a combinatorial game that uses that structure.

Unfortunately these two universes conflict over a term: Heaps.  The piles of sticks in Nim are usually referred to as heaps.  However, in CS a heap is a binary tree structure with a specific recursive property: each element is bigger (or smaller in a min-heap) than both child elements.  (There's more to it than just that, but that's the big deal.)  Currently we talk about heaps in class, but I don't have a project that includes just them.

It was brought to my attention last semester that some of my code is confusing for people with CS background.  Many of the games students play are Nim-based, and they often have a getHeaps() method that returns the data structure containing the Nim piles.

Sadly, I've decided against the Combinatorial Games language:  I'll replace the term "heaps" throughout my projects with "piles".  I'll be making these changes over the next two weeks and they'll show up in my projects starting this fall.

Sorry CGT, but people say "piles" anyways.

CGT has a website!

There has been some discussion about having a central resource for CGT material over the past few years.  Just a few days ago at Games at Dal 2015, Aaron Siegel took the initiative to actually get it going at combinatorialgames.org.

Aaron has already posted lots of basic info over there, including some notes on getting started in CGT, some reference materials, and information about upcoming conferences.

Please check it out and continue to check back as more information gets added.  Thanks to Aaron for getting this project started!

Games at Dal 2015: Afternoon Talks

Yesterday (Tuesday) we had two afternoon talks to round out that portion of Games at Dal 2015. 

Simon Rubinstein-Salzedo spoke first.  Simon has recently started a a math institute in California's Bay Area with the goal of teaching advanced math concepts to gifted highschool students.  In the meantime, he and Urban have worked out some interesting results about a multi-pile Nim variant.

The basic variant of the game starts with a heap of n stones.  The first player may take up to n-1 of them.  States are described by the pair (pile size, maximum allowed to take), so the initial position is (n, n-1).  In future turns, removing k stones from any state (a, b) results in the new position (a - k, 2k).  Thus, you can take at most twice as many as were taken last time.  (Naturally, you must take at least one stone.)

The analysis of this game employs a new representation of the positive integers that I was completely unfamiliar with: the Zeckendorf representation.  Apparently, every positive integer can be uniquely represented as a sum of non-consecutive Fibonacci numbers.  For example: 27 = 1 + 5 + 21.  Whoa moments:

• Wow, uniquely!  Awesome!
• Non-consecutive?  Sweet!
• The greedy algorithm works to find the representation.  Given n, choose the biggest Fibonacci number below that, include that in the representation, then recurse on the difference.  (You can kind of see why the elements must be non-consecutive by induction.

Back to the CGT: A position, (a, b), has a winning move exactly when you can take the smallest part of the Zeckendorf representation.  Thus, for (27, x), the winning move is to take 1 stone, so that the result is (26 = 5 + 21, 2).  The next player can't take 5.  In fact, you never have to worry about them taking the next-highest number in the Zeckendorf, because it's non-consecutive and must be more than twice the old smallest value.  This means that a starting position is in P exactly when the size of the heap, n, is in the Fibonacci sequence: the smallest part is the whole thing, which is the only thing you're not allowed to take.  Simon is continuing his analysis by looking at multiple piles and some variants of that.


Craig Tennenhouse, my travel buddy, gave the final talk on some variants of Bogus Nim he's created.  Poker Nim is a well-understood variant of Nim: you keep a bank of the sticks you've removed and if you have a non-zero amount, you're allowed to add some to one pile on your turn instead of taking any.  Unfortunately this doesn't give you any escape from P-positions; your opponent will just snatch up whatever sticks you re-add.

Craig makes two changes to create Non-Loopy Poker Nim:

• First, change this to an impartial game with a shared bank.
• Second, disallow repeated positions to prevent loopiness.  (Positions are recorded using multisets, so order doesn't matter.)

For example, if the game begins at {3, 5, 7} and the first player moves to: {3, 5, 4}, then no one can ever return to {3, 5, 7} by putting sticks back into the last pile (or any other moves that reach this configuration).  The 2-pile version can be represented by a rook on a half-checkerboard with the space at 0,0 being an "automatic" P-position.  Craig further changes the representation to show that for most of the square boards there is an automatic symmetry.   (Post-post-edit: changed the numbers of piles to be correct above.)

If the number of heaps is not fixed, then the game takes on new structure that might best be represented by undirected position graphs.  Since loops are not allowed (by tracking the list of moves) this acts like Undirected Vertex Geography, for which winning positions can be easily detected.

Craig came up with another nice game: Rook Nim.  This game includes a full n x m checkerboard with a single automatic P-position in one corner and with the rook in the far opposite corner.  Here, however, the rook may not move through deleted spaces.  This means that not all games will end with the rook moving to (0,0).


Excellent talks!  After discussing potential problems to work on, we visited the Board Room and enjoyed the Halifax gaming culture.  Today (Wednesday) we worked intensely on the suggested problems: nearly to the point of exhaustion.  This was followed up with some more exploring of Halifax and a bunch of rounds of Hanabi.

I've both learned a ton here and will walk away with new results to write up!  Only two days in and this has been an amazing conference!

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. :)

Portuguese Game Tournaments

Non-Portuguese parents have an excellent reason to be jealous: Portuguese grade schoolers recently competed in the 11th Annual Portuguese Tournament of Mathematical Games.  This big event, put on by Ludus, begins in regional schools for kids ages 7 to 17.  They compete in a wide variety of combinatorial games, then the winners advance to the final rounds as shown in the link above.

The final tournaments were held on March 6 of this year in Vila Real in northern Portugal.  1400 students played one of 6 games (I assume they're combinatorial, but I admit I'm not familiar with them all).

I picked up a copy of Traffic Lights in Lisbon at CGTC1, though I'm not very good at it yet.  It's definitely a nicely-balanced impartial game with easy-to-explain rules.  (I also got to meet João Neto there, without realizing that he's the author of the Trabsact Sagme Diaries.  (Those first two words in the name are anagrams for "abstract" and "game".)

One excellent aspect of the tournaments is that Ludus strives to make them as accessible as possible for all kids.  For example, the pieces for Traffic Lights have different shapes for each color.  This allows blind students to play by feeling the pieces without having to distinguish the colors!

In eighth grade I took an amazing class in mathematical games.  We played a bunch of Nim, Krypto, and Equations.  I wish we had fun tournaments like this to encourage abstract thought outside of the standard curriculum-box.  Unfortunately, I don't see this happening in the US on a large scale anytime soon.