2
$\begingroup$

I would like to write an analysis of go positions. Part of it requires me to determine the "groups" on the board and count their "liberties".

Any Go "position" is a collection of black x white o and empty . on the board. So I using an 2D array.

o.x.xxx..x
xoo.xoxxoo
....x...ox
.ox.o.o.o.
xox..xx...
.xox.x.xx.
o..oxxoooo
..o..xxo.o
.o...oxoo.
.xo..oxxox

I need to identify the components of the same type (o, x or .) connected by horizontal or vertical moves. Diagonal does not count.

...o...    vs    .x.x
oo...oo          x.x.

Once I have identified a group, I need to count the liberties or empty spaces around that group.

Here is a group of x pieces with 9 spaces around it

 234       ..ox
1xxx5     .xxxo
 89x6      o.xo
   7         .

However, 4 of them are covered with o pieces, and 5 of them have empty spaces . around it. So our gropu of x pieces only has 5 liberties.

. should count as 1 liberty, the o pieces should not count (contribute 0) and the x pieces should have been included in the group to begin with.


Is there a systematic way to identify connected groups on the board? And then to count the liberties.

$\endgroup$
  • $\begingroup$ 1. It's better if you stick to one question per question. The question of how to compute connected components is quite different from the question of how to count liberties, so it would have been better to have posted those two separately. You might want to edit out the part about liberties, and post that separately in a separate question. 2. If you want to ask about liberties, please provide a careful definition of what counts as a liberty, for those of us who don't play Go. One example wasn't enough for me to understand. $\endgroup$ – D.W. Sep 7 '14 at 19:37
  • $\begingroup$ @D.W. the notion of liberty is very delicate. one way - that work 99% of the time - usually it's define as "counting the empty spaces around a group". the other 1% has some hairy exceptions $\endgroup$ – john mangual Sep 7 '14 at 19:46
  • $\begingroup$ Well, if you can't define it precisely, how can you expect us to tell you how to compute it? I mean, figuring out how to specify what you want to compute is a basic prerequisite to figuring out how to compute it: if you're not sure exactly what you want, you probably aren't going to have much luck trying to write code to compute what you want. $\endgroup$ – D.W. Sep 7 '14 at 19:55
  • $\begingroup$ @D.W. Can you help me phrase the question in a more agnostic way? $\endgroup$ – john mangual Sep 8 '14 at 10:30
2
$\begingroup$

To count connected groups

Form an undirected graph, with one vertex per location on the board, and an edge between each two locations are are adjacent (horizontally or vertically). Then, use any standard algorithm for connected components. See https://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29 or your favorite CS algorithms textbookk.

You'll probably want to run the algorithm twice: once for x's (build a graph where you retain just the vertices with x's on them, and find all connected components), and once for o's (build a graph where you retain just the vertices with o's on them, and find all connected components).

To count liberties

If I understand the definition, this looks like a simple matter of programming. Find a connected component of x's, look at each cell which is adjacent to it, and count how many are empty. That's straightforward programming -- no fancy algorithms needed. Programming questions are better on StackOverflow, but make sure you show your effort.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.