Saturday, August 20, 2016

Integers 2016

Integers is back!

Integers is a conference in combinatorial number theory.  Traditionally it's been held every other year on the odd years, but it had to be skipped last year.  Integers is a great, low-key conference held at the University of West Georgia.  It has an associated electronic journal with no paywalls (so convenient!).  It's well run and everyone is very nice.  This year, they've moved it up to early October (6th-9th).  Here's the official Integers 2016 announcement.

Historically, there's been a contingent of gamesters attending Integers.  In 2011, I brought an undergraduate and met many of Richard Nowakowski's students.  In 2013, I met Silvia Heubach and Matthieu Dufour.

Unfortunately, I don't know of anyone attending Integers this time around.  This is partly due to the number of CGT events popping up.  Games@Dal has returned, and CGTC2 will be happening in January 2017 in Lisbon.

If you're planning to go for Combinatorial Games, please comment below (or email me).  At this point, it looks like we might not have any gamester attendees.

Wednesday, August 17, 2016

Games@Dal 2016: Tanya talks about Cookie Monster Games

Games@Dal 2016 talk: "Cookie Monster Plays Games" - Tanya Khosanova w/Leigh Marie Braswell, Eric Nie, Alok Puranik, Joshua Ziong, and Dhroova Aiylam

Tanya Khovanova shared some work with a bunch of high schoolers (whoa!) on patterns in Cookie Monster games.  Cookie Monster games are Nim games where k sticks (cookies) can be removed from multiple heaps.  Each ruleset has a different restriction on which sets of piles can be removed from.

She and her students considered rulesets where you can take from...:
  • No restriction
  • One-or-all piles
  • One-or-two piles
  • Any consecutive piles (assuming the piles are in a list)
  • One or two consecutive piles
  • Any set of piles including the first jar
  • Any odd number of piles.  (It turns out that the P positions are the same as in Nim!)
  • Any set of piles except all of them.
  • ... and more!

In one of these games, she noticed a surprising correlation with an automaton problem!  A sequence of the number of P positions is related to the number of new cells born from the Ulam-Warburton automaton.  She then looked more closely at other relationships to automaton!

Tuesday, August 16, 2016

Games@Dal 2016: Urban talks about Drawing Triangles

Games@Dal 2016 talks: "Hopeful Windows in Cellular Automata and Combinatorial Games" - Urban Larsson

Urban talked about the Hopeful Window Triangle-Placing Game, a very interesting game based on his work with cellular automata games.  In this game, there are multiple steps per turn revolving around drawing a digital 45-45-90 triangle on a grid.  The triangle always has one box at the top, and the hypotenuse descends on the left-hand side.  There is a single box lower in the grid that is the blocking box:
  • No triangle can be drawn that contains that box, and
  • The first player to draw a triangle past that box wins.
At the beginning of each turn, there are candidate boxes that the current player can start with are all in a horizontal row.  (I'll explain how those are generated as part of the turn below.)  The steps to each turn are:
  • The current player chooses one of the candidate boxes for the top of the triangle, then draws it as far down as they want.  (If they start out to the left of the blocking box, then they can automatically win by drawing a large-enough triangle.  Otherwise, they can't cover up the blocking box.)
  • Consider the boxes directly beneath the drawn triangle - the triangle's support, but increase this set by extending to the left and the right by two boxes on each side.  (This can be parameterized to be any l and r numbers.)
  • Inside of this elongated support, the next player chooses a "hopeful window" of, say, 6 adjacent boxes.  (Again, this can be parameterized.)
  • The previous player then gets to block, say, 3 of the boxes in that window.  (Parameterizeable again.)
  • The remaining 3 (in this example) boxes from that window become the candidate top boxes for the next player to choose from on their turn.
The game is certainly a bit complex, but Urban found an extremely surprising relationship between this game and automata that generate Sierpinski-Triangle figures.  By using the l, r, w (window size), and b (number of block) parameters in the formula for the triangle-creating automata, the resulting pattern of triangles tells you exactly which boxes you should choose to start a new triangle from: choose one of exactly those which remain uncolored in the diagram.  Amazing!

Monday, August 15, 2016

Games@Dal 2016: Alda and Carlos talk about Short Sums

Games@Dal 2016 talk: "Some notes on Disjunctive Short Sum" - Alda Carvalho & Carlos Santos

Alda and Carlos presented their work on Disjunctive Short sums.  They started from Paul Ottaway's definition of the difference from a short sum (to a normal long sum): The game ends when a player chooses a component in which they have no legal move.  This doesn't make a difference in Normal play (because players don't want to choose one of those games) but it's important for Misere.  In misere, this is equivalent to: The game ends when there is a component in which the current player has no legal move.

Now, instead of starting from zero as the terminal position, they start with two games that have no options: Infinity (Inf) and negative Infinity (-Inf).  Inf is the game with no options for Right, and -Inf has no moves for Left.  These are the only games born on day 0.  Then the day 1 games are:
  • Inf* = {Inf | Inf}
  • +/- Inf = {Inf | -Inf}  (like a switch)
  • 0 = {-Inf | Inf}
  • -Inf* = {-Inf | -Inf}
They showed a bunch of the birthday lattice for day 2, which is very large, then started talking about Color Nim: a short disjunctive sum of Nim games.  Another way to say this is that each pile has a color (not necessarily unique) and the game ends when one of the colors is gone.  In the Misere case, this means that each color behaves like Penultimate Nim.  (For some reason, Penultimate Nim kept coming up at this meeting!)

Games @ Dal 2016 Wrap Up

Yesterday morning, I put myself and three other Muppets back into my car and departed Games @ Dal.  675 miles, 16 hours (just under 12:45 actually behind the wheel) and three drop-offs later, and I was back at home. 

There are still more talk summaries to come over the next few days, don't worry.  We even had an unexpected bonus talk by Tanya Khovanova on Friday, so there are three more to go! :)

Here's a few things I learned:
  • I got a result!  It's not about the computational complexity of a game... who am I?
  • There are lots of very obvious rulesets that we still need to find the computational complexity for.  Even just impartializations or other variations of common rulesets need to be figured out.
  • Halifax Citadel's noon gun is loud if you're standing near the citadel entrance.  (Good choice, Amie!)
  • Hanabi is pronounced differently in Canada.
  • CGT is still a really good field to introduce to mathy undergrads.  (Also, I should really take a look at Tom Ferguson's book.) 
  • It would be very nice to have a list of gamesters.  I should probably make this.
  • It would be very nice to have a list of past and future CGT conferences/events.  I should probably make this.
  • I should spend more time working on the ruleset table.
  • I would really like to go to a workshop where my only job is to update the table.  I'd like this to be a CGT event because I'd like to be surrounded by Gamesters while doing it. 
  • A post on the Gamester Pen would not be worthless.
  • I should probably get on Twitter and tweet little things like these.
Thanks to Richard Nowkowski, AARMS, and Dalhousie for hosting such a great event!

Games@Dal 2016: Israel talks about Picaria

Games@Dal 2016 talk: "Eternal Picaria" - Israel Rocha w/Urban Larsson

Israel Rocha presented a new game to me: Picaria.  Picaria is a traditional board game of the Zuni tribe from the American southwest, but it also pops up in other parts of the world, including southwest Sweden (known there as a type of Luffarshack).  It plays a bit like a Three Mens Morris mixed with Tic-Tac-Toe.

Players play on a graph, usually set up in a 3x3 grid like Tic-Tac-Toe, but with diagonal connections as well.  In the first six turns, players are playing pieces, trying to make three-in-a-row.  After those pieces are played, players instead slide pieces to an adjacent location, still trying to make a line of three.

Israel explained that he and Urban Larsson showed that Picaria is a draw, via exhaustive search. (And without a computer!)  They then considered some variants, including giving a player more stones and playing on bigger boards.

Games@Dal 2016: Carlos talks about 3-player Nim

Games@Dal 2016 talk: "3-player Nim with podium rule" - Carlos Santos w/Richard J. Nowakowski and Alexandre M. Silva

Carlos's talk entered the somewhat-forbidden world of three-player games.  He spoke of different ways of considering these games, but continued using Lee's Podium Rule from 1978: If you can't come in first, you should instead try to come in second.  (Try to get as high up the podium as you can.)

In impartial games, this leads to a third outcome class: O ("Other") which has no P options, but at least one N option.  Playing on Nim heaps, to find P positions, we now have to perform the nim sum, but mod 3 instead of mod 2.  Thus, *7 + *17 + *22 + *23 is a P position.  Zeroness in the sum only actually tells us about P positions; non-zero values might be O or N, so we need further criteria.

Carlos described these further criteria, then continued by describing how to define canonical forms for Nim.