Maximum Number Of Live Groups
Independently Live groups on a Goban.
I found this in the IGS ftp archive some years ago, and the discussion in False Eye reminded me.
Cool, no?
(I've changed some of the formatting to 'suit' the wiki, but none of the contents)
-- Morten Pahle
How many live groups can there be on a go board?
Subject: Number of live groups. From: wft@math.canterbury.ac.nz Bill Taylor
Yijun Ding asks what is the maximum possible number of groups in a game.
Yes; I know he was asking for a practical maximum, for computer programming purposes, rather than a theoretical one; but I choose to interpret it the latter way. After all, it's clear that there's way too many computer scientists on rec.games.go and not nearly enough mathematicians ;-) .
Anyway, the question, the maximum possible number of groups on the board, has two interpretations (at least).
1: Maximum number independently alive. 2: Maximum number alive in seki (or similar).
Both of these are difficult to define unambiguously, without 134 densely printed pages of Japanese-style-rule bookishness. However we'll take for granted, (temporarily), that we all know what we mean.
It's already been mentioned that things like might be considered as either one or two groups, but I'll assume that it's clearly one, in the spirit of the regular rules.
- derPlumps: This should be "6 groups" according to diagram 1
Whereas something like this (on a 4x4 board), would have to be counted as four groups, two black and two white. The separate halves of the black groups are `connected' by a uni-colored eye; this doesn't hold for the two white bits.
Anyway, none of this appears to be relevant for the answers to questions 1 and 2 above; on a 19x19 board at least.
I get answers of 28, and 60, respectively.
As always, I would be delighted to see anyone write in with improvements.
Here are my solutions.
From: smith@pell.anu.edu.au (Michael Smith)
I didn't have time to fine tune this -- It might be possible to get an extra group one the edge somewhere.
Simply based on regular pattern in capital stones :-) which are a more efficient way of covering the board than the way you chose:
Instead of 15 intersections for the groups in the centre, I only use 12.
However I only get one extra fully alive group for a total of 29:
But I think with a bit more thought I can fine tune this.
Next question is how can you PROVE that a certain number is the maximum - apart from trying every combination of alive stones on a board and counting.
TapaniRaiko: One can count the points used by each group. They should add up to at most 361. In the corner a group takes up at least 8 points. In the middle, it takes up 12. In the border, it takes up 10 points consuming 4 points of the border or 11 points consuming 3 of the border. It seems that this leads to a maximum of 33 groups.
This one is not a part of the thread, but I thought it should be added here.
I could not find a way to rearrange the marked area to any shape that could contain a live white group. (circled stones would be black then)
Anyway, 30 groups fit quite nicely :-)
-- Bass
From: wft@math.canterbury.ac.nz (Bill Taylor)
Following up my own post, I'm able to improve one of my records for the maximum number of live groups on a go board.
The formation is....
From: wolfe@vina.Berkeley.EDU (David Wolfe)
I've worked on the problem of fitting the most live "strings" on a board, where a string is a connected group of stones, and a live string includes life in seki.
My understanding of Niek van Diespen's posting is that the solution is somewhere in the 130's:
- >Sometimes I'm simply too fast: Ger Hungerink also addressed the version with seki's. I did not put too much time in that, but the maximum is somewhere in the 130's, if I remember correctly. My last posting of course only addressed the "Independently alive" case.
I have a solution which has only 108 strings, and solves Bill Taylors original posting as well with 104 groups:
From: herbison@manage.enet.dec.com (B.J.)
- >I have a solution which has only 108 strings, and solves Bill Taylors original posting as well with 104 groups:
There are two white groups in this diagram with three liberties. (I circeled them to make them stand out.) From this configuration, white can capture most of the board.
From: wft@math.canterbury.ac.nz (Bill Taylor)
I've been plugging away at this business of maximum number of LIVE groups possible on the board. (Of course without the "live" restriction, the checkerboard patterns that have been posted will easily win).
I'm now convinced that the best patterns will have a basic shape like that shown here, which must be the max possible density of live groups in an infinite board. (These groups are only alive in seki, of course.)
This density is noticably better than any other solutions seen on the net.
It's a bit tricky fitting in stuff round the edges of a finite board, though. In view of the messy nature of my solution, and the alleged Dutch publication of a 130-odd group formation, I'm far from sure this is best possible. It must be close though.
So here's my solution:
- 128 groups (counting orthogonal connections only)
- 114 groups (counting 2 bits joined by an eye as the same)
Interestingly, (in Chinese counting), the result of the game is an exact tie ! ( 151 points each, with 59 neutral).
From: maiorana%idacrd.uucp@princeton.edu (James Maiorana)
This article is in reponse to wft@math.canterbury.ac.nz (Bill Taylor)'s message dated 21 May 92 04:19:15 GMT. He writes
- >I'm now convinced that the best patterns will have a basic shape (like that shown above) which must be the max possible density of live groups in an infinite board. (These groups are only alive in seki, of course.) This density is noticably better than any other solutions seen on the net.
There is also a variation on this configuration that proves useful, namely:
Here we have shown only a single strip. These strips can be put together to cover an infinite board. This second configuration allows the boundary connectivity to change phase.
He also writes
- >It's a bit tricky fitting in stuff round the edges of a finite board, though. In view of the messy nature of my solution, and the alleged Dutch publication of a 130-odd group formation, I'm far from sure this is best possible. It must be close though.
- >So here's my solution;
- 128 groups (counting orthogonal connections only)
- 114 groups (counting 2 bits joined by an eye as the same)
- 128 groups (counting orthogonal connections only)
We were able to get to the 130-odd group level. We found the following:
This arrangement has 132 groups (in the sense of connected components).
HandOfPaper: Shouldn't the phrase you want be " monochromatic connected components "? Otherwise, you would have only 8 of them...
If we allow connections though empty intersections, then the connected components combine to form 65 areas. The three circles are empty intersections that behave as false eyes (as opposed to seki points).
The false eyes at F6 and Q16 are the centers of "windmills". These windmills are there to solve phase problems with the edges of the board. Each one forms a single area with 4 connected components. The false eye at T1 is the center of another windmill. This rearrangement of that corner makes this clear.
This rearrangement does not change the area or component counts.
blubb: If you really count strings (i. e. groups "in the sense of connected components") - what about this? :P
Well, this is better:
Global seki?
All these seki examples deal with locally stable solutions. But what about this pattern?
If one player moves, is there any safe way to the opponent to win the game? Or, on the contrary, is there any safe way the first moving player wins the game? Perhaps it is something you could call a "global seki"? - Although i´ve been trying to analyse it for quite a while, I still don't know anything about that. So, if you're sure that it's not stable at all, which means moving first has a positive value here, just remove it. :) --rubilia
(Sebastian:) Well, that's what it's a game for - let's play it: Odd Dots Go Ongoing Game
blubb: For more discussion on this idea see Global Seki, and about this particular position as well as the amazingly complex resulting game, see DotsGo.
Random reader?: If you turn the board by 45 degrees, the resulting game is equivalent to a diagonal-go on a diamond board. Diagonal go means white stones have liberties and capture in one slant-direction, while the black stones capture along the crossing slant. This is a fair-game, and it is similar to go, although more complicated. This is not technically "life and death", it is a go variant.
---
Maximum number of (not alive) groups?
lefuet: if we drop the restriction of live groups, how many can be fit on a goban? heidi_row brought up an upper bound: 0.8 times 361. A bid less because of the edge. This can be motivated as follows: One stone could have at most 3 groups as neighbor and an empty intersection. So here we have 5 intersections (the stone and his 4 neighbor intersections) of wich 4 contain different groups. So on every 5 intersections there can be a maximum of 4 different groups. So 0.8 * 361.
This is such a pattern. Because of the edge some stones have to be removed. On every edge 3 stones have to be removed making this 288 - 12 = 276 groups. This is at least close to the optimum.
Gunnar Farnebäck: The maximum number is 277 on 19x19. For more information, see http://computer-go.org/pipermail/computer-go/2006-December/007398.html
George Caplan 31 two eyed groups are possible, 42 one eyed groups are possible and 129 alive in seki groups are possible.
Morten: I am not sure that is correct. Please read Maximum Number Of Live Groups or provide some justifaction for your statement..
George Caplan I am not sure either, but my source is "Harry Fearnley's Wierd Go Problems" -- see http://harryfearnley.com/go/bestiary/brain_hurts.html -- which is linked on the AGA website under "Problems".
Unsettled groups everywhere, and not a ko to be found... ~srn347
Toroidal Go Board
How many live groups can fit on a toroidal go board?