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.