13
$\begingroup$

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:

  1. 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.
  2. The squares can be either "white", "black", or "empty".
  3. On the grid, there is always a stepladder source. It looks like this:
    enter image description here
  4. There are two players, black and white. They take turns; each turn consists of colouring exactly one empty square with their own colour.
  5. 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
  6. Black wins, if he catches the white squares in the source.
  7. White wins, if she catches the inner black squares in the source.
  8. 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.

enter image description here

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:

enter image description here

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

enter image description here

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.

enter image description here

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 . . . . . . . . . .
    . . . . . . . . . . . . . . . . . . . .
    . . . . . . . . . . . . . . . . . . . .

Looks like its time for the daily hint then! (2018-01-10)

Jimmy's answer is good. Very good, actually. But there is still room for improvement.

$\endgroup$
  • $\begingroup$ Can we use computers? Also, not sure if it's possible, but I could imagine at some point there might be 2 or more lines of optimal play. Is it sufficient that we consider a pattern which allows a line of optimal play resulting in a northwestern ladder? Or, alternatively, do you have proof there's always 1 line of optimal play? $\endgroup$ – Lolgast Jan 9 '18 at 13:50
  • $\begingroup$ The puzzle is definitely more fun if solved by hand, but if you want to brute force it, I’m not going to stop you. The ”optimal play” I mean here has black attacking with maximum efficiency, and white resisting for maximally many turns; these strategies must send the stepladder going towards the top left. Any solution satisfying those conditions, with the minimum number of squares coloured, will qualify as correct. $\endgroup$ – Bass Jan 9 '18 at 14:04
  • 5
    $\begingroup$ I feel that this game needs a shorter name. Something like "Turn", perhaps, given the theme of this question. Or "Move" since we're looking at the paths of these ladders. Or maybe "Try" since we're attempting to solve a problem. Or "Leave" since white is trying to escape. If only there were some word that combines all those meanings... $\endgroup$ – Gareth McCaughan Jan 9 '18 at 14:14
  • $\begingroup$ Well, "more fun" depends on whom you ask :P I'd personally find it quite fun to make a program to simulate the optimal play (though finding a solution pattern might indeed be more fun to do by hand). Regarding optimal play, I was thinking of this kind of situations, where black has 2 possibilities: he can fill in the square to the left or the right, resulting in a northwestern or a northeastern staircase respectively. Would that be a valid solution? (Note: I don't have any proof such a position can arise, which I was asking if you had counterproof) $\endgroup$ – Lolgast Jan 9 '18 at 14:17
  • $\begingroup$ @lolgast, ah, I see. The intended solution doesn’t branch. I’ll have to fugure out a more complete definition of optimal play, it seems. I’ll try to find the time to do that today. $\endgroup$ – Bass Jan 9 '18 at 14:37
3
$\begingroup$

Here is my solution

With three pieces added

Two for the black player (in gray)
One for the white player (in blue)

solution

After a few laps, Black has a choice : play in A or B

base

The boxes contain the corresponding play number

If he plays in A, there are two possibilities that lead to the victory of the white player:

white wins 1

White wins because Black can't stop him to have three liberties.

white wins 2

White wins by catching n11 and having one more liberty.

So he will play in B and get to these results:

the path turns 1

the path turns 2


Here is my previous solution which is not valid since, as commented by Bass, b14 should be under n13 to catch n9 and win.

previous solution

$\endgroup$
  • $\begingroup$ Pretty close! After black plays n13, White can catch n9 to ruin black’s day though. $\endgroup$ – Bass Jan 10 '18 at 18:02
  • $\begingroup$ Right ! I just have to add a black piece here to prevent that move. But i don't know if there are a solution with only two added pieces :/ $\endgroup$ – Alix Eisenhardt Jan 10 '18 at 18:13
  • $\begingroup$ I just noticed, I left the plays in French. But it's understandable so I'll leave it like that. Sorry. $\endgroup$ – Alix Eisenhardt Jan 10 '18 at 18:24
  • $\begingroup$ Could you please post the solution with the piece added? There may possibly be a couple of surprises still in store, so it's good to be specific. $\endgroup$ – Bass Jan 11 '18 at 6:47
  • $\begingroup$ Nicely done! I haven't found a way to turn a stepladder with only one or two squares, so until I'm proven wrong, this is an acceptable answer. For the most "compact" answer (with all the coloured-in squares fitting in the smallest possible rectangle), you could also have added the extra black square just above the other one. $\endgroup$ – Bass Jan 11 '18 at 10:45
6
$\begingroup$

This seems like a straightforward way of turning the ladder -- the two marked white extra pieces force black to steer the ladder upwards and left, and the two marked black pieces are to maintain number of liberties.

enter image description here

Here's the starting position for this solution:

enter image description here

$\endgroup$
  • 5
    $\begingroup$ Sorry for my picture having such an odd-looking grid. I'm from an alternate universe where the Stepladder game is played with round pieces on the grid points. $\endgroup$ – Jimmy Jan 9 '18 at 20:21
  • $\begingroup$ I took the liberty to edit in a diagram with just the starting position, and added some spoiler tags. I think there may be some others here from that same universe, but I still used the CSN format, or Classical (as of today) Stepladder Notation for the diagram. $\endgroup$ – Bass Jan 9 '18 at 21:04
  • $\begingroup$ Now that @Alix_eisenhardt has posted a working solution with only three squares coloured, I have to ask: What would happen, if you just left out the lower white square/piece from your solution? $\endgroup$ – Bass Jan 11 '18 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.