Formal definition of group


KarlKnechtel contributes his understanding and formalism: A group of stones is a set of stones on the board, such that

  • all stones in the set are the same colour;
  • each pair of stones in the set is joined by some path of orthogonally adjacent points (I am not about to attempt to define "path" formally; it should be obvious anyway ;) ), such that every point on that path is either empty or covered by a stone of the same colour;
  • the set is not a proper subset of another group. (For those unhappy with that recursion: There does not exist another stone of the same colour on the goban which is connected by any path as described above, to any stone in the set.)

Unfortunately, the term is sometimes also used to mean something similar to the above, except that empty points are not allowed in the paths. I.e, a set of stones of the same colour, all connected to each other by orthogonal adjacency. However, it seems that the term string has become preferred for such an entity.

These sorts of things may be intuitive even to beginners, but those with an interest in ComputerGo programming really need mind-boggling precision in these definitions, and it's often a lot harder to give that precision than you'd think (given that you don't have any difficulty with the concepts when you're actually playing Go ;) ). See also Formal Definitions of Eye.

Surely this definition isn't very useful? In many games, there will only be two groups on the board (one black, one white) until late in the middle game.

Thanks for the definition Karl. To paraphrase then, a maximal subset of the stones of one color connected by stones of the same color or empty points. For the definition of string or unit, just remove the 'or empty points' clause. I agree that it seems like this definition may not be useful in the early or mid-game. We may have to invoke some sort of localness condition. Again, thanks. --DaveFinlay

BobMcGuigan: I think the second point in the definition needs some refinement. According to the definition given the black stones in the diagram below are one group. Is that really what you want?

19x19 diagram  

The points marked with squares show the required path. I think of stones in a group as being connected somehow, even if not strictly connected.

The problem is how to capture this sense of "wholeness" of the group when the stones could be quite far apart.

unkx80: Hardly possible to formally define a group, because this term is used very loosely. For a heuristic, you may consider some influence function: if two chains are connected in a path whose length is no more than alpha and the influence value of each point on the path is no less than beta, then these two chains are part of a larger group. Of course, you have to determine the alpha and beta values yourself.

RobertJasiek: If visible-group is what shall be defined, then this can rely on string hulls and iteratively nearer sector lines. String hulls are needed when strings bend themselves. In the example above, the sector line between the two white strings is nearer to the intersection in between than any sector line between the two black strings. Therefore the white sector line cuts the black ones. Interpreting this, we have two black visible-groups. Defining all this carefully and also considering crosscuts and the edge of the board is not trivial though.

Elroch: KarlKnechtel's definition has the benefit of being very clear and computable, and the disadvantage of being not close to a useful concept if the board is fairly open. My starting point for a definition is "a group is a set of stones of the same colour that could, in principle, be connected into a single chain regardless of what the opponent does." This definition imagines the whole object of an artificial game is to turn the group into a chain. Any thoughts on how this could be developed/replaced?

Formal definition of group last edited by Elroch on October 24, 2007 - 19:48
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Login / Prefs
Sensei's Library