Chasing game on the Go board

Question

In Go (Weiqi), two players take turns placing stones on the vacant points of a board. Once placed, stones can only be removed from the board if a stone or a group of stones are surrounded by their opponents on all orthogonally adjacent points, in which case the stone or group is captured.

---

Now we consider a variant of the game. A black stone is put on the center of an empty 19*19 Go board, and then the white player puts its stones on the vacant points. Different from traditional rules, the black will not put any other stones on the chessboard. Instead, he can move his unique stone to all orthogonally adjacent points on the board at will, as long as there is no white piece on the target point.

---

When the black moves one step, his opponent will take turns placing a white stone on the vacant points to intercept the black, until it is surrounded by white stones on all orthogonally adjacent points, in which case the black stone is captured and the white wins. If the black stone makes it to flee to the edge of the chessboard without being captured, the black will win.

Then my questions are:

1. How many white stones at least are needed to capture the only black stone? Or the black player is destined to win the game?
2. What if the board is infinite without the edge? Would the black be destined to win in that case?

Answer 1

second edit

Just for completeness, I'll write my own solution from the edit with Wlod AA's notation, in the case where we don't allow the angel to repeat a position (in which case we can't conclude anything about the number of stones, but can conclude something about the size of board needed).

As mentioned there is essentially only one thing that can happen in this strategy as well, but it takes twice as long as the strategy of Wlod AA, there are some sidelines, and I need a bounding box that is one cell larger. (As mentioned in a comment, one may interpret the difference as follows, in my terminology: Wlod AA skips straight to the pivot part by pretending there is a pivot at $(0, 1)$, and sidelines are skipped by adding a few lemmas.)

$$ P_1 := ((1 \; 0) \; \emptyset) $$ $$ P_2 := ((1 \; 0) \; \{(2 \; 0)\}) $$ $$ P_3 := ((1 \; 1) \; \{(2 \; 0)\}) $$ $$ P_4 := ((1 \; 1) \; \{(2 \; 0) \; (1 \; 2)\}) $$ Now we have two choices for the angel. Either they continue running in the cage, or they go right and we begin the pivot process. (As Wlod AA points out, this can be seen as a form of recurrence, but I did not realize this.)

While running around the cage we just drop stones in front of the angel, and this looks like $$ P'_5 := ((0 \; 1) \; \{(2 \; 0) \; (1 \; 2)\}) $$ $$ P'_6 := ((0 \; 1) \; \{(2 \; 0) \; (1 \; 2) \; ({-1} \;1)\}) $$ $$ P'_7 := ((0 \; 0) \; \{(2 \; 0) \; (1 \; 2) \; ({-1} \;1)\}) $$ $$ P'_8 := ((0 \; 0) \; \{(2 \; 0) \; (1 \; 2) \; ({-1} \;1) \; (0 \; {-1})\}) $$ Now you cannot avoid a literal repetition of the position (though indeed we could see the origin as a repetition already). We have to enter a sticky situation.

The angel might as well have entered the sticky situation immediately, and we continue the main line from the fifth step. $$ P_5 := ((2 \; 1) \; \{(2 \; 0) \; (1 \; 2)\}) $$ $$ P_6 := ((2 \; 1) \; \{(2 \; 0) \; (1 \; 2) \; (3 \; 2)\}) $$

The angel should not go north, as that is a trap (this is Wlod AA's Remark 3): $$ P''_7 := ((2 \; 2) \; \{(2 \; 0) \; (1 \; 2) \; (3 \; 2)\}) $$ $$ P''_8 := ((2 \; 2) \; \{(2 \; 0) \; (1 \; 2) \; (3 \; 2) \; (2 \; 3)\}) $$ and angel is forced to repeat.

We continue the main line, and repeat the above reasoning for any deviation from the pivot, and get $$ P_7 := ((3 \; 1) \; \{(2 \; 0) \; (1 \; 2) \; (3 \; 2)\}) $$ $$ P_8 := ((3 \; 1) \; \{(2 \; 0) \; (1 \; 2) \; (3 \; 2) \; (4 \; 1) \}) $$ $$ P_9 := ((3 \; 0) \; \{(2 \; 0) \; (1 \; 2) \; (3 \; 2) \; (4 \; 1) \}) $$ $$ P_{10} := ((3 \; 0) \; \{(2 \; 0) \; (1 \; 2) \; (3 \; 2) \; (4 \; 1) \; (4 \; {-1})\}) $$ $$ P_{11} := ((3 \; {-1}) \; \{(2 \; 0) \; (1 \; 2) \; (3 \; 2) \; (4 \; 1) \; (4 \; {-1})\}) $$ $$ P_{12} := ((3 \; {-1}) \; \{(2 \; 0) \; (1 \; 2) \; (3 \; 2) \; (4 \; 1) \; (4 \; -1) \; (3 \; {-1})\}) $$ $$ P_{13} := ((2 \; {-1}) \; \{(2 \; 0) \; (1 \; 2) \; (3 \; 2) \; (4 \; 1) \; (4 \; {-1}) \; (3 \; {-1})\}) $$ $$ P_{14} := ((2 \; {-1}) \; \{(2 \; 0) \; (1 \; 2) \; (3 \; 2) \; (4 \; 1) \; (4 \; {-1}) \; (3 \; {-1}) \; (1 \; {-1})\}) $$ $$ P_{15} := ((1 \; {-1}) \; \{(2 \; 0) \; (1 \; 2) \; (3 \; 2) \; (4 \; 1) \; (4 \; {-1}) \; (3 \; {-1}) \; (1 \; {-1})\}) $$ $$ P_{16} := ((1 \; -1) \; \{(2 \; 0) \; (1 \; 2) \; (3 \; 2) \; (4 \; 1) \; (4 \; {-1}) \; (3 \; {-1}) \; (1 \; {-1}) \; (0 \; {-1})\}) $$ and the angel is forced to repeat.

edit

As used Wlod AA points out, the optimization of the number of stones feels more like a computer science problem than a math problem, so maybe I should point out some simplifications if we just want an upper bound on the Manhattan distance we can travel.

We can use an idea that is classical for this game. Namely, I claim we may assume the Angel never repeats a position (in the sense that it never lands on a cell it has already visited).

Consider the maximal Manhattan distance the Angel can travel, and take a strategy $S$ that takes it the furthest from the initial point against any Devil strategy.

Make a new strategy for the Angel, where at each position, it looks at all possible ways the game can continue, depending on the Devil's strategy played against $S$. Among all these continuations, and among those the set of all turns where the current node is (re)exited, there is one after which the Angel gets the furthest before reentry (or before being trapped). Now just move directly in that direction, and pretend there are imaginary stones where the Devil would've put them.

Now the cage argument is trivial, the Angel with the new strategy will run in a circle and after a few moves it reaches a sticky situation. The pivot running is also simplified, you can just run around until you reach the end.

original

After the clarifications, this seems to be a version of Conway's Angel(s) and Devil(s) game, where the Angel is restricted to only cardinal movement. Usually it is allowed to move also diagonally (so like a chess king). Even if allowed diagonal movement, it is a result of Berlekamp that the Devil has a winning strategy if the game is played on the infinite plane.

I didn't look at Berlekamp's proof, but Conway writes in [1] that the strategy works on a $32 \times 33$ board. I looked also at the strategy given by Kutz and Pór [2], and if you follow it literally, I am not sure 19x19 suffices. However, with our more restricted speed 1/2, I think it is easy to give a winning strategy for the Devil directly.

I will call the players Angel and Devil following Conway. The black stone is also called the Angel, while I'll call the white stones stones, following the post.

I'll describe a naive strategy that gives an upper bound of 19 stones, where the Angel never moves more than $4$ steps away from the original position in Manhattan distance. In particular I claim that the Devil wins on a $11 \times 11$ board already. Furthermore, we track the movement of the Angel, and the Devil only puts stones directly in front of the Angel (after it moves) or diagonally in front, i.e. if the Angel moves east (I'll use cardinal directions), the devil will put the next stone stone east, southeast or northeast.

The Devil's strategy

The idea is as follows: The Devil wants to force the Angel into a situation where it is the Angels's turn, and the Angel has a stone (called the pivot) to the south, to the northwest, and northeast (or some rototranslation of this situation). Let's call this the sticky situation (because we'll show that the Angel is stuck to the pivot stone).

In picture form, where $S$ and $P$ are stones ($P$ the pivot stone) and $A$ is the Angel: $$\begin{array}{ccc} S & . & S \\ . & A & . \\ . & P & . \end{array}$$.

I claim that once in a sticky situation, the Angel is captured after at most 11 more stones are added, and the Angel will never be able to travel more than Manhattan distance 2 away from the pivot.

To achieve this, we'll indeed force the Angel to run around the pivot. If in the sticky situation, no matter where the Angel moves next, we will introduce a stone in front of it. If it moved north, it will be forced to come back south and return to the sticky situation. If it moved east, it is forced to come back or move south. If it moves south, we introduce a stone southeast of it, and it is back to another sticky situation.

In picture form, the aim is to keep going towards the following constellation, where $P$ is the pivot stone, $s$ are stones that are added on a per need basis, and $S$ are the stones ensuring the Angel rotates around the pivot: $$\begin{array}{ccccccc} . & . & . & s & . & . & . \\ . & . & S & . & S & . & . \\ . & S & . & . & . & S & . \\ s & . & . & P & . & . & s \\ . & S & . & . & . & S & . \\ . & . & S & . & S & . & . \\ . & . & . & s & . & . & . \\ \end{array}$$

At some point, the Angel repeats a position, and we can stop its movement around the pivot and trap it with at most 4 extra stones. So you need at most the $S$ stones, one of the $s$ stones, and 4 extra trapping stones. We assumed two $S$s were already in place so that's at total of 11.

To get the Angel into a sticky situation is easy. Namely, as long as the Angel avoids a sticky situation, it can be confined into a $2 \times 2$ area by just always putting stones in front of it when it moves.

I.e. the idea is to keep building this cage: $$\begin{array}{cccc} . & S & S & . \\ S & . & . & S \\ S & . & . & S \\ . & S & S & . \\ \end{array}$$ If the Angel never escapes from here, eventually we catch it with at most 11 stones in total.

If it escapes, a naive upper bound on the number of stones is the bounds of that box minus the escape corner plus the stone making the situation sticky (8 stones), after which the situation would be (up to rototranslation): $$\begin{array}{ccccc} . & S & S & . & S \\ S & . & . & A & . \\ S & . & . & P & . \\ . & S & S & . & . \\ \end{array}$$ and then the 11 stones from the previous strategy for a total of 19. Of course these overlap, i.e. if the box is in place we could shave several stones from the previous strategy.

Finally, to get the upper bound on Manhattan movement, observe that when we escape the cage, the pivot is at most two steps away from the original position (two of the cage stones are at distance $3$, but cannot actually become pivots as far as I can tell). And we don't get more than distance $2$ way from the pivot.

---

There are admittedly some points where I would either need to introduce some more concepts, or do the case analysis for a precise proof. I played this enough in my head to be completely sure I didn't miss anything, but games can be tricky... I'm not an expert but maybe one can get the upper bound by computer with just minimax+$\alpha\beta$+memoization, that might be something to try.

Also, if someone is interested in turning the arrays above into something more artistic, feel free of course.

References

[1] Conway, John H., The Angel problem, Nowakowski, Richard J. (ed.), Games of no chance. Combinatorial games at MSRI. Workshop, July 11–21, 1994 in Berkeley, CA, USA. Cambridge: Cambridge Univ. Press. Math. Sci. Res. Inst. Publ. 29, 3-12 (1997). ZBL0872.90133.

[2] Kutz, Martin; Pór, Attila, Angel, devil, and king, Wang, Lusheng (ed.), Computing and combinatorics. 11th annual international conference, COCOON 2005, Kunming, China, August 16–29, 2005. Proceedings. Berlin: Springer (ISBN 3-540-28061-8/pbk). Lecture Notes in Computer Science 3595, 925-934 (2005). ZBL1128.91312.

Answer 2

Request:   please, leave my notation alone.

---

---

Everything below is VERY SIMPLE while writing it down was still a tough challenge for me (the introduced terminology may be used in a follow up, under much more general circumstances).

The board:

I'll represent the GO (weiqi) board as

$$ \{(x\ y)\in\mathbb Z^2:\ \max(|x|\,\ |y|)\ \le\ 9\} \ \subseteq\ \mathbb Z^2 $$

It's smoother to define the game for the entire $\ \mathbb Z^2.\ $ Then one can show that only a small part of it -- actually, a small part of the GO board -- is sufficient for catching the sole black stone.

We assume the Manhattan metrics in $\ \mathbb Z^2$:

$$ \forall_{(u\ v)\ (x\ y)\in\mathbb Z^2}\quad d((u\ v)\,\ (x\ y))\ :=\ |x-u| + |y-v|\qquad $$

There are the obvious exactly eight linear isometries of $\ \mathbb Z^2.$

---

GAME

A position is an arbitrary ordered pair $\ P\ :=\ (b\ X)\ $ such that $\ X\subseteq\mathbb Z^2\ $ is finite, and $\ b\in\mathbb Z^2\setminus X.$

Position $\ \mathbf I\ :=\ ((0\ 0)\ \ \emptyset)\ $ is, by definition, the initial position.

An odd-move, also called a black move, in position $\ P:=(b\ X)\ $ is an arbitrary $\ c\in\mathbb R^2\setminus X\ $ such that $\ d(b\ c)=1.\ $ The resulting position is defined as $\ Q:=(c\,\ X).$ An odd-move $\ c\ $ is said to be original $\ \Leftarrow:\Rightarrow\ c\ $ is different from all previous moves.

An even-move, also called a white move, in position $\ P:=(b\ X)\ $ is an arbitrary $\ y\in\mathbb Z^2\setminus\{b\}.\ $ The resulting position is defined as $\ Q:=(b\ Y),\ $ where $\ Y:=X\cup\{y\}.\ $ (Even-move $\ y\in X\ $ would be silly but legal).

A game-score is an arbitrary finite or infinite maximal (non-extensible) sequence of consecutive positions $\ G\ :=\ (P_0\ P_1\ \ldots),\ $ where three conditions are satisfied:

• $ P_0 := \mathbf I; $
• each position $\ P_{2\cdot n+1}\ $ is a result of an odd-move (done by the sole black stone);
• each position $\ P_{2\cdot n}\ (n>0)\ $ is a result of an even-move (done by adding a white stone, if any).

Remark 1   every finite game-score ends in an odd-indexed position.

The set $\ T(G):=\{(0\ 0)\}\cup\{b_{2\cdot n}:\ n=0\ 1\ldots\}\ $ of all odd-indexed positions of $\ G,\ $ plus the origin, is called the trace of game $\ G.$

---

Winning:

Let $\ W\subseteq\mathbb Z^2\ $ be an arbitrary finite set. Game $\ G\ $ is $W$-won (by white stones) $\ \Leftarrow:\Rightarrow\ T(G)\subseteq W\quad $ (white stones can be played outside of $W\ $ (!))

Set $\ W\ $ is a winning domain $\ \Leftarrow:\Rightarrow\ $ the player of the white stones has a strategy, call it $W$-strategy, under which every game is $W$-won (regardless of the choice of the black stone moves).

If finite $\ W\ $ is not a winning domain then we say that the black stone defeats $\ W.$

Theorem 1   If the black stone defeats finite $\ W\ $ then it can defeat $\ W\ $ by playing original moves only.

Actually, a stronger theorem holds. We say that odd move $\ c\ $ that leads to position $\ P_{2\cdot n+1}:=(c\ Y)\ $ stumbles $\ \Leftarrow:\Rightarrow c=(0\ 0)\ $ or there exists an earlier position $\ P_{2\cdot k+1}:=(b\ X)\ \ (k<n),\ $ and a linear isometry $\ S:\mathbb Z^2\to\mathbb Z^2\ $ such that

• $\ S(W)=W,\ \ $ and
• $\ X\subseteq S(Y).$

Theorem 2   If the black stone defeats finite $\ W\ $ then it can defeat $\ W\ $ without ever stumbling.

Remark 2   Consider black stone's move $\ c\ $ such that there is only one nearest neighbor point that is not occupied by white stones. Then the white stone player wins immediately by setting a new white stone on the point that was left by the black stone just a moment ago.

Remark 3   Consider black stone's move $\ c\ $ such that there are exactly two nearest neighbor points that are not occupied by white stones. Then the white stone player can force the black stone into a repetition (hence stumbling) of its previous move by playing a new white stone onto the unoccupied nearest neighbor of $\ c\ $ different from the previous black stone move (one before $\ c$).

Theorem 3   If the black stone defeats finite $\ W\ $ then it can defeat $\ W\ $ without ever stumbling, and by playing moves $\ c\ $ such that there are (at the time) at least three nearest neighbors of $\ c\ $ that are not occupied by white stones.

---

THEOREM 4   Set

$$ V\ :=\ \{(x\ y)\in\mathbb Z^2:\ |x|+|y|\le 3\} $$

is a $25$-point winning domain.   (See the proof below).

I'll present a (natural) $V$-strategy against which the black stone has essentially only one non-nonsense defense.

---

Proof

We have $\ P_0=\mathbf I.\ $ Due to the symmetry of $\ V,\ $ we may assume that

$$ P_1\ :=\ (\,(1\ 0)\ \ \emptyset\,) $$

Let me play white stones, I am playing $\ (2\ 0)\ $ hence

$$ P_2\ :=\ (\,(1\ 0)\ \ \{(2\ 0)\}\,) $$

Black move back to $\ (0\ 0)\ $ would create a position inferior to $\ \mathbb I.\ $ Up to a symmetry, only one black move $\ (1\ 1)\ $ is left:

$$ P_3\ :=\ (\,(1\ 1)\,\ \{(2\ 0)\}\,) $$

Now, let me play move $\ (2\ 2)\ $ hence

$$ P_4\ :=\ (\,(1\ 1)\ \ \{(2\ 0)\,\ (2\ 2)\}\,) $$

Then the black stone's moves $ (1\ 0)\ $ and $\ (1\ 0)\ $ would stumble, and $\ (2\ 1)\ $ would have only two unoccupied nearest neighbors. Thus, only one move $\ (1\ 2)\ $ is left:

$$ P_5\ :=\ (\,(1\ 2)\ \ \{(2\ 0)\,\ (2\ 2)\}\,) $$

Now, I am forced to play $\ (1\ 3),$

$$ P_6\ :=\ (\,(1\ 2)\ \ \{(2\ 0)\,\ (2\ 2) \,\ (1\ 3)\}\,) $$

Here, the black stone has only one non-stumbling move $\ (0\ 2),$

$$ P_7\ :=\ (\,(0\ 2)\ \ \{(2\ 0)\,\ (2\ 2) \,\ (1\ 3)\}\,) $$

Thus, let me play $\ (-\!1\ 3),$

$$ P_8\ :=\ (\,(0\ 2)\ \ \{(2\ 0)\,\ (2\ 2) \,\ (1\ 3)\,\ (-\!1\ 3)\}\,) $$

In the view of the earlier remarks, there is only one non-nonsense black stone's move $\ (-\!1\ 2),$

$$ P_9\ :=\ (\,(-\!1\ 2)\ \ \{(2\ 0)\,\ (2\ 2) \,\ (1\ 3)\,\ (-\!1\ 3)\}\,) $$

Now, move $\ (-\!2\ 2)\ $ is forced,

$$ P_{10}\ :=\ (\,(-\!1\ 2)\ \ \{(2\ 0)\,\ (2\ 2) \,\ (1\ 3)\,\ (-\!1\ 3)\,\ (-\!2\ 2)\}\,) $$

Then the only black stone's non-stumbling move is $\ (-\!1\ 1),$ $$ P_{11}\ :=\ (\,(-\!1\ 1)\ \ \{(2\ 0)\,\ (2\ 2) \,\ (1\ 3)\,\ (-\!1\ 3)\,\ (-\!2\ 2)\}\,) $$

Finally, let me play $\ (-\!2\ 0),$

$$ P_{12}\ :=\ (\,(-\!1\ 1)\ \ \{(2\ 0)\,\ (2\ 2) \,\ (1\ 3)\,\ (-\!1\ 3)\,\ (-\!2\ 2)\,\ (-\!2\ 0)\}\,) $$

Here the black stone doesn't have any non-nonsensical moves.

END of Proof