International CGT in Japan, Day Four

Yesterday, Sunday, was the last day of the first international CGT conference in Japan.  Here are my summaries of the talks:

 

Kentaro Hoshi: "Evolution of ANI (Artificial Narrow Intelligence) in Shogi and Social Adaptation: A case study for Symbiosis in the era of ASI (Artificial Super Intelligence)" 

Kentaro talked about Shogi and play has evolved in the past thirty years.  Prior to the modern age, people had to move to Tokyo in order to be near other players and learn to play well.  Nowadays, everyone has access to a grandmaster in their pocket, so worldwide skill has exploded.  Unfortunately, cheating has forced airline-level security to be imposed on tournaments.  Kentari argued that human strategies have evolved greatly now in order to defeat AI opponents.

 

Nikhil Nareda: "Climb Over: A Combinatorial Game" 

Urban Larsson presented slides for Nikhil, who could not be at the conference.  In Climb Over, boxes of two colors can be moved on top of each other (if the height difference is at most 1) or fall off to the left hand side.  Urban showed a bunch of positions and their values, including integers and switches.

 

Thotsaporn "Aek" Thanatipanonda: "Generalizing OOOOOOB" 

OOOOOOB (One Or One Or One Of Both) is a 2-pile Nim variant where players can take one from either pile or one from both.  Aek said he often sets students on this, and they usually discover that the P-positions are those where both piles are even.  Aek's team generalized OOOOOOB to more piles in three different (but very natural) ways.  They proved that in all versions, if all piles are even, it's still a P-position!

 

Hironori Kiya: "Semi-Perfect Information Nim and It's Variants" 

NII is Nim with Imperfect Information; where the players know the nimber of all piles, but not the number of stones in each pile!  On a turn, a player picks a pile and a number of stones and either makes the move or loses if they pile isn't big enough.  Hironori's team extended this to multi-pile subtraction games.  They determined different oracle models for when optimal strategies can be determined.

 

Balaji Rohidas Kadem: "More Results on Modular Nim" 

Balaji talked about Modular Nim, a game similar to Sink-subtraction, except positions can't be repeated and the zero element isn't automatically terminal.  This was studied by Aviezri Fraenkel in 1995, with diamond strategies as a main result.  Balaji's new results include proofs of multiple conjectures from 2014.  (E.g. that a game on {a, b} with a starting size of 2a is an N-position.)  His team also solved many more families of two-pile games.

 

Ryohei Miyadera: "Twenty years of my research on Combinatorial Game Theory with high school students - Chocolate Games, Games with a Pass, Maximum Nim."  (Invited talk) 

Ryohei talked about his passion project for the last twenty years: teaching CGT to high school students and doing such advanced research with them that many present at international conferences.  (See the many talks presented here as examples!)  He talked about how he first teaches Impartial Games and Sprague-Grundy theory.  he talked about using a chomp-like Chocolate Game as an instructional example.  (Each turn consists of breaking the chocolate bar into two pieces along one edge or row.)  His methods revolved around four steps:

1. Show a game to the students (E.g. Chocolate Game)
2. Ask students to come up with variants
3. Select the most interesting variant proposed
4. Try to solve the chosen problem.

Ryohei has had lots of success with students in Chocolate Game, various games with a pass, and Maximum Nim.  His students have published many times over and we've seen them give great talks in multiple conferences now.  I love that combinatorial games are such a great vehicle for students to perform advanced mathematics!

 

Silvia Heubach: "The Invariance Reduction Process - a new tool to solve Circular Nim and related games" 

Silvia talked about Set Nim games, where players can play on specific sets of piles based on the set conditions.  Her team used an invariance reduction process to help identify P and N positions.  Silvia used Circular Nim as a motivating example through multiple invariance reduction methods they have had success with.

 

Hiromi Oginuma: "Scoring Nim" 

Scoring Nim is an impartial scoring game similar to Candy Nim, except that the score matters.  When players take tokens from a pile, they score that many points.  Additionally, when a player makes the final move, they score some bonus of points.  Hiromi showed conditions for when a player makes different moves based on the value of N and proved many results for the three-pile case.

 

Atsushi Iwai: "Gibbard-Satterthwaite Model as a Combinatorial Game" 

Atsushi talked about uses of social choice (voting) functions in combinatorial games.  He expanded on work of Elkind in 2015 on Gibbard Satterthwaite Games.  Elements of these games include four candidates, multiple preference profiles, and manipulator roles for the players on their turns.  Atsushi looks forward to applying CGT to social choice further.

 

Aditya Khambete: "The rulesets Expansion and Void Expansion" 

Expansion positions are grids with red and blue tokens on some spaces.  A turn consists of adding new tokens of your color to the empty boundary of a connected component of yours.  Aditya found integer and dyadic rational values on strips.  In Void Expansion, you can alternatively play a single token on any space not adjacent to one of your tokens.  This makes the game all-small.  Aditya found outcome classes for many empty grids.

 

Parth Sarda: "Analysis of Blippers and Flippers: 2 loopy placement games with elimination mechanics" 

Urban subbed in for Parth who could not make it to the conference.  He described Flippers, played on a grid with 2-color tokens.  When you play next to exactly one of your own tokens, you remove the old one.  In Flippers, you remove both of them.  In both games, playing next to two of your own tokens is called a Solidifying move.

 

Miloš Stojaković: "Maker-Breaker s-of-k games" 

Miloš talked about scoring-style Maker-Breaker games where the maker is trying to claim 3 of 4 corners in as many atomic squares on a grid as possible.  Optimal play of these kinds of scoring games leads to a "score of the game".  This notion can be generalized for any game where multiple "winning sets" can be achieved.  Miloš did a great job of using proofs by pictures to show the results his team found.

 

Matthieu Dufour: "Extension of Set Nim to Partizan" 

Matthieu continued the discussion of Set Nim which Silvia had spoken about.  In this extension, the left sets may be different from the right.  Matthieu and his group use Losing Sets for each player to describe when they won't have a winning strategy.  One interesting game they found was on five piles with the players playing on edges for the two different cycles: star vs pentagon.  The losing sets for each player are very surprising!  (The coolness is definitely a five, Matthieu!)

 

Nikhil Nagaria: "Fission and Cool Fission" 

Nikhil talked about a game similar to Sahana's on Thursday.  This game's starting positions are boards with stones on alternating spaces.  A left move consists of selecting a stone with empty space above and below and replacing it with stones in those two spaces.  (Right's moves are the same, but with the right and left spaces.)  Nikhil analyzed strips and found the values of all starting positions.  He was also able to prove results for wider boards.  Cool Fission is the all-small variant where players can make filling moves that don't remove the original stone, but can be made in either direction.

 

The last day of talks went great!  I'm already sad that the conference has ended.  The organizers put on a great time and I learned so much!  I met so many new gamesters and have a renewed appreciation for how much CGT has grown in Japan.  Great job, Koki and Tomoaki!

International CGT in Japan, Day Three

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 is well-known for including great characters in his talk slides.

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!

International CGT in Japan, Day Two

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! 

International CGT in Japan, Day One Talks

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.  He 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 reminding 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 criterion for reflexivity that appears to be quite useful.  Takuto was able to give a quick proof of an older criterion of reflexivity from Urban Larsson via his new criteron.  He was also able to show that minimality is implied by reflexivity!

 

Hikaru Hirata: "Another Cutcake" 

Hikaru 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 Hikaru's team showed that the formula given there is incorrect and were able to prove a correct general formula!  

(Edit: I fixed a misspelling of Hikaru's name.)

 

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

A Candid Cantor/Conway/Carlos Composition

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 stones in all empty adjacent spaces, but still requires that at least two of those spaces are empty to move.)  Sahana was able to find many 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 opponent's 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 at least as many sticks as 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 though 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!

 

Update: 3/20/2026: Hironori Kiya for pointing out that I got some names wrong.  Thank you, Hironori!  Also Alfie Davies noticed a bunch of grammar mistakes which I've amended.  Thank you again, Alfie!   

Integers 2025 CGT Talks

Today was the first day of Integers 2025.  I haven't been to Integers since 2013, so this is a very exciting trip for me.  Alfie is here and I've already met two new gamesters!

But I'm getting ahead of myself.  Quick explanation: Integers is a Number Theory and Combinatorics conference, with lots of number theorists and (as I've experienced in my previous visits) a small bunch of gamesters.  This year it looks like there's four of us and we all talked today.  (I hope I'm wrong about that!)

I went to a lot of number theory talks, but I didn't write things up about them, mostly because I just don't know a lot about that field.  The plenaries were great.  Number theorists are apparently hilarious.  Mel Nathanson had some great quotes, including "If I had to explain to grown-ups why I was interested in this, that'd be hard!" and "... one of the rare times doing mathematics I felt like a real scientist, ..."  I followed that talk a little bit, because I could correctly discern the words when "sumset" and "some set" were used in the same sentence spoken aloud.

This was also the first time I ever introduced speakers at someone else's conference.  (I think this counts as "chairing" though they weren't sessions.)  I will freely admit that I was 1 minute late to one of the talks I was introducing.  (We found lunch too far away.)  People were very nice about it, probably because I showed up quite sweaty.  

You're likely here to read my summaries of talks, though.  Enough delaying, here they are:

Francesca Yu: "Structure-Biased Maker-Breaker Games"

Francesca talked about maker-breaker games on complete graphs where both players choose unclaimed edges and the Maker is trying to create some kind of structure (e.g. a triangle).  In these games, however, the Breaker gets to claim b edges per turn instead of just one.  The threshold bias for a given game is the lowest possible b such that the Breaker still wins.  Francesca looked at a cool variant of this: the Breaker instead has to claim a specific structure in the graph instead of just any b edges.  She found bounds for the threshold sizes for structures of stars and disjoint edges when the Maker is trying to build a triangle.  A lot of these thresholds are in O(n).  It is very worth mentioning that Francesca just graduated with her bachelor's degree!

 

Caroline Cashman: "Black Hole Zeckendorf Games"

Caroline reminded us that any positive integer can be written as the sum of non-adjacent Fibonacci numbers, known as the Zeckendorf representation.  She then talked about the Zeckendorf game on weighted sums of Fibonacci numbers where moves include changing the representation via some small adjustments.  Each of these moves changes the weighted sum towards the Zeckendorf decomposition, so that the player that finally moves to the correct representation wins.  She looked at a "Black Hole" variant so that terms for the fourth fibonacci number (3) and above just fall off, meaning each state can be written as a triple (a, b, c).  She showed that (a, 0, 0) is always a P position and that (1, 0, c) is in P when c is not equal to 3.  She had other such classifications as well.  It is very worth mentioning here that Caroline is a rising senior in college!  

Alfie Davies: "Comparisons in the Misère Blocking Universe"

Alfie talked about the misère play convention and the definition of the <= operator.  He did a really good job of explaining the difficulties of misère analysis as compared to normal play using Aaron Siegel's recent work on the numbers of unique values.  He explained the idea behind Thane Plambeck's work on restricting to specific universes.  he gave the definition of universes and talked about how only finite steps are needed to prove their feasibility in many cases.  He then explained the details of those tests in the blocking universe.  He really did an excellent job of explaining the important parts to the audience of mostly number theorists.

 

What a great day of talks!  I'm especially impressed by these two undergrads for their excellent work.  I hope they continue to do work in combinatorial games! 

I don't expect there will be other CGT talks here, but if I'm wrong, I'll post again!

Sprouts2025 Wrap-up

Sprouts 2025 was a big one for us!  We broke a lot of records:

• Most talks: 13
• Most student talks: 11
• Most submitted computer players: 6  (The previous record was 2!)
• Most participants in the human tournament: 16

Other exciting things that happened:

• The computer player tournament was a real competition this year!  All six submitted players seemed better than the Gorgons players that came in last year.  You can try playing against them!  (I can say that about the Gorgons players because both people submitted better players this year.)
• Ian Grenville won the computer tournament again!  Efforts to dethrone him may be the big story next year.  
• Hiyu and Kouta participated in the entire conference, despite it running until 6am in Japan!  (I feel guilty, so I want to reiterate: it's okay for people to not attend the entire thing... especially to get sleep!)
  
• Hiyu won the human tournament and then beat HotShot to win the John Henry match.  

Things out of our control that went well:

• The student presentations were great!  I think I understood the main point of all of them.  There were a lot of really cool results!
• Everyone was very pleasant during the human tournament.  There was often a strong bias towards one player in the starting positions, but people took it in stride. 
  
• All presenters stuck to the timeline and everything ran smoothly. 
  
• The conversations during the computer tournament were great.  People were really curious and chatting about how each of the players worked.  
  

Things we had some control over:

• We had the John Henry match set up ahead of time with all the possible winners of the computer tournament so that we could run that right away.  (We didn't do it last year.)
• I used a script to organize the abstracts and talk schedule on the site which helped me keep on top of that.
• We were continuing to register people for the conference through the morning session.  (I think we might need to automate some of that in future years.)  I might consider this annoying, except that I was so excited that people kept wanting to join in.

The biggest negative unexpected thing that happened is that we went until 5pm because the human tournament ran longer than expected.  I think the human tournament ended at 4:15 instead of 3:45.  The computer tournament had four rounds, so I think that and the John Henry match ended at about 4:45.  Nevertheless, a bunch of people stayed around for the "End with Friends" until 5pm.  We closed the zoom down at 5:10.

I am so excited about how much of a success this was this year.  I hope everyone had a great time and that Sprouts continues to be this great!

Sprouts 2025 Keynote and Afternoon Session Summaries

Yesterday was Sprouts 2025.  In the afternoon session, we had our keynote by Matt Ferland of Dickinson College and six student talks.  Here are my (likely lacking) summaries of those talks.

 

Matt Ferland, Keynote: "Supernim is Much Harder than Nim"

Matt covered the Nim basics, then talked about superstars: games where all options are to nimbers.  Supernim is, then, the ruleset of any sums of superstars.  Matt talked about reductions to help relate computational problems.  (He described this using curing cancer to show the potential impossibility of solving hard problems.)  Matt covered NP and 3-SAT, then looked for a relationship from those to Supernim.  Unfortunately, an attempt at XORSAT did not yield a reduction.  Matt then described MXOR: Multi-state XOR, where variables can have one of many values instead of just boolean.  Then the literals each indicate for which of those assigned values they will evaluate to true.  Matt showed that MXOR is NP-hard, then showed the subset of Supernim positions and the reduction of MXOR to Supernim.

 

Nakul Srikanth: "GamesmanROS - A Generalized Game Playing Robotics Software Stack"

Nakul talked about his work with GamesCrafters, a long term (25+ years) project run by Dan Garcia at UC Berkeley.  Nakul's contribution has been to incorporate robotics into their automated players.  He talked about the physical constraints they deal with in general and then for specific rulesets.  He showed how the robots use string representations of positions to perform some of the logic.  Different types of games (Placement vs Capture) present different problems that they need to overcome.  He showed a great demo of it in action!

 

Jake Andersen & Cam Jefferys: "Developing Online Martian Chess"

Jake and Cam talked about creating a playable JavaScript Martian Chess program.  They described Martian Chess, a scoring game where control of the pieces changed hand depending on which side of the board they're on.  They showed the rules using screenshots, then did a quick demo.  They talked about how they trained a neural net player by reimplementing the game in python, then ported the model back to JavaScript.  They gave a high-level description of how the player model works.

 

Ethan Saunders: "Paintbucket and Paintbucket on Graphs"

Ethan talked about a partizan flood-fill game called Paintbucket.  The game started from being played among Dalhousie students using MSPaint.  Each turn you use the flood fill tool on a black-and-white image to change one contiguous color of your opponent's to your own.  He then talked about the generalization on graphs.  He was able to show that this version is PSPACE-complete.  One cool part about this presentation is that he used MSPaint to give the talk!

 

Caleb Aukeman: "Partial Jenga"

Caleb continued research from a previous study of Jenga by looking at a partizan version where the blocks are colored Blue and Red.  He talked about conditions for when layers are unplayable based on which blocks are missing.  He also categorized levels based on which blocks were red and blue.  (He had great graphics in his talk!)  He found switches with heat of 1/2 and showed families of positions that are in P.

 

Brendan Whitmire: "Gomoku in JavaScript"

Brendan talked about his JavaScript implementation of Gomoku.  He showed that he added the Pie Rule to his program, which took some tricky coding in the JS framework he is working with.  He talked about the AI "Evolved Player" he's creating.  He generated it by pitting the players against each other using an evolutionary learning algorithm using the Python NEAT library.

 

Brenden Gray: "Cops and a Destructive Robber"

Brenden talked about his work on a pursuit-evasion game on graphs.  His is a variant of Cops and Robbers where the Robber damages the vertex they start their turn on.  The cop's goal is to minimize the number of damaged vertices, with a secondary goal of capturing the robber.  (Damaged vertices do not prevent movement by either player.)  This can change the strategy from the original version because the cop may be content to not capture the robber if it will drop the amount of damage.  He showed a graph where the cop's best strategy is to stand still.