On day two of talks, there were multiple presentations by teams of high schoolers. I didn't get the names of everyone in each team, but if I get those names, I'll update and add them later. (I will point out which talks were done by the teams.)
Kikuno Ooyagi: "A Nim with two different rules"
This was the first of a few presentations given by teams of high schoolers! I apologize in advance for not listing all of their names. This team had three presenters. They started by covering Sprague-Grundy theory and then talked about Greedy Nim, which they combined with Nim on three piles. If the total number of stones is above a specified value, s, players may only take from the largest pile(s). If it's below, they may make traditional Nim moves. They looked at the cases s = 14 and s = 17, then showed now to find outcomes quickly for some complete families of s-values! They also flipped the conditions and analyzed options there. They also analyzed 3-pile Nim with a pass.
Takayuki Morisawa: "Periodicity of m-Pile Divisor Nim"
Takayuki talked about m-Pile Divisor Nim, where the amount to subtract, d, follows some additional contraints, similar to Saliquot, Salinquant, Stau, and Common Divisor Nim. In 2-pile Divisor Nim, d must divide the number of stones in the other pile. Takayuki's generalization is that there are multiple piles and d must divide all other pile sizes. He found a formula to determine the outcomes and discovered periodicity when fixing all but one pile size.
Ko Sakai: "Conway's Field of Characteristic 2 and the Algorithms for its Operations" (Invited Talk)
Ko talked about Sprague-Grundy theory in terms of transfinite induction on ordinals. Then he talked about Nim products (which I am wholly unfamiliar with), exponentiation, and inverses. All of these are defined inductively/recursively and are quite complicated. (At least, to me.) Ko showed how to find Nim square roots, and then something called star roots. He showed Nim polynomials, where the coefficients are ordinal numbers. For many of these, it's not clear how to compute them from the definitions, so he showed the processes to perform actual calculations to get equivalent results. Ko ended with an explanation of his method for performing the Nim multiplication over omega for two 2^(n+1)-bit binary numbers and also how to solve quadratic and quartic equations.
Craig Tennenhouse: "Mind the gap: A real-valued distance on Combinatorial Games"
Craig talked about work we did with Mike Fisher to look for useful metrics on game trees. This is part of a push to use genetic algorithms to try and solve games and find positions with properties or specific values. He described the metric as a weighted DAG edit difference where changes further from the root are cheaper. He showed examples where the sequences converge to loopy game values and showed some loopy games that are not limit points.
Kouta Kawakami: "Crushcar Nim"
Kouta talked about his transfinite version of Nim on piles in an ordered list. A turn consists of taking from one pile, then adding as many tokens as desired to any of the piles of higher index. Kouta needs to use omega and ordinal numbers in order to describe game values. Kouta explained a lot of the arithmetic on ordinals that was relevant to Ko Sakai's talk from before. He calculated transfinite Nim values for 2-pile positions and gave a general formula. Then he showed a method to compute it for more than two piles. He also figured out how to analyze the situation for misère play!
Takahiro Yamashita: "Combinatorial Games and the Golden Ratio on digraphs"
Takahiro introduceda 2-pile Nim variant where players can add to the other pile as long as the total number of tokens decreases, then showed that the P-positions are still (k,k). In Digraph Triangular Nim, a variant of Graph Nim (or NimG), a turn consists of moving along an edge (a,b), removing tokens from a and adding to b in the same fashion. Takahiro's team proved a formula for the set of P-positions on the one-directional 3-cycle, which uses the golden ratio!
Hiyu Inoue: "Asymmetric Wythoff's Game"
Hiyu's variant of Wythoff's Nim is a modification of r-Wythoff, parameterized by two values: m and n. If a move is (a,b) -> (a-i, b-j), then it must be that -m < (i-j) < n. Hiyu uses Raleigh's theorem to find P-positions when m = 3 and n = 2. (A lot of the calculations use continuing fractions!) Hiyu used a general version of a Zeckendorf-style representation in order to categorize positions for general n and m.
Kosaku Watanabe: "Triangular Nim with S-Wythoff Twist"
Kosaku continued with what Hiyu had spoken about by combining r-Wythoff and the triangular options. The triangular options are like normal Wythoff single-pile moves, except that you have to take at least two and must add at least one back to the other pile (while keeping the total removed positive). The S-twist is that instead of a constant r, the allowed differences are described by a sequence, S, and the "r-value" is based on the i-th element of S where i is the amount removed. Kosaku references Mersenne primes while analyzing the outcome classes!
Kosaku Watanabe: "Asymmetric Triangular Wythoff Nim"
Kosaku also talked about how to combine the asymmetric and triangular Wythoff variants in order to get P-positions at different polygonal numbers. (E.g. the pentagonal numbers.) Kosaku explained all the theory behind how the interaction of rules makes it work.
Aoi Murakami: "A variant of Wythoff's Game whose misère version is almost the same as Wythoff's Game"
This presentation was another done by a team of high schoolers! Amazing! This group found a misère variant that acts much like the original Wythoff's. The variant rule is simply that all positions with sum of piles sizes of two or less is a terminal position. With that condition, they found the normal play and misère P-positions. The new misère P-positions pair up nicely with the original normal play P-positions and follow a ratio and sequence based on Fibonacci words.
Anjali Bhagat: "Cyclic Sink Subtraction"
Anjali described a subtraction game where the pile size can go below zero: it just cycles around mod some constant. Zero (or another location(s)) is the sink: it still causes a terminal position. These games are loopy, so the outcome can be a draw (D). There are three types of nim values: nimbers, infinity (the next player wants the game to keep going as a draw) and indexed infinities, where one of the options is an infinity. On a basic example, Anjali's team found only infinite values (aside from zero at the sink). With bigger sets and multiple sinks, they were able to find nimbers! Anjali showed how to find the mex with these infinity values and proved theorems to find periodicity.
Urban Larsson: "Additive Subtraction" (Invited Talk)
Urban started off by explaining the anachronistic name of his talk: it's still about subtraction games, but the subtraction set is additive: {a, b, a+b}. His team distinguishes between Sink Subtraction (as Anjali just talked about) and "Wall Subtraction" as a new name for the non-modular (non-loopy) setting. Urban was very careful about looking at the history of subtraction results, both for the sink and wall cases. They went back and proved a statement that had gone unproven (but used!) for years. They found a general block construction for Additive Sink Subtraction and then discovered a great relationship between the outcomes of the sink and wall situations!
Hikaru Manabe: "Mex/rev-Mex Orbit Structure of 3-Move Subtraction Games"
Hikaru reported on work he's done with Urban's team in India, including a "CGT missionary" trip to campuses around the country. Hikaru was also interested in additive subtraction, but in the wall case specifically. He noticed a familiarity while doing the analysis that resembled Ferguson pairing. They called the Reverse Mex the correspondence when the g-values for an x are similar to -x. Unfortunately, there are many subtraction sets that don't have the Reverse-Mex invariance property.
Hikaru Manabe: "Dropping Two Coins"
This was the third an final talk by high schoolers of the day. Hikaru (now a college student) has been working with high schoolers on CGT projects. The Dropping Two Coins game is similar to iChess with two rooks, but with jumping allowed. (No double-occupancy, though.) This last part makes it different from 4-pile Nim. They also analyzed a second variant similar to the first but the two tokens are heading towards opposite corners of the board. Here the P-positions are complicated when the overlapping is not allowed. They got results showing that the values of the game look surprisingly different!
This was a great day of talks! The three high school team talks got me really excited for Ryohei Miyadera's talk on Sunday where he's going to go over his success with leading these teams for twenty years!
No comments:
Post a Comment