Monthly Archives: September 2019

Left-Right Hackenbush for Redwood Furniture

Here’s an interesting problem, but a hard one to explain.  Most of what I’m doing here comes from the very cool “Winning Ways for Your Mathematical Plays” book by Berlekamp, Conway, and Guy, which I hope at some point in the future to have the time to really dig deeply into.  But for now, I’ll just use it as a reference to this week’s problem.

The problem: Left-Right Hackenbush for Redwood Furniture.  This is problem GP12 in the appendix.

The description: Ok, here we go.  First, a Hackenbush problem consists of an undirected, connected graph.  The edges of the graph are marked as “Left” or “Right”(though the book has some very nice colored pictures, where the edges are labeled “Blue” and “Red”).  Some of the vertices are on the ground (In G&J’s definition, there is one ground vertex, but it’s equivalent to having several vertices that are all on the ground).

On Left’s turn, they remove a blue edge and then all edges that are not connected to the ground are removed.  On Right’s turn, they remove a red edge, and then all edges that are not connected to the ground are removed.  A player loses if there are no remaining edges of their color.

redwood furniture Hackenbush instance is one where:

  • No red edges touch the ground
  • Each blue edge (or “foot”) has one end on the ground and the other touches a unique red edge (the “leg”)

Here are some redwood furniture instances from the book:

The “value” of a Hackenbush position is the number of “spare” moves (with optimal play) one player has after the other player loses.  A value of 0 means that whoever’s turn it is will lose (on an empty board).  The definition can be extended to fractional values.  For example, a value of 1/2 for (say) Left means that if we made two copies of the game, we would end up with a situation with a value of 1 for Left.

So, the question is, for some Redwood Furniture graph, and some K, is the value <= 2-K?

Reduction:

I’m just going to sketch the process here since it takes several pages of the book (and depends on results and ideas from earlier in the book).

They show:

  • The value of any redwood furniture graph is 2-N for some N.  In the degenerate case, the graph with just one Left edge has a value of 1. (=20)
  • On Left’s turn, they will always remove a foot (by definition, that’s all they have).  On Right’s turn, they should make a move that does not disconnect the graph, if possible.
  • A “Bed” is a redwood furniture graph where every red edge that is not a leg connects to a leg.  It has value 2-(m+1), where m is the largest number of moves that do not disconnect the bed.
  • The value of the game depends on how many extra moves Red has to get down to just a bed.
  • To find m, you need to know the size of the largest redwood tree (a tree is a graph that will be disconnected by the removal of any edge) that contains all of the legs.
  • The edges of the bed (the red edges that are not legs) form a bipartite graph.  So finding m is equivalent to the set covering problem, where the elements of the set are the vertices, and the edges are the sets.

Here’s how I think the Set Covering reduction works.  Given a set covering instance: a set S of elements, and a collection C of subsets of S, we’ll build a bipartite graph.  One set of the bipartite graph will correspond to the elements of S (and will be on the legs of the furniture graph).  The other set will correspond to the elements in C (and will be the vertices in the bed that are not in the legs).  An edge will go from each “C vertex” to each “S vertex” in its set.  Now, the cover is the set of vertices from the bed that cover all of the legs.

The book says you want the “smallest redwood tree which contains all of the legs”, which I think is the same thing (smallest number of extra vertices), but I’m not 100% confident since the Hackenbush game involves removing edges, and we’re choosing vertices in the cover.

I’m a little sad that the book does such a great job describing the game, and the value function, and then glosses over the reduction part (and uses misleading terms like “Minimum Spanning Tree of a Bipartite Graph”, which is a polynomial problem).  The actual reduction in G&J is to a private communication, so that’s not much help.

Difficulty: Boy, I don’t know, I think it depends on where you start from.  If my Set Cover reduction is the right one, and all you ask a student to do is that, it’s probably a 4.  If you’re going to make them prove all of the things I glossed over about the value number, then it probably goes up to at least an 8.

NxN Go

Similar to the last problem from the appendix in that we’re taking an actual game and extending it.

The problem: NxN Go.  This is problem GP10 in the appendix.

The description: Given an integer N, and a position (consisting of black piece locations, white piece locations, and black piece locations) on an NxN go board, and the name of the current player’s turn, does white have a forced win on the game?

Example: Instead of a true example, what I think is most relevant here is a little discussion of the rules and basic strategy of Go.  In Go, players take turns playing stones on a grid, with the goal of surrounding spaces on the board with pieces of your color:

(all pictures are taken from the tutorial at https://www.pandanet.co.jp/English/learning_go/learning_go_2.html):

In this case, white has surrounded 9 spaces (stones are placed at intersections, including the edges of the board).

If a stone of the other color can be surrounded on all 4 sides by a stone of your color, the stone is captured, scoring you a point at the end of the game:

In this case, the black play at “1” captures the white piece (and likely gains black an additional point for having surrounded territory at the end of the game)

More than one piece can be surrounded at a time, but not all configurations of stones can be surrounded.  Most notably, a configuration with two “eyes” (or empty holes)  cannot be captured, for example:

Here, the white play at “1” creates two eyes.  There is no way for black to surround all of the white pieces since they would have to play in both empty holes, and as soon as black plays in one of the holes, the black piece is surrounded and immediately captured.

So, the main goal of Go (and the proof) revolves around creating “safe” structures that contain two eyes and using them to capture as much territory as possible.

Reduction: The paper by Lichtenstein and Sipser reduce from Planar Geography.  The idea is to have a set of safe territory for White, and another threatened set of stones large enough that if it can be made safe, White will win, but if it can be captured, Black will win.  Here’s the picture from the paper:

Black pieces surround white all the way around, so the only escape would be for white to extend the “pipe” on the left around to the safe white spaces (or some other group of two eyes, which will keep the large group alive).  Then we encode the vertices and edges in the graph as sets of stones, where each “choice” of going through an edge is reflected by a choice of where stones are placed.

There are many types of subgraphs and corresponding board positions in the paper, here’s just one of them:

(Graph position)

(Board position)

Here’s the general structure of the arguments that show how the play “has” to go through this vertex.  Suppose we are coming from the top, and white wants to go left.

  • If White doesn’t play at 1, 2, or 3 first, Black will play at 2.  White will now have to play at 1 to keep the middle vertical strip (which connects back to the big threatened set of pieces) alive.  But then Black plays at 3 and takes them all anyway.
  • Even if White plays at 3, Black wins by playing at 1, then White moves to 2, then Black plays at 5
  • If White does play at 1 or 2, (let’s say 1, because that will take us left), Black has to respond at the other point (so, 2 for us).  If they don’t, White plays at 2, and 3 black stones below the 1 and 2 are captured, and White will be able to connect to the two eye group below.
  • After Black plays at 2, white needs to go to 3 to build a line of white stones coming in from the top, and going out to the left.  Black plays at 4 to stop white from connecting to the group of 2 eyes on the left.

As a result, the “edge” going through this vertex and coming out to the left has been chosen.

Difficulty: 7. I think this is easier to see than the NxN checkers reduction, but still takes a lot of cases and structures to realize.