Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. 16 Aug '08 16:34
    Connect is a pencil and paper game, played between two players (I'll call them red and blue) on slightly out-of-phase rectangular grids, like this:
    http://img390.imageshack.us/img390/9779/grid1nh2.jpg
    The red player only uses the red dots, and the blue player only uses the blue dots. They take it in turns to draw a line between any two of their dots that are one space apart, so if blue goes, then red, then blue again, you might get a grid that looks like this:
    http://img516.imageshack.us/img516/4074/grid2ud3.jpg
    The aim for blue is to draw a line from left to right. The aim for red is to draw a line from top to bottom. In the following game, red has won:
    http://img141.imageshack.us/img141/1531/grid3te6.jpg

    Firstly, this is a brilliant game and you will have fun playing it without knowing the solution.
    Secondly, there is a 100% winning strategy for the first player. What is it? And can you prove it wins? Including winning on bigger boards?
  2. 16 Aug '08 21:52
    My notes on this game, also known as "pipelayer".

    First, ties are impossible. Even if the pipes were placed randomly, or both sides tried to avoid making the last connection, exactly one of the two will do it, and at the same time create a wall permanently blocking the other.

    Second, as is usual in two player games, first player gets the advantage of a move's initiative. So given ties are impossible, it's no surprise to me 1st player wins in a perfect match.

    Now onto my idea of good strategy. The core idea I would present is the idea of playing to obstruct the opponent's path, rather than to complete your own.

    There are two kinds of move for both sides. For purposes of this analysis, a "row" is defined according to the direction you want to go overall. For the player wishing to connect top to bottom, a row is a set of their dots running side to side. For the other player, a row runs up and down.

    A forward move connects two different rows. It is required to make a certain number of forward moves to win, depending on how big the grid is. For this reason, a forward move is usually preferred.

    A side move connects two dots in the same row. It is useful for bypassing a blocked path, and is often necessary. A side move will also tend to block off your opponent's ability to do the same. Side moves aren't absolutely required at all, but you'll see them nonetheless as paths get blocked.

    It is interesting to note that one players forward move is oriented the same way as the other player's side move and visa versa.

    Now my primary short term objective is to block my opponent's forward moves with my own. My second objective is to cut off side moves connecting his halves in the event I don't have the option to step in front of him. My third objective is to finish my path if given the chance, but this will usually occur after a great many moves and opponent's attempts to break through my roadblocks.

    If I start with a forward move in the corner, and do the above, it is my contention that I will eventually win, because as I set up roadblocks, I am also building my own path. And since I have the advantage of a move's initiative, his attempts to mirror this process will fall by a move.