Monday, January 23, 2023

CGTC IV Talks, Day 1

Woohoo!  We're back in Portugal for CGTC!  This is my first time at an in-person Combinatorial Games conference since COVID started, and also my first time on the Azores.  It is great to see so many colleagues and friends and I've learned a lot already on the first day!  

Let's get down to the summaries!

Opening Ceremony

We had a wonderful intro from Expolab (the facility we're at), the Science Director of the Azores, the University of the Azores, the Lagoa Mayor's office, and Ludus (of course). 

Aaron Siegel: "Horizons in Combinatorial Game Theory"

Aaron gave a high-level survey of three different topics: Temperature Theory, Misere Partizan games, and Computational Octal games.  For the first, he explained that we know how to evaluate single Ko situations in Go, but the theory remains incomplete for more complicated situations.  

For the second, he mentioned that the oldest unsolved problem in Misere Play is probably Dawson's Chess from 1935.  For partizan positions, Aaron rephrased G >= H in a way that extends to Misere (and beyond) with the language of absolute universes.  There are a lot of questions coming from that point.  

With Octal games, Aaron noted that the longest known period for values used to increase about every 10 years, until 2002, and it hasn't increased yet.  Aaron wrote some code to search for periods in octal games and recommended a distributed search among the community to find a new record.  Bonus: we would simultaneously be exploring the an open question from the 50s: Do all finite-length octal code games have a finite period?


Alda Carvalho: "<<All is number?>> Not so fast, Mr. Pythagoreas..."

Joint work with: Melissa Huggan, Richard J. Nowakowski, Carlos Pereira dos Santos

Alda gave a Konane example showing numbers as part of a sum.  Then she proved some requirements sufficient to showing ruleset that contains only numbers.  These are properties of pairs of positions known as "F-loss" and "descending".  Then she showed how to apply this to Partizan (Blue-Red) Chomp to show that all grid positions are numbers.  Then she did the same for Push, Shove, Blue-Red Hackenbush, and Cutcake.  Furthermore, she proved that if only the descending property is used in the proof, the values are not just numbers but integers!  

I'm excited to see what rulesets this can be applied to in the future.  As Alda pointed out, this is also an extremely useful pedagogical tool!


Paul Ellis: "The Arithmetic-Periodicity of CUT for C= {1, 2c}"

Joint work with: Thotsaporn Thanatipanonda  (Edit note: fixed name misspelling.  I'm sorry!)

CUT is a class of rulesets parameterized by a cut set C.  A turn consists of splitting a pile of n tokens into d+1 piles, where d is in C.  Paul found arithmetic periodicities for all sets of the form {1,2c}.  This is a very fast update on earlier results, as the game was initially defined in 2020.  Paul's group found some correspondences between sequences in shifted values of C (e.g. {1,6} and {1,8}).  Using this they were able to expand {1,6} to any {1,2c}.  Despite this, there are still many unsolved families of CUT sets out there!


Koki Suetsusu: "Some New Universal Partisan Rulesets"

Universal rulesets are those which contain positions for any short game value, as was previously shown for Generalized Konane.  Koki found three new rulesets with this property!  In Turning Tiles, there is a grid of tiles: Red, Blue, and Black with a token on one of the black tiles.  A turn consists of moving the token across neighboring tiles in one (cardinal) direction of your color and flipping all those tiles to black.  Koki showed his construction to get all the values.  

Beyond the Door is his second-such ruleset, also played on a grid with a token, where the token can move as many spaces as desired in one direction.  Here, the edges connecting spaces are modeled as doors which are colored on each side (the sides can be different colors).  Players can only move the token through doors that are their color on the side the token moves from.  As with the prior game, vertices cannot be revisited.  To show this is all universal, Koki showed a reduction from Turning Tiles.

Finally, Koki presented Go on Lattice, which is another grid graph game with a token and vertices that cannot be revisited.  In this one, the edges are only a single color or dotted.  Dotted edges become the color of the opposite player when a player moves the token to either incident vertex.  Koki again showed a reduction to this game from the others to show universality.  The nice part of that is that he then showed the PSPACE-completeness of Turning Tiles, co-oping the reductions to provide the same complexity for the others as well!


Carlos Pereira dos Santos: "Chess and Combinatorial Game Theory"

Carlos commented that CGT isn't normally great for Chess, because it's too universal and games don't break down well.  He first talked about prior connections between CGT and Chess, then showed ups and integers using a historic Chess zugzwang endgame as a component to build further positions.  Then he showed how to create a 1/2.  He followed that up by showing how to create a complicated position with three rooks that necessitates understanding how to derive 1/2 + 1/2 = 1 in order to find the White player's winning move!  


Bernhard von Stengel: "Zero-Sum Games and Linear Programming Duality"

Bernhard used LP duality and classical game theory notions in zero-sum games, using mixed strategies with simultaneous moves.  This leads to the equivalence of min-max and max-min strategies using a linear program.  It turns out that the reverse direction also works using skew-symmetric payoff matrices proposed by Dantzig in 1951.  Bernhard peeled apart what would happen if you ignored an extra assumption in that direction of the "equivalence", and then showed that you can still complete the proof, so now minimax really does imply the LP duality!


Bojan Bašić: "A Twist on the Classical Prisoners-in-a-Line Hat-Guessing Game"

Joint work with: Vlado Uljarević

Bojan described an Olympiad problem from Russia in 1997: if some sages have to guess the color of the hat on each of their heads, and they can only look at the other sages in the line ahead of them, how many of them can be correct?  What is the best algorithm for them if they can agree on conventions ahead of time?  The working solution allows all of them them to guess correctly except for the first one (in the back of the line) using a little bit of binary arithmetic.  

Bojan's twist allows them to turn side to side to see all hats in the line, but doesn't allow them to communicate as much info: they say "yes or no" to the question of whether they want to guess their hat's color (saying "no" is still a failed guess) but then they have to whisper the actual guess to the inquisitor so that part can't be used in information sharing with the others.  However, everyone does hear whether they were correct in their guess.  When c (the number of colors) is 4, Bojan showed that all but the first two sages can guess correctly by encoding the bitwise XOR sum.  

Bojan then showed that this is actually true for c=5 by using the results of the first two guesses as additional information.  He then looked at trying to figure out the maximum number of colors that can be figured out for any amount of wrong-guessing sages (in the beginning).  For 3, the maximum number of colors they can handle is between 12 and 14.


Hironori Kiya: "Normal-Play with Dead-End-Winning Convention"

Joint work with: Koki Suetsugu

Hironori added a convention where Left wins if Right can't play (Normal) or if every subgame of the current position is a Left-End (Misere-ish).  This comes from Shichinarabe, which is a popular card game in Japan.  (It has some similarities to Rummikub.)  You win that game by either playing out your entire hand (a Left-end) or if your opponent cannot play, which explains the change from basic Normal Play.

It's a very interesting combination because it mixes the Normal and Misere rules in a way that makes sense for the many actual play-out games that exist (e.g. Uno).  Hironori also showed how to find outcome classes under this play style.


Silvia Heubach: "How to Win in Slow Exact k-Nim"

Joint work with Matthieu Dufour

In Slow Exact k-Nim, each play consists of taking exactly one token from k of the existing piles.  Silvia showed how to win when k = n (the number of piles) - 1.  Her proofs require a number of cases that use reduced pile combinations to categorize things.  (Hilariously--to me anyways--this uses a "No stack Is Really Big" condition, which she shortened to NIRB, pronounced "Nerb".) 

The breakdowns of P-positions often look like well-structured, triangular regions of the 2-d space of values.  Each of these triangles either took the form of a checkerboard of P/N positions or a solid block of P or N.


Keito Tanemura: "Chocolate Games with a Pass and an Application to Symbolic Regression to These Games"

Joint work with: Yuji Sasaki, Hikaru Manabe, Yuki Tokuni, and Ryohei Miyadera

Keito (an undergrad in Japan!) talked about a version of Chomp where you make a single cut, vertical or horizontal, instead of removing the grid-poset from a chosen square of chocolate.  Keito then talked about what happens when you go to three dimensions.  This is all equivalent to easy Nim games, so he talked about what happens when the initial 3-d position is not rectangular, but staircase-shaped instead.  Keito's team then used symbolic regression (genetic programming) to discover formulas for the P-positions in the game.  Then they were able to do the same for other nimbers. (1 and 2)  They used their own library of functions and discovered formulas that gplearn failed to find.


What a great day!  I'm really looking forward to tomorrow!

2 comments: