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!
No comments:
Post a Comment