CGTC 5, Day Three Talks

The final day of CGTC 5 has come and gone.  Today featured more great research talks, followed by a short group of talks about different CGT books that are available that people might not know about.  (Some other CGT-relevant announcements were also made.)  This was actually another great decision made by Alda and Carlos; those talks really sparked a mood of camaraderie that closed down the conference.  

Let's get into the talks and maybe you'll see what I mean.

Alfie Davies: "What If Winning Moves are Banned?"

Alfie talked about a CGT problem posed by Jane Street in 2020 with Subtraction on the set {1, 2, ..., 10} on a starting pile of 100.  They gave away the Normal Play winning strategy, then made an adjustment: you can't take 11-x if the prior move was x.  Alfie generalized this to the Jane Reduction J(G) = {J(G^L) | J(G^R)}, where J filters out all winning moves, leaving only options to losing positions (outcomes of N and R for Left and N and L for Right) according to the original game.  Alfie then found some crazy properties of this: G = H does not imply that J(G) = J(H).  Even crazier, for any H and outcome class o, there is a position G in o where J(G) is isomorphic to H.  In impartial games, things get a bit less tricky; if n >0, then J(*n) = *(n-1).  Alfie gave an excellent (and hilarious) scenario about how to use this information to frustrate students while teaching them subtraction games.  He then described a swap option (like a delayed pie rule that either play can invoke) to simulate the Jane Reduction in any partizan game. 

Mike Fisher: "Atomic Variations of Roll the Lawn and Cricket Pitch"

Mike described his work on a Roll the Lawn variant and a Cricket Pitch variant, both of which include reducing a list of Nim heaps by moving a roller over them.  He explained how to find the outcome classes in both original games from Nowakowski and Ottaway.  He then quickly explained atomic weight and the two-ahead rule.  Mike's team's game, Roll the Stalk, is where you have all the normal Roll the Lawn moves as well as the ability to make a Nim move on any single heap.  Canonical forms are hard to find (they are very long) but they can easily find atomic weights and outcome classes.  Atomic Cricket Pitch is the same, but the roller cannot pass over zero-size heaps.  They conjecture that the atomic weights of that must be between -1, 0, and 1.  In addition to that, they provided another three further variants!

Hikaru Manabe: "Maximum Nim and the Josephus Problem"

Hikaru described the Josephus problem, a classic exercise I've seen in Algorithms courses.  Then he gave a generalization where the number of people to skip at each step changes (given in a list).  His team related this to Max Nim, where a function of the number of stones gives a max-allowed amount that can be removed in one turn.  They found that the Grundy values are the same to the basic Josephus problem when the bounding function is f(x) = floor(x/k).  Even further, they were able to find a function to correspond to any non-constant Josephus skipping sequence and vice versa!

Hikaru Manabe: "Amalgamation Nim with a Restriction on Amalgamation"

Hikaru described Amalgamation Nim, which is just like Nim except there's an additional move of merging two non-empty piles.  For two piles, the P-positions are the same, because merging is always a move to an N-position.  With three piles, however, (1,2,3) is no longer a P-position because it has an option to (3,3).  Hikaru's variant, Amalgamation Restricted Nim, is that merges are only allowed if both piles have two or more tokens.  With this, Hikaru showed that the pattern of P-positions of three piles form a 3-D Sierpinski triangle!  He is currently working on results for 4 and 5 piles.

(Two talks in a row!  We really squeeze these high schoolers for all they're worth!  (I'm just kidding, Hikaru!  Keep up the great work!))

Harman Agrawal: "QuadroCount: A Combinatorial Game"

Harman explained QuadroCount, a game on grids with White and Black stones and empty squares.  A turn consists of moving one your color stones to another space such that the sum of the areas of the rectangles it makes with all other opposing pieces decreases.  She implemented a playable version at: https://quadrocount.vercel.app/  Harman showed that alternating strips are terminal positions and conjectures that neighboring stacks of the same height are all P-positions.  She also has lots of lemmas about bands with two stones of each player!

Shun-ichi Kimura: "Transfinite Nim values of Specker's Nim"

Shun-ichi talked about playing Nim with infinites.  In Specker's Nim, you pick two non-zero piles a > b, then add some to a and subtract from b.  Shun-ichi's team's variant, Modified Specker's Nim, is where you don't have to add to the a pile.  They were able to show that even if you can add lots to the bigger pile, the games will still end in a finite number of turns.  They found the Grundy values of all three pile positions in both original Specker's Nim and their modified version.  In case you have not experienced a Kimura-talk, I'm including this photo to help illuminate the wonderful style of his slides:

(Coffee Break)

Balaji Rohidas Kadam: "Kotzig's Nim under Misère Play"

Balaji explained Kotzig's Nim, played on a directed cycle of nodes.  Each turn, the player selects the distance to move around the loop from a list (à la a subtraction set) and visited nodes cannot be used again.  Balaji then showed known results about this game.  He tackled the misère version and showed a "diamond" strategy to force a win when the list is [a, a+1] and the loop is a composite kd.  He also found outcomes for a bunch more cases, including when the list is [2,3].

Hironori Kiya: "Traffic Jam with Various Car Sizes"

Hironori explained Traffic Jam, designed by Urban and which we played in Games @ Mumbai.  Here, cars are trying to go straight through an n x n sized intersection.  This is an example of an affine game: if one player gets all their cars through, then they win this and any other games added to it.  Hironori and his team were able to find the outcomes via brute force up to 4x4 and conjecture that the alternating pattern continues.  Their variant includes cars that can be longer than two spaces and they proved that the starts are in N if the outer cars are long enough!  They also found up to 4x4 outcome classes for monomio (1x1) shaped cars.

Ethan Saunders: "Misère Cricket Pitch"

Ethan followed up on Mike's topic by looking at the misère version of Cricket Pitch.  His talk was very interactive: he presented positions and we gave the outcome classes until we could see the general formula!  (We did need some coaching.)  This was a very unique and extremely effective way to demonstrate the solution.  In the end, we all saw how to find all outcome classes.  It was quite slick.

(At this point, we switched over into announcements and talks about books.  I'll still include titles when they happened.)

Svenja Huntemann started off by making announcements, including VCGT, which is looking for volunteers to speak this semester.  (The schedule is already set, but speakers are needed.)

Colin Wright announced the existence of three things: Signal, Mathstodon.xyz (a Mastodon instance, which I am on), and Mathsjam (a regular meet up group for math-interested people).  

Carlos & Urban: "CGT Collection in IJGT"

Carlos and Urban talked about the collection of CGT papers that the International Journal of Game Theory (IJGT) is putting together into special issues.  It's not exactly proceedings, but they strongly encouraged sending to it.

Koki Suetsugu: "A Book by Abuku, Sakai, and Suetsugu"

Koki talked about the gensis of his new book with his team.  He explained the history of CG books in Japanese (original and translated).  Koki and Tomoaki actually met with the publisher of the Lessons in Play translation, who agreed to publish their text if they would write it.  In February 2024, they were published!  Koki also talked about the burgeoning CGT community in Japan.  This talk really brought the whole group together and we clapped and cheered for each excellent milestone Koki described, both as a part of their book happening and with the growing numbers of Japanese researchers making advances in CGT.  (Each time CGTC has more than the prior!)  I think we gave enthusiastic applause four times during the talk. 

Urban & Richard: "A Future of GONC"

Richard talked about the history of Games Of No Chance (GONC) through the third volume, and how it can be a long process from idea to publication; easily lasting multiple years.  GONC 6 should be coming out in a few months, but there are difficulties to get these compilations published.  Urban talked about potential future possibilities to keep GONC going, hopefully for a seventh edition and beyond.

Miloš: "Positional Games"

Miloš drew our attention to the book Positional Games, which is available online.

We had another productive working session afterwards!  

It's always bittersweet for CGTC to come to an end.  We will all wait anxiously for two years until the next "Granddaddy of them all". 

CGTC 5, Day Two Talks

The day two talks of CGTC 5 were also excellent!  One note I didn't mention before is that right before we started on Friday, Carlos declared that there would not be time for questions directly after individual talks.  I was a bit devastated at the time, but it actually worked out super well and we were pretty-much always on time (or more delayed by the length of breaks than anything else).

Here are my summaries.

Martin Müller: "A Search-based Approach to Solving Sum Games"

Martin talked about some of the differences in philosophy between Math CGT research and the CS perspective.  He and his team are currently working on linear versions of Clobber and NoGo.  In Clobber, they've solved it up to strings of 33 and for NoGo up to 39.  The latest NoGo solver uses actual CGT techniques in its searching, such as sums and partial orders.  However, they avoid finding canonical forms because of the computational explosion.  Instead they determine outcomes using a large table that includes using responses if they exist.  One of their main challenges is to determine when to try to simplify from a position.  They plan to release the first version of their software, MCGS, next week.

Bojan Bašić: "Yet Another (Not so Well-Known) Funny Afternoon in a Jail Courtyard, and Its (Even Less Well-Known) Variation with Quite Unexpected Consequences"

Bojan talked more about prisoners and hats problems, focusing on a lesser known one with three prisoners.  Each gets a hat with an integer on it.  They each pick a finite set of integers independently and to avoid punishment at least one must include their number.  They can win by choosing all ranges between the other two.  Bojan's question is now: What happens if you use real numbers instead of integers?  His team proved that the prisoners can win exactly if the Continuum Hypothesis is true.  (This was the second time I'd received a lesson on the CH in two days!)

Ankita Dargad: "Thermograph Invariance for Certain Games"

Ankita started talking about Toppling Dominoes (shameful plug: this is the Sprouts game for this year) and how to measure the temperature.  Her team has a new method to calculate temperatures that uses the notion of a penalty.  She went into the details of thermographs and using walls of options by turning them 45 degrees.  They worked it out with some basic "tent" thermographs.  Ankita showed that the game Robin Hood has positions that include all the situations she covered.

Kanae Yoshiwatari: "Universality and Polynomially-Decidable Rulesets

Kanae talked about known universal games: Rulesets where every short game value is in the habitat.  She also covered variations of Generalized Geography, then described Colored-Graph (a,b,c)-Geography: players can only traverse objects of their color.  The three parameters are:

• a: whether the colored objects are Vertices or Edges
• b: whether the edges is Directed or Undirected
• c: what gets deleted, Vertices or Edges

So, Colored-Graph (V,D,E)-Geography means that the vertices are colored (e.g. only Red can move to Red vertices), edges are Directed, and after a move, the traversed edge is deleted.  Kanae then described universality and computational complexity results her team found across the variants.  They also considered a partizan variant, Tron, where there are two tokens.  They have another set of variants, (a,b,c)-Tron.

Koki Suetsugu: "A Survey on Universalities"

Koki talked about different kinds of universalities by defining a bunch of terms in a similar way to computational complexity and subsets.  He's covered tables and tables of results in his survey, an excellent coverage of known things.  He described two methods to determine habitats: induction (by building positions to cover all possible trees) and by reduction (transformation from another known universal ruleset).  He then described δ-Beyond the Door (a Beyond the Door variant) that is also Universal.  Additionally, his team showed that Inertially Capturing Chess has a habitat of all partisan values (not just the short game ones).

Yannick Mogge: "Creating a Tree-Universal Graph in Positional Games"

Yannick described Positional Games, Maker-Maker type games where the goals are described by subgraphs of claimed vertices.  (The players alternate turns claiming different structures given by the ruleset.)  Yannick's work is focused on Waiter-Client games where Waiter offers a choice of edges, then Client must pick one each turn and Waiter wins if they can force Client to create some specified subgraph.  (The Waiter gets the unchosen edge, so they can't offer it again.)  Yannick looked at cases where the goal subgraphs are spanning trees.  His team got good results that follow the intuition of random graph generation!

(Coffee Break)

Craig Tennenhouse: "Temperature of Partizan Arc Kayles"

Craig talked about a project stared at CGTC 4 in 2023.  He gave a temperature overview using Amazons and Domineering as examples.  He talked about the known Domineering position with temperature 2, then discussed the conjecture attributed to Berlekamp in the 1970s that the boiling point is two.  Craig's team looked at a generalization: Partizan ArcKayles (PArcK).  They looked at generating positions with genetic algorithms to see if they could get higher temperatures.  They found one with a temperature of 5/2 in about a hundred generations of their algorithm.  They were able to analyze that and find a temp 3 position, then go further to find temperature n, meaning the temperature is unbounded.

Anjali Bhagat: "Fork Positions and 2-Dimensional Toppling Dominoes"

Anjali continued work I saw at Games @ Mumbai last year, where Toppling Dominoes is extended so that one domino can knock over two at branching points.  They showed some considerations in inequalities when you double red or blue dominoes.  They also considered green dominoes, especially in the forkifying positions where one domino is placed at the end of two rows.  They found a sequence of Grundy positions for full triangles of green dominoes and looked at what happens when one of those dominoes is replaced by a single colored domino.

Thotsaporn "Aek" Thanatipanonda: "Two Games on Arithmetic Functions: Saliquant and Nontotient"

Aek talked about the Saliquant, the set of non-factors of a numbers.  E.g. the saliquant of 12 is {5, 7, 8, 9, 10, 11}.  The game of the same name is then where you are allowed to subtract off any of those values.  The Nontotient is similar, but uses relatively prime residues instead.  Aek extended prior results to find the Grundy values of odd integers (as (n-1)/2).  Aek showed us a table of even values, and challenged us to look for patterns.  He then clued us in to the powers of 2, which we recognized as 2^b = *(2^(b-1)-1).  He also proved a lower bound on Grundy values of all even heaps, which are reached on finitely many values.  He created a Fundamental Theorem for Saliquant (sweet!) that he used to calculate a lot of the values, then he found the first 5000 min values.

Paul Ellis: "The Penults of Tak: Adventures in Impartial Normal Play Positional Games"

Paul talked about Penultimate positions, where it's not terminal, but each option has a terminal option, so they all have value zero if impartial.  Paul then discussed the game Impartial Tak, where the game ends when there's an orthogonal path across a grid of selected spaces.  (Each turn is a selection of one vertex.)  He then was able to describe positions that are the penults based on some different constructions.  Paul's team is still working on solving things on the 7x7 board.  They've also used this idea to look at many other rulesets.

Tomoaki Abuku: "A Variant of Mulitple Hook Removing Game with Carry-on Moves"

Tomoaki continued the topic of entailing moves for Hook Removing, which using Young Diagrams.  A turn consists of removing a hook: a subset of the squares that include all spaces directly below and directly to the left of a single square (and that square as well).  Then the remaining spaces slide together towards the disappeared corner.  This has a good closed formula for the Grundy values.  In this new variant, Multiple Hook Removing (MHRG), unimodal numberings are used on the Young Diagram spaces.  A turn consists of picking a hook, noting the multiset of unimodal values therein, removing the hook, then repeating on another hook with the same multiset on the remaining diagram, if any exist.  Tomoaki's team showed a variant of this game that uses carry-on moves: if you removed two hooks, you go again!  They found formulas for many initial sizes.  The values for this game are often Moon!

Prem Kant: "Zugzwangs and Infinitesimals in Bidding Combinatorial Games"

Prem talked about advances in his study of bidding between turns in Toppling Dominoes to see who gets to take their turn. The system uses a tie-breaking marker to make sure it's always well-defined as to who will make a move.  Prem introduced some notation, then talked about how to determine the outcome classes.  He also showed a backwards construction: given a string of outcomes, he can create a bidding Toppling Dominoes position with those outcomes!  He then discussed how to find Zugzwang positions, where neither player wants to move.  He found that these are a totally ordered subset under the >= relation.  Surprisingly, they found that each Zugzwang is equivalent to a classical Hackenbush position!

Hiroki Inazu: "Ending Partizan Quotient for Octal Code 4.001 and 0.033"

Hiroki covered two octal games using the same ending conditions ("EP") that Hiyu Inoue introduced yesterday.  Hiroki used quotient semigroups to define a Partizan Quotient to help do his analysis.  He was able to show that these groups were periodic with period 5.  Hiroki's team used Gröbner bases to get depeer in the 4.001 case to find a larger quotient set.  They have also done work on Kayles (.77) and 4.4.  They found a unifying theorem that states that knowing the EP outcomes are equivalent (isomorphic?) to knowing both the normal play and misère outcomes.  

François Carret: "Split Sums of Nim Games With a Large Number of Piles"

François, out of Lyon, took on Nim with a pass--there is a single pass that a player can take at any point when there are options in the Nim position.  François' team related this to Split Sum, which is nearly the same, and was able to recursively define the Grundy values.  They also came up with a new version of the mex rule to handle this situation; infinite Grundy values are included!  The Split Sum works almost as normal, but not quite.  François really think this may help guide future research on games with a pass.

Another day of great talks!  The working groups this time were very successful as well; it looks like we may have a publishable result!