construction - Stepladder Game, Introduction and Puzzle 1: Turning

Friday, 20 June 2014

construction - Stepladder Game, Introduction and Puzzle 1: Turning

I want to introduce a new game to PSE: the Stepladder Game!^*
_{_{* You may already know this game by another name.}}

The rules for the Stepladder Game:

The game is played on a grid.
- Our grid is rectangular, and in the grid, each square, apart from the edges, has four neighbours.
- The grid is "big enough", meaning that there will always be an edge in any direction, but unless the edges are shown, there is always "enough empty space" for any construction.

The squares can be either "white", "black", or "empty".

On the grid, there is always a stepladder source. It looks like this:

There are two players, black and white. They take turns; each turn consists of colouring exactly one empty square with their own colour.

After colouring a square, check that every opponent's square has a path, along adjacent same coloured squares, to an empty square. Those squares that don't, are caught and emptied

Black wins, if he catches the white squares in the source.

White wins, if she catches the inner black squares in the source.

White goes first.

Examples

Here's an example game with nothing except the source and the eventual edge. Both players are playing optimally. (For the purposes of these puzzles, "optimal play" means that the losing side always chooses the longest resistance, and the winning side always chooses the shortest path to a guaranteed victory.) The first couple of plays are numbered for your convenience.

As you can see, if the grid is empty, black will win; in the above diagram, it's white's turn, but whatever white does, black will win on the next move.

This all changes, if some squares are already coloured in. Here's an example with just one white square added:

This time around, with optimal play from both players, it is white who will win:

In the above diagram, it's black's turn, but white is already adjacent to 3 empty squares. Whatever black plays now, white can use her following two turns to catch the inner black shape and win.

That should just about be enough for the rules, so it's finally time for the first puzzle.

Stepladder Puzzle 1: Turning.

As you have no doubt noticed, the stepladder source always sends the stepladder in the northeast direction. Your job is to colour the minimum number of squares in the target area (marked in the diagram) so that with optimal play from both players, the stepladder continues, but is now proceeding towards the northwest.

What constitutes "optimal play" isn't always self-evindent, as Lolgast pointed out. To remove any ambiguities, here's the official definition of "optimal play":

This is a game of full information, so for any given situation, the winning player can always be figured out, even though it may get complicated at times.

The losing player will always choose the variation that leads to the most turns before losing.

The winning player will always choose the variation that leads to a guaranteed win in the fewest possible turns.

For the purpose of these variation length calculations, any stepladder terminating in an unseen edge will have ”many” steps.

Given choices that are equal by the above criteria, the players will choose the option that is the most inconvenient for the purposes of solving the puzzle.

Here's a text version of the puzzle for the graphically challenged. X is black, O is white, dots are empty squares, and the target area is marked with underscores.


    . . . . . . . . . . . . . . . . . . . .
    . . . . . . . . . . . . . . . . . . . .
    . . . . . . . . . . . . . . . . . . . .
    . . . . . . . . . . . . . _ _ _ _ _ _ .

    . . . . . . . . . . . . . _ _ _ _ _ _ .
    . . . . . . . . . . . . . _ _ _ _ _ _ .
    . . . . . . . . . . . . . _ _ _ _ _ _ .
    . . . . . . . . . . . . . _ _ _ _ _ _ .
    . . . . . . . . . . . . . _ _ _ _ _ _ .
    . . . . . . . . . . . . . _ _ _ _ _ _ .
    . . . . . . . . . . . . . . . . . . . .
    . . . . . . . . . . . . . . . . . . . .
    . . . . . . . . . . . . . . . . . . . .
    . . . X X X X X . . . . . . . . . . . .

    . . . X O O O O O X . . . . . . . . . .
    . . . X O X X X O X . . . . . . . . . .
    . . . X O X . X O X . . . . . . . . . .
    . . . X O X . X O X . . . . . . . . . .
    . . . X O X X X O X . . . . . . . . . .
    . . . X O O O O O X . . . . . . . . . .
    . . . X X X X X X X . . . . . . . . . .
    . . . . . . . . . . . . . . . . . . . .
    . . . . . . . . . . . . . . . . . . . .