Thursday, January 24, 2019

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.

Tuesday, January 22, 2019

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.

Sunday, March 11, 2018

Sprouts 2018 Announcement

Sprouts 2018 is happening Friday April 13 and Saturday April 14 at Plymouth State!  Sprouts is a combinatorial games conference for undergraduate research.

Here's the conference page, complete with directions, a draft of the schedule, and other notes: http://turing.plymouth.edu/~kgb1013/sprouts/sprouts2018/

Craig is bringing his contingent from University of New England, and it looks like we're going to have a bunch of Tafl talks!

I'm going to try to put together a computer tournament so attendees can submit a player.  If possible, I'm going to reuse my code from Data Structures.  We'll see how far along I get in that process.

Saturday, January 6, 2018

Graphs and Games Workshop, Day 3 Talks

Games and Graphs Workshop in Lyon had three days of great talks.  Here are my short summaries of the third day.


Richard Nowakowski's Tutorial: "Introduction to the Theory of Scoring Games"

Richard gave a great tutorial introduction to to scoring games.  There are a lot of issues here I wasn't aware of, including really painful Zugzwangs. ("Anti-Switches"?)  E.g: {Final Score: -1 | Final Score: +1}  How does this happen?

Consider an Independent Set game played on a cube added to another already-finished game with a score of -3.  In the IS game, players choose independent vertices and Left scores a point for the total size of the set.  Now, if Left is forced to go first on the cube, Right can choose the opposite vertex, ending the game with a score of 2 (and a total score of -1).  If Right goes first, Left can choose another vertex that shares a face with the first.  This will force the score to be 4, for a total of +1.

Richard went on to describe many other properties that scoring games can have.  He also polled us about whether we should even allow some types of outcomes and games.


Koki Suetsugu: "Normal and Misere play of Multiplayer Games with Preference

Koki looked at what happens in more-than-two-player games when the players have a preference on who they would like to win.  He described a result using generalized Nim Sums that I was not aware of.  Koki has extended this to misere play by shifting the preference lists any number of spaces to mimic a misere situation.  With this, he uses the generalized Nim Sum to solve the game.


Paul Dorbec: "Quantum Nim"

Paul looked at what happens when instead of making a single move in Nim, you make a superposition of two different moves.  He points out that it's important to specify the number of sticks you're taking--not the number you're leaving--in each of the submoves.  Since some moves may be no longer legal on some parts of the superposition, there are five different versions of the ruleset concerning the allowance of classical moves.  (E.g. unsupervised moves are allowed only if they're valid in all of the parts of the current superposition, etc.)


Melissa Huggan: "What Happens When Players Move Simultaneously in a Combinatorial Game?"

Melissa is really pushing at the border of CGT and Classical (Economic) Game Theory (EGT?).  She wants to let both players take their turn simultaneously and wrap new theory around it.  For her examples, she used Hackenbush where the resulting move is the intersection of the two chosen options  She then defines the outcome classes of terminal positions based on which player has moves left:

  • Draw: no moves for either player
  • Positive: Left still has a move
  • Negative: Right still has a move
Perhaps unsurprisingly, many of the ideas from Classical GT arise as a result of Melissa's ideas, including matrices, expected values, and the benefits of mixed strategies.


Adam Atkinson: "Medieval French Poetry"

This is the only talk that had multiple people climbing to the front of the room to get a better look at all the poems that Adam brought with him.  Adam claimed to have brought some old poems that had been rediscovered in 1950, but that was a bit of a ruse.  I don't want to fully explain what happened here because I don't want to blow his cover on the chance he's giving a similar talk in any other venue.  Nevertheless, maybe we could write some poetry about combinatorial games... but not in English.


Wai Lim (William) Fong: "The Edge-Coloring Game on Trees Played with One More Color"

As I learned at this workshop, there are some really weird and interesting results in the world of Maker-Breaker games.  For example, in the edge-coloring game, adding more colors doesn't necessarily help Alice win on graphs.  Specifically, exactly one more than the minimum needed to ensure Alice has a winning strategy can actually cause her to lose!  William worked on the tree case and showed that if the max degree of the tree is 4, and Alice can win with 4 colors, then she can also win with 5.  (6+ colors is already known to be a win for her.)  William shows this by constructing Alice's winning strategy!


Urban Larsson: "Playful Game Comparison and Absolute CGT"

Urban and team are looking at other extensions using Absolute CGT.  Here he uses an abelian group, called "adorns", of values to assign to terminal positions.  This really opens the doors to many rulesets outside of the Winning Ways spectrum.  He explains that universes of games are absolute if they are dense and parental.  "Normal play is more absolute," he explained.  In any absolute universe, comparisons work exactly as you'd want.


Khaled Mama: "Computing the Shapely Values of Graph Games with Restricted Coalitions"

The Shapely value of a coalition describes how much each actor contributes to the coalition.  Khaled & team looked at this in an interesting way: what if some coalitions are impossible due to communication barriers?  Given some constraints, Khaled can compute these new values using chains across the lattice of coalition chains.  To get working games for this, he's focused on some cool graph games. 


I learned a ton as a result of these talks!  I met a lot of new people that I hope I get to see again.  I'm also very interested in everything I learned about Maker-Breaker games.  I did not realize there was so much being done on this.  Which Maker-Breaker games should I add first to the ruleset table-page?

Friday, January 5, 2018

Graphs and Games Workshop, Day 2 Talks

Day 2 of the Graphs and Games Workshop continued a wonderful conference with more great talks!


Rebecca Milley's tutorial: "Progress and Problems in Misère Play"

Rebecca's excellent talk finally convinced me that I could understand this backwards world.  Although there isn't all the nice group structure, she showed how to use dicot and dead-end universes to reclaim some nice operations (e.g. invertibility, comparisons, and reductions).  It was especially helpful when she explained that Domineering, Hackenbush, NoGo, Snort, and Col are all dead-ending.

More recently, she's applied Absolute Game Theory to get even deeper with dicots and dead ends, including a version of comparisons ("subordinate") and reversibility through ends.


Fionn McInerney: "Spy Games on Graphs"

Fionn showed a cops and robbers variant knows as the spy game.  In this game, first a spy is placed on a vertex, then the guards are placed.  The spy then moves up to their speed, s.  After, the guards can each move up to one space.  (It's okay for the guards and spy to co-locate a vertex.)  The spy wins if they can escape from the guards on any turn by being at least d+1 distance from all guards.  The guards win if they can always prevent this.

Cool complexity connection: It's NP-hard to determine the minimum number of guards needed for their team to win.


Tomoaki Abuku: "Ryuo Nim: a Variant of Wythoff's Nim"

Tomoaki presented a nice variant of Wythoff's Nom, motivated by Shogi.  If we consider the piece to move as Shogi's Ryuo, instead of a Chess Queen, then we get a new game.  (Ryuo can move as a Rook (Hisya) or as a King.)

Tomoaki found a bunch of Grundy values for game positions and considered many variants.


Gabrielle Paris: "Pre-Grundy Games"

Gabrielle showed an extension to Grundy's Game: given a heap of n tokens, a move consists of splitting it into two different-sized heaps.  Gabrielle's Pre-Grundy games allow multiple cuts on one turn: any number in a given set L.  Her team has focused on lots of results here, including:

  • If L does not contain 1, then the Grundy values are arithmetic-periodic, and
  • If 1 is in L, L has at least two elements, and everything in L is odd, then the Grundy values are periodic!

Lior Goldberg: "Rulesets for Beatty Games"

Lior investigated a problem from 2010 where rulesets were discovered for any Beatty game given by (alpha, beta) where 1 < alpha < 2 and 1/alpha + 1/beta = 1.  The problem is that the rulesets were also very complicated.  Lior has found a nice ruleset for Beatty games where alpha < 1.5 and alpha >= 1.5.  Unfortunately, there are some examples where the ruleset must explicitly reference alpha.  He also showed how to get some specific rulesets that look like t-Wythoff generalizations.


Valentin Gledel: "Maker-Breaker Domination Game"

Valentin introduced a new Maker-Breaker version of a dominating set game.  Each player choose an unchosen vertex.  The Dominator (player) adds them to a potential dominating set (a set of vertices that contains and are neighbors to all vertices).  The Staller (player) chooses nodes to remove as options of the Dominator.  The Dominator wins if the final set dominates the entire graph.  Valentin and his team showed that there are only three outcome classes (N - Fuzzy, D - Dominator wins, S - Staller wins) and showed what happens for all disjoint unions and joins.  He showed that it's easy to decide on cographs and trees, but PSPACE-complete in general.


Clement Charpentier: "Nordhaus-Gaddum Inequalities for Coloring Games"

Clement and team investigated the Maker-Breaker Graph Coloring Game: Alice (Maker) and Bob (Breaker) take turns coloring vertices from one of k colors, following the regular graph coloring rules.  If, in the end, all vertices are colored, then Alice wins.  Otherwise, Bob wins.  

The Nordhaus-Gaddum inequality is about the chromatic number of a graph.  Clement applied these to help determine strategies for Alice.  Clement used this to create new inequalities describing when Alice can win!


Stephan Dominique Andres: "Characterizations of Game-perfect Graphs and Digraphs"

Dominique found a bunch of variants of the Graph-Coloring game by varying:
  • Who goes first (Alice or Bob)
  • Whether Alice or Bob (not both) can pass, and
  • Whether missing a turn is allowed.
Then, for any variant, he and his team define a nice property: a graph is "game-perfect" for one variant exactly if the game-chromatic number equals the size of the largest clique.  They have lots of results for the different variants!  This talk was the first I've seen that used the word "perfectness". :)






Thursday, October 26, 2017

Games and Graphs Workshop, Day 1 Talks

The Games and Graphs Workshop in Lyon was outstanding!  There were so many talks, but I think I understood at least the basics of most of them.  The first talks were on Monday.


Aviezri Fraenkel: "Problems and Results in Combinatorial Games and Combinatorics"

Aviezri presented a talk about games with some elements of (Economic) Game Theory (EGT).  For example, he considered playing Geography on a binary tree where all terminal nodes are after Alice's turn, except for a great many on the lowest level.  At each level, Alice has one instantly-winning move, but what if there are many other moves and Alice can't differentiate between them? Now she is essentially choosing at random because of some hidden information.  With enough of these extra edges, she is not going to be able to win the game, despite having a winning option each turn.

Aviezri showed many other connections to EGT and called for future work on infinite games in the partizan, scoring, and misere realms.


Craig Tennenhouse: "Three Graph Games"

Craig presented three new games: Tumbleweeds, Deletion/Contraction, and Total Conversion.  Tumbleweeds is a cool variant of Hackenbush without a static root.  Instead, whenever a player chooses an edge that breaks the graph up into multiple connected components, that player chooses either of the components to completely discard!

The partizan game Deletion/Contraction is played on a multigraph (but no loops).  The Left player moves by deleting an edge on their turn, while the Right player chooses an edge to contract (removing any loops that are created).

In Total Conversion, the position is a graph with a non-zero game embedded into each edge and each vertex colored either Red or Blue.  To take a turn, the player must make a move on each game where the edge has ends colored in opposing colors.  Edges with exactly 0 are then removed and both vertices are subsequently repainted with that player's color.

Craig already drew attention with these games and, as always, I suspect he has about three new projects as a result of the conference.


Loic Cellier: "The Game of Hex"

It always seems like there are new things to learn about Hex.  Loic presented just about everything I knew and lots that I didn't.  He covered the history---I did not know that Einstein was a supporter of the game!---the connection to Y, and even presented a variant of the Pie Rule, the Swap Rule:  Here, instead of swapping the identity of the players (if Player 2 wants), instead just swap the color of the piece on the board.  This is, of course, not always equivalent; it prevents the first player from playing in a position that would be too good for their opponent as well.

I also (finally) learned why a Y game must end, by the self-reduction of each vertex into a hex on a slightly-smaller board.  This is surprisingly elegant and easy to explain, but with that little twist that makes it amazing.  It may be more likely to be in The Book than the Hex Theorem (that no Hex game can end in a tie.


Milos Stojakovic: "Maker-Breaker Games Played on Random Graphs"

Milos talked about Positional Games: maker-breaker games on a finite set of elements, X, where F, the winning set, is a subset of the power set of X.  The players alternate turns claiming one element of X.  Maker then wins if they claim all the elements in some set in F; Breaker wins otherwise.  Milos paid special attention games where X is the set of edges in a complete graph.

Unfortunately, for many common sets F (e.g. set of Triangles) it is too easy for Maker to win.  To balance things out, he considers adding biases for each player to change the frequency of turns.  (E.g. Maker takes 3 turns, then Breaker takes 7.)  The idea he took off with was to begin the game by removing a number of random edges.  If each edge remains with probability p, how low does p have to be before Breaker can (usually) win?  He calls this the Threshold Probability, and looked in to determining this value.


Mirjana Mikalacki: "Fast Winning in Positional Games on Graphs"

Mirjana is also interested in positional games, but is looking for other ways to give Breaker a chance to win.  Instead of removing some edges, she considers a "fast" variant where Maker only gets to make a certain number of moves before the game ends in Breaker's favor.  (Breaker still gets to move as normal too.)

Mirjana also combined this with the biases mentioned above.  These "combination" fast games generalize positional games significantly.