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". :)