33
$\begingroup$

As follow up to Checkmate in $\omega$ moves?, we can ask the same question about go. Is there a position on a $\mathbb Z \times \mathbb Z$ goban such that either black can kill a white group, but white can stave off the capture for $n$ moves, or white can make a group live, but black can stave off life of the group for $n$ moves (for any $n \in \mathbb N$).

This is considerably trickier than chess, since go is more of a local game. My first thought is to use ladders somehow. The other thought is that the superko rule, since it actual has global influence.

(Although it does not matter too much, using Tromp-Taylor rules is probably best, since they are the simplest.)

$\endgroup$
9
  • 1
    $\begingroup$ must a "position" have finitely many stones in this game? $\endgroup$ Commented May 5, 2018 at 19:33
  • 1
    $\begingroup$ (also, "ladders" could provide a mechanism for such a construction.) $\endgroup$ Commented May 5, 2018 at 19:34
  • 1
    $\begingroup$ It's a nice question. But I find the title to be wrong (and I have similarly objected to the title of the infinite chess question), since the game value, when infinite, is not measuring the number of moves. Rather, a position has game value $\omega$, if the loser is in effect counting down from $\omega$, not up to $\omega$, and any such attempt will end in finitely many moves, not $\omega$ many. I would suggest the title: Is there a position in infinite Go for which the life of a particular stone has transfinite game value? $\endgroup$ Commented May 5, 2018 at 19:41
  • 2
    $\begingroup$ Yes, I was only objecting to the title---the question is great! Previous attempts to make sense of infinite Go have found difficulty with defining the winner at time $\omega$, since perhaps one has groups surrounding groups surrounding groups in a way that the density does not converge, and so it isn't clear who has won. The interesting innovation of this question, to my way of thinking, is changing the game to the life or death of a particular stone. $\endgroup$ Commented May 5, 2018 at 19:45
  • 3
    $\begingroup$ I created the infinite-games tag and added it to this question and a number of other questions. I plan to gradually add this tag to the many other infinite-game-related MO questions over the coming days and weeks. Anyone who is interested, please help with this! $\endgroup$ Commented May 6, 2018 at 2:01

1 Answer 1

38
$\begingroup$

This is a really great question!

Previous attempts to make sense of infinite Go have sometimes had problems because it wasn't clear how to define the winner of a game of Go after transfinite play. The problem was that perhaps a black group was surrounded by a white group, which was surrounded by a black group, and so on forever in such a way that the asymptotic density did not converge. In this case it wouldn't necessarily be clear who had more area. (Another separate issue is to define the state of the board at time $\omega$, in situations where stones had been placed and then killed unboundedly often; it seems most natural to keep only stones that had persisted from some time on.)

Your formulation of the problem gets around this difficulty by making the winner of the game depend on the life or death of a single designated stone. This makes the game an open game and therefore subject to the theory of transfinite open game values.

The answer is yes. There is a position with a black stone that is part of a group that white can definitely kill in finitely many moves, but black can make this take as long as desired.

Consider the following position.

A position in infinite Go with game value $\omega$

There are infinitely many stones, with black to play, and one should imagine that the pattern continues to the right. The designated black stone is part of the main infinite horizontal group of black stones, which continues to the right, with little black knobs poking down on the underside. This group is nearly surrounded and has only three liberties (at top) and no eyes. Because of the knobs, the surrounding white stones form separate groups, although they are nearly connected.

For each knob, black has the opportunity to make a hopeless cut, attempting to capture the two isolated white stones touching the end of the knob. For example, black could play at $A$, cutting the two white stones off on one side. This move is hopeless by itself, of course, because white can simply connect the two isolated stones on the other side at $B$, and then aim to kill the main black group shortly thereafter. So the hopeless initial cut is only valuable for black, if white should ignore it. There are similar such hopeless cutting moves at each knob.

A key point to observe, however, is that white cannot afford to follow the policy of always answering the hopeless cuts, since this would lead to infinite play, which is what black wants. So eventually, white will indeed have to ignore one of the hopeless cuts, in order to make progess on surrounding the main black group.

When white ignores the hopeless cut, then black will immediately play the other cut, with Atari on the two white stones. White cannot allow that black will connect the main black group to the live black group, and so white must extend. This leads to a ladder, which is ultimately broken by the lower isolated white stones.

The main thing to observe is that these ladder-breaking stones are further and further away as you consider successive knobs. Thus, black can choose to act on knob $n$, aiming to have a ladder of size at least $n$. After the ladder is played out, then the white stones in the ladder will gain sufficient liberties for white to kill the main black group shortly thereafter. So ultimately, the ladder is also hopeless for black, since white will eventually kill the main group; but the point is that black can prolong play as long as she likes, by choosing to act on a knob whose ladder is that long, even if she does lose after that.

So the main line play is as follows. Black makes a hopeless cut on the $n^{th}$ knob for some particular $n$, chosen as large as black likes. White cannot afford to always answer these hopeless cuts, because this would lead to infinite play. And so white will eventually choose to ignore the hopeless cut, playing instead so as to reduce the main black group to only two liberties. At this point, black gets to make the other cut, which leads to a ladder of $n$ forcing moves with black playing Atari on the white group at each step in the ladder. Ultimately, however, the ladder was hopeless, because it is broken by the isolated white stones. When this happens, the white stones in the ladder will get three liberties, which is not enough, since at this point white will make Atari on the main black group and then capture it, as black has no response. Note that after the ladder is broken, further hopeless cuts on other knobs are now truly hopeless, since white can answer them by capturing the main group.

In summary, white will eventually kill the main black group in finitely many moves, but black can choose any $n$ and play so as to postpone her loss of that group for at least $n$ steps. So the life-and-death of that group has game value $\omega$.

I believe that one could hope to modify the position to achieve much larger game values in Go. One could also modify the example by making the main black group much larger, so that it has asymptotic density 3/4, say, which would find tranfinite game values in the asymptotic density area calculation formulation of the game.

Update. Let me explain how to modify the position to achieve game value $\omega\cdot n$ for any finite $n$. What we do is give the main black group $n+2$ liberties, instead of only 3, and then also make the ladder-blocking white stone a live group. In addition, we can add a diagonal of white stones parallel to the ladder, just to ensure that black has no advantage to deviating from the main line.

With these revisions, black will be able to make $n$ hopeless cuts in succession, each leading to a ladder of length $n$ before the next begins, giving the game value $\omega\cdot n$ overall. Black may make $n$ announcements in all, with each being the length of play before the next announcement, until he loses his group at the end.

I'll try to post an image later. Next challenge: $\omega^2$.

$\endgroup$
15
  • 4
    $\begingroup$ Infinitely hilarious! :) Very, very good, in my opinion. $\endgroup$ Commented May 5, 2018 at 22:51
  • 1
    $\begingroup$ If one makes the main black group really huge, with asymptotic density more than half, then one can make an alignment between winning this version of the game and winning the asymptotic density version of the game. $\endgroup$ Commented May 5, 2018 at 22:59
  • 4
    $\begingroup$ "If only I had the time to play Infinite Go"... :) $\endgroup$ Commented May 5, 2018 at 23:02
  • 1
    $\begingroup$ @JoelDavidHamkins Concerning the winner of infinite go, you could just use a weighted sum. My question is essentially putting all the weight on one point. You could imagine other weight distributions. Another option is to use hyper-integer sized boards. $\endgroup$ Commented May 5, 2018 at 23:15
  • 1
    $\begingroup$ Another good idea. My solution shows that with any weighted system, there is a position with infinite game values. $\endgroup$ Commented May 5, 2018 at 23:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .