Category Archives: Appendix- Games and Puzzles

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.

NxN Checkers

Back from my trip with a simple problem to explain, but a hard reduction to do.

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

The description: Given a position on an NxN checkerboard, does black have a forced win?  It turns out the reduction will also work if we restrict the board to only having kings on the board (and so no “un-kinged” pieces)

Example: The “NxN” requirement is there since on a standard 8×8 checkerboard, there is a finite set of moves, and so theoretically you could solve the problem in O(1) time (for a really large constant factor, of course).  The starting configuration adds extra rows and columns of pieces to the board, still leaving two blank rows in between the two pieces.

So, let’s do an example on a 4×4 board.  The starting configuration is this:

* *
O O

(the dashes are empty spaces, * is Black, O is White)

Here is a configuration of pieces that will lead to a black win:

*
O
*

If it’s Black’s turn, they should move the piece in the second row up to either location on the first row (recall that all pieces are kings).  Then White’s only move is to go to the space Black just vacated, where it will be jumped, giving Black the win.

Reduction:

The paper by Fraenkel, Garey, Johnson, Schaefer, and Yesha contains a pretty detailed description of the reduction, which contains lots of complicated structures.  I’ll just give the general idea here.

The reduction is going to be from Geography, which is still NP-Complete even if the graph is bipartite and planar.  They create several structures to help them build their instance of the checkers game.

The first is what the call a phalanx– an open rectangle of (say) White kings that surround the (say) Black pieces.  The idea is that since there is no way for the Black pieces to jump anything in the rectangle, then White can “shrink” the phalanx towards Black, running them out of room to maneuver.  Here is a picture of a small phalanx on a 6×6 board:

O O O
O O O
O X O
O O
O O
O O O

..notice that whatever Black does, they will be captured on their next turn.  This remains true no matter how many Black pieces are trapped inside the phalanx, and no matter how much open space is inside the phalanx (White can use their moves to shrink it over time).

The key to the reduction is to build a set of interlocking “potential” phalanxes- situations where a Black king may be able to escape the phalanx.  If it can, Black can jump White’s pieces and win, but if it can’t, the phalanx will engulf Black and they will lose.  The geography instance is placed in the center of these potential phalanxes in such a way that a Black king can “escape” the Geography instance if and only if Black can win the geography game.  The reason why the Geography graph had to be planar was so that we could directly represent the vertices in the graph as positions on the checkerboard.  The reason why the Geography graph had to be bipartite was so that edges going from the first vertex set to the second could be all Black pieces, but the edges going from the second set to the first could be all White pieces.

The game starts with black at the “start vertex” for the geography problem, and jumping a line of White checkers:

When a vertex has more than one possible exit, that leads to more than one possible set of checkers to jump for the other player:

(This is part of figure 10 from the paper.  Here, after White jumps down the chain of Black pieces, Black can choose the chain of White pieces to jump through.)

The construction takes advantage of the rule in checkers (which I was not aware of until I was in my twenties!) that if a player can make a jump, they must make a jump.  So as long as players can jump checkers along these chains (alternately, as long as they can follow edges in the geography graph), they will.  As soon as a player cannot make a jump they will be able to deal with the Black king that can either escape the phalanx structure (and win for Black) or trap it (and win for White).

This is the general idea of the reduction, there are a lot of details that I am glossing over.

Difficulty: 8.  This is a bit hard to see and very hard to come up with, and it’s very easy to get lost in the weeds of the details.  I do like the way that the “removal” of edges from the Geography problem is modeled by the actual removal of pieces from the checkerboard, though.

Annihilation

I’m going to be out of town for a few weeks, so the next few posts might be delayed from my already slower schedule.

The problem: Annihilation.  This is problem GP9 in the appendix.

The description: G&J’s description is a little obscure, so we’ll go with the one in the paper by Fraenkel and Yesha that has the reduction.

Given a directed graph G=(V, E), and r subsets of E, E1 through Er.  The subsets may not be disjoint, but each edge of E is in at least one subset.

We’re also given r different types of tokens, placed on vertices of the graph.  Each token type corresponds to one of the r subsets of E.  A player moves by taking a token (of type i) and choosing an edge (u,v) in set Ei, where u is the current position of the token.  The token is moved to vertex v in the graph.  If 2 tokens ever meet on the same vertex, both are “annihilated” and removed from the game.  A player loses if they cannot make a move.  Does player 1 have a forced win?  (Though note that the Fraenkel and Yesha paper actually proves whether player 2 has a forced win)

Example: Here is a simple example that will hopefully be useful in the reduction that follows:

In this graph, the red edges are in E1 and the blue edges are in E2.  The red vertices currently hold a type 1 token, and the blue vertex holds a type 2 token.

If player 1 makes any move except moving the token on g to the vertex h, player 2 will be able to move a red and a blue token onto the same space, annihilating both.  Then there will be just 2 moves left in the game (the 2 remaining red pieces moving along their edges), the first moved by player 1, the second moved by player 2, then player 1 will have no move and will lose.

If player 1 moves from g->h, then there are 4 more moves in the game (the h->i edge, and the three red edges).  Thus, player 1 will get the last move and will win.

Reduction: Fraenkel and Yesha use Minimum Cover.  I’ll note again here that he reduction will show that the Cover instance is true if and only if player two has a forced win.

So we’re given a collection of sets Si where i goes from 1 to m, and an integer K.  We’re going to build a directed acyclic bipartite graph R= (V, E):

  • The graph has vertices xi and yi for i from 1 to K.
  • The graph has one vertex for each set Si and one vertex for each element ei in the union of the sets.
  • The graph also has two “special” vertices a and b.
  • “Type 1” edges go from all xi to its corresponding yi, and from each yi to all Si vertices.
  • “Type 2” edges go from a to all ei vertices, from all ei vertices to all set vertices that contain that element, between all e and x vertices, and from all x and S vertices to b.
  • Type 1 pieces start on all x vertices.  There is 1 type 2 piece, and it’s on a.

Here is the example used in the paper for the covering problem {{e1,e2}, {e2,e3}, {e3,e4}, {e1,e3,e5}, {e6}} and K=4:

An arrow going to a circled group of vertices represents a group of edges going to all vertices in the group.

Notice that without annihilation, the path a type 1 piece takes is from some x vertex to its y vertex, and from there to some S vertex (2 moves), and the path of the type 2 piece is 3 moves (either a->some e-> some x ->b or a->some e->some S ->b), so there is an odd number of moves, and thus player 1 wins if no annihilations happen.  Player 2 wins if a type 1 and type 2 piece collide someplace (on an x or S vertex).

This is because if 2 pieces of different types collide, we remove an odd number of moves from the game:

  • If they collide on an x vertex, we remove the 2 moves the type 1 piece can make, and the move the type 2 piece could make from x->b
  • If they collide on an S vertex, we remove the one move the type 2 piece makes from S->b

On player 1’s move, they will have to move all pieces off of the x vertices before moving the type 2 token off of the a vertex.  Otherwise, after player 1 moves a->e, player 2 can move e->x (to some x that hasn’t left its starting space yet).

So,  player 1 starts by moving some xi->yi.  Player 2 will move the piece from yi to the next set in the cover.  Recall that there are k different x and y vertices.  So what will happen is that the k vertices that comprise the cover will have tokens on them.

Once all of the type 1 pieces are some S vertex, player 1 will have to move the type 2 piece from a to some e vertex.  If there is a cover, no matter what e vertex player 1 chooses, player 2 will be able to move the token to an S vertex that contains that e element.  If there is no cover, player 1 will be able to choose an e vertex that has no e->S (or e->x) move that causes an annihilation, and player 1 will win.

Difficulty: 7.  This is a very cool reduction, and you can see from the picture how it works.  It’s fun to see how all of the edges and sets work out.

Alternating Maximum Weighted Matching

This is a “private communication” problem I haven’t been able to solve or find an actual reduction for.  I think I have the start of a reduction, though, but I haven’t put in the time to work out the details.  Hopefully, I’m on the right track.

The problem: Alternating Maximum Weighted Matching.  This is problem GP8 in the appendix.

The description: Given a weighted graph G=(V,E), with positive weights, and a positive bound B, each player chooses an edge from E.  No two chosen edges can share an endpoint.  Player 1 wins if the weights of the edges chosen ever exceed B.  Does player 1 have a forced win?

Example: Here’s a graph:

If B=11, and it’s player 1’s turn, then they can’t remove the highest-cost edge (d,e) because every edge is incident on d or e, so player 2 would have no moves, and the game would end with cost 10.

If player 1 removes one of the 6-cost edges (let’s say (a,d)) we’re left with:

..and so player 2 will have to take one of the remaining 6-cost edges, bringing the total cost of edges removed to 12.

Reduction (sort of): So, like I said at the top, the reference in G&J is to a “private communication” by Dobkin and Ladner.  I couldn’t find the actual result published anywhere.  I actually emailed both Dobkin and Ladner to ask if they remembered what the reduction was, but their response (reasonably) was “It’s been 40 years, I have no idea”.

But, I thought about it for a little while, at least, and came up with what I thought are the beginnings of an idea.  I didn’t have the time (or, perhaps, the ability) to get all of the details right, but this feels like a start, at least:

We’re going to reduce from One in Three 3SAT.  Each variable will be represented as a pair of vertices xi and xia, connected by a weight 1 edge.  The negation of the variable (~xi and ~xia) will also be vertices and also connected by a weight 1 edge.  The vertices xi and ~xi will be connected by a “large” edge of weight 10.

From each clause, we build up a component of a graph that looks like this:

The weights of 10 and 1 might not be right, think of them as “large” and “small” weights.  Each of the xi variables corresponds to the actual variables in the formula, we only include the variables that correspond to the clause we’re looking at.

(One thing I did wrong was to assume that player 1 loses if the edge cost goes over B.  So in what follows, player 1 is trying to keep the score low.  We can fix this by making it player 2’s turn and swapping the roles)

The idea is that player 1 will choose either the x1-x1a edge or the ~x1-~x1a edge to “fix” the value of the first variable.  If the variable shows up in the clause (for example, they chose the x1-x1a edge in the diagram above), this will eliminate the edges (x1a,c1), (x1a, x2a), and (x1a, x3a) from being able to be chosen.

Then player 2 will want to choose an “expensive” edge.  He’ll choose the edge (x2a,x3a)

Then we’ll move on to the next variable.  It’s again player 1’s turn to decide on a setting of x2.

The idea is that each clause will have it’s “ci” vertex connect to that central “home” vertex by an expensive edge, so if after all of the variables have been given their values, there still is an edge to the home vertex, it will be chosen, and that amount will be the amount that sends the total cost over the bound.  (So right now, I’m thinking of the bound being something like 11*N +1 for a problem with N variables, at least until the extra things below get added).

What still needs to be done is the detail work (and probably extra edges and vertices) to ensure that players have to choose the edges in the order I specify (i.e., not doing so loses a player the game immediately).  It’s entirely possible that doing so will make this whole construction wrong.  But I like the idea behind it, at least

Difficulty: N/A.  I don’t want to call this a 10, even though it stumped me.  I think if my idea is right, it’s not that hard.

Alternating Hitting Set

I think this might be the last of the problems we do from the Schaefer paper we’ve used so much recently.

The problem: Alternating Hitting Set.  This is problem GP7 in the appendix.

The description: Given some universe set B, and a collection C of subsets of B.  Players take turns choosing an element from B.  Once enough elements are chosen to make all sets in C have at least one element chosen, the player who made that move loses.  Does player 1 have a forced win?

Example: Let B= {1,2,3}, and C = {{1,2,3}, {2,3}, {1,3}, {1,2}}.  Player 1 can win by choosing 1, which hits all sets in C except {2,3}.  Since player 2 has to pick either a 2 or 3, they will hit that set and lose.

Reduction: Schaefer remarks that this is just a special case of Variable Partition Truth Assignment. with sets instead of variables.  Here’s how that goes:

Suppose we have an instance of Variable Partition Truth Assignment, so a CNF formula with all positive variables.  We just create a set B with one element per variable, and the clauses become the sets in C.  Then picking an element of B is the same as setting a variable to true.  Hitting a set in C is the same as making the clause true.

Difficulty: 3.  Maybe this problem is close enough to Variable Partition Truth Assignment that it didn’t need its own article.  On the other hand, it’s nice to see an easy reduction for once.

 

Sift

Finally, we’re ready to go back to the problem in the appendix.

The problem: Sift.  This is problem GP6 in the appendix.

The description: Suppose we have some set X, with collections of subsets of X A and B.  The sets A and B have no elements in common.  Players take turns choosing elements from X until every subset in A (in which case player 2 wins) or every subset in B has a chosen element (in which case player 1 wins).

We do need to have a rule for what happens if an element is chosen that makes both players lose (because the element chosen intersects with the last subsets in both A and B).  In this case, the player who made the move loses.

Example: Suppose X was {1,2,3,4,5,6}.  A = {{1,2}, {3,4}, {5,6}} and B = {{1,2,3}, {4,5,6}}.  Then A could force a win by choosing element 3.  This intersects the second set in A, and the second set in B.  So the current “live” subsets are:

A = {{1,2}, {5,6}}

B = {{1,2,3}}

Player B needs to pick 5 or 6, or they immediately lose.  But once that happens, player A can choose 3, which means the set of elements chosen {3,4,5} (or {3,4,6}) intersects with every set in B, but not every set in A, so A wins.

Reduction: The Shaefer paper reduces from Avoidance Truth Assignment, which means we start with a CNF formula with no negated literals.  Let’s assume the formula has m clauses and n variables.  For each clause k define the set Sk to be the indices of the variables in clause k.   (So if clause 1 was: x∨ x4 ∨ x7, then S1 = {2,4,7}).  Let “Set 1” = all of the Sk sets of even length, and “Set 2” = all of the Sk sets of odd length.  If n is even, give player 1 “Set 1” and player 2 “Set 2”.  If n is odd, reverse the allocation.

Notice that “Set 1” is the set of all clauses with an even number of distinct variables in them, and “Set 2” is the set of all clauses with an odd number of distinct variables in them.  Recall from our discussion of the Avoidance Truth Assignment problem that the player whose turn it was could win that game if we had an even number of unplayed variables, and an odd number of unplayed variables in every clause  (or an odd number of unplayed variables, with an even number in every clause).  What our “Set 1” and “Set 2” constructions are doing is listing out those clauses and assigning them to each player.  Once one set runs out, then we have the winning case for one of the 2 players.  So this construction of Sift is equivalent to the original Avoidance problem.

Difficulty: 8.  I wish there was a good proof of this odd/even claim he makes.  I don’t 100% buy his intuitive argument.

Avoidance Truth Assignment

This is the second of the two proofs in Schaefer’s paper that will get us the Sift reduction.

The problem: Avoidance Truth Assignment.  (My name for it).  This problem does not appear in the G&J appendix.  It is named “Gavoid (POS CNF)” in Schaefer’s paper.

The description: Given a CNF formula with no negated literals (and not necessarily 3 literals per clause), players take turns choosing a variable to make true.  A player loses if after their play the formula becomes true, even if all unchosen variables are set to false.  Does player 1 have a forced win?

Example: Suppose the formula was (x1 ∨ x2) ∧ (x1 ∨ x3) ∧ (x2 ∨ x3 ∨ x4).  Then player 1 could force a win by choosing x2, which makes clauses 1 and 3 true.  The player who chooses x3 will lose, so player 2 should pick one of x2 or x4.  But then player 1 chooses the other, leaving player 2 forced to pick x3, making the second clause (and the whole formula) true.

Reduction: Schaefer reduces from Pre-Partitioned Truth Assignment.  So we start with a logical formula given as a set of clauses, and the variables are partitioned into two sets, one for each player.  We’ll call player 1’s variables x1 .. xn and player 2’s variables y1 through yn.   We’ll assume (or modify the formula to make it happen) that each clause contains at least one x variable, and that every variable occurs both positively and negatively as a literal someplace in the formula.

Our new formula will have:

  • 4 copies of each variable (xi turns into xi, ~xi, xi‘, and ~xi
  • One clause (xi ∨ ~xi) for each x variable
  • One clause (yi ∨ ~yi ∨ yi‘) for each y variable
  • For each clause in the original formula: if it contains an unnegated variable xi (or yi), then our new clause will contain xi and xi‘.  (Or yi and yi‘).  If it contains a negated literal, we’ll use the 2 “negated” variables instead.  This clause will probably have more than 3 elements in it, but that’s ok.

Shaefer notes that if we hit a point in the game where we have:

  1. An even number of unplayed variables, and
  2. An odd number of unplayed distinct variables remaining in every clause.

or:

  1. An odd number of unplayed variables, and
  2. An even number of unplayed distinct variables remaining in every clause

..then the player who’s turn it is can win by picking some unsatisfied clause and picking any variable that does not satisfy it.  So the strategy for the first player is to create the first situation (by satisfying all clauses with an even number of variables), and the strategy for the second player is to create the second situation (by satisfying all clauses with an odd number of variables).  Since the first kind of clause we made (with the x variables) has an even number of variables, player 1 will want to satisfy those clauses as fast as possible.  Similarly, since the second kind of clause we made (with the y variables) has an odd number of variables, palyer 2 will want to satisfy those clauses as quickly as possible.  If this happens, we are exactly imitating the Pre-Partitioned Truth Assignment game.

The remainder of the reduction is a detailed proof explaining the above argument in detail (showing, for example, what happens when players do not play this way).

Difficulty: 8  Maybe they’re getting a little easier for me because I’ve been doing so much of them.  Or maybe because I’m still skipping all of the low-level details.

Protected: Variable Partition Truth Assignment

This content is password protected. To view it please enter your password below:

Protected: Generalized Kayles

This content is password protected. To view it please enter your password below: