CGTC3 Talks: Day Three

More great talks on the final day of CGTC3!  Here are my summaries.


Tomoaki Abuku: "On Nim-like Games Played on Graphs"

Tomoaki investigated NimG with heaps on the edges.  Fukuyama proved a bunch of results about these in 2003.  Tomoaki's team used groups of independent zero-sum-valued vertices to find new results, including for many bipartite graphs.


Svenja Huntemann: "Enumerating Domineering"

Svenja build off work by Oh and Lee that counted independent sets on grids (accidentally) counting Kayles positions--as well as Col.  By considering each square as falling into one of five categories, Svenja and her team found a formula for the number of positions on an m x n board.  Even more complicated is enumerating the maximal positions--in order to build the polynomials, 3x3 matrices are needed instead of 2x2.


Valentin Gledel: "Maker-Breaker Domination Number"

Valentin and his team extended previous work on the Maker-Breaker Domination game.  In the game, the Dominator tries to build a dominating set while the Staller chooses vertices to exclude.  This new work investigates the number of moves the Dominator needs to win; a pair with each case of each player going first.  They found graphs that work for any pair of numbers!


Ravi Kant Rai: "Optimal Play in Duidoku Game"

Ravi found Duidoku--a two-player game based on Sudoku that I had been playing back in 2011 (though under another name).  Ravi found a set of permutation strategies for the second player to never lose (so either win or draw) from the initial position.  Ravi generalizes this to grids of any size, showing that Player two has the advantage exactly when n is even.


Hironori Kiya: "Two Player Tanhinmin and its Extension"

Kiya introduces Tanhinmin as a combinatorial version of a Japanese card game, Daihinmin.  In this game, players play increasing cards (or pass) until one player has emptied their hand (they then win).  Kiya's team found a linear-time algorithm to determine winnability (assuming the cards are already in sorted order).  Kiya extended this to show that it also works when you add in the 8-cut rule from Daihinmin.


Matt Ferland: "Computational Properties of Slimetrail"

Matt presented work he completed with me while an undergraduate at Plymouth State!  Slimetrail is one of the games used by Ludus in their tournaments all across Portugal.  Matt proved that a generalized version (on graphs) is PSPACE-complete.  Matt showed the gadgets in the reduction from QBF.

CGTC3 Talks: Day Two

The second day of talks at CGTC3 were also excellent!  Here are short summaries.


Yuki Irie: "p-Saturations of Welter's Game and the Irreducible Representations of Symmetric Groups"

Yuki confirmed a long-standing conjecture by Mikio Sato (from the 70's!) stating that Welter's Game is related to the representations of groups.  Yuki made the connection by generalizing Welter's game using p-Saturations.  In these versions, the nimber values can be found via a formula using addition without carry in base p and Young diagrams!


Thane Plambeck: "Shotgun Wedding: EGT & CGT"

Thane showed a new potential method for combining EGT and CGT.  In this, he considers some repeatable economic game where players have a set of options to choose from each round.  The application of CGT comes from adding an alternating-turn game to generate those option sets.  Thane's method of choosing includes switches, creating a first-mover advantage situation.


Alda Carvalho: "Combinatorics of Jenga"

Alda and her team considered perfect play in Jenga as a combinatorial game.  Each row low enough in the tower (meaning, it has at least one full row above it) acts as a *2 component.  The total value is not just a simple sum, however, because blocks are added to the top, revealing a new *2 pile after every three moves.  Alda generalized this concept as Clock Nim, then found nimbers by considering it as a type of subtraction game.


Koki Suetsugu: "On a Wythoff-type Extension of the General Subtraction Game"

Koki and his team defined a variant of Cyclic Nimhoff ("Restricted Cyclic Nimhoff") where you can only take up to some given q sticks from a pile.  Like Cyclic Nimhoff, they found a closed-form expression to find the nimber.  He then generalized this further by defining separate subtraction-style sets for each of single-heap-removal moves.  In this game, the nimber evaluation uses the Grundy evaluation functions of the corresponding subtraction games whenever the Grundy sequence is a p-stair.


Fionn McInerney: "The Orthogonal Colouring Game"

Fionn and his group have worked on some cool scoring games using two copies of a graph.  Players can color vertices on either copy, but must adhere to an additional orthogonality restraint: the ordered pair of colors for any vertex and its copy cannot be repeated.  Each graph "belongs" to a single player, but they can color in either; the score is determined by the number of vertices that get painted in the game.  Fionn shows that Player 2 can always force a tie when there's a strictly-matched involution, but determining whether the involution exists can be NP-hard.


Urban Larsson: "Cumulative Games"

Urban took a different tack with combining EGT and CGT using subtraction games.  Similar to Candy Nim, you keep track of how many total elements you've subtracted, hoping to collect more than your opponents.  Unlike Candy Nim, you ignore who gets to play last; you're just concerned about the total collected.  In this way, Urban's team was able to connect to extensive form games in EGT.  To generalize this for other combinatorial games, a reward function is needed on the moves, along with an outcome function for n-player games.


Melissa Huggan: "The Index: a Measure of Equality"

Melissa delivered an update on her team's progress on simultaneous games.  A lot has happened since I last saw this in Lyon.  Here a game called Subtraction Squares is used, where players remove a number of squares from a strip.  A removal can be made from either end.  If we play a continued conjuctive sum, then the index, I(G), is a pair, (x, y), where x is the probability Left can win with a good mixed strategy and y is the same for Right.  They can then show that equality of games happens exactly when the indices are the same.

CGTC3 Talks: Day One

It's so exciting to be back in Lisbon for CGTC3.  Especially after missing it two years ago.

The first day (Tuesday, January 22) started off with some great talks.  Here are some very brief summaries.


Richard Nowakowski: "What's happening in CGT (since 2010)"

Richard opened the meeting by speaking about new branches of CGT that have appeared this decade.  His survey included explaining Misere and Scoring play, simultaneous moves, ties, placement games, and more.  It was best summarized by his statement: "What did they [BCG] not think about because they didn't need to?"


Antoine Dailly: "Connected Subtraction Games on Graphs"

Antoine described a new game inspired by subtraction games.  CSG(S) is a game on a graph where you may remove k connected vertices from G where k is in S and the resulting graph is still connected.  His team has shown some nice periodicity results when appending paths to an initial graph.


Mike Fisher: "Beatty Games Big and Small"

Mike explained Beatty sequences, then talked about some new Beatty-based games, including two partizan subtraction games, octal games, and even infinite octal games.  The talk name is from these subtraction games: big values occur if the subtraction sets are exactly the Beatty sequences and small values happen if you include 1 to both sets.


Carlos Pereira dos Santos: "Extended CGT"

Carlos considers adding infinity and negative infinity to the set of game options as terminal moves: infinity is an automatic win for left (and vice versa), no matter what else is going on in other parts of a game sum.  (He motivated this by Atari Go.)  He calls these types of game Race Games.


Marc Heinrich: "Partizan Subtraction Games"

Marc and his team made nice progress on partizan subtraction games.  I did not know that outcome classes are periodic here, though values are not always!  Marc showed that the sizes of the sets can be much less important that the size of the numbers in the set.


Bernhard von Stengel: "Computational Progress on the Catch-Up Game"

Bernhard described Catch-Up, a kind of scoring game that doesn't use alternating play; instead, whomever has the LOWER score gets to take the next turn.  Bernhard showed a really cool method he found to solve this for big games, using the representation of prior choices as a binary address for the table of values being generated.