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!

CGTC 5, Day One Talks

We are in Lisbon for the "Granddaddy of them all": CGTC.  Ten years ago we had the first one and today we had the first day of talks for CGTC 5.  They were excellent!  Here are my summaries: 

We started with the opening ceremony, an excellent introduction to the meeting and to NovaMath from administrators of the school (NOVA School of Science and Technology), Cemapre, and UAberto, as well as Carlos and Jorge of Ludus.

Richard Nowakowski: "Dicotification and Ender Games"

Richard talked about modifying a ruleset by dicotification, meaning when any portion has no moves for one player, the position is zero instead of its original value.  (Di(R))  Richard's team is looking at what happens when used on an Ender-Game.  Then the values seem to have the form *:H.  They are working out what the possibilities are for H in these cases.

Miloš Stojaković: "Generalized Saturation Games"

Miloš talked about the Turan problem: what is the maximum number of edges that can be included in a graph without containing some forbidden graph F.  A well-known game is where a min and max player add edges in turn to a starting empty graph (only vertices) without creating F.  A generalization of this is where players add some H on their turn instead of a single edge.  Miloš's team has studied what happens when both max and min start when H=P_3 and F=S_4, as well as for longer paths for H and other combinations.

Ryan Hayward, given by Martin Müller: "Alternating Linear Clobber"

Ryan's team solved an open problem from 2001 about Clobber starting from a path of alternating colors of stones.  They proved that all even length boards are in N, except for xoxoxo, which is in P.  The proof appears to be constructive, giving values of all positions the players will encounter when the winner follows the strategy.

Hiyu Inoue: "Ending Partizan Subtraction Nim"

Hiyu talked about Ending Partizan Subtraction Nim, which is both impartial and not: both players have the same options, but the outcomes can be in L and R.  This is because the ending conditions are different: Left wins if there are an even number of stones at the end, and Right wins if it's odd.  Hiyu's team looked at outcome sequences for different subtraction steps.  They looked at lots of such sets and found that Ls appear often, but Rs are quite rare.  They proved some cool strategy-stealing theorems to help explain this.

Svenja Huntemann: "Degrees are Useless in Snort When Measuring Temperature"

Svenja talked about Snort and temperature, which dodging the detailed definition of temperature.  Her team disproved the conjecture that the temperature of a Snort position is bounded by the degree of the graph.  More specifically, they proved that the temperature can be more than the degree of G + k for any constant k you might want to use as a bound.  Furthermore, they found a way to beat any constant ratio as well!

Hideki Tsuiki: "A Cellular Automaton for Blocking Nim"

Hideki described Blocking Nim, where players select forbidden nubmer to remove from the subtraction set in a game.  When using multiple piles, k-Blocking Nim allows removing different numbers from the different piles' sets.  Hideki related the surplus number, which is based on the number of winning options, to the outcome class by subtracting off k+1.  His team then computed these for the 2-pile case from adjacent points, then went further by looking in higher dimensions, which they were able to model with Cellular Automaton on a hexagonal grid in the 3-pile case.

Alda Carvalho: "Cyclic Impartial Games w/Carry on Moves" Part 1

Alda talked about the application of affine games in impartial game with the added context of loopy positions.  She first talked about how to handle loopy positions with nimbers using reversibility (which is a case I've never explicitly used) and adorned infinites (also unused by me).  She then described the effect of carry-on moves, where one player is forced to play on a particular sum component.  She used Generalized Geography to present this, which was an excellent example to explain things.  The values of carry on positions in short games are Z+_0-{set of options}.  Then Moon is the value used to denote positions where you can move there.

Carlos Pereira dos Santos: "Cyclic Impartial Games w/Carry on Moves" Part 2

Carlos continued the talk, describing some of the cases of the formulas that determine outcome classes.  He then covered the new versions of all of the basic pieces of Sprague-Grundy Theory, combining the concepts from the cyclic (loopy) games as they carry-on (entailing moves).  Importantly, they need carry-on positions to have only one option, then they can elegantly combine the theories to again find the outcome classes.  The combination only has two new symbols: infinity with superscript adornments and moon with adornments.

Paul Ellis: "Categories of Impartial Rulegraphs and Gamegraphs"

Paul talked about a different CGT categorization with Rulegraphs and Gamegraphs in place of Rulesets and positions.  He considers mappings as equivalent if they preserve the same options.  He covered different properties of maps depending on whether they are on rulegraphs or gamegraphs.  They generalized the idea of birthdays as Valuations that can be applied to any of these graphs.

Kosaku Watanabe: "The Fractal Structure in the P-positions of Wythoff's Game Variations"

Kosaku showed that the Zigzag graph appears in the P-positions of Wythoff's Nim variants.  These variations are parameterized by two inputs, as (a,c)-WythoffsNim, that restrict how many are allowed to be taken in single-pile moves.  ((1,0)-WythoffsNim is the normal Wythoff's.)  Kosaku's team then saw that a repeating indicator existed in the (2,0) case, revealing exactly the zigzag graph.  They were then able to generalize for other (a,c) pairs as well and also get the same graph.

Takahiro Yamashita, given by Shun-Ichi Kimura: "Triangular Nim and Its Wythoff Variations" 

Shun-Ichi talked about Triangular Nim: you take at least two tokens from one pile and then add 1 or more to another pile so that you have taken more than you re-added.  Their team found nim values for many positions.  Then they applied a Wythoff variation to this game.  The basic version of this is where if you make a single-pile move, you can add to the other pile, but you don't do anything different with two-pile moves.  In another generalization, they showed that the P-positions are exactly at pairs (n^2, (n+1)^2).  They found other amazing sequences as well, including the pentagonal numbers, power serieses, and Merseinne numbers!

Vlado Uljarević: "A Variation of Hats-in-a-Line Game"

Vlado talked about an improvement from one of Bajan's talks at CGTC 4, based on the Hats-in-a-line problem.  This includes prisoners who can all see each others' hats, but not their own.  (They in a circle instead of a line.)  If there are up to five possible hat colors, the first two prisoners can encode enough info about the rest of the hat colors that everyone else can guess exactly.  The improvement here is what to do if the number of colors grows and when the prisoners can handle things.  They found some simple bounds and some very complicated bounds.  Vlado's team use SAT solvers to test some of the possible cases.  The problem is that the number of variables is extremely high.  Nevertheless, they've narrowed it down for three prisoners who can encode up to between 12 and 13 colors of hats.  

Urban Larsson: "Subtraction Games in More than One Dimension"

Urban talked about a game between a Squirrel and a Crow playing a subtraction game of multiple types of nuts where there are different combinations the players are allowed to gather on their turn.  This creates a multi-dimensional subtraction game described by vectors as elements of the subtraction sets instead of positive naturals.  Urban's team found a bunch of properties of different cases and showed cool graphs of the P-positions.  Some of these really looked like the houndstooth pattern (from garments).

I'm looking forward to hearing more great things tomorrow!

(Carlos wins the best out-of-context quote of the day: "I need to destroy these moons.")

CGTC 5, Day 0 Talk

Technically, yesterday, January 30, CGTC 5 hadn't started yet.  This year we were co-located with Recreational Math, which happened right beforehand, and there was a sort of bridge event last night in the form of a talk by Robin Wilson: "Lewis Carroll in Numberland", so I'm counting that as this year's day zero.  

Dr. Wilson talked about Charles Dodgson (Lewis Carroll), who was a Math lecturer at Oxford, Christ Church, from 1856 to 1881, including his use of fanciful mathematics in his children's fiction.  As a child, Charles made mazes for his ten siblings (he was third oldest of eleven children).  He studied at Oxford 1851-1854, where he got top marks on his exams.  he did a lot of artful photography, at an early age for the field.  

In his career, he taught from Euclid's Elements and wrote the text "Euclid and His Modern Rivals," a fictional book where Euclid is compared to current mathematicians.  He also had an interest in voting theory and did some examples about problems with First-Past-the-Post.  He also did a lot of examples with proportional voting scenarios.  He was interested in tournament brackets and described alternatives.  He also wrote a book about mathematical puzzles, including the Monkey Puzzle.

In further interest to us CGT types, he created a logical game which was used to make symbolic logic derivations using a board and counters.

This was a great way to get my appetite ready for all the talks we had in store!