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.")
