Skip to main content
2 of 4
a def repeated usefully
Wlod AA
  • 4.8k
  • 17
  • 23

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 $\ (2\ 1)\ $ 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 $\ (0\ 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_{11}\ :=\ (\,(-\!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

Wlod AA
  • 4.8k
  • 17
  • 23