The talks continued to be great on day three! Here are my summaries:
Shun-ichi Kimura: "Disjunctive Sums can be Non-Commutative or even Non-Associative"
Shun-ichi talked about "exotic" ending conditions that can break commutativity and associativity. One example is subtraction games with sets not containing 1 where the terminal positions award a winner depending on whether there are tokens or not. (E.g. Left wins on zero tokens; Right wins on 1 or more.) Shun-ichi showed more complicated winning conditions, then presented a case where even associativity fails.
Shun-ichi Kimura: "Variations of Greedy Nim"
Shun-ichi reminded us about the winning strategy for Greedy Nim, then described k-bounded Greedy Nim, where players are not allowed to remove more than k stones on their turn. Recently, it's been shown that misère k-bounded Greedy Nim is not tame, but the behavior is still very similar to tame games. In another variant, 1,2-Greedy Nim, players can play on both the largest and second-largest piles, which yields the same strategies in Normal and Misère. Shun-ichi's team then defined my other versions with more complicated ways to determine outcomes, including versions where some tokens can be added back to smaller piles. One of these, Koreeda Nim, surprisingly has the same outcome classes as Greedy Nim.
Nanako Omiya: "A new approach to the analysis of variants of Nim in Misère Play"
Nanako continued the discussion from Shun-ichi's last talk, proposing a method of analyzing misère play by reducing to positions in a Normal-play ruleset. Nanako's team found that even though k-bounded Greedy Nim is wild (not tame), there is still a reduction that makes it easier to classify. Her team refers to this as Omega-misère-to-normal-reducible. They proved a theorem to harness the reducibility into a tame-looking set of g-values. Nanako showed how to apply this to k-bounded Nim and also showed that this tactic still applies to tame games.
Hiroki Inazu: "Game values and quotients for LR-ending partizan games"
LR-ending games are subtraction games where the lowest element of the subtraction set is 2 and the winning conditions are that Left wins if zero tokens remain at the end and Right wins if one remains. They extended to multi-heap versions, where Left wins if there are an even number of tokens at the end across all piles and Right wins if the sum is odd. They analyzed this on the subtraction set {2,5}. To find canonical forms, Hiroki's team found methods to reduce beyond domination and reversibility!
Ryohei Miyadera: "Variants of Nim with a Forced Pass"
This talk was actually given by three of Ryohei's high-school students! This group talked about 3-pile nim with a forced pass, meaning a player can, once per game, force their opponent to pass. This is equivalent to taking a second turn. The team notes that when the pass is unused, there are very few P-positions. The group also analyzed many variants on this forced pass model, including making restrictions on the moves that can be made during these double-turns.
Takenobu Takizawa: "Combinatorial Game Theory Applied to Go Endgames" (Invited Talk)
Takenobu talked about his work on Go Endgames. He joined Berlekamp's team back in 1991 to implement a program to analyze and play go. He talked about starting work in situations without kos. Takenobu demonstrated that even simple-looking regions can be very difficult to analyze, even for professional players back in 1991. He also showed that it's more valuable for a player to play into a longer corridor than a shorter one. Takenobu then go into what they did to handle ko situations, including positions where unexpected "hidden ko" component could arise. This was a great look back at the value of collaboration in early CGT research.
Svenja Huntemann: "Snort Temperature Compared to Maximum Degree"
Svenja talked about Snort, where two players place tokens on a simple graph but can't play adjacent to opposing pieces. She explained temperature and boiling points, and then reminded us of an old conjecture that the temperature was bounded above by the degree, which was broken earlier this decade. In her team's most recent work, they broke the conjecture even further using some caterpillar-style graphs. They were able to show that the temperature can be nearly twice the degree! Then they took it a step further and showed that they can pump the temperature up past any constant multiple of the degree.
Madhav Miglani: "Divisibility Duel and the Remainders"
Madhav's game, Divisibility Duel, is played on a sequence of numbers where the players remove pairs of numbers from the sequence based on partizan divisibility properties between them. Madhav showed different outcomes based on the different situations for the two players and described Left's winning strategy in one case in detail.
Koki Suetsugu: "Extended Sprague-Grundy Value for Two-Step Games; How can you deal with cloning ninjas?"
Koki talked about an extension of Corner the Rook (2-pile Nim) and Corner the Bishop, which is like Wythoff's Nim with only the diagonal moves. In Corner the Ninja Rook, a turn consists of first killing one of the ninja rooks that was created in the last turn, then splitting one of the other ninja rooks and moving one copy up and one copy to the left, both towards the origin. Corner the Ninja Bishop is similar, except the Bishop first moves towards the origin, then splits into two spaces along the orthogonal line. Koki then related this to quantum games and discussed a general theory for how to deal with P/N-positions as well as disjunctive sums. Koki's team proved that things work out as you'd want them to!
Alda Carvalho: "Cyclic Impartial Games with carry on moves"
Alda talked about entailing moves in impartial games in the context of loopy games. She described Green-Lime Hackenbush, where green (non-lime) edges are carry-on moves; the player that just went must go again. To make it cyclic, a third type of move is available: neighboring green/lime edges can be swapped. She explained protection and how to extend the mex rule to the new values, like Moon and adorned Moons. She showed when infinities and nymphets (infinite-nims) appear as values due to the cyclicness.
Kengo Hashimoto: "Ordinal Sums and Poset Games with Initialization"
Kengo talked about playing games on a Poset where playing on one game also resets all games less than that one to their initial positions. Kengo used ordinal sums and variance sets on top of standard Sprague-Grundy theory in order to analyze his games. He was able to use sums to simplify the representation of diamonds. He analyzed many situations like paths and grids, all consisting of *-initial games.
Kuo-Yuan Kao: "Construction of Sumbers"
Kuo-Yuan talked about the indivisible atomic pieces of partizan all-small games. Sumbers are the set of games that are sums of ups. He explained that ups are these elementary elements; they can't be built as sums of more elementary games. Kuo-Yuan showed a generalization of ups parameterized by two numbers that remain totally ordered and are still "fundamental particles" for all-small games. He showed how to extend this all the way to n-dimensions!
Alfie Davies: "The misère invertibility of Amazons and Kōnane"
Alfie talked about how under misère play, non-zero inverses of Amazon and Kōnane don't exist in those two rulesets. (Alfie had to keep reassuring the audience that we'd be able to follow him, which worked.) He successfully showed baby-step-size propositions until he arrived at the fact that including { |2} and {bar(2) | } preclude non-zero inverses. Alfie showed that this applies to many rulesets, including Yashima and Omni-Fission, which he'd learned about here.
Tomasz Maciosowski: "Lean into Misère: Formally Losing is Hard"
Tomasz talked about Dead Ends and Dead-ending games, and P-free, which are misère games where no subpositions have outcome P. The P-free subset of all dead-ending games is the invertible subset of dead-endings. Tomasz then talked about using Lean with combinatorial games to help prove things in CGT. He showed an example on P-free orderings that was already known, then showed some new theorems that Lean was able to prove!
A third great day of talks here at CGT Japan!
No comments:
Post a Comment