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!

The Curious Case of Col's Computational Complexity

Col is one of three basic placement games on graphs along with Snort and Node Kayles.  In all three, players take turns painting vertices their color, with a restriction based on what colors are neighboring.  In Col, you can't paint a vertex adjacent to another vertex that already has your color.  In Snort, you can't paint adjacent to a vertex in your opponent's color.  In Node Kayles, you can't paint adjacent to either color.  (That's not usually how Node Kayles is described, but this is equivalent.)

Winning Ways mentions these in its discussion of the computational complexity of games.  (It's in Volume 1, chapter 7, "Hackenbush", under "NP-Hardness" as part of the chapter's Extras.)  From Page 224 of the second edition:

"Even & Tarjan have shown that Generalized Hex is PSPACE-complete and Schaeffer [sic] has done the same for Generalized Geography, Generalized Kayles, Col and Snort."

Winning Ways is a fundamental work.  In 2009, Alessandro Cincotti referenced this to state that Col was PSPACE-complete in his paper on a 3-player Col variant.

The sentence in Winning Ways is a reference to Thomas J. Schaefer's 1978 paper On the complexity of some two-person perfect-information games, which is probably the most important paper in Algorithmic CGT.  In that paper, Node Kayles ("Generalized Kayles") is shown to be PSPACE-complete.  And the same for Snort.

And not Col.

Like the others, Col is certainly in PSPACE: on a graph with n vertices and m edges, the height of the game tree is at most n and each player has at most n options on their turn.  We can do an exponential-time traversal of the game tree using polynomial (in terms of n and m) bits to keep track of our work (Polynomial Space, PSPACE, sized) and determine the outcome class of the position in question. 

The hardness was tricky, however.  It seemed like an easy enough game, but Col is quite cold.  Each position is equal to a number or a number plus *.  For each player, the options might toggle the inclusion of that * and/or push the number towards the opponent's direction.  There are no switches or otherwise hot positions where it is a significant benefit to play first.  The lack of heat made it hard to find a reduction from another partisan games.  Impartial games are automatically cold games, but reducing from impartial to partisan is a pretty tough paradigm shift.  (It's not as bad to go the other way, e.g. the reduction from QSAT to Generalized Geography from Schaefer's paper.)  

These inherent difficulties combined with the Winning Ways typo meant that Col's computational complexity went unsolved for a long time, despite the simplicity of its rules. 

In 2009, Bob Hearn and Erik Demaine adapted Hearn's thesis into the book Games, Puzzles and Computation, which became a catapult to resolving the complexity of many other games that had eluded categorization, including Amazons and Konane.  (This led to the coining of the term Algorithmic Combinatorial Game Theory, i.e. ACGT.)  I met Bob Hearn a few years later and we agreed that solving Col was a big prize.  Not only was it a long standing open problem, but the game seemed computationally hard and proving it would "cure" the hole and make the Winning Ways sentence true. 

In 2013, 35 years after Schaefer's foundational paper, we got to work.  Bob explained Constraint Logic, the main tool from his thesis, to me.  We got the gadgets (mostly him) and everything slowly came together.

And then we got scooped.  In early 2015, a team with Steve Fenner showed that Col was PSPACE-complete in Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games. 

The Col result is only a small part of Fenner, Grier, Messner, Schaeffer, and Thierauf's excellent paper, but it's an absolute gem of a proof.  The reduction goes straight from Positive CNF and yields uncolored graphs!  That means that these can be considered starting positions that are shown to be hard, an impressive feat!  Finally, the question of Col's complexity was resolved, joining its cousins Node Kayles and Snort as PSPACE-complete. 

We did continue our work.  Part of the benefit of using Constraint Logic is that our reduction produced Col instances on planar graphs (though they certainly weren't uncolored).  We also showed planar PSPACE-hardness of Fjords, NoGo, and Snort, which was an improvement on Schaefer's original non-planar case.  With those additions, we got our paper out in 2018, one of my best publications.

Col remains an interesting ruleset in the short-lived history of ACGT.  For a long time it was accidentally understood by many to be solved.  Over 35 years after Node Kayles and Snort were solved, it was finally shown to be hard in two separate scenarios, independently proven in a short span.  I'm very lucky that I got to be a part of such a cool "academic moment".

Currently the remaining "biggest" rulesets with unknown complexity are probably Clobber and Domineering.  I know that advances are being made towards the complexity of at least one of these.  Perhaps one day we'll see another race to the finish on another of the most highly-regarded games in CGT.

Edit notes: I originally had an image of the quote from Winning Ways, but it wasn't displaying properly, so I replaced the image with the quote.

Sprouts 2024 Talks

Sprouts 2024 was on Saturday, and it was excellent!  Here are my summaries of the talks:

Pritika Raj, "Red-Blue Hackenbush and the Construction of Real Numbers"

Pritika covered the basics of Hackenbush and showed how to create integers from mono-colored stalks: path graphs with one end on the ground.  Then she got to dyadic rationals, and showed that they can also all be created from finite stalks.  After that, Pritika explained how to use infinite stalks to create non-dyadic-rational real numbers.  For example, she showed that 2/3 is equal to an alternating Blue/Red/Blue/Red/... infinite path from the ground.  

Vivaan Daga, "Nim and Base 2"

Vivaan explained the rules of Nim and gave a good example of a playthrough.  He showed how to use the binary XOR to figure out the outcome class of a position.  Then he got into the details of the proof that XOR works.  Vivaan explained that binary is the important operation because, due to the mex rule, Grundy values are as small as they can be.

Keynote: Mike Fisher, "Octal Games: Old and New"

Mike introduced impartial games and the basis of Sprague-Grundy theory.  Then he explained the rules of Kayles and showed the table of the first 84 Kayles values.  He showed the same with Dawson's Chess, explaining the rules and giving a table of values that showed the periodicity.  Then he covered Treblecross in the same way, but showed a graph of the Grundy values, since it's unknown whether the Grundy values are periodic.

Mike then explained the coding of octal games.  Each game is represented as d0.d1d2d3d4... with d0 = 0 or 4, and all other di being between 0 and 7 (inclusive).  Each digit di is the sum of up to three components:

• 1 if you can remove i when the pile has exactly i,
  
• 2 if you can remove i when the pile has more than i, and
• 4 if you can remove i and split the remaining items into two piles, when the pile has more than i+1

Mike showed that Kayles is 0.77, Dawson's Chess is 0.137, Treblecross is 0.007, and Nim is 0.3333...  He then showed off Achim Flammenkamp page of known octal game properties.  

He continued by describing Wythoff's Nim, Beatty Sequences, and the Golden Mean, then explained what the Silver and Bronze means are.  He used that to lead into the three octal games he created from sequences based on each of these means.  The Olympic Games, as they are known: The Golden Game, the Silver Game, and the Bronze Game.  Mike ended with a new result to me: the Plastic Game, based on the plastic sequence, which is generated by Van der Laan numbers.

 

Ethan Saunders, "Misère Cricket Pitch"

Ethan explained Cricket Pitch, themed around a bumpy field that must be leveled out by a huge roller.  The game is described by a list of non-negative integers with the roller inserted somewhere.  A move consists of moving the roller in your direction (left/right) over as many piles as you want, but you can't cross a zero-sized pile.  Every pile you roll over in your turn gets decremented.  Ethan showed how to calculate some basic games, then used this to discuss group representations.  

Sean Pye, "Fighting Fires on Infinite Grids"

Sean researched the fire-fighting problem on graphs: where fires break out on vertices then fire fighters are sent to defend them.  The fire fighters prevent the vertices they visit from burning as the fire spreads out from its initial location each round.  Sean studied solutions on hexagonal grids and strong grids.  He showed the known strategies for hexgrids that use only 2 firefighters to contain a fire and that strong grids need only 4 firefighters.

Devan Burke, "Reinforcement Learning with Super Mario Bros."

Devan talked about how he worked towards training an AI player to beat level 1-1 of Super Mario Bros.  He talked about the formulas he used to reward the AI player using reinforcement learning.  He explained that the player can see four snapshots of the screen to use as input. In order to keep the size reasonable, they used grayscale images.  Devan described the design of the neural networks used by his player.  His algorithm included a double-deep Q network.   

Raymond Riddell, "Monte Carlo Tree Search"

Raymond talked about the MCTS algorithm he wrote for my HTML-(and JS-)based combinatorial games.  He explained the difference between heuristic and aheuristic algorithms.  He showed a demo of the algorithm applied to Connect Four.  He described a bunch of details of his code, including how the tree is structured and all of the UCB1 values of the nodes based on their win records.  These values are used to determine which node to traverse when exploring more of the tree.

Max Fierro, "Computational Methods Uniformly Pushing the Solving Horizon"

Max talked about exhaustive searches for solving deterministic games.  In order to do this, he employs the notion of histories, sets of states that include a utility function.  His team created a 4-tuple to represent vertices in a graph that works for any sort of deterministic game.  Max described a minimax implementation to search and make decisions.  His group uses multiple threads and a custom database system to speed up his code.

Tomasz Maciosowski, "The Temperature of a Snort Position can be Infinitely Larger Than its Degree"

Tomasz explained the game of Snort and described a game simplification that removes unplayable vertices and tints vertices that can only be played by one player.  He described the notion of temperature and showed how it applies to star graphs.  He then talked about using a genetic algorithm to search for positions with higher temperature than the max degree of the graph.  This led to the discovery of caterpillar graphs that led to unbounded differences between the temperature and degree.

One of our scheduled presenters got sick and couldn't present, but otherwise this was an immensely successful edition of Sprouts!  Thank you to everyone who came and especially thank you to everyone who presented!  See you next year!

Games at Mumbai: Not the Talks

Games at Mumbai just ended.  In a few hours, I will arrive at the airport and fly home.  My first time in India has been wonderful!  I loved it!  Here are some quick notes about my time here that I think are interesting:

• The traffic outside the IIT Bombay campus is the wildest I have ever experienced.
• Learning to look right first when I try to walk across a road is harder than I thought it would be.
  
• All of the food was awesome!  I discovered so much!
• Many bathrooms have a bidet spray nozzle instead of toilet paper.  I attempted to learn to use bidets without using toilet paper, but failed.  I had to rely on stalls that were equipped with rolls of toilet paper.
• The venue at IIT Bombay, the Victor Menezes Convention Center, was excellent.  There is a great indoor room for presentations and a nice shaded outdoor space for eating and collaborating.  (We also had access to some classrooms.)
• I got addicted to chai, both with and without masala.

Notes specific to CGT:

• I talked about what (I think) a ruleset is and this sparked some conversations.
• Lots of people wanted to talk with me about my research!  That was a (dangerous) ego boost, for sure.
• I was lucky about the topics I put in my second talk; it addressed many of the questions I got in the two days after the first one.  I barely changed anything from the slides I had before I arrived!
• Four days of talks about CGT is not too much for me, even being sleep-deprived for three of them.
• I learned a TON about the pre-history of CGT from Carlos. 
  

Long, sappy note:

I was very nervous about this trip, because air travel is tough for me.  Mumbai is the furthest east I have ever traveled.  I got quite sick a few weeks ago, and then the day before I left I still had to visit the doctor.  My flights here got cancelled on the morning they were set to depart.  

Nevertheless, I still made it here and I am extremely glad I did.  I learned so much.  Thank you to everyone I met!  Thank you to everyone on the organizing committee!  I feel like I could have jumped into 5 or more new research projects!  (I'm not a research professor, so there's no way I'll be able to do that, sadly.)  

I have been very lucky in my career.  Many times I have not been able to follow through on all the things I wanted to do, and I've had the fortune to continue on anyways.  I received a lot of appreciation here, and it means a ton.  I hope that it is deserved; I did spend a lot of time preparing my talks. 

Just like the Games and Graphs Workshop six-and-a-half years ago and the BIRS meeting in 2011, I really feel like a valuable part of the CGT community.  Thank you to everyone.  There may not be any chance in our rulesets, but I've still been very lucky.