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!