12
$\begingroup$

On a standard $19\times19$ Go-board there are four stones: two white stones in the lower left and the upper right corner, and two black stones in the lower right and the upper left corner. Alice (playing white) and Bob (playing black) alternately move one of their stones to a horizontally or vertically adjacent point. Bob makes the first move.

Alice wins, if she manages to navigate her two white stones to two points that are (horizontally or vertically) adjacent to each other. Bob wins, if he can prevent Alice forever from winning.

Determine the winner of the game. (As usual, we assume that Alice and Bob use optimal strategies.)

$\endgroup$
  • 10
    $\begingroup$ Moving go stones? Do you know no shame? $\endgroup$ – CodesInChaos Jan 29 '15 at 17:10
  • $\begingroup$ @CodesInChaos Maybe it should be reworded to say you take one stone off the board, and then put another on the board adjacent to where the stone you took off was. Or use different pieces. $\endgroup$ – KSmarts Jan 29 '15 at 20:18
3
$\begingroup$

I need to see it visually.

Reduce the problem to a simpler one.

Take a 3x3 board with black and white stones as indicated in the problem statement. (Think tic-tac-toe board with black in 1 and 9 and white in 3 and 7.)

B|2|W
4|5|6
W|8|B

Bob makes the first move which is to move a black stone next to one of Alice's white stones and reducing Alice's possible moves to 2, 6, and 8 as indicated here. It doesn't matter which stone moves or to which point, because they are all reflections of each other. So, Alice's first move it always from this position and she has 3 choices: 2, 6, or 8.

If Alice chooses to move 7 to 8 and Bob does not move to 5,

B|2|W    1|2|W    1|2|W    1|2|W    1|x|W
4|5|6 -> B|5|6 -> B|5|6 ?> B|5|B -> B|W|B
W|8|B    W|8|B    7|W|B    7|W|9    7|8|9

or

B|2|W    1|2|W    1|2|W    B|2|W    B|x|W
4|5|6 -> B|5|6 -> B|5|6 ?> 4|5|B -> 4|W|x
W|8|B    W|8|B    7|W|B    7|W|9    7|8|B

Alice will move 8 to 5, providing at least one move that cannot be blocked. So Bob must move to 5.

B|2|W    1|2|W    1|2|W    1|2|W
4|5|6 -> B|5|6 -> B|B|6 -> 4|B|6
W|8|B    W|8|B    7|W|B    7|W|B

Alice then moves 3 to 6 reducing the distance between the four stones to the minimum.

1|2|3
4|B|W
7|W|B

At this point Bob must move the black stone at 5 to either 2 or 4 allowing Alice to move either of her stones into the vacated point for the win.

Other possible moves for Alice yield the same results. As long as Alice always moves one of her stones towards the other, no matter how Bob blocks, eventually the stones will converge to minimal distance between the 4 stones and Bob will be forced to move away allowing Alice to move into the vacated point and take the win.

Expand to a 19x19 board and the results will be the same. Go Alice!

$\endgroup$
13
$\begingroup$

Assuming Alice goes first, Bob can win.

Bob can always makes a move that keeps the four stones as corners of a grid-aligned rectangle, with opposed corners belonging to opposite colors. Alice cannot get her two stones adjacent by making a move from such a position.

enter image description here

In more detail: Assume this invariant is true before Alice's move. We show how after Alice moves, Bob can make a move after which the invariant is again true.

Alice's move causes only one of the edges of the rectangle to break, by shifting to an adjacent column or adjacent row. Then, Bob can move his stone in that edge the same displacement, reforming that edge while keeping its other edge intact.

Doing so is always a legal move: it will be on the board because Alice's move was on the board, and no stone can be occupying the space because the other two are in a different and parallel row/column, as Alice cannot get both her stones onto the same row or column.

$\endgroup$
  • $\begingroup$ An alternate strategy would be to mirror Alice's move. If she moves the top stone down, you'd move your bottom stone up. So long as you keep the mirror in the same spot, you will guarantee that she can never get her stones to cross the mirror, thus preventing a win. $\endgroup$ – Trenin Jan 29 '15 at 17:56
  • 1
    $\begingroup$ Actually, that only works if the board is even. Since it's length is 19 (odd) Alice can get to the middle rank with this strategy and win. Your answer however, mitigates that. $\endgroup$ – Trenin Jan 29 '15 at 18:03
  • $\begingroup$ Hooray for strategy-stealing. $\endgroup$ – KSmarts Jan 29 '15 at 20:17
10
$\begingroup$

If Bob moves first, then Alice can win.

Alice's strategy is simple: Move her stones closer. We show that such a move is always possible, so the game can only end when Alice's stones are adjacent.

Bob's moving first induces a parity restriction. If we color the points of the go board in a checkerboard pattern, then each moves changes the checkerboard color of one of the stones. Since all stones start on the same color, after each of Bob's moves, and odd number of moves have been made, so there are an odd number of stones on each checkerboard color.

This means that if one of Bob's stones is next to one of Alice's stones, then Bob's other stone can't be next to Alice's other stone, or else there would be two stones on each checkerboard color. So, one of Bob's stones is always not impeding Alice's move. Therefore, Bob is only blocking two of the four moves Alice has to bring her stones closer, and so Alice has a move (two in fact) to do so. The exception is when Bob's stone is immediately in between two of Alice's stones on the same line, but Alice can avoid this by choosing not to put both her stones on the same line unless this wins immediately.

Note that Alice isn't slowed down by Bob at all: each of her moves decreases the Manhattan distance between her stones by 1, so she wins in 35 of her moves, same as if Bob wasn't there.

$\endgroup$
0
$\begingroup$

I believe Bob will always wins. He just has to "circle" a stone (adjacent vertically and horizontally).

Assuming the shortest way is to move just one stone in a "L" way, Alice needs 18 movements vertically and 17 movements horizontally (or viceversa). Meanwhile, in order to circle the static stone he just has to move 17 times vertically and 17 times horizontally.

Even if Alice starts, she will always be behind Bob's movements and by the time she gets one stone close to the other one, Bob will have it circled making it impossible for Alice to make the two stones adjacent.

$\endgroup$
  • 1
    $\begingroup$ What if you achieve this "L" pattern, but Alice then moves her other stone. You'd need to abandon the "L", which allows her stone to get free. $\endgroup$ – Trenin Jan 29 '15 at 17:58

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.