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.


  1. Y generalized to any even-numbered dimension using micro-reduction, as requested:

    First, let's restate the game of Y in 2d in more abstract terms. Imagine the board as an upward-pointing triangle of hexagonal cells. Label the topmost cell with the coordinates (0,0). Now label the two adjacent cells below it (1,0) and (0,1). Continue labeling all the cells such that for any cell (x,y) the one to the lower-left of it is (x+1,y) and the one to the lower-right (x, y+1).

    Now, to perform micro-reduction on a filled board of size n, on a new board of size n-1 color in cell (x,y) with the majority color of cells (x,y), (x+1,y), and (x,y+1) on the filled board. Do that for every cell except the very last row to end up with a filled board of size n-1. Repeat the process to end up with a size 1 board with a cell of the winning color.

    Using micro-reduction as a defining feature of Y, we can extend the game to be played on a simplex of any even-numbered dimension. Using ordered n-tuples, label the "topmost" cell as all 0s, and each cell under it as +1 in a single element. For example, in four dimensions, the topmost cell would be (0,0,0,0) and the cells adjacent to it "below" would be (1,0,0,0), (0,1,0,0), (0,0,1,0), and (0,0,0,1). Note that one can easily check if cells are adjacent if their coordinates differ from another by +1 or -1 in a single element, or differ by +1 and -1 in exactly two different elements.

    To perform micro-reduction in this generalization, simply take the majority color of a cell and its children (in other words, the majority color of the set containing a cell and the cells one gets by adding 1 to each element in its n-tuple) and put that color in the corresponding cell of a board of one smaller. In even dimensions, there will be an odd number of cells in each of these sets, so a majority color will unambiguously be chosen. Just like with 2d Y, repeat this step with every smaller board until you get a board of size 1 with a single, winning, color.

    Unfortunately, I have no idea how to visualize what a winning state would look like on a large board in such dimensions (other than 2, of course), but I assume it still connects facets of the polytope in some way.

    I originally posted this discovery in a much altered form on the BoardGameGeek Abstracts forum:

  2. I am definitely enjoying your website. You definitely have some great insight and great stories

    aliza sheikh