Recently I was revisiting Harry Fearnley’s collection and became interested in this position from a Dutch magazine:
White cannot make a living group even with an arbitrary number of moves in a row, and it seems like this may be the least amount of black stones required to achieve this (although I’m not sure anyone has claimed that it actually is optimal, so feel free to try to improve it!).
Obviously this question will not get more interesting on bigger boards (20x20, 21x21…), since the same pattern can be easily extended. But how about small boards?
Here are some quickly thrown together solutions for sizes 2-5 to get us started:
2x2
Obviously optimal, since just one stone can’t prevent white from making this shape instead. The two black stones could possibly be placed next to each other, since even after white captures making two eyes is not possible… but if suicide is legal, or if superko is used, white would actually live. So better keep it straightforward like above.
3x3
Obviously optimal, since two stones can always be captured. This strategy of dividing the board in two is very powerful here, but doesn’t really work on bigger sizes (except for 3xN), since it relies on white not being able to form even a false eye inside either territory. Note for instance that surrounding a single corner with three stones wouldn’t work.
4x4
Six stones can be done in a number of different ways, but I can’t make five work. I suspect six is optimal but haven’t proved it.
5x5
This solution wasn’t as immediately obvious to me as the other ones. It seems optimal but I haven’t proved it yet.
Edit: Just realized that we could simply extend the 4x4 pattern for an alternative 8-stone solution with more symmetry:
But we can’t keep extending like this for bigger sizes, since then there’s too much room in the corner!
Would anyone like to try their hand at sizes 6, 7, 8, 9? Or perhaps some rectangular boards?
At some point the solutions will start to look very similar to the 19x19 solution, but based on the diversity of sizes 2-5 I think we will see some more interesting ones before then!
Here’s some more attempts:
(didn’t try super hard to optimize these, so I’m sure there’s improvements possible!)
6x6, 12 stones
7x7, 17 stones
8x8, 23 stones
9x9, 28 stones
Table of upper bounds so far
Size
Stones
2
2
3
3
4
6
5
8
6
12
7
17
8
23
9
28
Looking at the 19x19 pattern, it seems very likely that the values will trend to (n^2)/3 for big boards. The fit actually isn’t half bad already for these values:
(dotted line = (n^2)/3, red line = values from table above)
(sorry for bad plot, plotting is not my strong suit )
Improvements inspired by the original 19x19 solution:
7x7, 16 stones
8x8, 21 stones
9x9, 27 stones
Now there are only two values which do not agree with the simple formula:
size
stones
floor(area/3)
0
0
0
1
0
0
2
2
1
3
3
3
4
6
5
5
8
8
6
12
12
7
16
16
8
21
21
9
27
27
19
120
120
(sizes 0 and 1 thrown in for completeness… white can’t make a living group on 0x0 or 1x1 board )
Note that for square boards, floor(area/3) = round(area/3), since n2 mod 3 ≠ 2. It remains to be seen whether flooring or rounding fits better for rectangular boards.
So do you think the 4x4 is an exception because it might be impossible to make a living shape with less than 6 stones, that is living in the sense of passing forever as opposed to the usual sense? (given a big enough board I suppose has to be added)
Well 4x4 is small enough that 5 stones suffices to be pass-alive, it’s just unfortunate that it leaves enough space for white to live…
I would say that it’s not surprising that small boards show some irregularites, the surprising part is how quickly the approximate formula is (as far as we can tell so far) exact!
The reason the values approach area/3 in the limit is of course this repeating pattern where the stones make up exactly 1/3 of the area:
This tells us that the sequence should be n2/3 + O(n), but a priori there’s no reason to expect it to be close to n2/3 for small n.
For instance, if we try this other repeating pattern, which also covers exactly 1/3 of the area:
… we find that “finishing off” the chains when they reach the edges requires a lot more work, so the O(n) term is a lot more noticable.
I’m happy to see that this thread is still getting some interest, so let me share a few more diagrams to make the “obvious” repeating pattern a bit more explicit
Here are solutions for 8x8, 9x9 and 10x10:
In each case, number of stones = floor(area/3). To create a solution for any larger square board, pick the boardsize above with the same remainder mod 3, then extend the repeating pattern down and to the left.
For instance, 9x9-solution gets extended to 12x12-solution like so: (newly added stones in white)
This “proof by ellipsis”, along with the earlier solutions for sizes 5 to 7, establishes:
Theorem. On an n*n go board with n > 4, the number of stones required to prevent the opponent from making a living group (even with an arbitrary number of moves) is at most n2/3.
It also seems extremely likely that this is optimal, except for possibly some minor improvement we’ve missed on the small boards (before the regular pattern kicks in around size 8).
I searched different patterns.
My quick result is to be optimal:
(If you go with not small boards which are specific cases)
Black need two eyes. If not you need to prevent white to make eyes or fake eyes, see at the end of the post)
Black stones should form one group only (or you need more eyes and you will have more sub areas to manage).
Note that the double snake pattern with two fake eyes to live doesnt seem that efficient.
It’s better to use the corner as the center to make the two eyes.
When there is a central axe symetry, it’s interesting to use it to spare moves although i didn’t succeed on a 9x9.
One approach could be useful for exploring when black don’t have two eyes is to deny white to make smallest living shapes for n-2 sub areas, if n is the number of subareas. And to have no eyes or fake eyes at all in the remaining two areas.
)
)
