CGTC IV Talks, Day 3

The last round of talks just happened!  They were great again!  Here are my summaries.

Dana Ernst: "Impartial Geodetic Convexity Achievement and Avoidance Games on Graphs"

Joint work with: B. Benesh, M. Meyer, S. Salmon, and N. Sieben.  Dana, who also spent time teaching at Plymouth State University, talked about impartial games on graph subsets that contain all shortest paths between vertices in the subset.  The games deal with alternating adding vertices to a set and either avoiding a set that "generates" the entire graph if you include all shortest paths between those vertices, or try to create such a set.  Dana talked about some instances where the initial positions are 0 or *, including both games played on trees, cycles, and hypergraphs.  His team did find initial positions with values up through *7.  In addition, they looked at the opposite games, where you remove vertices and avoid/seek the termination of the generating set.

Colin Wright: "MathsJam and Mastodon"

Colin advertised both for MathsJam, which is a meeting series I've never been to, and the Mastodon server Mathstodon.xyz, which is where I joined a few months ago.  (You can follow me there: https://mathstodon.xyz/@CGTKyle) 

Mark Mitton: "Random Thoughts: Nim is a Hustle"

Mark delivered his perspectives on academia and CGT as a magician.  (E.g. he learned Nim as a swindling tactic.)  He reminded us it's important to listen to the non-logical parts of our brains because truth is not equal to reason.  I took this to mean that we need to not only research our games, but also actually play them as a part of our craft.

Antoine Dailly: "Subtraction Games on Graphs"

(Updated the list!) This presentation covers a bunch of projects with: Laurent Beaudou, K. Burke, Pierre Coupechoux, Éric Duchêne, Sylvain Gravier, Julien Moncel, Nacim Oijid, Aline Parreau, and Éric Sopena.  Antoine was interested in how to change subtraction games into graph games.  They translated removing counters into removing specific connected subgraphs of that many vertices.  Then Antoine's team looked specifically at the case where you're not allowed to disconnect the graph during your turn, naming this the Connected Subtraction Game.  They wanted to have nice sequences of nimbers, so they considered graphs where you connect a path of k vertices to a specific vertex in the graph.  They showed that you still get periodic sequences.  They then showed lots of results for CSG({1,2}) but their techniques don't work for general trees.

Craig Tennenhouse: "Vexing Vexillological Logic"

Joint work with me.  Craig talked about Flag Coloring, which is the game we're using at Sprouts this year. (If you attend, you can play in our human tournament or submit a (Javascript) player for our computer tournament!) In Flag Coloring, you play on an image (or graph) and change a colored region (connected component of one color) by flood-filling it with the color of an adjacent region a la MS paint.  Craig analyzed the outcome classes of various flags, then showed some other results we got on 2-color graphs, including showing that it's PSPACE-complete in general. 

 

Urban Larsson: "Feasible Outcomes of Bidding Combinatorial Games"

Joint work with: Prem Kant, Ravi Rai, Akshay Upasany.  Urban talked about the idea of bidding play in games: before each turn, players blind bid money to decide who takes the next turn.  (Using a Richman auction.)  Ties are broken with an extra marker, which, if used, is passed to the other player.  The winning bid transfers that much money to the bid loser, so there is a static total pool of cash.  Urban's team looked at two different scenarios: when players can choose to include the marker in their bid or not.  They proved (when you can bid with the marker) that there's a perfect strategy for one player under the second model.  Moreover, they get the standard CGT outcome classes as well as extra ones for who has the marker.  They looked specifically at the game with integer bids and a total pool of $0, $1, and $2.

Nándor Sieben: "Impartial Hypergraph Games"

Nándor talked about four new impartial games on hypergraphs where players mark vertices on their turn and the end of the game is triggered by the marking of an entire edge.  To divide this into two games, we first use the avoid/seek dichotomy.  (I heard "achieve" used a lot instead of "seek".)  To divide it again to get four, instead of marking, we use "creation" and "deletion" of vertices on each turn.  This gives us four games similar to what was seen in Dana's talk: "Achieve", "Avoid", "Destroy", and "Preserve".  Nándor notes that for any H, the game DAG for some pairs are complements!  He also showed that PRV(H) = AVD(Transversal(H)) and ACH(H) = DES(Transversal(H)), as well as vice-versa, since the transversal is it's own inverse.  Nándor proved that if two sets are structurally equivalent and their sizes have the same parity, then the positions will have the same nimber.  He also found that there games have an infinite Nim-dimension!

Svenja Huntemann: "Temperature of Partizan ArcKayles Trees"

Joint work with Neil McKay.  Svenja talked about some of the advances she and Neil have been making towards finding the temperatures of Domineering, which is the grid case of Partizan (Red/Blue) ArcKayles (PArcK).  She reminded us about temperature and that Berlekamp conjectured that the max temperature of Domineering is 2.  She explained that the regular sentiment has been that the grid structure was responsible for this apparent bound, but her team has not found anything of higher temperature "off the grid".  Based on their work so far, they boldly conjecture that the temperature of PArcK trees is at most 3/2 and even bolder, that the overall max tempreature is 2.

 

Florian Galliot: "The Maker-Breaker Game on Hypergraphs of Rank 3"

Joint work with Sylvain Gravier and Isabelle Sivignon.  In this game, Florian has players claiming vertices and the condition that triggers the end of the game is the creation of an edge.  Florian's team looked at the case with small edges and which player has a winning strategy.  The rank cases for 1 and 2 have relatively simple polynomial time strategies, so they looked at case 3.  This led to a good notation for the positions, including the notion of a "danger" subgraph, which means a region where the Maker can win if the Breaker doesn't immediately move there.  They showed that this is solvable in polynomial time, by recognizing a set of complex, but recognizable, situations.  The cool thing is that this solves another problem that's been open for a few years!  The computational complexity is still open for ranks 4 and 5. (6 and up is PSPACE-complete.)

Prem Kant: "Bidding Combinatorial Games"

Joint Work: Urban Larsson, Ravi K Rai, Akshay Upasany.  Prem continued the topic from Urban's talk earlier in the day, building off of the idea of bidding for who takes the next turn in each game.  Outcomes of only the game positions can be described as lists of standard outcome classes, with both different quantities of money for Left as well as with and without Left having the tiebreaking token.  Similar to Misere play, Prem's team defines conjugation instead of negatives.  They showed that there's no such game, G, where G + * = 0.  Without the negatives, they still went to see if there could be numbers and found them!  Prim then worked out when numbers are comparable with zero and how to test this property using only 0-bid strategies.

Nacim Oijid: "Bipartite Instances of Influence"

Joint work with Eric Duchene and Aline Parreau.  In the game of Influence, players take vertices from a bipartite graph, scoring points for the size of the immediate neighborhood, all of which get removed.  However, players can only play on their side of the bipartiteness, so it plays a bit like bipartite Snort, except with the scoring in addition.  Nacim's team decided to use Milnor's rules (universe) for scoring, which doesn't worry as much about which player went last.  They are looking for graph families where the analysis is easy, but the simple solutions are elusive.  Nacim is very interested in complexity and showed that determining the winnability is PSPACE-complete.  Moreover, they showed that detecting draw situations is Graph-Isomorphism-Hard!  He talked about computing temperatures in scoring games, including some advances his team has made.  (I really want to learn more about Scoring Play!)  Nacim's team was able to apply these things to help evaluate paths in Influence.

This was a great conference!  (CGTC is "The Conference" for the field, as Richard put it.)  All the talks were great and it was wonderful to see everyone in person for the first time in so long!  Thank you again to the conference organizers and hosts!

CGTC IV Talks, Day 2

 There were great talks again on Day 2! 

Miloš Stojaković: "Strong Avoiding Positional Games"

Joint work with Jelena Stratijev.  Positional games are played on a finite set X where the Winning Sets are given subsets.  Players take turns claiming elements until all are taken.  Then the winner is determined based on different classes of the positional games (e.g. the Strong Maker-Maker condition for Tic-Tac-Toe).  Miloš talked about Strong Avoider-Avoider: the first player who claims an entire Winning Set (now the "losing set") loses.  If no one does, then the game is a draw.

Sim, for example, is played on K_c with triangles as the Winning Sets.  (Ramsey Theory tells us that a draw is not possible.)  It turns out there is a winning strategy for the first player on 3^3 Tic-Tac-Toe!  (The potential name Tic-Tac-No was mentioned.)  No draws are possible here either.

Miloš's team found winning strategies for the second player for different Winning Sets of complete graphs.  The proofs use a lot of cool techniques including strategy stealing!

Daniella Popović: "A New Approach to Equivalence of Games"

Joint work with Nikola Milosavljević and Bojan Bašić.  Daniella began by reminding us of the equivalence of games.  She then presented a new idea: partitioning game DAGs into classes where two positions share a class if they all have options to the same other classes.  This is called "Emulational Equivalence" and is flexible because it does not require knowledge of the play convention (Normal/Misere).  Her team defined Hackenforb: players alternate deleting edges from a graph.  If any component matches a forbidden set of subgraphs, it is also deleted.  

Daniella then showed that Hackenforb and Nim are emulationally equivalent.  They were also able to show equivalence from Hackenforb to Chomp!  More importantly, they showed there are games that cannot be related to Hackenforb in this way!

Michael Fisher: "Olympic Games: Three Impartial Games with Octal Codes"

Joint work with Keith Hazen and Craig Tennenhouse.  Mike reminded us about Wythoff's Nim and Beatty sequences: using irrationals to define partitions on the natural numbers.  He then reminded us about Octal Games, Kayles, Dawson's Chess, and Nim.  Then Mike tied this in to Number Theory and Metallic Means: the Golden Ratio and Silver mean based on Pell Numbers.  Bronze numbers exist as well, so Mike's team made an octal game based on each.  E.g. the Golden Game uses the infinite octal code .1211212112112... (non-repeating!).  The P-positions are at 0 = F1, F3, F5, F7, ...  (the odd elements of the Fibonacci sequence).  The Silver game does the same thing: each index is 1 or 2 depending on which side of the Silver-based Beatty sequences the index lands on.  Mike showed graphs of Grundy values, but these did not reveal any obvious formulas.

Richard J Nowakowski: "The Game of Flipping Coins"

Joint work with Anthony Bonato and Melissa Huggan.  This talk came about from teaching CGT to a non-CGT faculty member.  They tried using Turning Turtles, but then wanted something to include partizan games as well.  To do that they created Flipping Coins.  This game is played on a string of 1s and 0s: Left can change two 1s into 0s (no matter what is between them) and Right can change a 0...1 to 1..0 (yes, the order matters).  Thus, for example, the strings 11 = integer value 1 and 01 = -1.  His group found integers and fractions.  They discovered that Left has a serious advantage, but that all values are numbers.  (That last bit uses the conditions from Alda's talk the previous day!)

It turns out that both players want to play usually at the right-end of the string, meaning it looks like the analysis could be related to ordinal sums.  Richard's team found a complete way to evaluate positions!

Tomoaki Abuku: "A Multiple Hook Removing Game Whose Starting Position is a Rectangular Young Diagram with Unimodal Numbering"

This is Joint Work with Masata Tada.  In this new impartial game, the players play on a Young Diagram and remove one box and the corresponding hook: the boxes directly below and to the right.  Then the remaining boxes are shifted up and to the left.  This is a very interesting Chomp variant!  Tomoaki then described a variant with a unimodal numbering on the boxes.  After a move that removes a hook, the player has to go again if they can remove a book with the same multiset.  This continues until no such matching multiset move exists.  Tomoaki's team found a diagonal expression to classify positions, which they used to calculate many of the nimbers.  Tomoaki described an equivalence to a version with shifted Young Diagrams that helped reduce game sizes.

Kanae Yoshiwatari: "Complexity of Colored Arc Kayles"

Joint work with Tesshu Hanaka, Hironori Kiya, and Hirotaka Ono.  Colored Arc Kayles is the partizan version of Arc Kayles where edges are colored by the player (or green/gray for either) who can play on that edge.  Kanae reminded us about the relationship between Arc Kayles and Cram and Domineering.  Kanae's team showed that Colored Arc Kayles is NP-hard, as well as some parameterized algorithms (still exponential) to solve it that improved on multiple previous results.  Some of the parameters they use include the vertex cover and neighborhood diversity.

Eric Duchêne: "Partizan Subtraction Games"

Joint work with Marc Heinrich, Richard J Nowakowski, and Aline Parreau.  Eric next presented his result on Partizan Subtraction games, which is just like impartial subtraction, but with separate subtraction sets.  Eric's team showed that this game is NP-hard via a clever reduction from Generalized Knapsack.  Then they showed the game is quite easy from some small sets and talked about the different styles of sequences of outcome classes.  They showed that computing the length of the preperiod of the sequence is NP-hard using the Frobenius problem!  Then they looked at the effects of set sizes between the players.

Aline Parreau: "Maker-Breaker Domination Game"

Joint work with: Guillaume Bagan, Eric Duchêne, Valentin Gledel, Tuomo Lehtilä, and Gabriel Renault.  In this game, one player (the Maker) is trying to build a dominating set on the vertices of a graph while the other player tries to prevent that.  Aline pointed out that you can swap the roles by thinking of the Breaker as trying to created closed neighborhoods.  Aline's team showed that the game is PSPACE-complete, even for bipartite and split graphs.  They also showed a property that implies a Maker win, then showed that the property is NP-hard to detect, but not in trees!  Trees are one of few graph families Aline found to be solvable in Polynomial time.  The hardness remains open for interval graphs.  There are really interesting relationships between matchings.

 

Hikaru Manabe: "Four-Dimensional Chocolate Games and Chocolate Games with a Pass Move"

Joint work with Aditi Singh, Yuki Tokuni, and Ryohei Miyadera.  Hikaru is a high-school student in Japan!  He spoke about Chomp games (on chocolate) but also using only horizontal and vertical cuts.  His team looked at staircase functions that result in different board shapes and the nimbers you can get.  Then Hikaru generalized to 3-d and then to 4-d!  His team continued to use stair-shaped functions to grow boards out from the bitter (poison) square.  Then they looked at the relationship with adding a pass move and how that could be modeled by shifting dimensions.

Amazing talks!  Then we had a great conference dinner until way too late.  (That's why these weren't out last night.)  One more day to go!

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!