Four stones on a Go-board

Question

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

Answer 1

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!

Answer 2

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.

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.

Answer 3

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.

Answer 4

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.