I'm in Japan for the first time ever for the first ever International Conference on Combinatorial Game Theory in Japan! Today was the first day of talks and we had a whirlwind amount of them!
Koki Suetsugu started things off with the opening ceremony introduction, complete with information about Waseda and a complete history of CGT in Japan. Him and Tomoaki Abuku have done an amazing job promoting the study of combinatorial games in Japan and it is paying off in spades. (I heard someone ask earlier whether there were more gamesters inside or outside of Japan.) Koki was very appreciative for all the talks; we have over 55 in total! "Today a new page in history is written," he said.
Note: there were some visa/funding issues and some talks got moved around or skipped because the speaker couldn't make it. I don't know exactly how everything got shuffled around.
Ryota Ikeda: "Extended Grundy's Game"
Ryota talked about a variant of Grundy's Game where the difference between the two created piles must be at least two. For example, a pile of 7 can be split into 6 and 1, or 5 and 2, but not 4 and 3. Grundy's Game has famously not been solved. Ryota explained the term Tame, which is when a ruleset has misère Grundy values that act similar to those found in normal play, pointing out that Grundy's Game is not tame. Ryota showed that the Extended Grundy game is solved and that the nimbers reach a period of only five! In addition, Misère Extended Grundy's Game is tame and the Grundy values reach a period of only four!
Haruki Wada: "On Negative Code Game, the Generalization of Code Game"
Haruki talked about octal games and the notation for them. His work with his group extends the octal notation to include negative indices. For example, if d_-2 = 4, it means a player can add two tokens to a pile, then split it into two heaps, e.g. a pile of 1 can become piles of 1 and 2, which can become piles of 1, 2, 2. To ensure finiteness, they added the requirement that for d_-i, it must be a multiple of 2^(i+2). Haruki's team showed that this forces termination in a finite number of moves. They also found a way to find nimber sequences for different families of codes.
Yuto Morikawi: "Continim (Continuous Subtraction Nim)"
Yuto started by remininding us about Subtraction games, which he phrased as cutting from a string. His variant includes non-integers in the subtraction set, meaning irrationals are the interesting part. He expressed nim sequences as step graphs instead and was able to find a periodicity of 1 + sqrt(6) on {1, sqrt(2), sqrt(6)}. Yuto was able to prove many things about periods of sets of the form {a, b, 1} for different values of a and b. Yuto's team also showed that {1, e, 1+e} is aperiodic!
Takuto Maki: "Reflexivity Criteria and Minimality in Subtraction Games"
Takuto talked about the definition of reflexivity, which is when you find the new P-positions after removing the terminal positions. If doing this twice for a subtraction set results in a game with the same subtraction set, then it's considered reflexive. Takuto found another criteria for reflexivity that appears to be quite useful. Takuto was able to give a quick proof of an older criteria of reflexivity from Urban Larsson via his new criteria. He was also able to show that minimality is implied by reflexivity!
Hiraku Hinata: "Another Cutcake"
Hiraku described Cutcake where Right and Left make cuts on a grid of spaces Horizontally (Right) or Vertically (Left) and discussed the known results from Winning Ways, including the integer values. Another Cutcake was also introduced in Winning Ways, but Hiraku's team showed that the formula given there is incorrect and were able to prove a correct general formula!
Carlos Pereira dos Santos: "The discovery of the Surreal numbers" (Invited Talk)
Carlos talked about the beginning of Surreal numbers by John H Conway and then the book written shortly after by Don Knuth where he coined the term "Surreal". Apparently Conway regarded the creation of the surreals as his greatest achievement. Carlos discussed Dedekind cuts (used to define the reals), Cantor ordinals, and finally Zugzwang situations as the three ingredients that led Conway to the surreal numbers. Carlos introduced Hackenbush and the relationship of the surreals from the game notation we're used to. He talked about integers, then dyadic rationals via simplest numbers. Through all of this, Carlos used Blue-Red Hackenbush to present the concepts, emphasizing the fact that all this can be done with a single stalk. Carlos wrapped it up by showing a diagram of different stalks and the photos of Dedekind and Cantor to show where they fit together in this "moment in the history of mathematics".
Sahana Jahagirdar: "Omni-Fission"
Sahana, an undergrad at IIT Bombay, talked about the game she created mimicking atomic fission. Players have colored stones on a grid and a turn consists of replacing a stone of your color with two or more stones of the same color in spaces adjacent to where the original stone lay. (Max-Omni-Fission is the version where each stone is replaced by steons in all empty adjacent spaces, but still requires that at least two of those spaces are empty to move.) Sahana was able to find mahy values in games on strips and 2 x n bands!
Kanae Yoshiwatari: "Computational Complexity of biased Undirected Vertex Geography"
Kanae talked about a variant of Undirected Geography. First she covered the basics, then a weighted version where each vertex has a counter that gets decremented when play passes through, and removed when it hits zero. She also showed Exact k-Vertex Geography, where each turn consists of k graph moves. Kanae's team showed that Exact 2-Vertex Geography is PSPACE-complete for positions with max degree of four and Exact 3 (or more)-Vertex Geography is also PSPACE-complete for graphs of max degree three. Then her team showed a biased version of the game where players have separate k's and is also PSPACE-complete when three k's are greater than 1, also for low-degree graphs. The gadgets they created are very elegant.
Matt Ferland: "Slimetrail is PSPACE-hard on grids"
Matt presented work by him and his undergrad student Anne Pham on Slimetrail, a game played in the nationwide school tournaments in Portugal. He demonstrated the game and then talked about the basics of computational complexity and reductions. Matt described QBF and then showed some of the gadgets they used in their reduction. The recent work on this problem is the update of showing that these gadgets can "snap" to the grid. Not only did they make this work, but also had a working version that didn't include the diagonal cross edges!
Anuj Jha: "Heavenly Domineering"
Anuj described his variant of domineering where players have to play dominoes as high up on the board as possible. He found that some basic positions have the same values, but then also showed a small position with value tiny(-1). Anuj argued that there are a lot of numbers because of the move restrictions and showed that the negation-by-reflection doesn't work in this variant. He found values for a lot of positions and noted that there seems to be a strong bias for the Left player.
Rakshit Rane: "CrissCross - Diagonal Domineering"
"You can already guess the rules," Rakshit said as he began. In CrissCross, Left plays dominoes tilted up-right and Right plays them tilted up-left. The reason he gets different results is, as you may imagine, that dominoes can now cross over each other. However, he showed constructions to transform Domineering to CrissCross and vice versa. In the CrissCross to Domineering direction, he splits the board into two because shifting by one square leaves two independent component boards!
Tomoaki Abuku: "Various Diamond Properties in Combinatorial Game Theory"
Tomoaki described the Yashima Game, which is undirected Geography with separate tokens for each of the players. His team noticed a "diamond property" when both players' moves have opposite options to the same position. This can be generalized when the Left-Right grandchild compares favorably to the Right-Left grandchild. Tomoaki's team extended the previous work on these properties to new versions, then applied their results back to the Yashima game on some bipartite graphs.
Divye Goyal: "Tap and Top Match"
Tap Match and Top Match are variants of Chopsticks, which is playable by people just on their hands. In Tap Match, the players hold matchsticks in each of their hands (or hold out their fingers) so the position is described by a 4-tuple. In a turn, a player chooses one of their hands and taps one of their opponents' hands with it. The opposing hand adds matchsticks to it equal to the number from the active player's hand that did the tapping. When a hand gets too big (e.g. five or more) it is eliminated. Divye found values for many positions and proved that the atomic weight must be less than the vanish level. Top Match is the same, except that you can only tap with a hand if it has greater than or equal to the number of sticks than the one getting tapped. He found that this version has a boiling point of 3/4.
Ruchir Mital Parekh: "Grid Nim: Analyzing the Game"
Grid Nim is a partizan game played on a grid of tokens. A turn for Left/Right consists of picking a Column/Row and removing any positive number of tokens from it. Ruchir found some values of positions and proved that the atomic weight is based on the number of rows minus the number of columns! He also defined a non-all-small variant where players cannot remove all of the tokens available to them in one turn.
Mike Fisher: "Atomic Variations of Roll the Lawn and Cricket Pitch"
Mike gave an update on work he'd spoken about at CGTC last year about the lawn rolling games where players remove "bumps" that are entries in a list of non-negative integers. He described Roll the Lawn first where the values can be calculated very quickly. Then he talked about Cricket Pitch, which is the same except that the roller cannot cross any bump of size zero. He then went into his atomic weight versions where players can additionally make a play on any bump as thought it were a nim heap in lieu of their normal turn. In Atomic Cricket Pitch, it seems like the nim moves are often the most important to make right away.
Somya Dahiaya: "A Normal Play Chain-Reaction"
Somya talked about his game, inspired by the popular game Chain Reaction. This game includes playing tokens of your color onto a grid where each space has a threshold number. Tokens of different players cannot be played on the same space and once the threshold number is reached, the tile becomes an "Attacker" tile and all neighboring tile tokens are removed and can no longer be played on. Somya found a bunch of values and also created an all-small variant where players can place green tokens as well.
Ankita Dargad: "Full and Truncated Support Subtraction"
Ankita described Full Support, a right-biased partizan subtraction game where the two sets are {1, 2, ... a} and {1, 2, ... b} (a < b). Right always has a winning strategy going first on non-terminal positions. In fact, as Ankita proved, the canonical form of positions only has zero as a right option. To make things more fair, if the Right player doesn't have small-number options, then we call this game Truncated Support. Ankita showed that the game is still quite biased for Right on large heap sizes and found a periodicity once enough truncation had been applied.
I am surprised that today included eighteen talks because they were all very good and easy to follow. I can't wait to hear tomorrow's! Also, I appreciate Alfie Davies, who answered some questions I had in between talks that helped me write these notes!
No comments:
Post a Comment