Tag Archives: Generalized Geography

Planar Geography

In the process of reading up on the next problem in the appendix, I saw this nice reduction for a generalization of Geography that we used last week and will use next week.  So I thought it would make a nice addition to post it here.

The problem: Planar Geography.  This problem is not in the appendix (though the reference to this problem and the paper with this reduction appears in the notes to the “Generalized Geography” problem).

The description: Given an instance of the Generalized Geography problem, but where the graph G is planar, does Player 1 have a forced win?

Example: The example we had in the Generalized Geography problem is actually a planar graph:

Reduction: The paper by Lichtenstein and Sipser which has the reduction for next week’s NxN Go problem has this in the ramp-up.

What we’re doing to do is re-build the graph that was created in the Generalized Geography reduction.  That graph may not be planar. Any time the graph has two edges that cross:

We replace it with the following construction

(figures are on pages 395 and 396 of the paper).

The important things to realize are these:

1) If we use this on the graph generated from the original Geography Construction, it will never be the case that we will use both crossing edges in one solution.  This is an important point that isn’t really addressed in the paper.  The Lichtenstein and Sipser paper has a slightly different reduction for Generalized Geography where it’s easier to see.

2) Suppose it’s player 1’s turn, and they enter the intersection going up.  Then it will be their turn again once they hit the middle point.  The point of the extra loop structures (instead of just adding a vertex at the intersection point) is to create a situation where if player 1 decides to turn right, player 2 can turn down, and make player 1 lose.  This works in both directions.

Difficulty: I was hoping that this would be a good difficulty 4 or so problem in the middle of all of these really hard ones, but the whole “you’ll never use this intersection twice” problem makes the construction hard to see, and it’s a tough thing to think about why it matters, even if you told the student the rule.  Maybe this is a 5 if you give them that information.

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.

Protected: Generalized Geography

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