CGTC1 Day 1

Today was a great day at the conference!  Bonus info: this is the first pure math workshop organized by Ludus, a Portugese organization that promotes math and holds outreach events for kids.  They're well-known for holding an annual game competition for middle schoolers that has regional and final-level parts.

A quick summary of today's talks:

Aviezri Fraenkel spoke about using alternative numeration systems to determine the complexities of games.  He noticed that he could express rulesets for Wythoff generalizations (extremely generalized, so generalizations of generalizations of generalizations of Wythoff) using a numeration system based on continuing fractions.  Aviezri used this to show that one class of games studied by Wei An Liu and Haiyan Li has a polynomial-time solution to differentiate between P and N positions.  Best quote by Aviezri: "33 years ago, I proved..."

Melissa Huggan spoke about Intersection-Restriction games.  She's been studying Arc Kayles, which is just like Node Kayles, except that players choose edges, which are removed along with their neighbors.  She's written code to analyze star graphs with three rays.  (The rays are not restricted to path of length 1; otherwise each star is just equal to *.)  She's also analyzing wheel graphs.  In arc Kayles, playing on a spoke of a wheel turns the graph into a path, while taking an edge on the rim turns it into something that resembles a pizza.

As Melissa said, it's "computationally expensive because we need all subpositions of the pizzas!"

After this, she showed some work on triple-packing and triple-overlapping games.  She has Grundy values for games played on {1, ..., n} up to n = 10.  She's very interested in continuing work on this, but for the 10 case the running time of her code jumped from 8 seconds to 17 minutes!  So far, her data matches the Grundy sequence of arc kayles on complete graphs.  (Edit: I originally read her table as 8 minutes to 17 hours, but I was corrected, and these are the correct times.)

Urban Larsson spoke on some new work on scoring games.  He mentioned the term "Galgemster", which is apparently a gamester who is more interested in algebra. :)

His talk concentrated on finding a subuniverse of scoring games that could be analyzed nicely.  He called these games Guaranteed.

Carlos Santos then spoke about Absolute CGT.  He wants to figure out analytical tools that will work for many universes of games: Normal-play, misere, and scoring games.  He defines the term CG space, which must have nice properties for recursion, order, an operation (e.g. disjunctive sum), and atomic positions.  With this definition, he is able to find "Absolute Theorems" which can then be applied to any space.

Thane was very excited about this joint work by Carlos and Urban and Richard Nowakowski.  As he said, "I love this talk!  Can I now talk, for, like, 30 seconds?"

Gabriel Renault spoke on comparison modulo sets of games.  Unfortunately I don't follow all the monad arguments well, but I did learn some new terms:

* A binary position is one in which each player has no more than one option (and all options are also binary).

* A dicot game is the same as an all-small position.  However, "dicot" is more commonly used under misere play.

Craig Tennenhouse then spoke about his joint work with me on games that use data structures, as described in an undergraduate CS data structures course.  He got lots of interest from people after describing Rotisserie Nim, which is Nim played on a queue.  We noticed that there's an optimal strategy to follow, but the strategy does not actually tell us the outcome class without simulating the entire game.

I played some more great games today!  I'm hoping to test out my Clobbineering skills again tonight!